10.5. Синтез алгоритмов БПФ-m методом полиномиальных преобразований

Рассмотрим случай вычисления квадратного Наиболее простая конструкция, использующая ПП, имеет вид [7].

Таким образом, ДПФ-2 может быть вычислено с помощью ПП по с предварительным умножением входной последовательности на и N СДПФ размерностью N. В случае применения с расщепленным основанием типа (7.47) оценка числа арифметических операций для (10.46) равна

Алгоритм (10.46) является наиболее простым по конструкции из семейства алгоритмов ПФ-2, синтезированных методом ПП, однако даже его реализация вызы врет трудности вследствие большого числа операций перестановок типа где

Структурная схема алгоритма (10.46) дана на рис. 10.6.

Минимальное число арифметических операций требует гори: использующий набор различных ПП по Для такого алгоритма факторизуется на размерностью по размерностью по размерностью и операции приведения по требующие только сложений (рис. 10.7). Далее для ДПФ-2 меньших размерностей данное разбиение рекуррентно повторяется.

Такой алгоритм БПФ-2 в случае применения СДПФ с расщепленным основанием типа (7.47) дает наименьшие из известных оценки числа

Рис. 10.6. Структура алгоритма двумерного БПФ на основе полиномиального преобразования по

Рис. 10.7. (см. скан) Структура алгоритма двумерного БПФ на основе набора полиномиальных преобразований по

нетривиальных вещественных арифметических операций (входной сигнал комплексный)

Определим теперь оценки и а в случае вещественного, входного сигнала Тогда для всех сокращений по и полиномиальных преобразований выполняются операции в поле вещественных чисел. Таким образом, входные вектора для СДПФ также являются вещественными. Отсюда для вычисления СДПФ можно применить безызбыточный алгоритм БПФ типа (8.36), что в конечном итоге дает следующие оценки:

Необходимо отметить, что рассмотренный алгоритм требует в 1,3 раза меньше умножений и в 1,1 раза меньше сложений по сравнению с гнездовым алгоритмом (10.45); в 1,46 раза меньше умножений и в 1,69 раза меньше сложений по сравнению с алгоритмом вещественного БПФ-2, предложенным недавно Кротом и Минервиной [21].

Анализ различной литературы, а также известных методов построения алгоритмов БПФ-2 размерностью показывает, что оценки (10.48) и (10.49) являются наименьшими.