3.4. Обобщение факторизации ДПФ на случай m множителей

При обобщении полученных базовых форм факторизации на случай множителей возможны три варианта:

1) произвольные множители:

2) взаимно-простые множители:

3) смешанный случай: но что Перечисленные варианты приводят к обобщенным выражениям факторизации с помощью которых можно получить большинство известных к настоящему времени алгоритмов БПФ.

Приведем без промежуточных преобразований (подробнее см. в [4]) окончательные выражения для первых двух случаев. Пусть тогда

где матрицы перестановок и определяются правилами:

На рис. 3.3 приведен граф вычислений, построенный согласно (3.21). Для практики наиболее интересен случай, когда тогда матрица цифроинверсной перестановки. Отсюда

где

Пусть теперь Тогда на основе факторизации (3.14)

Рис. 3.1. j-й этап обобщенной факторизации ДПФ для и произвольных множителей

рекуррентным способом можно построить следующее общее выражение для

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

Из (3.23) в зависимости от выбора лолучаются различные варианты факторизации На практике наиболее часто грименяются следующие случаи.

Полученное выражение (3.23) в чвном виде не определяет структуру быстрого алгоритг и как, например, (3.21). Для определения гакой структуры в явном виде возможны два подхода: а) применить к (3.23) георему фактопизации 6; б) применись к (3 23) свойство 5 кронекеровского произведения матриц (из разд. 1.2). При этом мы получаем два класса алгоритмов БПФ - построчно-столбцовые и гнездовые алгоритмы. Возможно совместно применение свойств 5 и 6, что дает смешанный класс алгоритмов БПФ, так называемые квазигнездовые алгоритмы. Подробный аналгз этих алгоритмов приводится в гл. 5.

Пусть теперь среда множителей существуют как произвольные с так и взаимно-простые . В любом случае размер ность можно представить в виде

Тогда согласно (3.23) и имеем

В свою очередь, каждую матрицу можно представить в форме (3.22)

Подставим (3 28) в (3.27) и воспользуемся свойством 5 кронекеровского произведения матриц разд. 1.2), Тогда, определив получаем

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

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