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

Содержание

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

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

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

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

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

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

Приведем еще раз выражение для ДПФ:

equation 1
(1)
Процедура разделения-объединения была рассмотрена в предыдущем разделе.

Мы будем оперировать с поворотными коэффициентами ДПФ:

equation 2
(2)
как мы уже делали при рассмотрении свойств ДПФ. Тогда выражение (1) с учетом (2) принимает более упрощенный вид:

equation 3
(3)

Разделение исходной последовательности прореживанием по времени

Прореживание по времени заключается в разделении исходной последовательности s(n), n = 0 \ldots N-1, на две последовательности половинной длительности s_0(m) и s_1(m), m = 0 \ldots \frac{N}{2}-1, таким образом, что s_0(m) = s(2 \cdot m), а s_1(m) = s(2 \cdot m + 1).

Последовательность s_0(m) содержит отсчеты с четными индексами, а s_1(m) — с нечетными.

Прореживание по времени для N = 8 наглядно представлено на рисунке 1.

Прореживание по времени для
Рисунок 1. Прореживание по времени для N=8

Процедура объединения

Рассмотрим ДПФ прореженного по времени сигнала:

equation 4
(4)

Если рассмотреть только первую половину ДПФ S(k) для индексов k = 0 \ldots \frac{N}{2}-1, а также учесть, что

equation 5
(5)
то (4) преобразуется к виду:
equation 6
(6)
где

equation 7
(7)
\frac{N}{2}-точечные ДПФ прореженных последовательностей s_0(m) и s_1(m), m = 0 \ldots \frac{N}{2}-1 соответственно.

Таким образом, прореживание по времени можно считать алгоритмом разделения последовательности на две последовательности половинной длительности. Первая половина ДПФ есть сумма ДПФ S_0(k) «четной» последовательности s_0(m) и ДПФ S_1(k) «нечетной» последовательности s_1(m), умноженного на поворотные коэффициенты W_N^k.

Проанализируем теперь вторую половину ДПФ S\left( k+\frac{N}{2} \right) для k = 0 \ldots \frac{N}{2}-1:

equation 8
(8)
Рассмотрим более подробно поворотные коэффициенты W_{N}^{2 m  \left( k+\frac{N}{2}\right)}:

equation 9
(9)
Аналогично можно упростить W_{N}^{(2 m + 1) \left( k+\frac{N}{2}\right)}:

equation 10
(10)

Тогда выражение (8) с учетом (9) и (10) принимает вид:

equation 11
(11)
Используя выражение для первой (6) и второй (11) половин ДПФ, окончательно можно записать процедуру объединения как:
equation 12
(12)

Граф <<бабочка>>

Выражение (12) объединяет два \frac{N}{2}-точечных ДПФ S_0(k) и S_1(k), k = 0 \ldots \frac{N}{2}-1, прореженных сигналов половинной длительности s_0(m) = s(2\cdot m) и s_1(m) = s(2\cdot m+1), m = 0 \ldots \frac{N}{2}-1, в результирующее N-точечное ДПФ S(k), k= 0 \ldots N-1, исходного сигнала.

Графически процесс объединения представлен на рисунке 2.

Граф
Рисунок 2. Граф «бабочка»

Из-за специфической формы графа он получил название «бабочка». Данная процедура объединения является основной при построении алгоритмов БПФ по основанию два.

На рисунке 3 представлен граф алгоритма БПФ в соответствии с (12) для N = 8.

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

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

Выражение (12) представляет собой процедуру объединения для расчета N-точечного ДПФ S(k), k = 0 \ldots N-1, через два \frac{N}{2}-точечных ДПФ S_0(k) и S_1(k), k = 0 \ldots \frac{N}{2}-1, четной и нечетной прореженных последовательностей s(2 \cdot m) и s(2\cdot m+1), m = 0 \ldots \frac{N}{2}-1.

Такую же процедуру можно применить для расчета каждого из \frac{N}{2}-точечных ДПФ S_0(k) и S_1(k) через два \frac{N}{4}-точечных ДПФ.

Тогда для N = 2^L можно произвести L-1 этап деления последовательности на «четную» и «нечетную» и после этого производить объединение спектра за L этапов.

В результате мы получим полный граф алгоритма БПФ.

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

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

На первом этапе отсчеты входного сигнала переставляются местами и исходная последовательность делится на «четную» и «нечетную» последовательности. Потом «четная» и «нечетная» последовательности в свою очередь делятся на «четную» и «нечетную» последовательности.

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

Например, s(4) имеет индекс в десятичной системе счисления 4_{10} = 100_2, если же 100_2 переписать справа налево, то получим 001_2, то есть s(4) после разделения на «четные-нечетные» перед первой операцией «бабочка» встанет на место отсчета s(1), который в свою очередь встанет на место s(4).

По аналогичному правилу поменяются местами все отсчеты, при этом некоторые останутся на месте, в частности s(2), так как если 2_{10} = 010_2 переписать справа налево, то все равно останется 010_2, аналогично s(0), s(5) и s(7).

Важно отметить, что данный метод перенумерации должен применяться при записи числа в двоичной системе, состоящей из L разрядов. В приведенном примере N = 2^L = 8 использовалось 3 разряда двоичного числа, но если бы N было равно 16, то необходимо было записать число при использовании 4 разрядов. В этом случае 2_{10} = 0010_2, и после перестановки получим 0100_2 = 4_{10}, то есть при N=16, отсчет s(2) не останется на месте, а поменяется местами с s(4).

После двоично-инверсной перестановки получаем четыре 2-точечных ДПФ:

equation 13
(13)
На основе четырех 2-точечных ДПФ формируются два 4-точечных ДПФ:
equation 14
(14)

И на последнем уровне формируется полное ДПФ входного сигнала:

equation 15
(15)

Выводы

В данном разделе мы рассмотрели один из наиболее широко распространенных алгоритмов быстрого преобразования Фурье: алгоритм с прореживанием по времени.

Показана процедура разделения прореживанием по времени и приведена процедура объединения на основе графа «бабочка» согласно выражению (12).

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

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

Список литературы
[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:11)
Страница создана Latex to HTML translator ver. 5.20.11.14