6. АЛГОРИТМЫ БПФ, СИНТЕЗИРОВАННЫЕ ПО МЕТОДУ ПРОИЗВОЛЬНЫХ МНОЖИТЕЛЕЙ

6.1. Алгоритмы БПФ по смешанному основанию

Пусть Будем рассматривать упрощенную факторизацию по методу произвольных множителей, основанную на представлении (3.22):

Необходимо отметить, что выражение (6.1) справедливо при Однако если то факторизацию целесообразнее выполнять через кронекеровское произведение или если среди такое, что то целесообразнее гибридная факторизация типа (3.29).

Из (6.1) непосредственно следует транспонированная форма факторизации

По устоявшейся классификации алгоритмы БПФ, реализующие (6.1) и (6.2), относятся соответственно к БПФ с прореживанием по частоте и прореживанием по времени

Для конкретизации структуры вычислений в (6.1) и (6.2) должны быть определены структуры вычисления модулей Если например, представлены в канонической форме типа (4.13), то для (6.1) получаем следующее окончательное выражение (аналогичное для алгоритма

Для алгоритмов (6.1) и (6.2) характерна организация процесса вычислений с замещением (кроме вычислений внутри блоков За счет этого объем оперативной памяти такой же, как и в случае вычислений по методу простых множителей (алгоритм Однако другие характеристики для БПФ произвольных множителей хуже АПМ, а именно:

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

В оценках (6.4) и в дальнейшем учитывается, что

где операции умножения соответственно комплексных и вещественных чисел, операции комплексного и вещественного сложений.