Алгоритм фильтрации, пример на основе БПФ (стр. 3 из 6)
Х0 (п)=х(п) +x(n+N/2); (4.5)
Х1(п)=х(п) -х(n+N/2). (4.6)
Рисунок 5 - Выполнениебазовой операции «бабочка»
Следовательно, вычисление N-точечного ДПФ X(k) сводится к вычислению двух N/2-точечных ДПФ причетных и нечетных значениях k для функций х0(п) и x1(п) и выполнениюбазовой операции «бабочка» (рис.5)отличие операции «бабочка» здесьзаключается в том, что комплексноеумножение выполняется после операции сложения-вычитания.
Ту же процедуру можно теперь применить к x0 (п) и х1(п) и перейти от N/2-точечных ДПФ к N/4-точечным ДПФ и, такимобразом, свести вычисление Х (2k) и Х (2k + 1) через Х (4k), X(4k+2), X(4k+ 1), X(4k+3). Продолжив этот процесс, перейдем в конечном итоге к 2-точечным ДП Ф с последующим прямым вычислением всех выходных отсчетов Х (k). Полный алгоритм БПФ с прореживанием по частоте и его программная реализация аналогичны рассмотренным выше для метода БПФ с прореживанием по времени.
Необходимо отметить, что в обоих алгоритмах БПФ - и с прореживанием по времени, и с прореживанием по частоте требуется примерно Nlog2N операций (комплексных умножений) и оба алгоритма могут быть реализованы по способу с замещением, используя только один массив ячеек памяти. В обоих алгоритмах должна быть предусмотрена процедура двоичной инверсии - на входе (при прореживании по времени) или на выходе (при прореживании по частоте).
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.
Применение алгоритмов БПФ позволяет выполнить эффективное вычисление выходной последовательности у(пТ) ЦФ. С этой целью следует определить ДПФ H(k) и X(k) в N+M-1 точках для последовательностей h(пТ) и х(пТ), затем определить ДПФ Y(k)=H(k)X(k) выходной последовательности у(пТ). Вычисление у (пТ) по ОДПФ Y(k) выполняется, например, по алгоритму (5.3). Для вычисления ДПФ и ОДПФ используются алгоритмы БПФ. Отметим, что если длина М последовательности х(пТ) велика, то реализация упомянутого выше алгоритма вычисления у(пТ) связана со значительной временной задержкой (для накопления всех М выборок х(пТ)). С целью уменьшения этой задержки можно входную последовательность х(пТ) разбить на отрезки xi(пТ) каждый длиной L и обрабатывать каждый из них независимо от других. Представим
(6.2)Тогда можно (6.1) записать в виде
 |
(6.3)
Где частная свертка
 |
(6.4)
Таким образом можно начинать расчет методами БПФ частных сверток и формировать у(пТ) путем соответствующего суммирования элементов частных сверток [2].
7. ДРУГИЕ БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
7.1 Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота
Кроме рассмотренных выше классических алгоритмов БПФ известных как алгоритмы Кули-Тьюки по основанию 2, известно множество других. Некоторые из них позволяют существенно повысить эффективность вычисления дискретного преобразовании Фурье. Так, алгоритмы Винограда при равном числе сложении требуют примерно в 5 раз меньше умножений, чем алгоритмы Кули-Тьюки.
В основе всех известных алгоритмов лежит принцип разбиении исходного ДПФ на совокупность мало точечных. Различие заключается в способах вычисления мало точечных алгоритмов и последующего объединения частичных результатов. При этом размер преобразования не обязательно равен степени двух, т. е. становится возможным БПФ произвольной длины, что очень важно для ряда практических задач. Так, в технике связи при цифровом преобразовании многоканальных сигналов размер БПФ определяется числом объединяемых каналов.
Кратко рассмотрим только некоторые, наиболее важные алгоритмы, на основе которых впоследствии возникло множество различных эффективных модификаций. Это: 1) обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота; 2) алгоритм простых множителей Гуда-Винограда; 3) алгоритм Винограда.
Для простоты изложения везде будем полагать N=N1N2, где N - длина преобразования. Очевидно, приводимые ниже положения легко могут быть перенесены на более общий случай, когда 
Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота. Итак, пусть N=N1N2, гдеN1и N2 - положительные целые. Покажем, что в этом случае вычисление исходного N-точечного ДПФ можно свести к вычислению N1N2-точечных и N2N1-точечных ДПФ и N умножениям на множители поворота
. Для этого в выражения для ДПФ (1.1)  |
(7.1)
где
, необходимо сделать подстановку:k=k1 +k2N2, k1=0, …., N2-1; k2=0, …., N1-1; (7.2)
n=n1 +n2N2, n1=0, …., N2-1; n2=0, …., N2-1. (7.3)
Рисунок 6 - Сигнальный граф алгоритма
Тогда ДПФ (7.1) преобразуется к виду
 |
(7.4)
Таким образом, полученный алгоритм включает в себя две основные ступени: на первой ступени переставленные в соответствии с (7.3) входные выборки подвергаются N2-точечному преобразованию Фурье. На второй ступени производится вычисление N1-точечных ДПФ. Между первой и второй ступенями осуществляется операция поворота путем умножения на поворачивающие множители
. Полученная последовательность на выходе ДПФ должна быть переставлена в соответствии с (7.2).Пример 4. Пусть N=6, N1=3, N2=2. Положим k=k1+k2*2; n=n1+ +n2*3; n1k2=0,1,2; n2k1=0, 1.
Тогда
 |
Соответствующий сигнальный граф алгоритма изображен на рис.6.
Рассмотренный подход может быть положен в основу синтеза алгоритмов БПФ Кули-Тьюки с произвольным постоянным основанием. Наибольшую популярность получили алгоритмы с основаниями 4 и 8, позволяющие повысить эффективность вычисления ДПФ по сравнению с классическими алгоритмами по основанию 2. Отметим, что алгоритмы с основанием 2 также могут быть получены с использованием рассмотренного подхода. Таким образом, рассмотренный метод синтеза является общим и позволяет синтезировать различные модификации алгоритма Кули - Тьюки с произвольными постоянным и смешанным основаниями.
7.2 Алгоритм простых множителей
В случае, когда N представимо произведением взаимно простых множителей, имеется возможность избавиться от поворачивающих множителей в разложении (7.4). Тем самым можно достигнуть еще большей экономии числа операций.
Чтобы избавиться от множителей поворота, нужно произвести перестановку входной и выходной последовательностей, отличную от (7.2) и (7.3). Такой перестановкой может быть следующая:
для входной последовательности
(7.5)n1.=0,...., N1-1; п2=0,..., N2-1;
для выходной последовательности
(k1N2 +k2)=X((s1k2N1 + s2k1N2)mod N), (7.6)k1=0,..., N1-1; k2=0,..., N2 -1,
где запись п mod N означает «остаток от деления п на N», а s1и s2 определяются из следующих уравнений в соответствии с китайской теоремой об остатках о восстановлении целого числа по его вычетам: s1N1= 1mod N2,s1<N2, s2N2== 1modN1, s2 <N1. Тогда алгоритм N=N1N2 - точечного ДПФ представляется в виде