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

Содержание
Введение
В предыдущих разделах мы рассмотрели ДПФ и его свойства, а также показали принцип построения алгоритмов быстрого преобразования Фурье (БПФ) на основе процедуры разделения-объединения.
В данном разделе мы рассмотрим один из наиболее распространенных алгоритмов БПФ: БПФ по основанию два с прореживанием по времени.
Приведем еще раз выражение для ДПФ:
$$ S(k) = \sum_{n = 0 }^{N-1} s(n) \cdot \exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k\right), \text{ } k = 0 \ldots N-1. $$
(1)
Процедура разделения-объединения была рассмотрена в предыдущем разделе.
Мы будем оперировать с поворотными коэффициентами ДПФ:
$$ W_N^{ k} = \exp \left( -j \cdot \frac{2\pi}{N} \cdot k\right),\text{ } k = 0 \ldots N-1, $$
(2)
как мы уже делали при рассмотрении свойств ДПФ. Тогда выражение (1) с учетом (2) принимает более упрощенный вид:
$$ S(k) = \sum_{n = 0 }^{N-1} s(n) \cdot W_N^{n \cdot k}, \text{ } k = 0 \ldots N-1. $$
(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$
Процедура объединения
Рассмотрим ДПФ прореженного по времени сигнала:
$$ S(k) = \sum_{m = 0}^{\frac{N}{2}-1} s( 2 \cdot m) \cdot W_N^{2 \cdot m \cdot k} + \sum_{m= 0}^{\frac{N}{2}-1} s( 2 \cdot m+1) \cdot W_N^{(2 \cdot m+1) \cdot k} = \\ = \sum_{m= 0}^{\frac{N}{2}-1} s( 2 \cdot m) \cdot W_N^{2 \cdot m \cdot k} + W_N^k \cdot \sum_{m= 0}^{\frac{N}{2}-1} s( 2 \cdot m+1) \cdot W_N^{2 \cdot m \cdot k} , \text{ } k = 0 \ldots N-1. $$
(4)
Если рассмотреть только первую половину ДПФ $S(k)$ для индексов $k = 0 \ldots \frac{N}{2}-1$, а также учесть, что
$$ W_N^{2 \cdot m \cdot k} = \exp \left( -j \cdot \frac{2\pi}{N} \cdot 2 \cdot m \cdot k \right) = \exp \left( -j \cdot \frac{2\pi}{\frac{N}{2}} \cdot m \cdot k \right) = W_{\frac{N}{2}}^{m \cdot k}, $$
(5)
то (4) преобразуется к виду:
$$ S(k) = \sum_{m= 0}^{\frac{N}{2}-1} s( 2 \cdot m) \cdot W_{\frac{N}{2}}^{m \cdot k} + W_N^k \cdot \sum_{m= 0}^{\frac{N}{2}-1} s( 2 \cdot m+1) \cdot W_{\frac{N}{2}}^{m \cdot k} = $$ $$ = S_0(k) + W_N^k \cdot S_1(k), \text{ } k = 0 \ldots \frac{N}{2}-1, $$
(6)
где
$$ S_0(k) = \sum_{m= 0}^{\frac{N}{2}-1} s_0(m) \cdot W_{\frac{N}{2}}^{m \cdot k}, \text{ } k = 0 \ldots \frac{N}{2}-1; $$ $$ S_1(k) = \sum_{m= 0}^{\frac{N}{2}-1} s_1(m) \cdot W_{\frac{N}{2}}^{m \cdot k}, \text{ } k = 0 \ldots \frac{N}{2}-1, $$
(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$:
$$ S\left( k+\frac{N}{2} \right) = \sum_{m= 0}^{\frac{N}{2} - 1} s(2\cdot m) W_{N}^{2\cdot m \cdot \left( k+\frac{N}{2}\right)} + \sum_{m= 0}^{\frac{N}{2} - 1} s(2\cdot m+1) W_{N}^{(2\cdot m + 1) \cdot \left( k+\frac{N}{2}\right)}, \text{ } k = 0 \ldots \frac{N}{2} - 1. $$
(8)
Рассмотрим более подробно поворотные коэффициенты $W_{N}^{2\cdot m \cdot \left( k+\frac{N}{2}\right)}:$
$$ W_{N}^{2\cdot m \cdot \left( k+\frac{N}{2}\right)} = \underbrace{W_{N}^{2\cdot m \cdot k}}_{W_{\frac{N}{2}}^{ m \cdot k}} \cdot W_{N}^{2 \cdot m \cdot \frac{N}{2}} = W_{\frac{N}{2}}^{ m \cdot k} \cdot \underbrace{W_{N}^{ m \cdot N}}_{1} = W_{\frac{N}{2}}^{ m \cdot k}. $$
(9)
Аналогично можно упростить $W_{N}^{(2\cdot m + 1) \cdot \left( k+\frac{N}{2}\right)}$:
$$ W_{N}^{(2\cdot m + 1) \cdot \left( k+\frac{N}{2}\right)} = \underbrace{W_{N}^{2\cdot m \cdot k}}_{W_{\frac{N}{2}}^{m \cdot k}} \underbrace{\cdot W_{N}^{2 \cdot m \cdot \frac{N}{2}}}_{1} \cdot W_{N}^{k} \underbrace{\cdot W_{N}^{\frac{N}{2}}}_{-1} = -W_{N}^{k} \cdot W_{\frac{N}{2}}^{m \cdot k}. $$
(10)
Тогда выражение (8) с учетом (9) и (10) принимает вид:
$$ S\left( k+\frac{N}{2} \right) = \sum_{m= 0}^{\frac{N}{2} - 1} s(2\cdot m) W_{\frac{N}{2}}^{m \cdot k} - W_{N}^{k} \cdot \sum_{m= 0}^{\frac{N}{2} - 1} s(2\cdot m+1) \cdot W_{\frac{N}{2}}^{m \cdot k} = \\ = S_0(k) - W_N^k \cdot S_1(k), \text{ } k = 0 \ldots \frac{N}{2} - 1. $$
(11)
Используя выражение для первой (6) и второй (11) половин ДПФ, окончательно можно записать процедуру объединения как:
\begin{eqnarray} S(k) &=& S_0(k) + W_N^k \cdot S_1(k), \text{ } k = 0 \ldots \frac{N}{2} - 1; \\ S\left(k+\frac{N}{2} \right) &=& S_0(k) - W_N^k \cdot S_1(k), \textrm{ } k = 0 \ldots \frac{N}{2} - 1. \end{eqnarray}
(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-точечных ДПФ:
\begin{eqnarray} S_{00}(0) = s(0) + W_2^0 \cdot s(4);\nonumber \\ S_{00}(1) = s(0) - W_2^0 \cdot s(4);\nonumber \\ \nonumber \\ S_{01}(0) = s(2) + W_2^0 \cdot s(6);\nonumber \\ S_{01}(1) = s(2) - W_2^0 \cdot s(6);\nonumber \\ \\ S_{02}(0) = s(1) + W_2^0 \cdot s(5);\nonumber \\ S_{02}(1) = s(1) - W_2^0 \cdot s(5);\nonumber \\ \nonumber \\ S_{03}(0) = s(3) + W_2^0 \cdot s(7);\nonumber \\ S_{03}(1) = s(3) - W_2^0 \cdot s(7).\nonumber \end{eqnarray}
(13)
На основе четырех 2-точечных ДПФ формируются два 4-точечных ДПФ:
\begin{eqnarray} S_{10}(0) = S_{00}(0) + W_4^0 \cdot S_{01}(0);\nonumber \\ S_{10}(1) = S_{00}(1) + W_4^1 \cdot S_{01}(1);\nonumber \\ S_{10}(2) = S_{00}(0) - W_4^0 \cdot S_{01}(0);\nonumber \\ S_{10}(3) = S_{00}(1) - W_4^1 \cdot S_{01}(1);\nonumber \\ \\ S_{11}(0) = S_{02}(0) + W_4^0 \cdot S_{03}(0);\nonumber \\ S_{11}(1) = S_{02}(1) + W_4^1 \cdot S_{03}(1);\nonumber \\ S_{11}(2) = S_{02}(0) - W_4^0 \cdot S_{03}(0);\nonumber \\ S_{11}(3) = S_{02}(1) - W_4^1 \cdot S_{03}(1).\nonumber \end{eqnarray}
(14)
И на последнем уровне формируется полное ДПФ входного сигнала:
\begin{eqnarray} S(0) = S_{10}(0) + W_8^0 \cdot S_{11}(0);\nonumber \\ S(1) = S_{10}(1) + W_8^1 \cdot S_{11}(1);\nonumber \\ S(2) = S_{10}(2) + W_8^2 \cdot S_{11}(2);\nonumber \\ S(3) = S_{10}(3) + W_8^3 \cdot S_{11}(3);\nonumber \\ S(4) = S_{10}(0) - W_8^0 \cdot S_{11}(0);\nonumber \\ S(5) = S_{10}(1) - W_8^1 \cdot S_{11}(1);\nonumber \\ S(6) = S_{10}(2) - W_8^2 \cdot S_{11}(2);\nonumber \\ S(7) = S_{10}(3) - W_8^3 \cdot S_{11}(3). \end{eqnarray}
(15)
Выводы
В данном разделе мы рассмотрели один из наиболее широко распространенных алгоритмов быстрого преобразования Фурье: алгоритм с прореживанием по времени.
Показана процедура разделения прореживанием по времени и приведена процедура объединения на основе графа «бабочка» согласно выражению (12).
Был приведен полный граф БПФ с прореживанием по времени для $N = 8$.
В следующем разделе мы рассмотрим еще один алгоритм БПФ по основанию два: алгоритм БПФ с прореживанием по частоте.

Ваши комментарии, вопросы и пожелания вы можете оставить на форуме или в гостевой книге.
Список литературы
[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.

Oбнаружили ошибку в тексте? Выделите ее мышкой и нажмите
Описание (необязательно)
Закрыть Х