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

Содержание

Введение

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

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

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

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

Выводы

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

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

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

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

Введение

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

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

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

(1)

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

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

(2)

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

(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

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

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

(4)

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

(5)

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

(6)

где

(7)

$\frac{N}{2}$ -точечные ДПФ прореженных последовательностей s_0(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$ :

(8)

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

(9)

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

(10)

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

(11)

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

(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$ , в результирующее -точечное ДПФ S(k) , $k= 0 \ldots N-1$ , исходного сигнала.

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

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

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

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

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

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

Выражение (12) представляет собой процедуру объединения для расчета точечного ДПФ 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 этап деления последовательности на «четную» и «нечетную» и после этого производить объединение спектра за этапов.

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

В качестве примера на рисунке 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) .

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

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

(13)

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

(14)

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

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

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

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