4.5. Базовые алгоритмы ДПФ для N = 4, 9

Из (4.2) можно увидеть, что при использовании схем, полученных в последнем разделе, наивысигий реализуемый порядок . Учитывая это, добавим тривиальный алгоритм для (рис. 4.9), увеличив таким образом максимальное значение до 210.

Если бы мы захотели получить еще большие нам нужно было бы или построить новые схемы для следующих по порядку простых чисел ( или придумать новые схемы для — простое). Выберем последнее.

Рис. 4.9. Алгоритм ДПФ порядка 2

4.5.1. ДПФ порядка 4

, т. е. в соответствии с (4.12)

Примитивный корень из 4 равен 3. Отсюда

Число строк, исключаемых из ЛЦ-таблицы, равно 2. Оно значительно увеличивается в последующих таблицах, достигая 8 при Это обстоятельство требует новой и слегка модифицированной терминологии для облегчения работы с частью матрицы, не являющейся левым циркулянтом.

Во-первых, расширим определение так, чтобы (4.15) включало теперь (4.16):

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

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

Дополним теперь (4.19) — (4.21):

И, наконец, зная, что элемент матрицы ДПФ (4.9) — это , введем «экспоненциальную-» матрицу Е:

которая оказывается очень удобной для учета вклада части, не являющейся лево-циркулянтной

Рис. 4.10. Алгоритм ДПФ порядка 4

В данном случае

Здесь добавлены оба типа индексов строки и столбца. Проще всего получить Е непосредственно из определения (4.99). Выписывая эту матрицу, нужно следить за тем, чтобы незаключенные в скобки индексы а следовали в порядке Этим матрице придается ЛЦ-структура. Последовательность других индексов безразлична.

Видно, что (4.100), как и следовало ожидать, представляет ЛЦ-подматрицу второго порядка. Используем действие этой подматрицы вместе со схемой на рис. 4.1, начиная с вычисления

Следовательно (см. рис. 4.1),

Отсюда следует, что только строка (За лает вклад в формирование Перепишем ее в строку (53 на рис. 4.10. Выходной вектор (см. рис. 4.10) оказывается неупорядоченным по своим составляющим. В разд. 4.9 будут показаны преимущества некоторых схемных структур, которые обеспечивают экономию объема памяти при реализации алгоритма. Схемы, построенные до этого, имеют и такого рода структуру, и упорядоченную индексацию выходного вектора Начиная с этого момента, по-видимому, уже невозможно иметь оба желаемых свойства одновременно. Мы выбрали структуру, экономящую объем памяти, что представляется более важным, поэтому имеем неупорядоченный выходной вектор. В данном случае закон перемешивания индексов достаточно прост, но при он становится сложным. Для облегчения выкладок введем дополнительный вектор в формируемые схемы. Неупоря дочеиный вектор идентичен упорядоченному 1] (см. рис. 4.10).

Теперь вернемся к реализации оставшейся части матрицы Е (4.100)

Здесь использован тот факт, что Равенства, подобные (4.100), могут быть выведены непосредственно из матрицы Е.

Такие равенства будут даваться в дальнейшем без каких-либо комментариев:

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

4.5.2. ДПФ порядка 9

Следовательно, из (4.12) имеем

Примитивным корнем из 9 является примитивный корень из 3, а именно 2. Это приводит к

Отсюда матрица Е имеет вид

Поскольку здесь применима схема рис. 4.4. Рассмотрим сначала Матрица Е (4.106) отображает последовательность а; [это согласуется также с (4.76)]. Тогда

Рис. 4.11. Вычисление для алгоритма ДПФ порядка 9 (см. скан)

Вычисление - показано на рис. 4.11. Заметим, что в терминологии рис. 4.4, 4.11

Это означает, что в реализации которая выполняется копированием рис. 4.4, 4.11 в рис. 4.13, члены, связанные с , должны быть отброшены. При копировании этих рисунков используем некоторые перестановки, кроме очевидных перестановок входных и выходных переменных. Эти перестановки расшифрованы на рис. 4.12. Заметим, что перестановка показана за два последовательных шага: (Например,

Обратимся к учету оставшейся части матрицы, используя в качестве руководства (4.106). При этом нам встретятся следующие константы:

Рис. 4.12. Перестановка индексов для формирования рис. 4.13

которые будут применяться в дальнейшем.

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

Этот случай по сравнению с предыдущим требует замены на . Отсюда . С этих позиций обе группа можно реализовать так, как показано на рис. 4.13.

Теперь реализуем Из (4.106)

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

Обратимся теперь к . Единственное отличие здесь состоит в замене на . Отсюда

Наконец,

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

С двумя схемами, разработанными в этом разделе, максимальное реализуемое значение достигает Мы увеличим его до 5040 с помощью схем, рассматриваемых в следующем разделе.