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

Content

DSPL-2.0 is free digital signal processing algorithms library

Distributed under LGPL v3 license

GitHub project page.

Found a mistake? Select it with the mouse and press ctrl+enter
Введение

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

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

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

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

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

В алгоритме с прореживанием по частоте исходный сигнал , , делится пополам, т.е. и , .

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

(1)

Рассмотрим выражение (1) для спектральных отсчетов , , с четными индексами:

(2)

Учтем в выражении , что , а также , тогда получим:

(3)

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

Аналогично рассмотрим выражение (1) для спектральных отсчетов , , с нечетными индексами:

(4)

Учтем в выражении (4), что , а также, что .

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

(5)

Спектральные отсчеты , , с нечетными индексами есть точечное ДПФ сигнала .

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

После чего можно заменить точечное ДПФ двумя точечными ДПФ сигналов и .

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

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

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

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

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

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

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

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

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

Граф  алгоритма БПФ с прореживанием по частоте для
Figure 2. Граф алгоритма БПФ с прореживанием по частоте для

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

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

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

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

(7)

Для расчета 4-точечных ДПФ сигналов и , , снова используем алгоритм с прореживанием по частоте. Тогда получим сигналы:

(8)

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

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

Выводы

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

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

Reference

[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 с.

Page update: 23.06.2020 (23:46:42)