5. БЫСТРЫЕ АЛГОРИТМЫ, ОСНОВАННЫЕ НА ФАКТОРИЗАЦИИ КРОНЕКЕРОВСКОГО ПРОИЗВЕДЕНИЯ БАЗОВЫХ МОДУЛЕЙ ДПФ

В данной главе приводятся методы Факторизации обобщенного представления где

Матрица как было показано выше, может соответствовать (с точностью до перестановок) матри: опноме эного ДПФ или ТЧП размерностей где многомерного ДПФ или ТЧП размерностей дискретного преобразования Виленкина размерности произвольные). Кроме того, является основной формой представления ДПХ размерности

Таким образом, методы факторизации определяют общие структуры быстлых алгоритмов для данных с указанными размерностями

5.1. Построчно-столбцовый метод факторизации или алгоритм простых множителей

Применяя георему факторизации (свойство 6, разд. 1.1) к (5.1), непосредственно получаем

Факторизация матрицы одномерного ДПФ на основе (5.2) была впервые реддожена Колба и Нарксим под названием алгоритма простых множителей (Pvime Factor Algorithm - PFA) [1]. В матричном представлении алгоритм, предложенный в имеет вид (алгоритм )

где — матрицы перестановок соответственно по правилам "руританского" и китайского" соответствий (при таких перестановках, как было показано в гл. 3 каноническое представление модулей лида (4.13).

Аналогично (5.3) может быть определен алгоритм простых множителей для в полях или При вместо блоков в (5.3) вычисляются блоки

На осноъе (3.45) и (3.55) может бьгь также определена структура быстрого алгоритма для с учетом представления базовых блоков в транспонированной канонической форме (4.15)

Рис. 5.1. (см. скан)Обобщенная факторизация ДПФ методом "простых" множителей

На рис. 5.1 приведена обобщенная блок-схема АПМ.

Перечислим кратко модификации АПМ, отличающиеся от первоначального алгоритма (5.3), которые нашли применение на практике.

Как следует из (5.3), первоначальное определение АПМ требует различных внешних перестановок, что в ряде случаев нежелательно (например, при вычислениях на мини-ЭВМ) из-за дополнительного буферного ОЗУ. Для устранения данного недостатка Баррас и Эскенбачер [2]; предложили модифицированный подход к построению АПМ, в котором входной и выходной векторы представляются в виде многомерных матриц, структура которых соответствует "руританскому" отображению, т. е.

В этом случае имеет вид (3.24) или в факторизованном виде (алгоритм )

где модифицированное преобразование Фурье, которое также представимо в канонической форме

Очевидным недостатком алгоритма в виде (5.5) является

зависимость модулей друг от друга. Это связано с наличием множителя в степени не позволяет программировать модули независимо от других. Однако, несмотря на указанный недостаток, в целом модификация АПМ в виде (5.5) дает выигрыш в скорости вычисления и в случае предварительного кодирования входных данных согласно правилу "руритакского" соответствия, перестановка результатов вычислений на выходе не требуется, а следовательно, отпадает необходимость в буферном

Учитывая указанный недостаток алгоритма в [4] предложена его дальнейшая модификация (алгоритм ). В матричном виде алгоритм описывается выражением

В (5.6) модифицированное заменяется обычным и дополнительными внутренними перестановками Таким образсм, для объем требуемого буферного ОЗУ равен вещественных слов. Это гораздо меньше, чем емкость буферного ОЗУ, требуемого для алгоритма .

В [6] предложено расширение АПМ для случая при При этом выполняется факторизация вида (5.3) для Затем каждое факторизуется по методу произвольных множителей по основанию был применен для синтеза БПФ длинных последовательностей длиной числа из приведенного в гл. 4 списка, простые числа вида где . В этом случае показано, что разбивается на циркулянтные матрицы, каждая из которых молет быть вычислена посредством ТЧП в поле или

Из векторно-матричного представления многомерного ДПФ (2 14) и (2.16) следует, что АПМ представляет собой построчно-столбцовый метод вычислений в терминах многомерного спектрального анализа. При этом, если в (5.8) входной и выходной векторы представлены в виде многомерных матриц размерностей то вычисляется в виде построчно-столбцового алюритма (ПСА) многомерного ДПФ с соответствующими перестановками на входе и выходе

Таким образом, несмотря на различную терминологию, методы вычисления одномерного АПМ и многомерного ПСА идентичны.

Определим вычислительные характеристики Число вещественных умножений и сложений равно

где соответственно число умножений и сложений для модулей приведенные в табл. 4.1. Из (5.8) следует, что число умножений и сложений не изменится при изменении порядка следования

Для вычисления модуля требуемый объем для хранения весовых коэффициентов равен вещественных слов, отсюда общий объем ПЗУ равен

вещественных слов.

При использовании модифицированного алгоритма (5.5) для хранения промежуточных данных в ОЗУ достаточно вещественных слов (так как согласно (5.5) вычисление выполняется с замещением и перестановками , не требующими дополнительной буферной памяти), плюс буферное ОЗУ дня хранения промежуточных данных при вычислении самих модулей объем которого составляет вещественных слов. Таким образом, общий объем ОЗУ для алгоритма (5.5) равен

вещественных слов.

Для алгоритма (5.3) необходимо дополнительное буферное для обеспечения выходной перестановки которая (кроме отдельных случаев) не может быть выполнена с замещением, отсюда

Для алгоритма (5.6) по отношению к необходимо дополнительное буферное ОЗУ для выполнения внутренних перестановок и отсюда