Алгоритм БПФ по основанию два с прореживанием по частоте

Содержание

DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов

Распространяется под лицензией LGPL v3

Страница библиотеки на GitHub

Обнаружили ошибку? Выделите ее мышью и нажмите ctrl+enter
Введение

В предыдущем разделе был подробно рассмотрен алгоритм БПФ с прореживанием по времени. Рассмотрим еще один способ разделения и объединения, который носит название прореживание по частоте.

Алгоритм БПФ с прореживанием по частоте

Пусть имеется N отсчетов входного сигнала s(n), n = 0 \ldots N-1, при этом N представляет собой целую степень двойки N = 2^L.

В алгоритме БПФ с прореживанием по времени производилось разделение исходного сигнала в соответствии с двоично-инверсной перестановкой.

Таким образом, мы получили первую и вторую половины дискретного преобразования Фурье (ДПФ).

В алгоритме с прореживанием по частоте исходный сигнал s(n), n = 0 \ldots N-1, делится пополам, т.е. s_0(m) = s(m) и s_1(m) = s\left(m+\frac{N}{2}\right), m = 0 \ldots \frac{N}{2} - 1.

Тогда ДПФ сигнала s(n) может быть записано в виде:

equation 1
(1)

Рассмотрим выражение (1) для спектральных отсчетов S(2 p), p = 0 \ldots \frac{N}{2}-1, с четными индексами:

equation 2
(2)
Учтем в выражении \label{fft_dec_in_freq:eq2}, что W_N^{\frac{N}{2}  2  p} = W_N^{N  p} = 1, а также W_N^{2m p} = W_{\frac{N}{2}}^{m p}, тогда получим:
equation 3
(3)
Таким образом, спектральные отсчеты S(2 p), p = 0 \ldots \frac{N}{2}-1, с четными индексами есть \frac{N}{2}- точечное ДПФ сигнала x_0(m) = s(m) + s\left( m + \frac{N}{2} \right).

Аналогично рассмотрим выражение (1) для спектральных отсчетов S(2 p+1), p = 0 \ldots \frac{N}{2}-1, с нечетными индексами:

equation 4
(4)

Учтем в выражении (4), что  W_N^{\frac{N}{2}  (2  p+1)} = W_N^{\frac{N}{2}  2  p}  W_N^{\frac{N}{2}} = -1 , а также, что  W_N^{m   (2  p+1)} =W_N^{m}  W_N^{m   2  p} = W_N^{m}  W_{\frac{N}{2}}^{m  p} .

Тогда выражение (4) можно представить в виде:

equation 5
(5)
Спектральные отсчеты S(2 p+1), p = 0 \ldots \frac{N}{2}-1, с нечетными индексами 2  p+1 есть \frac{N}{2}- точечное ДПФ сигнала x_1(m)= \left[s(m) - s\left( m + \frac{N}{2} \right)\right] W_N^{m}.

Таким образом, процедура разделения заключается в расчете сигналов половинной длительности x_0(m) и x_1(m), m = 0 \ldots \frac{N}{2} - 1.

После чего можно заменить N-точечное ДПФ двумя \frac{N}{2}-точечными ДПФ сигналов x_0(m) и x_1(m).

Граф «бабочка» алгоритма БПФ с прореживанием по частоте

Процедура расчета сигналов половинной длительности

equation 6
(6)
может быть представлена в виде графа «бабочка», как это показано на рисунке 1.

Граф > алгоритма БПФ с прореживанием по частоте
Рисунок 1. Граф «бабочка» алгоритма БПФ с прореживанием по частоте

Отличие графа «бабочка» алгоритма с прореживанием по частоте от аналогичного графа для алгоритма с прореживанием по времени заключается в том, что умножение на поворотный коэффициент W_N^m производится после вычитания ветвей.

В графе «бабочка» алгоритма с прореживанием по времени умножение на поворотный коэффициент производилось до вычитания ветвей.

Полный граф алгоритма БПФ с прореживанием по частоте

Мы заменили расчет N-точечного ДПФ двумя \frac{N}{2}-очечными.

В результате граф алгоритма БПФ с прореживанием по частоте для N=8 приведен на рисунке 2.

Граф  алгоритма БПФ с прореживанием по частоте для
Рисунок 2. Граф алгоритма БПФ с прореживанием по частоте для N=8

При этом каждое из \frac{N}{2}-точечных ДПФ также может быть рассчитано с использованием алгоритма с прореживанием по частоте.

В результате получим полный граф алгоритма БПФ с прореживанием по частоте, как это показано на рисунке 3.

Полный граф  алгоритма БПФ с прореживанием по частоте для
Рисунок 3. Полный граф алгоритма БПФ с прореживанием по частоте для N=8

На первом этапе получаем x_0(m) и x_1(m), в соответствии с (6):

equation 7
(7)
Для расчета 4-точечных ДПФ сигналов x_0(m) и x_1(m), m = 0 \ldots 3, снова используем алгоритм с прореживанием по частоте. Тогда получим сигналы:

equation 8
(8)
После расчета двухточечных ДПФ на последнем уровне разбиения получаем переставленные спектральные отсчеты:

equation 9
(9)
которые мы должны подвергнуть двоично-инверсной перестановке аналогично тому, как производится эта процедура в алгоритме с прореживанием по времени.

Выводы

В данном разделе мы рассмотрели алгоритм БПФ по основанию два с прореживанием по частоте.

В следующем разделе мы рассмотрим вычислительную эффективность алгоритмов БПФ по основанию два и некоторые вопросы программной реализации алгоритмов БПФ.

Список литературы
[1] James W. Cooley and John W. Tukey An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, Vol. 19, no. 2, April 1965, pp. 297-301.

[2] Оппенгейм А., Шаффер Р. Цифровая обработка сигналов. Москва, Техносфера, 2012. 1048 с. ISBN 978-5-94836-329-5

[3] Bracewell R. The Fourier Transform and Its Applications McGraw-Hills, 1986, 474 c. ISBN 0-07-007-015-6

[4] Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов. Москва, Радио и связь, 1985.

[5] Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Москва, Радио и связь, 1985.

[6] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Мир, 1989, 448 c.

[7] Сергиенко А.Б. Цифровая обработка сигналов СПб, Питер, 2002.

[8] Рабинер, Л., Гоулд, Б. Теория и применение цифровой обработки сигналов. Москва, Мир, 1978. 848 с.

Последнее изменение страницы: 14.11.2020 (11:16:01)
Страница создана Latex to HTML translator ver. 5.20.11.14