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

Содержание

Введение

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

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

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

Выводы

Список литературы

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

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

Страница проекта на SourceForge

Введение

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

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

Пусть имеется отсчетов входного сигнала s(n) , $n = 0 \ldots N-1$ , при этом представляет собой целую степень двойки 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) может быть записано в виде:

(1)

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

(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}$ , тогда получим:

(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$ , с нечетными индексами:

(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) можно представить в виде:

(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$ .

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

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

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

(7)

Для расчета 4-точечных ДПФ сигналов x_0(m)

, $m = 0 \ldots 3$ , снова используем алгоритм с прореживанием по частоте. Тогда получим сигналы:

(8)

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

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

Последнее изменение страницы: 12.05.2022 (19:41:49)

Страница создана Latex to HTML translator ver. 5.20.11.14