9.2. Алгоритмы БПХ по основанию 4

Пусть тогда из (9.1) непосредственно следует

где

Рис. 9.5. Первый этап факторизации алгоритма БПХ по основанию 4 и прореживанием по частоте

Учитывая, что матрицы и можно связать следующим соотношением:

Подставляя (9.15) в (9.14), получаем факторизацию

На рис. 9.5 приведена структурная схема первого этапа факторизации, выполняемой согласно (9.12) и (9.16).

Полный граф алгоритма БПХ по основанию 4 (прореживание но частоте)

Рис. 9.6. Граф алгоритма БПХ по основанию 4 с замещением и прореживанием по частоте

Рис. 9.7. Разложение Хаусхолдера для матрицы ДПХ

изображен на рис. 9.6 для N = 16. Данный алгоритм определяется следующим матричным выражением:

Очевидно, что для БПХ по основанию 4 также возможны транспонированная структура и постоянная структура вычислений.

Оценки числа арифметических операций для данного алгоритма БПХ равны

а с учетом факторизации (9.10)

Далшейшее уменьшение числа сложений в (9.17) возможно, если для факторизации блоков применить разложение Хаусхоадера [19]

где Тогда

и, следовательно, для вычисления достаточно семь сложений (рис. 9.7) вместо восьми сложений при обычной факторизации (9.13). В этом случае оценки числа вещественных сложений для алгоритма (9.17) равны

или