4.4. Базовые алгоритмы ДПФ для простых N

В этом разделе построенные выше схемы используются для получения алгоритмов для простых нечетных элементов списка (4.3), а именно, 3, 5, 7. Как указывалось в разд. 4.1, они послужат конструктивными блоками для алгоритмов ДПФ более высоких порядков. В разд. 4.2 показано, что при соответствующей перестановке индексов матрица ДПФ порядка N отображает ЛИ-подматрицу порядка . Основная часть вклада этой подматрицы в выполнение преобразования в целом раскрыта в (4.21), которое повторим еще раз:

С другой стороны, ЛЦТ-схемы в последнем разделе основываются на представлении ЛЦ-преобразования порядка определяемом (4.29), (4.39). Поэтому при применении ЛЦП-схем к ЛЦ-преобразованиям, выражаемым (4.74), нужно принять следующие определения:

Обратим внимание на роль (4.76). ЛЦП-схемы как обобщенные задают лишь правила вычисления а по значениям Однако, поскольку (4.76) содержит явную формулу для можно на самом деле вычислить конкретные значения

где — функции и поэтому их можно вычислить заранее.

Перепишем оставшиеся выражения ДПФ с переставленными индексами (4.19), (4.25), (4.26):

Заметим, что (4.79) и (4.80) справедливы только для случая простого и основаны на равенстве

С другой стороны, равенства (4.74) -(4.78) являются совершенно общими и могут использоваться также в следующих двух разделах, где — не простое.

Первый шаг в конструировании ДПФ-схемы для простых заключается в вычислении констант Для этого с помощью (4.76) вычисляются которые применяются затем в ЛЦП-схемах порядка для вычисления , следовательно, (4.77).

Следующим шагом является преобразование ЛЦП-схем порядка в ДПФ-схемы порядка Это эквивалентно реализации (4.74) и дает схему преобразования в Теперь с помощью (4.14) - (4.16), (4.75) заменим эти переменные переменными С этого момента индексация на входе и выходе будет, как правило, немонотонной. Поэтому, чтобы сохранить монотоннность, переставим строки и столбцы во входных и выходных квадратах.

Следует отметить, что замена переменных (4.14) — (4.16) была введена для того, чтобы выявить ЛЦ-структуру и сделать, таким образом, возможным использование (4.45). Однако после этого нам хотелось бы иметь результирующую ДПФ-схему в таком виде, чтобы в ней фигурировали переменные со стандартной монотонной последовательностью индексов, поскольку это облегчает объединение отдельных схем в алгоритм для больших

Обратимся теперь к реализации (4.80). Поскольку все три ЛДП-схемы удовлетворяют соотношению

равенство (4.80) эквивалентно

Наконец, чтобы эффективно реализовать (4.78), во всех трех ЛЦП-схемах выделяем член, который появляется с коэффициентом всех Оказывается, что этот член есть Следовательно, замена на

преобразует на выходе Заметим, однако, что слагаемое уже входит в вычисленное в (4.83). Это дает возможность исключить одно или два умножения в (4.84). Действительно, объединяем (4.83) с (4.84) и получаем [используя (4.77)]:

Отсюда видно, что множитель является произведением и некоторой функции от Это оказывается общим для всех во всех ДПФ-схемах, которые предстоит построить. Поэтому введем обозначение

где — функция только всегда первоначально преобразуется в соответствии с (4.86). Следовательно, одной из задач при конструировании ДПФ-схем будет определение значений констант В ходе разработки будет видно, что лежащее в основе ЛЦП-схемы вместе с выражениями (4.77), (4.86) всегда однозначно определяют . В случае (4.85)

Итак, мы рассмотрели с общих пизиций связь с ДПФ. Обратимся теперь к частным случаям.

4.4.1. ДПФ порядка 3 (рис. 4.5)

Равенство (4.83) явно указано на схеме. Из (4.76), учитывая, что получаем

Рис. 4.5. Алгоритм порядка 3

где W - комплексно сопряженное значение Следовательно, Применяя ЛЦП-схему второго порядка (см. рис. 4.1), находим

4.4.2. ДПФ порядка 5 (рис. 4.6)

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

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

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

4.4.3. ДПФ порядка 7

Тогда из (4.76)

Все выражаются через угол

и кратные ему углы. Правило рис. 4.4 для вычисления показано на рис. 4.7, а окончательная схема, основанная на нем, — на рис. 4.8.

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

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