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

Первый этап факторизации по основанию 2 состоит в разделении длины преобразования на два множителя тогда непосредственно из (9.1) получаем

где — матрица класса "совершенных" перестановок, определяемая

правилом находится из (3.36) и для данного случая определяется выражением

где или в развернутой форме

На рис. 9.1 приведена блок-схема построения алгоритма БПХ по основанию 2 для случая

По аналогии с (9.3) могут быть факторизованы ядра Полученные формы факторизации рекуррентно подставляются в (9.3). Окончательное матричное выражение для алгоритма БПХ (прореживание по частоте) имеет вид

На рис. 9.2 изображен полный граф алгоритма БПХ по основанию 2 с прореживанием по частоте для

Для построения алгоритма БПХ с прореживанием по времени необходимо транспонировать выражение (9.6), тогда

Граф такого алгоритма БПХ приведен на рис. 9.3.

По аналогии с (6.7) для ДПХ также возможно определение алгоритма БПХ с постоянной структурой (рис. 9.4)

Вычислительная эффективность всех трех алгоритмов БПХ одинакова и определяется следующими оценками:

Число умножений в (9.6)-(9.8) можно уменьшить, если в матрице выполнить факторизацию типа

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

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

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

В алгоритмах типа (9.6) и (9.7) выполняются вычисления с замещением и, следовательно, для хранения промежуточных данных требуется вещественных слов. Алгоритм с постоянной структурой (9.8) требует в 2 раза больший объем памяти, что является его существенным недостатком.

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

Рис. 9.4. Граф алгоритма БПХ по основанию 2 с постоянной структурой и прореживанием по частоте