clear all; close all; clc;
M = 2;
L = 3;
N = M*L;
% Заполняю матрицу W [L x M] поворотных к-тов составного FFT
W = zeros(L, M);
for l = 0:L-1
for m = 0:M-1
W(l+1, m+1) = exp( -j * 2 * pi * l * m / N);
end
end
% Случайный комплексный сигнал 6 отсчетов
x = randn(N,1) + 1i * randn(N,1);
% Перевожу входной сигнал в матрицу [M x L],
A = reshape(x, M, L);
% транспонирую матрицу A и получаю матрицу B [L x M]
B = transpose(A);
% FFT по столбцам матрицы B
Y = fft(B);
% Поэлементное умножение матрицы Y и
% матрицы поворотных к-тов W
Z = Y .* W;
% Транспонирую матрицу Z и получаю матрицу Q размера [M x L]
Q = transpose(Z);
% FFT по столбцам матрицы Q. Получим матрицу V [M x L]
V = fft(Q);
% Транспонируем матрицу V и получаем P [L x M]
P = transpose(V);
%стыкуем столбцы матрицы P друг за другом и получаем результат FFT
X = reshape(P, M*L, 1);
err = max(abs(X - fft(x)));
fprintf('max error = %.3e\n', err);
Алгоритм БПФ составной длины
![]() DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов Распространяется под лицензией LGPL v3
Страница проекта на SourceForge
|
В предыдущих разделах мы рассмотрели алгоритмы БПФ по основанию два
с прореживанием по времени
и
с прореживанием по частоте.
Данные алгоритм очень эффективны, но они имеют существенное ограничение: длина входных данных и выходного вектора должна быть целой степенью двойки .
В данном разделе мы рассмотрим алгоритмы БПФ для произвольной составной длины , где
и
— произвольные положительные целые. Данный подход позволит построить эффективные процедуры
дискретного преобразования Фурье
практически для всех длин, а не только для
. Кроме того, мы покажем, что рассмотренные ранее алгоритмы БПФ по основанию два являются частным случаем алгоритма БПФ составной длины.
Пусть длина ДПФ равна произведению , где
и
— целые положительные числа.
Выражение для ДПФ сигнала ,
можно записать в виде:


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



















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







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

Рассмотрим пример для . Тогда
,
. Вектор входного сигнала имеет вид:

Индексы ,
и согласно (6) получаем два набора сигналов
в виде векторов
и
для индексов
и
соответственно:




















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




Шаг1. Исходный вектор размерности Преобразуется в матрицу
размерности
, содержащую 2 строки и 3 столбца.
Шаг 2. Транспонируем матрицу и получаем матрицу
размерности
.
Шаг 3. Рассчитываем 3-точечное ДПФ каждого столбца матрицы и сохраняем результат в матрицу
той же размерности
.
Шаг 4. Производим поэлементное умножение матрицы и предварительно подготовленной матрицы поворотных коэффициентов
(знак
означает поэлементное умножение). На выходе имеем матрицу
размерности
.
Шаг 5. Транспонируем матрицу и получаем
размерности
.
Шаг 6. Рассчитываем 2-точечное ДПФ каждого столбца матрицы и сохраняем результат в матрицу
той же размерности
.
Шаг 7. Наконец транспонируем матрицу и преобразуем матрицу
в вектор 6-точечного ДПФ исходного сигнала.
Данная схема подходит для любого размера и требует три операции транспонирования матриц размерности
и
,
комплексных умножений
, а также
ДПФ размера
точек и
ДПФ размера
точек.
Если один или оба множителя и
также представляются составным числом, то процедуру можно применять рекуррентно для расчета ДПФ размера
и
точек, до тех пор пока не достигнем разложения исходного размера
на простые множители.
Следующий скрипт dft_composite.m реализует расчет ДПФ составной длины в соответствии с приведенным алгоритмом. Скрипт можно запустить в пакете GNU Octave или в Matlab.
Во всех вышеприведенных примерах для мы представляли
, где
,
. Однако мы можем изменить порядок представления, т.е. задать
, а
. В этом случае получим равносильный алгоритм, в котором на первом этапе потребуется 3 ДПФ размера 2 точки, а на втором этапе — 2 ДПФ размера 3 точки.
Тогда произведем разложение для сигнала (10) при изменении порядка представления.
Индексы ,
и согласно (6) получаем три набора сигналов
в виде векторов
,
и
для индексов
соответственно:

Рассчитаем 3 ДПФ размера 2 точки для ,
и
. Получим три вектора
,
, и
, хранящие значения
:


Следующий шаг: умножение на поворотные коэффициенты и переиндексация в
. Тогда получим 2 вектора
,
:












Можно заметить, что размеры матриц на рисунке 2 являются транспонированными по отношению к матрицам на рисунке 1. C точки зрения вычислительных операций, оба алгоритма эквивалентны.
Ранее мы рассмотрели алгоритмы БПФ по основанию два: с прореживанием по времени и с прореживание по частоте для расчета ДПФ размера .
В данном случае составное число, которое можно представить как
, где
,
и тогда применив алгоритм составной длины получим БПФ по основанию 2 с прореживанием по времени, как это показано на рисунке 3 для
,
,
.




Процедура «прореживание по времени» возвращает два столбца матрицы .
Далее мы выполняем два ДПФ размера 4 точки над каждым столбцом матрицы
и получаем матрицу
. После этого производим поэлементное умножение
на матрицу поворотных коэффициентов
. Выходной граф бабочка на структуре алгоритм БПФ с прореживанием по времени описывают 4 ДПФ размера 2 точки по столбцам транспонированной матрицы
, в результате получаем матрицу переставленных отсчетов спектра
.
Заметим, что каждое из 4-точечных ДПФ мы также можем рассчитывать с использованием алгоритма составной длины, применив который мы получим полный граф алгоритма с прореживанием по времени.
Если же мы изменим порядок разложения, т.е. для зададим
,
, то получим алгоритм БПФ по основанию 2 с прореживанием по частоте, как это показано на рисунке 4.




Первый каскад «бабочек» рассчитывает 4 ДПФ размера 2 точки и выводит матрицу , которая умножается на транспонированную матрицу поворотных коэффициенты
и получаем транспонированную матрицу
. После этого рассчитываем два ДПФ размера 4 точки и возвращаем матрицу спектра
. На последнем этапе транспонируем матрицу
и получаем результат ДПФ.
Производя расчет 4-точечных ДПФ как ДПФ составной длины получаем алгоритм БПФ с прореживанием по частоте.
Таким образом, мы показали, что рассмотренные алгоритмы по основанию два это частный случай алгоритма составной длины, когда все множители равны двойке. Однако использование данного подхода позволяет получить высокоэффективные алгоритмы для ДПФ произвольных составных длин . Например ДПФ размера
можно представить как
, и для расчета потребуется 5 ДПФ размера 20 точек и 20 ДПФ размера 5 точек. Причем каждое 20-точечное ДПФ также можно представить в виде составного алгоритма с множителями 5 и 4.
Таким образом можно заключить, что для эффективной реализации алгоритма составной длины необходимо иметь процедуры коротких ДПФ простых длин (2, 3, 5, 7, 11 и т.д.), тогда можно будет построить эффективные алгоритмы БПФ практически для всех размеров входных векторов. Эффективные алгоритмы простых длин были разработаны Шмуэлем Виноградом и опубликованы в 1978 году. Данные алгоритмы мы рассмотрим в следующем разделе.