4.6. Базовые алгоритмы ДПФ для N = 8, 16

Разрабатывая схемы для , мы сталкиваемся с затруднением, обусловленным тем, что

не имеет примитивных корней. Другими словами, не существует целое число, степени которого по модулю порождали бы все нечетные числа из интервала Однако одну половину этих чисел можно сгенерировать, используя степени числа 3 по модулю , а другую половину — используя отрицательные значения этих степеней по модулю Таким образом, возникает необходимость разбиения на 3 подмножества:

Как и индексы, заключенные в скобки (см. разд. 4.2), индекс служит для идентификации подмножества, к которому принадлежит . Заметим, что нулевой индекс появляется во всех трех подмножествах:

Теперь можно заменить (4.14) на

Проиллюстрируем это для

Равенства (4.15), (4.16) должны теперь читаться как

гак что общее функциональное соотношение между для может быть подытожено следующим образом:

Аналогичная таблица устанавливает соотношение между и а. Равенства применяются теперь, чтобы исключить из (4.9) (см. анализ аналогичной ситуации в разд. 4.2. учитывая, что здесь ):

Очевидно, что все четыре матричные произведения, появляющиеся в (4.120), являются преобразованиями Ханкеля порядка Докажем теперь, что они являются также ЛЦ-преобразованиями. Для этого надо показать, что [см. (4.6), (4.22)]

или, что эквивалентно,

Докажем (4.122) индукцией по Предположим, что оно истинно для Тогда . Возведение в квадрат дает так что и (4.122) истинно для . Наконец, очевидно, что (4.122) истинно для

Таким образом, (4.120) включает в себя четыре произведения ЛЦ-матриц. Кроме того, эти четыре матрицы содержат в себе составную матрицу второго порядка, которая сама является ЛЦ-матрицей. Все эти свойства выявляются совершенно отчетливо в двух случаях, разбираемых ниже.

4.6.1. ДПФ порядка 8 (рис. 4.14)

Применяя перестановку (4.116), получим матрицу:

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

получаем:

Рис. 4.14. Алгоритм ДПФ порядка 8 (см. скан)

Мы видим здесь четыре ЛЦ-подматрицы второго порядка, по две матрицы каждого типа: Используя введенную терминологию. выпишем эквивалентную блочную матрицу второго порядка

Заметим, что (4,126) тоже является ЛЦ-матрицей. Оценим (4.126) непосредственно с помощью схемы на рис. 4.1. Здесь приходится прибегнуть к некоторым уточнениям. Все схемы в этой главе разрабатывалась с неявным предположением о скалярном характере всех появляющихся в них переменных. На самом деле это не является необходимым. Таким образом, можно сделать вывод, что все схемы справедливы и при такой обобщающей интерпретации: I) строки (столбцы) переменных являются подматрицами-столбцами; являются квадратными матрицами; 3) остается скалярной константой; 4) входы в схемы нужно интерпретировать как матричные произведения

Непосредственной целью введения такого обобщения является вычисление (4.126). Однако важность его выходит за рамки непосредственного применения. Это обобщение означает, что наше

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

Вернемся к вычислению (4.126). Из рис. 4.1 получаем

Отсюда (обозначая

Обратимся теперь к оставшимся частям (4.123).

Этим завершается вывод.

4.6.2. ДПФ порядка 16

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

Отсюда получаем следующую матрицу Е: (см. скан)

Учитывая сложность случая, будем строить схему в два приема. Составляющая ЛЦ-подматриц рассматривается сначала в промежуточной схеме (рис. 4.15), а затем будет перенесена в окончательную схему (рис. 4.17).

Как и в предыдущем случае, выпишем ЛЦ-часть явно

т. е.

Рис. 4.15. Промежуточная вычисления для ДПФ порядка 16 (см. скан)

Обработаем (4.132) по схемам (4.127), (4.128). Из (4.128) очевидно, что будут ЛЦ-матрицами. Следовательно, для их вычисления достаточно иметь первые строки. Выразим их через базовый угол

Обращаясь к (4.127), получаем:

Следующий шаг в (4.127) требует вычисления двух ЛЦ-преобразований порядка 4, а именно:

Выберем следующие обозначения для компонент

Теперь их можно определить с помощью схемы на рис. 4.2.

Реализация

Исчезновение первых двух множителей в (4.139) означает, что необходима только часть схемы рис. 4.2, включающая строки Эта часть переписывается в строки на рис. 4.15 (этим объясняются индексы ). Заметим, что на рис. 4.15 указаны два альтернативных пути, ведущих от к Верхний путь сейчас можно игнорировать. Предыдущие относились к Обратимся теперь к .

Реализация

В (4.140) это очень напоминает случай . Строки на рис. 4.2 переписываем теперь в строки на рис. 4.15.

(кликните для просмотра скана)

Рис. 4.16. Матрица для вычисления (см. скан)

Имея применим (4.127) для получения как показано в нижней части рис. 4.15. Переход от к (см. нижнюю часть рисунка) требует 8 сложений. Верхняя часть реализует то же самое преобразование, только за 4 сложения. Именно этот вариант перенесен на рис. 4.17. В идентичности обоих путей можно легко убедиться. Например, в верхней части но то же самое имеет место и в нижней части. Прослеживание таких соответствий по всем восьми выходам позволяет установить идентичность обоих вариантов.

Рассмотрим теперь реализацию оставшихся частей (4.130). Для того чтобы подчеркнуть использованные здесь симметрии, на рис. 4.16 в явной форме показана оставшаяся часть матрицы ДПФ с выполненными перестановками. Для удобства эта матрица представлена здесь в виде суммы двух матриц и выражена через константу

Теперь определим

(кликните для просмотра скана)

(кликните для просмотра скана)

Отмечая на рис. 4.16 столбцы, связанные с каждым из четырех входящих в видим, что те же самые входят в но с другими знаками:

Наконец, рассмотрим четыре верхние строки

На этом вывод завершается. (Заметим, что размеры схемы на рис. 4.17 накладывают определенные ограничения на обозначения, в частности,