2.4.2. Алгоритм быстрого преобразования Фурье для общего случая периодической дискретизации сигналов

В этом разделе рассмотрим эффективные алгоритмы ДПФ следующего вида:

. (2.105)

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

В дальнейшем в этом разделе мы будем считать, что все используемые матрицы состоят только из целочисленных элементов. Любая матрица для которой , будет называться унимодульной матрицей. Следует заметить, что тоже является унимодульной матрицей. Унимодульные матрицы - единственные целочисленные матрицы, у которых обратные матрицы также являются целочисленными.

Если является простым числом, мы будем говорить, что является простой матрицей. Если - не простая и не унимодульная матрица, будем называть ее составной. [Необходимо помнить, что - всегда целое число и что он равен количеству отсчетов в опорной области .]

Если - составная матрица, то ее можно разложить на произведение двух матриц

, (2.106)

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

(2.107)

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

Будем говорить, что два целочисленных вектора и конгруэнтны по матричному модулю , если для некоторого целочисленного вектора

. (2.108)

Введем обозначение , которое означает, во-первых, что и, во-вторых, что . Любой вектор в периодическом продолжении конгруэнтен вектору в .

Любой вектор в области можно однозначно представить как

, (2.109)

где , .

Множество содержит , а множество содержит целочисленных векторов. Далее, любая пара векторов (по одному из и из ) определяет единственный элемент из . Вектор можно интерпретировать как «частное» при «делении» на , а - как «остаток».

Таким же образом можно определить

, (2.110)

где и .

Имея в виду эти определения, выражение (2.105) можно переписать следующим образом:

. (2.111)

Раскрывая экспоненту, эту сумму можно разбить на две части:

, (2.112а)

. (2.112б)

Эти соотношения представляют собой первый уровень разбиения по алгоритму Кули-Тьюки прореживания БПФ во времени. Полезно рассмотреть по отдельности оба выражения. Последовательность периодична по с матрицей периодичности . Таким образом, сумма в выражении (2.112а) представляет собой двумерное ДПФ массива по матрице периодичности . Опорную область этой последовательности необходимо выбирать равной одному периоду , рассматриваемому как функция . Для каждого значения вектора нужно вычислить свое ДПФ по матрице . Это означает, что всего должно быть выполнено таких преобразований.

Суммирование в выражении (2.112б) показывает, каким образом эти результаты ДПФ по матрице следует объединить для получения ДПФ по матрице . Числа сначала необходимо умножить на множители (их иногда называют «поворачивающими множителями»), а произведения объединяются в ряды ДПФ по матрице , или «бабочки».

Количество умножений на поворачивающие множители равно , а количество «бабочек», соответствующих матрице , - . Если векторы или являются составными, возможно соответствующее дальнейшее разбиение на меньшие ДПФ.

Векторы

, , (2.113)

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

, (2.114)

образуют соподмножество по отношению к этому подмножеству. Поскольку каждое соподмножество имеет тот же размер, что и само подмножество, всего имеется соподмножеств. Члены любого из соподмножеств конгруэнтны друг другу по модулю . Область необходимо выбрать таким образом, чтобы она содержала по одному члену каждого соподмножества - всего элементов.

Области и можно выбрать аналогичным образом. Поскольку дискретное преобразование Фурье периодично по с матрицей периодичности и

, , (2.115)

ясно, что в частотной области играет роль, аналогичную , а - роль, аналогичную в пространственной области. Тогда можно определить отсчет вида

, , (2.116)

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

(2.117)

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

Сейчас, пожалуй, следует пояснить некоторые из этих результатов простым примером. Рассмотрим расчет прямоугольного -точечного ДПФ с матрицей периодичности

, (2.118)

используя разложение на множители

, . (2.119)

На рис. 2.11 показана область , разбитая на четыре соподмножества матрицей дискретизации ; члены одного соподмножества обозначены одним символом. Обратите внимание, что все четыре соподмножества при периодическом продолжении располагаются одинаково. Для определения нам необходим набор из четырех векторов, удовлетворяющий (2.113); другими словами, нам необходим набор из четырех векторов, которые благодаря (2.109) охватят одно из соподмножеств. Один из наборов векторов, который позволяет это сделать, имеет вид

. (2.120)

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

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

. (2.121)

На рис. 2.12 показана опорная область для БПФ, разделенная на четыре соподмножества с помощью матрицы дискретизации в частотной области . Рассматривая этот рисунок, мы видим, что возможным вариантами выбора и являются следующие:

, (2.122)

. (2.123)

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

Для выбранных четырех множеств можно нарисовать часть блок-схемы алгоритма, как это сделано на рис. 2.13. Каждое ДПФ по матрице действует на одно из соподмножеств входных данных, которые были показаны на рис. 2.11, образуя промежуточное множество . [Это то же множество, что и в (2.112а), но оно выражено через два действительных индекса вместо двух векторных.] Это множество умножается на поворачивающие множители (которые для этого БПФ все равны 1) и результаты передаются на вход ДПФ по матрице . Каждое из ДПФ по матрице образует одно из выходных соподмножеств, показанных на рис. 2.12.

Рис. 2.13. Блок-схема -точечного БПФ для примера, описываемого уравнением (2.119).

Четыре выходных результата ДПФ по матрице можно вычислить непосредственно по данным четырех входов. Если входы обозначить через , , и , а выходы - через , , и , то прямое вычисление этих ДПФ дает

, (2.124а)

, (2.124б)

, (2.124в)

. (2.124г)

С другой стороны, поскольку вектор является составным, мы могли бы использовать разложение на множители:

. (2.125)

Схема четырехточечного ДПФ, основанного на этом разложении, приведена на рис. 2.14.

Рис. 2.14. Блок-схема расчета БПФ по матрице с использованием разбиения согласно уравнению (2.125). (С любезного согласия Р. М. Мерсеро и Т. К. Спик, IEEE Trans. Acoustics, Speech, and Signal Processing, © 1981 IEEE.)

Для этого конкретного примера ДПФ по матрице очень похожи. Если входные данные для этих преобразований обозначить через , , и , а выходные - через , , и , то прямое вычисление результатов дает те же уравнения (2.124), что и для ДПФ по матрице . В этом примере входы и выходы могут быть организованы таким образом, что схема на рис. 2.14 будет описывать ДПФ как по матрице , так и по матрице .

Если обозначить через вычислительную сложность алгоритма БПФ по матрице , характеризуемую количеством необходимых комплексных умножений, то

. (2.126)

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

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

, то (2.127)

. (2.128)

Часто при или числа .

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

, (2.129а)

. (2.129б)