Алгоритм фильтрации, пример на основе БПФ (стр. 2 из 6)
(2.5)В качестве примера граф на рис.3, б представляет операции (2.3) и (2.4). Аналогично можно теперь выразить (N/2)-точечные ДПФ Хv-1,0(k) и Хv-1,1(k) через (N/4)-точечные ДПФ:
(2.6а)И
(2.7б)где Хv-2,0(k) и Хv-2,1(k) - соответственно (N/4)-точечные ДПФ четных Хv-2,0(n) и нечетных Хv-2,1(п)
членов последовательности Хv-1,0 (п), а Хv-2,2(k) и Хv-2,3(k)-соответственно (N/4)-точечные ДПФ четных Хv-2,2 (п) и нечетных Хv-2,3 (п) членов последовательности Хv-1,1(п).
Процесс уменьшения размера ДПФ от М до M/2, где М равна степени 2, продолжается до тех пор, пока на v-м шаге (v = log2N, где N-исходный размер ДПФ) не окажутся только 2-точечные ДПФ Ф(k), k=0,1, для двухточечных последовательностей
(п),п = 0,1, определяемые из соотношений  |
(2.8)
Последние вычисляются без операции умножения.
Пример 1. Построим алгоритм БПФ с прореживанием по времени для N=8=23, v=3, т. е. для последовательности х(пТ), п=0,1,2,З,4.5,6,7. Разобьем согласно (2.1) исходную последовательность х (пТ) = х3 (п) на две последовательности: x2,0 (п) и х2,1(n),-состоящие соответственно из четных и нечетных членов х3 (п):
\ (2.9)
Рисунок 4 - Алгоритм 8-точечного БПФ
Теперь вновь разобьем последовательности (2.9) на последовательности из нечетных и четных членов последовательностей (2.9):
(2.10)Последовательности (2.10) являются уже двухточечными.
Теперь, используя алгоритм, представленный графом «бабочка» (см. рис.3, а), строим алгоритм 8-точечного БПФ (рис.4). Вначале построим исходный массив. Как видно из (2.10), он из элементов последовательности х(n)=х(nТ), n=0,1... 7, причем на входах первого графа «бабочка» первой ступени помещаются числа х(0) и х(4). На входах второго графа «бабочка» -числа х(2) и х(6), на входах третьей «бабочки» - х(l) и х(5) и на входах четвертой «бабочки» - x(3) и x (7).
Таким образом, если предположить, что последовательность Х(п) записывается в массив ячеек памяти, то удобно осуществить размещение х(п) в следующем порядке (рис.2): х(0), х(4), Х(2), х(6), х(1), х(5), х(3), х(7). Легко заметить, что элементы этой последовательности получаются из исходной х(п) в соотnетствии с двоичной инверсией номеров, т. е. число х(п) с номером в двоичном представлении п=(пv-1,..., n0) запоминается в ячейке памяти с номером
=(n0,..., п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, получается в естественном порядке следования.
Как показано в рассмотренном примере, все входные числа «бабочек» Х0 (k) на начальной ступени являются элементами заданной последовательности х(п), п=0... N-1, причем получаются из х(п) в соответствии с двоичной инверсией номеров т. е. число х(пТ)=х(п) с двоичным представлением номера п является входным числом Х0(k) «бабочки» с номером k, равным инверсному двоичному представлению номера п.
Заметим, что в рассмотренном алгоритме БПФ можно выполнить вычисления по способу с замещением. Если разместить входную последовательность Х 0(k) «бабочек» в массиве из 2v ячеек памяти, то после вычисления выходов «бабочек» входные элементы становятся ненужными и в указанные ячейки памяти могут быть записаны вычисленные выходные числа. На следующей ступени вновь вычисленные значения выходов «бабочек» записываются в ячейки массива вместо использованных входных чисел, и в конце вычислений во входном массиве окажутся записанными значения 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, w0= 
0=0, А1=I, w1=0,125, 1=0,7854, А2=3, w2=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), при значениях параметров Ak, wkи
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)где теперь для значений
: