4. МЕТОДЫ ФАКТОРИЗАЦИИ БАЗОВЫХ МОДУЛЕЙ ДПФ

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

4.1. Вычисление ДПФ через циклическую сверху

Для случая, когда простое число, Рейдер [1] показал базовую теорему о возможности представления матрицы в виде циркулянтной матрицы размерностью При этом спектральный вектор X может быть представген в виде

Рейдер показал, что матрица может быть сведена к циркулянтной, если

где - матрицы перестановок, определяемые правилами:

первообразные корни по т.е. при

Приведем пример построения матрицы . Пусть тогда . Для первообразными корнями являются

3 и 5. Пусть в или тогда

Таким образом, для мы получили левоциркулянтную матрицу и для правоциркулянтную.

Итак, если простое число, матрица может быть преобразована в циркулярную матрицу в этом преобразование вида представляет собой циклическую свертку или корреляции

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

где - матрицы, не требующие операции умножения

Выражение (4.3) може быть переписано в несколько другой эквивалентной форме.

где диагональная матрица весовых коэффициентов

Для построения существуют две регулярные процедуры синтеза.

1. Процедура синтеза на основе интерполяционной формулы Лагранжа (алгоритм Тоома Кука) [2].

Представим циклическую свертку в полиномиальной форме

где (аналогично )

Полином с другой стоооны може быть представлен в виде

интерполяционной формулы Лагранжа

Тоща мы приходим к форме Матрица С в этом случае непосредственно следузт из (4.6) Диагональная матрица весовых коэффициентов определяется из

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

2. Сокращения по модулям неприводимых полиномов. Полином в выбранном поле разлагается в произволе неприводимых над этим полем полиномов с целочисленными коэффициентами

где степень каждого полинома . Тогда совокупность сокращений

определяет матрицы (часто ), а произведения вида

определяют матрицу Восстановление гроизводится к китайской теореме остатков (полиномиальный вариант)

где определяет матрицу C.

Очевидно, что к (4.9) может быть ггоименен алгоритм Тоома Кука (4,6) с нижней границей числа умножений Отсюда нижняя граница числа умножений для (4.10) равна

Обычно матрицы синтезируются в поле рациональных чисел

и содержат тривиальные элементы типа Однако в ряде работ показано, что синтез матриц над некоторыми расширениями поля дозволяет получить экономию требуемого чистка умножений Так, при синтезе в поле гауссовских рациональных чисел получается экономия числа умножений порядка 20% при комплексном входном сигнале показано, что дальнейшая экономил числа умножений (порядка 40% по сравнению с ) может получена при синтезе алгоритмов в поле рациональных чисел Эйзенштейна

Из можно получить транспонированную форму [2]

Такое представление может быть полезно, когда последовательность является фиксированней. Тогда целесообразно заменить матрицу С, обла пающук более сложной стоуктурой, на более простую матрицу В. При интезе алгоритма (4.12) часто выбирают тогда

Для вычисления базовых модулей вектор заменяется на вектор весовых коэффициентов Фурье тогда с учетом определения нулевого члена в (4.1) базовый модуль может быть определен в следующих трех канонических формах:

где матрица получается из добавлением 0-й строки (для определения отсчета в (4.1)), матрица получается из добавлением 0-й строки и нулевого столбца (для добавления отсчета в (4.1)).

В общем случае коэффициенты матриц являются комплексными числами. Однако учитывая, что числа четные, полином можно представить в виде

Аналогично

Так как то окончательно получаем

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

В [9, 10] предложена модификация представления (4.15), позволяющая уменьшить число сложений. Предложенный вариант канонического представления авторы назвали вертикально-гнездовым алгоритмом Основная его суть заключается в факторизации матрицы А путем последовательного сокращения (4.8), т.е. сначала выполняется сокращение по двум полиномам При этом получается матрица

Затем вьшолняется следующее сокращение по двум полиномам что дает матрицу . В результате такого разбиения окончательно получается

где

Тогда

Аналогичный подход может быть применен к факторизации матрицы за счет поэтапного синтеза по

где

Например, при имеем

Для вычисления базовых ДПФ Виноградом была найдена оптимальная форма (4.13) для размерностей . В работе [11] данный список расширяется до . В [12] сообщается в процедуре синтеза модулей прямым способом, т.е. форма (4.13) непосредственно приравнивается к матрице отсюда или

Для решения (4.19) применен вычислительный подход поиска элементов минимизирующи функционал:

Такой подход позволил найти оптимальные алгоритмы для причем для полученные алгоритмы требуют меньше сложений, чем алгоритмы, описанные в [11]. В табл. 4.1 приведены оценки числа нетривиальных вещественных операций умножения и сложения а из указанного списка.

Таблица 4.1 (см. скан)