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%.
