2.4.3. Некоторые частные случаи

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

.                                                                    (2.130)

Алгоритмы с разбиением по строкам и столбцам соответствуют разложению на множители

,                                 (2.131)

.                                (2.132)

При первом разложении преобразования по столбцам выполняются перед преобразованиями по строкам, при втором - наоборот. Для первого разложения любой целочисленный вектор  в области

можно записать в виде

.                                     (2.133)

Таким образом, множество  содержит  векторов

.

Аналогично мы можем определить множество  в виде

.

Если  и  являются степенями 2, можно разложить  и  далее и получить

.        (2.134)

Это разложение соответствует использованию одномерного БПФ по основанию 2 для выполнения преобразований по строкам и столбцам.

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

.                                               (2.135)

Тогда любой целочисленный вектор в множестве  можно выразить в виде

.                                                                        (2.136)

В этом случае множество  содержит четыре элемента , ,  и , а множество  состоит из  векторов вида , где  и .

Это разложение  на множители соответствует первой стадии прореживания в алгоритме по векторному основанию, выведенному в разд. 2.3.3. Если  и  является степенью 2, то полным разложением  на множители для БПФ по основанию  будет разложение

.                                                           (2.137)

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

В гл. 1 мы видели, что после прямоугольно-дискретизованных сигналов следующим наиболее важным классом последовательностей является класс сигналов с гексагональной дискретизацией. ДПФ, связывающее сигналы с гексагональной дискретизацией с гексагональными отсчетами их Фурье-представления [6], описывается выражением

.          (2.138)

Оно соответствует матрице периодичности

.                                                                               (2.139)

Если двумерный дискретный сигнал получен в результате дискретизации функции с ограниченной полосой  с помощью гексагональной матрицы дискретизации

,

то матрица , связывающая  и , описывается выражением

.                (2.140)

 имеет вид гексагональной матрицы дискретизации c  и .

Матрицу периодичности  можно разложить следующим образом:

.                                          (2.141)

Это разложение приводит к алгоритму типа алгоритма по векторному основанию для гексагонального ДПФ.

Полная схема алгоритма показана на рис. 2.15,а. Области  и  для первой стадии этого алгоритма таковы:

,                                                    (2.142)

.                             (2.143)

Если  является степенью 2, можно получить более полное разложение:

.                                               (2.144)

«Бабочки» для всех этапов, за исключением первого, аналогичны друг другу и содержат четыре входа и четыре выхода. Первый этап содержит «бабочку» с тремя входами и тремя выходами; одна из них показана на рис. 2.15, в.

Рис. 2.15.

а - полная графическая схема гексагонального БПФ для , когда  разложено на множители в соответствии с уравнением (2.141); б - одна из трехточечных «бабочек» первой стадии и выполняемые в ней умножения. (С любезного согласия Р. М. Мерсеро и Т. К. Спик, IEEE Trans. Acoustics, Speech, and Signal Processing, © 1981 IEEE.)

Матрицу  можно также представить в виде сомножителей следующим образом:

.                                    (2.145)

Это приводит к алгоритму с разбиением по строкам и столбцам, показанному на рис. 2.16. Три -точечных ДПФ, идентичные прямоугольным ДПФ, выполняются после того, как данные рассортированы на три группы и переобозначены. Таким образом, эти ДПФ можно выполнить или с помощью прямоугольного алгоритма с разбиением по строкам и столбцам, или с помощью прямоугольного алгоритма по векторному основанию. Результаты этих ДПФ объединяются затем с использованием одной ступени «бабочек» с тремя входами и тремя выходами. Разница между гексагональным ДПФ и прямоугольным ДПФ состоит в количестве отсчетов в их опорных областях. Гексагональное ДПФ есть преобразование по  комплексных значений отсчетов в каждой частотной или пространственной области. Эти опорные области можно выбрать таким образом, чтобы они имели гексагональную форму с радиусом  отсчетов. Прямоугольное ДПФ со сравнимым частотным разрешением требует  комплексных значений отсчетов. Таким образом, преимущество гексагонального ДПФ перед прямоугольным состоит в том, что оно требует на 25% меньшего объема памяти.

Рис. 2.16. Граф гексагонального БПФ для , в случае когда  разложено на множители в соответствии с уравнением (2.145).

Оно также требует меньше вычислительных операций. В гексагональном БПФ по векторному основанию общее количество вещественных умножений составляет . По сравнению с этим прямоугольный алгоритм по векторному основанию для последовательности, обеспечивающей сравнимое частотное разрешение, требует  вещественных умножений. Таким образом, экономия в объеме вычислений составляет около 25%.