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 с постоянной структурой и прореживанием по частоте