6.3. Алгоритмы БПФ по основанию 3, 6, 12

Для алгоритмов БПФ по основанию 3 также возможен способ вычислений, не требуищий умножений в блоках Основной идеой такого способа вычислений является переход из поля комплексных чисел в поле чисел Эйзенштейна где множество вещественных чисел и Таким образом отсюда

Из (6.9) легко определить переходы из одной числовой системы к другой

Арифметические операции в выполняются следующим образом

т.е. сложение в эквивалентно двум вещественным сложениям, а умножение в четырем вещественным умножениям и двум вещественным сложениям. Умножения да весовые коэффициенты и тривиальны, так как

Рис. 6.5. Алгоритм в системе

Рис. 6.6. Модуль в системе

т.е. каждое умножение на весовой коэффициент выполняется за одно вещественное сложение.

Приведем пример алгоритма БПФ в для . В этом случае матричная запись имеет вид

где матрицы перехода соответственно в систему и обратно согласно матрица трехточечного ДПФ в системе

Граф алгоритма (6.11) приведен на рис. 6.5.

Общее выражение для данного алгоритма БПФ имеет вид

Число нетривиальных арифметических операций для алгоритма (6.12) приведено в табл. 6.2 (вариант № 2 для данный метод вычислений распространен на Для учитывается, что Таким образом, при переходе в систему приведенное на рис. 6.6, также не требует операций умножения. Число нетривиальных арифметических операций приведено в табл. 6.2 (вариант № 2 для ).

Рассмотрим дальнейшее распространение данного метода вычислений на случай Блок ДПФ в системе можно представить

Таблица 6.2 (см. скан)

где

где модуль определен выше (см. рис. 6.5). В свою очередь, модуль в системе равен

где Согласно равен отсюда умножение на определяется

Рис. 6.7. Модуль в системе

выражением

т.е. эквивалентно двум вещественным умножениям и двум вещественным сложениям (сдвиги на 2 в расчет не принимаются, так как считаются более элементарными операциями).

На рис. 6.7 приведен граф блока откуда следует, что для вычисления такого модуля требуется шесть вещественных умножений и 118 вещественных сложений.

Общее число нетривиальных арифметических операций для данного алгоритма БПФ приведено в табл. 6.2 (вариант № 2 для предложены более эффективные алгоритмы и 12, не требующие арифметики. Данные алгоритмы синтезированы методом прореживания по времени с небольшой модификацией. Пусть тоща первый этап факторизации при прореживании по времени определяется как

где

Выражение (6.15) может быть переписано в виде

Таким образом, если входной вектор, то блок определяет три ДПФ размерности вида

Подставим (6.17) в (6.16), тогда спектральный вектор определяется выражением

Отсюда

Определим число арифметических операций, необходимых для вычисления Пусть Согласно принятым ранее обозначениям Величина выше была определена как Справедливы также соотношения Тогда

Таким образом, для вычисления (6.19) требуется четыре вещественных умножения и восемь вещественных сложений. Далее

Для вычисления (6.20) требуется четыре вещественных умножения и четыре вещественных сложения, (так как величины 5,- определены ранее). Далее

Для вычисления (6.21) требуется всего четыре вещественных сложения, так как величины и вычислены ранее.

Всего для вычисления (6.18) требуется вещественных умножений (учитывается случай вещественных сложений.

Продолжая аналогично факторизацию и т.д., получаем следующие оценки:

Рис. 6.8. Первый этап факторизации алгоритма БПФ по основанию 3 с прореживанием по времени

На рис. 6.8 приведен первый этап факторизации алгоритма БПФ по основанию 3, построенный на основе (6.16).

Аналогичный подход может быть распространен на факторизацию по основанию . В этом случае первый этап факторизации

По аналогии с (6.18) -(6.21) можно показать, что блок

требует вещественных умножений и вещественных сложений. Общее число арифметических операций приведено в табл. 6.2 (вариант № 3 для ).

В табл. 6.2 приведены оценки числа нетривиальных вещественных арифметических операций для алгоритмов БПФ по основаниям 3, 6 и 12. При этом рассмотрены следующие варианты.

Вариант № 1 - алгоритмы в случае канонического представления модулей . В скобках указаны уточненные оценки, учитывающие, что модуль может быть вычислен не за два, а за одно умножение и одно дополнительное сложение, так как умножение на коэффициент 1,5 требует только одно сложение.

Вариант № 2 - алгоритмы БПФ, построенные в системе .

Вариант № 3 - модифицированный алгоритм в комплексной плоскости.