11.3. Алгоритмы ТЧП с расщепленным основанием

Очевидно, что при факторизации ТЧП, так же как и в случае факторизации может быть применен метод "расщепленного" основания (см. разд. 7.4). Покажем, что для ТЧП возможно более глубокое расщепление весовых коэффициентов, чем в алгоритме (см. также рис. 7.8).

Пусть задано ТЧП в размерностью Быстрый алгоритм ТЧП с расщепленным основанием основан непосредственно на следующем разбиении:

где

Рис. 11.3. (см. скан) Граф алгоритма ТЧП с расщепленным основанием в поле простое Мерсенна)

В предыдущем разделе было показано, что умножение на коэффициент не требует нетривиальных умножений. Таким образом, согласно точечное ТЧП разбивается на одно -точечно с ТЧП с базовым элементом четыре -точечных ТЧП сбазовым элементом комплексных умножений на коэффициенты а. Очевидно, что аналогично (11.23) данное разбиение может быть выполнено для -точечного ТЧП, -точечных ТЧП и т.д., до тех пор, пока в остатке не будут получены элементарные блоки двухточечных (более точно такой рекуррентный процесс разбиения может продолжаться, пока в остатке не получатся -точечные блоки которые не требуют операций умножения).

На рис. 11.3 представлен граф такого алгоритма ТЧП с расщепленным основанием для Из рисунка видно, что данный алгоритм имеет структуру с замещением и прореживанием по частоте и обычную

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

цифро-инверсную перестановку на выходе. Число вещественных умножений и сдвигов определяется согласно (11.23) следующими рекуррентными соотношениями:

Число вещественных сложений равно отсюда общее число арифметических операций равно

Точное число арифметических операций приведено в табл. 11.2.

Для сравнения алгоритм БПФ с расщепленным основанием типа (7.24) имеет примерно в 1,35 раза больше умножений при примерно том же числе сложений.

Алгоритм ТЧП типа (11.23) ориентирован на обработку комплексного сигнала. При обработке вещественного сигнала можно использовать свойство комплексной сопряженности спектра (отдельно вычисляются элементы . В этом случае возможно упрощение алгоритма (11.23), а именно

На рис. 11.4 приведен граф алгоритма (11.25) для где обозначает операцию образования комплексного числа из двух вещественных, — знак операции комплексного сопряжения. Для обратного ТЧП граф имеет отраженно-симметричный вид (с учетом замены

Рис. 11.4. (см. скан) Граф алгоритма ТЧП с расщепленным основанием для обработки вещественных сигналов

всех а на Число арифметических операции при этом равно

В целом алгоритмы ТЧП с расщепленным основанием типа (11.23) или (11.25) являются наиболее привлекательными из всех рассмотренных быстрых алгоритмов ТЧП, так как они имеют меньше умножений, чем любой из классических алгоритмов БПФ размерности могут быть синтезированы для широкого класса размерностей и, крэме того, существует более широкий ассортимент простых чисел Мерсенна по сравнению с простыми числами Ферма. Это обеспечивает выбор

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

где целая часть а.