7.5. Гибридные методы факторизации

Анализ различных методов построения алгоритмов БПФ размерности показывает, что существует нижняя граница числа вещественных арифметических операций, равная

Такой границы достигает ряд современных алгоритмов БПФ [13, 21], введенных в практику цифровой обработки сигналов сравнительно недавно. Анализ различных методов факторизации также показывает, что если преобразуемые в алгоритмах БПФ данные не выходят из поля комплексных чисел, то никакими методами уменьшить оценки (7.27) не удается.

В то же время в [22, 23] показано, что нижняя потенциально достижимая граница числа вещественных нетривиальных умножений в алгоритмах БПФ размерности равна

что при значительно ниже оценки (7.27).

Одним из возможных путей преодоления разрыва между оценками (7.27) и (7.28) является гибридная факторизация с дальнейшим применением полиномиальных и теоретико-числовых преобразований. Ниже рассматриваются некоторые гибридные алгоритмы БПФ, позволяющие уменьшить число умножений по сравнению с оценкой

7.5.1. Алгоритм БПФ, использующий полиномиальные и теоретико-числовые преобразования. Пусть тогда согласно переходной форме факторизации (3.20) получаем

где оператор циклической свертки. Матрицу можно переписать в более привычном виде

На рис. 7.9 изображена общая структурная схема алгоритма (7.29). Очевидно, что алгоритм (7.29) можно также представить в транспонированной форме [24].

Итак, согласно (7.29) А - точечное ДПФ - может быть вычислено как двумерное ДПФ размерности циклических сверток размерности

Пусть двумерное ДПФ вычисляется методом полиномиального преобразования. В гл. 10 будет показано, что наименьшие оценки числа арифметических операций в этом случае равны

Рис. 7.9. Структура вычисления -точечного произвольные) через двумерное циклических сверток размерностей

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

Общий результат свертки при этом восстанавливается по формулам

Не трудно определить, что совокупная оценка вычисления (7.30) и (7.31) равна

Отсюда общая оценка числа арифметических операций для алгоритма (7.29) в случае равна

В случяе нечетного возможна комбинированная факторизация. этап обычный, типа (7.10)

Затем в (7.34) подставляем (7.29) окончательно получаем

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

Как следует из (7.33) и (7 36), число умножений, требуемое для такого алгоритма БПФ, меньше оценки (7 27) потенциально до 2 раз при увеличении числа сложений в 1,5 раза.

7.5.2. Смешанное частотно-временнос прореживание с использованием теоретико-числовых преобразований. Выполним первый этап фаторизации методом прореживания по частоте, тогда

Факторизуем теперь матрицу методом прореживания по времени

Полученные ядра и могут быть далее факторизеваны аналогично (7.37) и (7 38)

Рассмотрим отдельно факторизацию СДПФ (1/2, 1/2) — Данная матрица имеет следующую структуру

В [25] показано, что матрица може: быть преобразована в две косоциркуляртные матрицы размерностями

Приведем один из возможных способов такого разложения, требующего в отличие от метода, предложенного в [25], одинаковых перестановок строк и столбцов

Представим номер строки к (аналогично столбцу и) нечетными цифрами

Определим перестановку строк (аналогично столбцам ) в виде

Тогда, применяя перестановки к матрице мы получаем матрицу с блочноциркулянтной структурой типа

которая факторизуется в виде

Можно показать (доказательство в [25]), что элементы матриц связаны соотношением комплексной сопряженности, т. е. отсюда элементы матриц соответственно равны; т.е. являются чисто действительными или чисто мнимыми числами.

Последним этапом преобразования СДПФ является определение знаковых матриц и преобразующих матрицы в косоциркулянтные

На рис. 7.10 и 7-11 приведены соответственно блок-схемы факторизации

Приведем пример факторизации для Тогда согласно (7.39) матрица имеет следующую структуру:

Рис. 7.10. Вычисление ДПФ через косоциркулянтные свертки

Рис. 7.11. Факторизация блока

Перестановка согласно (7.40) определяется таблицей

Отсюда матрица имеет следующую структуру:

Рис. 7.12. Факторизация циркулянтного блока

После факторизации (7.41) получаем две матрицы

Матрицы изменения знака в данном случае имеют вид отсюда

Как мы видим, обе матрицы и являются косоциркулянтными, и следовательно, могут быть факторизованы любым из методом факторизации косоциркулянтных сверток.

Например, если матрица имеет структуру

то она может быть факторизована в виде

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

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

Пусть определено ТЧП по модулю чисел Ферма Зададим начальный элемент X равным для косоциклической свертки и правило или Тогда для ТЧП Ферма дня элемент X, является тривиальным, равным

Кроме того, на стадии факторизации умножение на также не требует умножений [26], так как

Таким образом, если в (7.42) не превышает при рекуррентной факторизации типа (7-42), на всех этапах не требуется операций умножения (только сложения и сдвиги) и только на последнем этапе требуется умножений на весовые коэффициенты.

Следовательно, для модуля для вычисления СДПФ требуется не более двух умножений на отсчет входной сигнал комплексный), если т.е. и для модуля

Если превышает указанные размерности, то умножения на становятся нетривиальными и общее число умножений резко возрастает.

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

Как видим, для указанных размерностей получается оценка даже ниже минимальной (7.28), причем такое преимущество для модуля сохраняется при а при модуле при Это связано с тем, что оценка (7.28) построена для арифметики в поле комплексных чисел и основана на теореме Винограда о минимальной границе числа умножений при вычислении циклической свертки [27], которая для арифметики в конечных полях неверна.

Таким образом, алгоритмы БПФ, приведенные в данном разделе, позволяют повысить вычислительную эффективность за счет уменьшения операций умножения в 2—3 раза, однако при этом необходима специальная организация модулярной арифметики для вычислений в конечных полях.