4.7. Общий алгоритм

Теперь у нас, наконец, есть схемы ДПФ всех порядков, перечисленных в (4.3). Объединим их в алгоритм ДПФ порядка

Наш метод опирается на идею блочной матрицы ДПФ, введенной в последнем разделе. Проиллюстрируем его простым примером. Предположим, мы хотим реализовать ДПФ порядка Можно ли использовать схему восьмого порядка для решения этой задачи? Можно было бы, конечно, рассмотреть исходную матрицу ДПФ как блочную матрицу порядка 8 с блоками порядка 15. Однако применение схемы порядка 8 оправдано только при условии, что эта блочная матрица отображает структуру блочной матрицы ДПФ порядка 8. Простая проверка показывает, что здесь это определенно не так. Тем не менее это обстоятельство не отменяет выбранный подход. Мысленно можно переставить элементы во входном и выходном векторах таким образом, чтобы матрица преобразования превратилась в блочную матрицу ДПФ порядка 8. В этом случае, несомненно, можно было бы применить схему порядка 8 (см. рис. 4.14). Однако на этом пути мы очень скоро столкнулись бы с другим препятствием: схема требует вычисления где является теперь матрицей порядка 15, входящей в качестве блока (0,0) в блочную матрицу ДПФ с переставленными элементами. В схеме необходимо реализовать 8 таких преобразований, при этом для обеспечения высокой вычислительной эффективности алгоритма нам надо избегать прямого умножения

экения матриц. Здесь появляется привлекательная возможность: можно предложить дополнительные ограничения на начальную перестановку, так чтобы превратилась в блочную матрицу ДПФ, укажем, третьего порядка. Если бы такая возможность была, это позволило бы нам использовать преимущества высокой эффективности схемы ДПФ порядка 3 и, таким образом, реализовать ДПФ порядка 120 с помощью схем порядков 8, 3, 5.

Обратимся теперь к более точной формулировке упомянутой идеи, начиная с разработки необходимой терминологии. Будем считать, что индексы в (4.142) отражают порядок применения схем. Так, — порядок первой реализуемой схемы, соответствует второй схеме и т. д. В нашем примере

Пусть будет исходной матрицей ДПФ порядка с переставленными элементами. Если рассматривать ее как блочную матрицу порядка то каждый ее блок будет иметь порядок Обозначим блок (0,0) через Следующий шаг в реализации основывается на рассмотрении как блочной матрицы ДПФ порядка Ее блок (0,0), обозначенный имеет порядок Это приводит к следующим определениям:

Пусть будет матрицей ДПФ порядка с переставленными элементами. Тогда — верхняя левая подматрица порядка Заметим, что (4.144) подразумевает существование последовательности таких подматриц: Порядок подматриц понижается слева направо. слева имеет порядок и поэтому идентична полной матрице. справа имеет порядок 1 и поэтому является верхним левым элементом полной матрицы.

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

должна быть блочной матрицей порядка т. е. блочной матрицей, блок , который является матрицей умноженной на где {см. (4.9)]. Это обеспечит реализацию фазы 1 схемы порядка Фаза 2 требует определения Следовательно,

должна быть блочной матрицей ДПФ порядка Мы используем фазу 1 схемы порядка и на фазе 2 приходим к преобразованию, включающему Следовательно,

должна быть блочной матрицей ДПФ порядка

должна быть блочной матрицей порядка к.

Подведем итоги сказанному. Приемлемой схемой изменения индексов была бы схема, удовлетворяющая следующим требованиям:

Подматрица матрицы У должна быть блочной матрицей ДПФ порядка Это должно выполняться для всех

Хотя основанный на предыдущих рассуждениях алгоритм был бы вполне удобен с точки зрения его реализации, однако не ясно, существует ли на самом деле схема изменения индексации, удовлетворяющая одновременно всем и требованиям (4.145).

Приступим теперь к разработке схемы изменения индексации, которая быстро приводит к (4.145), лишь незначительно усложняя приведенный выше эскиз алгоритма. Начнем со стандартной матрицы ДПФ [см. (4.9) при ]:

Пусть

где

а функцию X еще предстоит определить. Тогда (4.146) преобразуется в

Функция X будет определена в терминах модульного представления . Другими словами, изменение индексации зависит от величин

В соответствии с китайской теоремой об остатках [4.7] эти остатки единственным образом определяют любые Следовательно, можно выбрать следующее представление для

Теперь функция X определяется с помощью объединения :

следующим образом:

должна быть такова, что, когда пробегает значения изменяются, периодически принимая значения из последовательности начиная с должно принимать новое значение три каждом увеличении на [см. (4.144)]. Это означает, что изменяется очень медленно, — быстрее и т. вплоть до которое изменяется синхронно с

Чтобы проиллюстрировать такую перестановку, рассмотрим пример (4.143), для которого часть индексной последовательности будет выглядеть так:

Для определения этой последовательности с помощью ЭВМ можно воспользоваться подпрограммами модулярной арифметики. С другой стороны, ее можно построить по схеме, не применяя ни ЭВМ, ни какие-либо вычисления. Все, что потребуется, — это утомительное переписывание повторяющихся последовательностей. Этот метод для примера (4.143) проиллюстрирован в табл. 4.2, 4.3.

Сначала выпишем последовательность как показано в табл. 4.2 в колонке для Затем из колонки для выпишем повторение последовательности и повторим это для всех Такполучаем представление (4.151) для всех и. Частичное упорядочение табл. 4.2 экономит усилия и удобно для выполнения следующего шага, который является просто переупорядочением табл. 4.2 в требуемую последовательность.

Чтобы упростить процесс, используем табл. 4.2 для определения порядка, в котором заполняется табл. 4.3. Например, первыми значениями копируемыми табл. 4.2 в табл. 4.3, являются Табл. 4.3 теперь задает последовательность индексов у входного вектора с переставленными элементами для (4.143), а именно:

Чтобы облегчить анализ выбранного способа перестановки, введем Е — экспоненциальную матрицу У. Вспомним, что из (4.149) вытекает

Таблица 4.2. Модулярное представление в примере (4.143) (см. скан)

Отсюда определяем экспоненциальную матрицу следующим образом:

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

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

Очевидно, что блок (0,0) этой блочной матрицы идентичен . Выберем элемент в произвольной позиции в е. Его индексы будут иметь вид

Таблица 4.3. Изменение индексации для примера через (см. скан)

Выбранная схема перестановки гарантирует, что все скалярные элементы матрицы занимающие те же самые позиции в других блоках имеют которые отличаются от (4.156) только в и удовлетворяют (4.155). Это означает, что разность между элементами в блоке матрицы и соответствующим элементом в [блок (0,0)] равна

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

Нам нужно явное выражение для этой важной константы. Учитывая неявную ее формулировку (4.157), приходим к выводу, что константа должна быть целым числом, кратным где

А именно, мы должны иметь

где целое удовлетворяет

(4.161)

Соотношение (4.161) является линейным однородным относительно неизвестного и имеет решение [4.8], а именно:

где

Результат, установленный для подматриц распространяется на подматрицы следующим образом: блок матрицы представляет собой Используя (4.159), находим:

Обозначим

тогда

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

Это очень напоминает блок блочной матрицы порядка Единственная разница состоит в том, что заменено на Эта, однако, тривиальная разница сводится только в перестановке столбцов. Для доказательства достаточно показать, что существует однозначное соответствие между и так что когда пробегает значения пробегает те же значения в переставленном порядке. А это, несомненно, так, если — взаимно-простые. Но это гарантируется (4.164), поскольку — взаимно-простые [см. (4.158)].

Отсюда можно сделать вывод, что тривиальная модификация схемы ДПФ порядка позволит найти преобразование, определяемое матрицей . А именно, мы модифицируем входной квадрат схемы перестановкой строк/столбцов так, чтобы последовательность была идентична последовательности (вместо последовательности натуральных чисел в немодифицированной схеме). Назовем такую схему «модифицированной схемой» и

будем с этого момента использовать этот термин только в этом ограниченном точном значении.

Проиллюстрируем модификацию схемы для в примере

Следовательно,

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

Отличие от (4.145) состоит в перестановке столбцов. Но, как уже отмечалось, это означает только то, что в алгоритме порядка N (4.142) стандартные схемы должны быть заменены на модифицированные. В этом и заключаются незначительные усложнения, о которых упоминалось выше.

Рис. 4.18. Входной квадрат модифицированной схемы восьмого порядка для примера (4.143)

Рис. 4.19. Схематическое представление базовых схем ДПФ

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

Изучение схем показывает, что все они состоят из трех частей, соответствующих трем различным фазам алгоритмов, которые ими описываются. На первой фазе обрабатывается -мерный входной вектор чтобы получить -мерные векторы На второй фазе матрица умноженная на скаляр, преобразует в в соответствии с — это число умножений, определяемое назначением схемы. Очевидно, это также число векторов построенных на фазе , наконец, на фазе 3 для получения -мерного выходного вектора обрабатываются -мерные векторы Три фазы представлены схематично на рис. 4.19 со следующими обозначениями. Все линии отображают векторы. С каждой линией связано целое число, показывающее размерность вектора, представляемого этой линией (рис. 4.20). Фаза 1 обозначается кружком, фаза 3 — квадратом. В каждом случае символ внутри фигуры обозначает матрицу, определяющую преобразования очерченного кругом входа в очерченный квадратом выход. Заметим, что единственными арифметическими операциями, включенными внутрь кружка или квадрата, являются сложения или вычитания.

Общий алгоритм приведен на рис. 4.20. Здесь показан конкретный пример для

Модификация для любого другого случая выполняется совсем просто, как это будет показано позже. Первый шаг алгоритма — перестановка элементов входного вектора порождающая вектор Это действие и соответствующая перестановка вектора преобразуют матрицу ДПФ в матрицу У из (4.153). Теперь матрица У разбивается так, как показано на рис. 4.21 (указанные «размеры» относятся к числу строк и столбцов). На следующем шаге рассматривается как блочная матрица третьего порядка и используется модифицированная схема ДПФ третьего порядка со значением на схеме, тождественно равным на рис. 4.21. Фаза 1 показана в верхней части рис. 4.20 ( в кружке), фаза 3 — в нижней части ( в квадрате), а фаза 2 — на остальной части рисунка между ними. На фазе 1 требуется

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

Таблица 4.4. Множители схемы (см. скан)

разделение входного вектора на три его «компоненты». Это делается следующим очевидным образом:

Выходом фазы 1 являются три вектора , размерности 10. Перед тем как перейти к рассмотрению фазы 2, необходимо ввести обобщенные обозначения, которые используются для . Величины в схеме ДПФ порядка будут обозначаться как которые также появляются на рис. 4.20, будут определены позже). Эти константы или явно указаны на схемах, или выводятся из условия, что каждое умножается на Например, на схеме ДПФ порядка 5 явно указано, что Очевидно, что -Для удобства все значения сведены в табл. 4.4. Эти значения вычислены на -разрядном калькуляторе. Более точные значения можно получить, используя явные выражения, указанные в схемах.

Возвращаясь к рис. 4.20, обнаруживаем, что на фазе 2 схемы

Рис. 4.21. Разбиение матрицы У для примера (4.170)

третьего порядка требуется вычислить Здесь мы снова применяем результат (4.169), из которого вытекает, что для преобразование может быть вычислено с помощью модифицированной схемы ДПФ второго порядка [со схемным значением идентифицируемым как см. рис. 4.21]. Поэтому каждый из трех -мерных векторов показан на рис. 4.20 как вход первой фазы схемы второго порядка. В каждом из этих трех применений схемы второго порядка фаза 1 порождает пару векторов размерности 5. Рассмотрим теперь самый левый пятимерный вектор на рис. 4.20. Он порожден фазой 1 схемы, реализующей преобразование, в основе которого лежит матрица Поэтому фаза 2 требует его преобразования с помощью матрицы На рис. 4.20 вместо этого указана матрица Здесь мы придерживаемся несколько необычной терминологии:

Таким образом, определена только по отношению к конкретной диаграмме. Кроме того, тот же самый символ может иметь разные численные значения при разных расположениях на диаграмме. Например, мы только что видели (см. рис. 4.20), что на крайнем слева месте Этот же символ появляется еще два раза правее. В первом случае он равен во втором —

Вернемся к основному предмету наших рассуждений. Каждый из пятимерных векторов теперь должен быть входом модифицированной схемы ДПФ порядка 5. На этот раз «векторы» полученные на фазе имеют размерность 1, т. е. фактически являются скалярами. Они должны умножаться на — это скалярная 1). В этой точке фактически и выполняются умножения, и необходимо иметь численные значения множителей. Эти значения очевидны. Рассмотрим, например, самый левый множитель на рис. 4.20:

Подобным образом самый правый множитель на рис. 4.20 равен

и вообще значение множителя в конкретном узле является произведением всех членов (без значка которые встречаются при движении по древовидной структуре вверх от рассматриваемого узла.

На рис. 4.20 эти умножения показаны в форме полукруга и полуквадрата, расположенных вдоль средней линии схемы.

(Их можно рассматривать как объединенные три фазы алгоритма ДПФ порядка 1 при )

Получаемые после умножения 36 членов образуют 6 независимых групп, являющихся результатом шести отдельных применений модифицированной схемы порядка 5. Члены каждой группы объединяются теперь в соответствии с предписаниями фазы 3 схемы пятого порядка для получения шести векторов размерности 5. Каждый из них является членом вида требующим для завершения вычислений в трех применениях схемы второго порядка. Эти вычисления порождают теперь в качестве выходов схемы три вектора размерности 10, которые идентичны для схемы третьего порядка. Объединение их в соответствии с предписаниями фазы 3 этой схемы порождают -мерный вектор который с точностью до перестановки является нужным нам вектором Р.

Хотя рис. 4.20 непосредственно применим только к примеру (4.170), он достаточно характерен и для всех значений Для больших может появиться еще один уровень ветвления в каждой половине схемы, а число ответвлений от каждого узла может увеличиться. Но общая структура идентична показанной на рис. 4.20.