8.4. Алгоритмы БПФд для взаимно-простых множителей

Как было показано в гл. 3, если длина и — взаимно-простые, т.е. то представимо в виде

где и — матрицы перестановок, определенные согласно правилам из разд. базовые Фурье-подобные блоки вида

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

Так как есть матричный аналог многомерного выражение (2.16)), то в случае вещественного входного сигнала справедливо выражение

т.е. по первой координате вычисляется раз "вещественное” а по остальным координатам — комплексное” . Причем в силу комплексной сопряженности спектра (8.1) достаточно для каждого вычислить половину комплексного массива промежуточных данных, т.е. каждое вычисляется раз (для комплексного ДПФ необходимо проходов по каждой координате).

Таким образом, число арифметических операций а (8.40) может быть

снижено на половину по сравнению с комплексным ДПФ [10, 11]. При этом учитывается, что в базовом блоке устраняется избыточность операций за счет сопряженности спектра.

Существует альтернативный подход к построению алгоритмов БПФд для взаимно-простых множителей [12, 13], позволяющий синтезировать как алгоритмы простых множителей так и алгоритмы Винограда

Рассмотрим первый этап вычисления в На этом этапе вычисляется вещественное” ДПФ - F от переставленных отсчетов входного вектора. В каждом блоке силу комплексной сопряженности спектра достаточно на выходе четное) или нечетное) комплексных отсчетов спектра. Причем, для любого и для четного Таким образом, в отсчетах можно упаковать все (или ) комплексных отсчетов спектра. Если спектральный вектор упакован в виде четное).

(аналогично для нечетного), то справедливо соотношение

где

Далее, так как вектор т. е. состоит из вещественных отсчетов, то после -кратного применения к входному сигналу весь вектор промежуточных данных будет вещественным следовательно, на втором этапе вычислений, где используется ДПФ-F, также справедливо выражение, аналогичное

Продолжая аналогичные рассуждения до конца, окончательно получаем

Из (8.42) следуют две формы реализации БПФд:

1. Алгоритм простых множителей

Рис. 8.13. Модуль БПФдр

Рис. 8.14. Модуль БПФд

Рис. 8.15. Модуль БПФдр

2. Алгоритм Винограда

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

Рис. 8.16. Модуль БПФд

Матрицы определяются из на основе свойства комплексной сопряженности спектра, т.е. удаляются все операции комплексно-сопряженных отсчетов и на их место записываются мнимые части оставшихся комплексных отсчетов.

На рис. 8.13-8.16 приведены примеры построения модулей

Число умножений для данных алгоритмов БПФд уменьшается ровно вдвое по сравнению с соответствующими "комплексными" алгоритмами БПФ, а число сложений более чем вдвое, так как операции типа где не считаются арифметическими.

В таблице приведены данные по числу арифметических операций в базовых модулях