упеня поміщаються числа х (0) і х (4). На входах другого графа В«метеликВ»-числа г (2) і х (6), на входах третьої В«метеликиВ» - х (l) і х (5) і на входах четвертої В«метеликиВ» - x (3) і x (7).
Таким чином, якщо припустити, що послідовність Х (п) записується в масив елементів пам'яті, то зручно здійснити розміщення х (п) в наступному порядку (рис.2): х (0), х (4), Х (2), х (6), г (1), г (5), г (3), х (7). Легко помітити, що елементи цієї послідовності виходять з вихідної х (п) в соотnетствіі з двійковій інверсією номерів, т. е. число х (п) з номером у двійковому поданні п = (п v-1, ..., n 0 ) запам'ятовується в комірці пам'яті з номером = (n 0, . .., п v-1 ). Так, число г (4) з номером в двійковому поданні 4 (10) = 100 (2) запам'ятовується в осередку з номером 001 (2) = 1 (10) , а число г (3), де 3 (10) = 011 (2) , запам'ятовується в осередку з номером 110 (з) = 6 (10) і т. д. Отже, можна вважати, що початкова ступінь перетворення Х 0 (K), k = 0, I. .. 7, вийдуть просто в результаті проріджування (в зазначеному сенсі) вихідної тимчасової послідовності х (ПТ), п = 0, I. .. 7, т. е Х 0 (k) = х ( T), де k = - двійковій-інверсне уявлення номери п.
На виходах N/2 = 4 В«метеликівВ» т = l-го ступеня утворюються значення Х 2 (k), є вхідними числами В«МетеликівВ» т = 2-го ступеня. На виходах останньої значення вихідний послідовності Х З (k) = X (k), k = 0. .. 7. Вихідна послідовність X (k), k = 0,1 ... 7, виходить в природному порядку проходження. p> Як показано в розглянутому прикладі, всі вхідні числа В«метеликівВ» Х 0 (k) на початковій щаблі є елементами заданої послідовності х (п), п = 0. .. N-1, причому виходять з х (п) відповідно до двійковій інверсією номерів тобто число х (ПТ) = х (п) з двійковим поданням номери п є вхідним кількістю Х 0 (k) В«метеликиВ» з номером k, рівним інверсному бінарного поданням номери п.
Зауважимо, що в розглянутому алгоритмі ШПФ можна виконати обчислення за способом із заміщенням. Якщо розмістити вхідну послідовність Х 0 (k) В«метеликівВ» в масиві з 2 v осередків пам'яті, то після обчислення виходів В«метеликівВ» вхідні елементи стають непотрібними і в зазначені комірки пам'яті можуть бути записані обчислені вихідні числа. На наступному щаблі знову обчислені значення виходів В«метеликівВ» записуються в комірки масиву замість використаних вхідних чисел, і врешті обчислень у вхідному масиві виявляться записаними значення X (k) в природному порядку, тобто значення ДПФ при k = 0, I, 2 ... N-1.
3. ПРОГРАМА І ПРИКЛАД РЕАЛІЗАЦІЇ АЛГОРИТМУ БПФ З проріджування ЗА ЧАСОМ
Нижче при водиться програма обчислення ШПФ з проріджуванням за часом за способом із заміщенням і розглядаються при заходи реалізації цієї програми.
Програма 1 - швидке перетворення Фур'є з основою два і проріджуванням за часом. Програма здійснює алгоритм ШПФ з основою два і проріджуванням за часом комплексної або речовій послідовності х (п) довжиною N відліків. Речові складові відліків вихідної послідовності записуються в масив А1 (N), а уявні - масив А2 (N). У програмі для ознайомлення з її роботою передбачено формування вхідний послідовності, що відповідає отсчетам полігармонічного сигналу
(3.1)
рядки (80-240). При використанні програми для виконання ШПФ довільній послідовності необхідно замінити рядки 80-240, організувавши введення початкової послідовності.
В В
Основними етапами обробки є: введення вихідних даних (рядки 50-240), двійковій-інверсна перестановка вихідної послідовності (рядки 250-350), власне алгоритм ШПФ (рядки 360-510), розрахунок амплітуд і фаз аналізованого сигналу за результатами БПФ (Рядки 520-590) і виведення результатів (рядки 600-690). Користувачеві виводяться в вигляді таблиці значення номера компоненти (гармоніки) БПФ, речова і уявна її складові [Аl (1) і А2 (1)], амплітуда і фаза відповідної гармоніки [R (1) і Fl (1) ] .
Приклад 2. Реалізація БПФ речового сигналу містить три складові при значеннях параметрів: А 0 = 2, w 0 = 0 = 0, А 1 = I, w 1 = 0,125, 1 = 0,7854, А <...
