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

Введение
В предыдущих разделах мы рассмотрели ДПФ и его свойства, а также показали принцип построения алгоритмов быстрого преобразования Фурье (БПФ) на основе процедуры разделения-объединения.
В данном разделе мы рассмотрим один из наиболее распространенных алгоритмов БПФ: БПФ по основанию два с прореживанием по времени.
Приведем еще раз выражение для ДПФ:
(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] Cooley James W. and Tukey John W. An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 1965 p. 297–301.

[2] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Мир, 1989.

[3] Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Москва, Радио и связь, 1985.

[4] Оппенгейм А., Шафер Р. Цифровая обработка сигналов. Москва, Техносфера, 2006.

[5] Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов. Москва, Радио и связь, 1985.

[6] Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. Москва, Мир, 1978.

[7] Сергиенко А.Б. Цифровая обработка сигналов. Санкт-Петербург, Питер, 2002.