sub> 2 = 3, w 2 = 0,3125, 2 = 1,57.
В
В якості вихідних даних послідовно вводяться значення:
N = 16; J = 3; А (0) = 2; w (0) = 0; w1 (0) = 0; A (1) = 1; w (1) = 0,125; w1 (1) = 0,7854; А (2) = З; w (2) = 0,3125; w1 (2) = 1,57; I 9 = 1;
Приклад 3. Реалізація БПФ комплексного сигналу (3.1), що містить три складові ( J = 3), при значеннях параметрів A k , w k і k таких же, як
В В
в прикладі 2. Введення вихідних даних аналогічний прикладу 2, за винятком того, що значення I 9 = 0.
4. АЛГОРИТМ БПФ З проріджування ПО ЧАСТОТІ
Розглянутий нижче алгоритм обчислення ДПФ (1.1) відрізняється тим, що вхідна послідовність х (ПТ), п = 0,. .., N -1, розбивається на дві послідовності посередині (т. е. одна послідовність для n = 0...N/2-1, а інша - для п = N/2...N -1) і ця процедура триває для кожної нової послідовності доти, поки не виходить шукана вихідна одноелементна послідовність Х (k); при цьому величини Х (k) вже виявляються у вихідному масиві в В«ПрорідженомуВ» порядку та їх приведення до природному порядку пов'язано з інверсією двійкового подання індексів k в обчислених значеннях Х (K).
Отже, запишемо ДПФ (1.1) у вигляді:
(4.1)
Враховуючи, що = отримуємо
. (4.2)
Підставивши замість k в (4.2) значення 2k або (2k + 1), отримаємо вирази для парних і непарних відліків ДПФ:.
В
; (4.3)
, (4.4)
де тепер для значень:
В
Х 0 (п) = х (п) + X (n + N/2); (4.5)
Х 1 (п) = х (п) -Х (n + N/2). (4.6)
В В
Рисунок 5 - Виконання базової операції В«метеликВ»
Отже, обчислення N- точкового ДПФ X (k) зводиться до обчислення двох N/2-точечних ДПФ при парних і непарних значеннях k для функцій х 0 (п) і x 1 (п) та виконанню базової операції В«метеликВ» (мал. 5) відміну операції В«метеликВ» тут полягає в тому, що комплексне множення виконується після операції додавання-віднімання.
Ту ж процедуру можна тепер застосувати до x 0 (п) і х 1 (п) і перейти від N/2-точечних ДПФ до N/4-точечним ДПФ і, таким чином, звести обчислення Х (2k) і Х (2k + 1) через Х (4k), X (4k +2), X (4k + 1 ), X (4k +3). Продовживши цей процес, перейдемо в кінцевому підсумку до 2-крапковим ДП Ф з подальшим прямим обчисленням всіх вихідних відліків Х (k). Повний алгоритм ШПФ із проріджуванням по частоті і його програмна реалізація аналогічні розглянутим вище для методу ШПФ із проріджуванням за часом.
Необхідно відзначити, що в обох алгоритмах ШПФ - і з проріджуванням за часом, і з проріджуванням по частоті потрібно приблизно N log 2 N операцій (комплексних множень) і обидва алгоритму можуть бути реалізовані за способом із заміщенням, використовуючи тільки один масив комірок пам'яті. В обох алгоритмах повинна бути передбачена процедура двійковій інверсії - на вході (при проріджуванні по часу) або на виході (при проріджуванні за частотою).
5. ЗАСТОСУВАННЯ МЕТОДУ БПФ ДЛЯ ОБЧИСЛЕННЯ ЗВОРОТНОГО ДПФ (ОДПФ)
За визначенням (1.2) ОДПФ х (ПТ) N -точковою послідовності X (k), k = 0, 1, ..., N-1, виражається співвідношенням
(5.1)
причому в загальному випадку і х (ПТ), і Х (k)-комплексні. Нехай х (ПТ) і Х * (k)-послідовності, комплексно зв'язані відповідно з х (ПТ) і X (k). Згідно (5.1) можна записати
(5.2)
В
Але вираз суми в правій частині (5.2) є пряме ДПФ послідовності Х * (k), k = 0,. .., N-1, і, отже, ця сума може бути обчислена за допомогою розглянутих алгоритмів і програм ШПФ.
Таким чином забезпечується обчислення послідовності Nx * (ПТ) і для визначення х (ПТ) залишається взяти комплексно поєднане з Nx * (ПТ) вираз і розділити його на N:
В В
(5.3)
В
6. ЗАСТОСУВАННЯ БПФ ДЛЯ ОБЧИСЛЕННЯ РЕАКЦІЇ ЦФ
Обчислення реакції у (ПТ) ЦФ з імпульсною характеристикою h (ПТ), п = 0, 1, ..., N-1, на вхідний вплив х (ПТ), п = О, 1, ... M -1, може бути виконано на основі алгоритму згортки
(6.1)
при п = 0, 1, ..., N + M-2.
Застосування алгоритмів ШПФ дозволяє виконати е...
