4.2. Разложение модулей ДПФ на прямую сумму циркулярных матриц

Пусть простое число, тогда модуль может быть представлен в виде [13].

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

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

произвольный элемент коля образующий мультипликативную группу

Приведем пример синтеза циркулянтных матриц и (граф полного алгоритма (4.20) для приведен на рис. 4.1)) для случая

Рис. 4.1 (см. скан) Структура модуля ДПФ

Таким образом, матрица ДПФ F разбиваются на две -точечных циклических свертки , отсюда минимальное число умножений для

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

алгоритма (4.20) равно

Число вещественных умножений так как весовые коэффициенты в и являются действительными числами. Число вещественных сложений равно

где — число сложений, требуемых для вычисления точечных ЦС.

В табл. 4.2 приведены оценки числа арифметических операций для алгоритма (4.20) (оценки а взяты из [3]).

Как следует из табл. 4.1 и 4.2, вычислительная эффективность алгоритмов (4.13) и (4.20) примерно одинакова. Для размерностей 13 и 17 алгоритм (4.20) является более экономичным. Кроме того, алгоритм (4.20) перспективнее в случае применения распределенной арифметики с использованием так как в этом случае требуется векторный вход размерностью вместо полной размерности .