2. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ

Пусть требуется вычислить ДПФ (1.1) при N=2^v, где v>O. где v>O целое (если N 2V, то можно последовательность х(пТ) дополнить в конце нулевыми элементами так, чтобы длина результирующей последовательности была степенью 2).

Разобьем исходную N-точечную последовательность х(пТ)=х_v (п), где v =log₂ N. п=О...., N -1, на две (N/2)-точечные последовательности Х_v-1,0(п) и Х_v-1,1 (п), состоящие соответственно из четных и нечетных членов х (пТ), т. е.

(2.1)

При этом N-точечное ДПФ (1.1) можно записать в виде

(2.2)

Учитывая, что получаем

(2.3)

Где и - (N/2)-точечные ДПФ соответственно последовательностей и :

; .

Так как X_v (k) должно быть определено для N точек (k=0, 1,..., N-1), а Х_v-1,0(k) и Х_v-1,1(k) определяются толькo для N/2 точек (k=0, 1,..., N/2-1), доопределим (2.3) для значений k=N/2, N/2+1,...,N-1; учитывая, что Х_v-1,0(k) и Х_v-1,1(k)периодические функции с периодом Н/2, можно записать

X_v (k+N/2)= Х_v-1,0 (k+N/2) + Х_v-1,1 (k+N/2)= Х_v-1,0 (k)- Х_v-1,1 (k),

(2.4)

Так как = = -1.

Формулы (2.3) и (3.4) дают алгоритм вычисления N-точечной ДПФ через (N/2)-точечных ДПФ. Этот алгоритм можно представить направленным графом, имеющим вид «бабочки»

Рисунок 3 - граф имеющий вид «бабочки»

(рис.3, а), в котором выходные числа с и d получаются из входных чисел а и b по правилам

(2.5)

В качестве примера граф на рис.3, б представляет операции (2.3) и (2.4). Аналогично можно теперь выразить (N/2)-точечные ДПФ Х_v-1,0 (k) и Х_v-1,1(k) через (N/4)-точечные ДПФ:

(2.6а)

И

(2.7б)

где Х_v-2,0(k) и Х_v-2,1(k) - соответственно (N/4)-точечные ДПФ четных Х_v-2,0(n) и нечетных Х_v-2,1(п)

членов последовательности Х_v-1,0 (п), а Х_v-2,2(k) и Х_v-2,3 (k)-соответственно (N/4)-точечные ДПФ четных Х_v-2,2 (п) и нечетных Х_v-2,3 (п) членов последовательности Х_v-1,1(п).

Процесс уменьшения размера ДПФ от М до M/2, где М равна степени 2, продолжается до тех пор, пока на v-м шаге (v = log₂ N, где N-исходный размер ДПФ) не окажутся только 2-точечные ДПФ Ф(k), k=0,1, для двухточечных последовательностей (п), п = 0,1, определяемые из соотношений

(2.8)

Последние вычисляются без операции умножения.

Пример 1. Построим алгоритм БПФ с прореживанием по времени для N=8=2³, v=3, т. е. для последовательности х(пТ), п=0,1,2,З,4.5,6,7. Разобьем согласно (2.1) исходную последовательность х (пТ) = х₃ (п) на две последовательности: x_2,0 (п) и х_2,1(n),-состоящие соответственно из четных и нечетных членов х₃ (п):

(2.9)

Рисунок 4 - Алгоритм 8-точечного БПФ

Теперь вновь разобьем последовательности (2.9) на последовательности из нечетных и четных членов последовательностей (2.9):

(2.10)

Последовательности (2.10) являются уже двухточечными.

Теперь, используя алгоритм, представленный графом «бабочка» (см. рис.3, а), строим алгоритм 8-точечного БПФ (рис.4). Вначале построим исходный массив. Как видно из (2.10), он из элементов последовательности х(n)=х(nТ), n=0,1... 7, причем на входах первого графа «бабочка» первой ступени помещаются числа х(0) и х(4). На входах второго графа «бабочка» -числа х(2) и х(6), на входах третьей «бабочки» - х(l) и х(5) и на входах четвертой «бабочки» - x(3) и x (7).

Таким образом, если предположить, что последовательность Х(п) записывается в массив ячеек памяти, то удобно осуществить размещение х(п) в следующем порядке (рис.2): х(0), х(4), Х(2), х(6), х(1), х(5), х(3), х(7). Легко заметить, что элементы этой последовательности получаются из исходной х(п) в соотnетствии с двоичной инверсией номеров, т. е. число х(п) с номером в двоичном представлении п=(п_v-1,..., n₀) запоминается в ячейке памяти с номером =(n_0,..., п_v-1). Так, число х(4) с номером в двоичном представлении 4₍₁₀₎ = 100₍₂₎ запоминается в ячейке с номером 001₍₂₎=1₍₁₀₎, а число х(3), где 3₍₁₀₎ =011₍₂₎, запоминается в ячейке с номером 110_(з) =6₍₁₀₎ и т. д. Итак, можно считать, что начальная ступень преобразования Х₀ (k), k=0,I... 7, получатся просто в результате прореживания (в указанном смысле) исходной временной последовательности х(пТ), п=0, I...7, т. е Х₀ (k) = х (T), где k = - двоично-инверсное представление номера п.

На выходах N/2 = 4 «бабочек» т=l-й ступени образовываются значения Х₂(k), являющиеся входными числами «бабочек» т=2-й ступени. На выходах последней значения выходной последовательности Х_З (k)=X(k), k=0... 7. Выходная последовательность X(k), k=0,1...7, получается в естественном порядке следования.

Как показано в рассмотренном примере, все входные числа «бабочек» Х₀ (k) на начальной ступени являются элементами заданной последовательности х(п), п=0... N-1, причем получаются из х(п) в соответствии с двоичной инверсией номеров т. е. число х(пТ)=х(п) с двоичным представлением номера п является входным числом Х₀(k) «бабочки» с номером k, равным инверсному двоичному представлению номера п.

Заметим, что в рассмотренном алгоритме БПФ можно выполнить вычисления по способу с замещением. Если разместить входную последовательность Х ₀(k) «бабочек» в массиве из 2^v ячеек памяти, то после вычисления выходов «бабочек» входные элементы становятся ненужными и в указанные ячейки памяти могут быть записаны вычисленные выходные числа. На следующей ступени вновь вычисленные значения выходов «бабочек» записываются в ячейки массива вместо использованных входных чисел, и в конце вычислений во входном массиве окажутся записанными значения X(k) в естественном порядке, т. е. значения ДПФ при k=0, I, 2... N-1.