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

Содержание

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

(4)

Если рассмотреть только первую половину ДПФ для индексов , а также учесть, что

(5)
то (4) преобразуется к виду:
(6)
где
(7)
-точечные ДПФ прореженных последовательностей и , соответственно.

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

Проанализируем теперь вторую половину ДПФ для :

(8)

Рассмотрим более подробно поворотные коэффициенты

(9)

Аналогично можно упростить :

(10)

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

(11)

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

(12)

Граф «бабочка»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По аналогичному правилу поменяются местами все отсчеты, при этом некоторые останутся на месте, в частности , так как если переписать справа налево, то все равно останется , аналогично , и .

Важно отметить, что данный метод перенумерации должен применяться при записи числа в двоичной системе, состоящей из разрядов. В приведенном примере использовалось 3 разряда двоичного числа, но если бы было равно 16, то необходимо было записать число при использовании 4 разрядов. В этом случае и после перестановки получим , то есть при , отсчет не останется на месте, а поменяется местами с .

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

(13)

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

(14)

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

(15)

Выводы

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

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

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

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

Список литературы
[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 с.

Последнее изменение страницы: 22.10.2020 (19:50:59)