3.4. Основные алгоритмы БПФ по модулю 2 с замещением

Существует 4 основных алгоритма БПФ по модулю 2 с замещением, различающихся способом прореживания данных (по времени или частоте) и расположением входных и выходных данных (прямое или двоично-инверсное). Особенностью алгоритмов с замещением является то, что если входные данные

вобычном порядке, то выходные в двоично-инверсном и наоборот.

Вкаждой паре алгоритмов один является основным и соответствует рис.3.1 для прореживания по времени и рис.3.3 для прореживания по частоте, а второй получается перестановкой входных и выходных данных, чтобы поменять прямой порядок данных на двоично-инверсный и наоборот.

Каждый алгоритм может быть представлен в виде граф-схемы, таблицы индексов и схемы алгоритма программы. Далее приведены все эти три представления для каждого варианта алгоритма: алгоритм БПФ с прореживанием по времени и двоично-инверсным расположением входных данных (рис.3.9-3.11), алгоритм БПФ с прореживанием по времени и прямым расположением входных данных (рис.3.12-3.14), алгоритм БПФ с прореживанием по частоте и прямым расположением входных данных (рис.3.15-3.17), , алгоритм БПФ с прореживанием по частоте и двоично-инверсным расположением входных данных

(рис.3.18-3.20).

Схемы алгоритмов БПФ очень похожи и основное их отличие заключается

вначальных значениях приращений адресов и индексов, а также направлением их изменения (увеличение или уменьшение). При этом в дополнительных алгоритмах изменяется также порядок следования поворачивающих множителей с прямого на двоично-инверсный, что незначительно усложняет алгоритм.

Взаключение приводятся примеры программной реализации 4-х алгоритмов БПФ. В этих программах используется универсальная «бабочка» без учета частных случаев поворачивающих множителей. Представленные примеры выполнены в виде универсальных подпрограмм, предназначенных для реализации прямого БПФ (при вызове подпрограммы в аккумуляторе А должен быть 0) и обратного БПФ (аккумулятор А не равен 0).

Вголовной программе, вызывающей подпрограмму FFT, должны быть выполнены настройки режимов процессора, как было показано в примерах реализации базовой операции, определена размерность БПФ N=2^(M+1), где константа N – число обрабатываемых значений (размер выборки), а константа М – число итераций-1, а также подключена таблица одного периода синуса длиной N отсчетов с начальной меткой sint.