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

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.

Похожие работы

Дискретизация и квантование изображений

Скачать

133819

3

0

... учесть введением в блок-схему дополнительного .источника шума [11]. Расстояние между отсчетами должно удовлетворять теореме Найквиста для двумерных колебаний [1]. Устройства для дискретизации и квантования изображений основаны на технике микроденситометрии. В подобных системах на пленку проектируется луч света с интенсивностью I1. Интенсивность I2 света, прошедшего сквозь пленку (или отраженного ...

Цифровая обработка сигналов

Скачать

37777

1

2

... Интересным примером применения спецпроцессора СПФ СМ явилась обработка радиолокационных сигналов зондирования поверхности планеты Венера, которое проводилось со спутника. Глава 3. Применение цифровой обработки сигналов. 3.1 Шумоподавление для звука Звуковой сигнал, записываемый в реальных акустических условиях, часто содержит нежелательные шумы, которые могут порождаться окружающей средой ...

Запись голоса через микрофон на компьютер

Скачать

168346

1

36

... , расположенной напротив одного из ушей, к точке, расположенной перед человеком. Дилэй применяется, прежде всего, в том случае, когда запись голоса или акустического музыкального инструмента, выполненную с помощью единственного микрофона, встраивают в стереофоническую композицию. Этот эффект служит основой технологии создания стереозаписей. Подробные рекомендации по применению задержки в этих ...

Сигналы и их характеристика

Скачать

59427

2

0

... построения оптических систем и сетей связи В результате изучения данной дисциплины студент должен: знать: принципы построения инфокоммуникационных сетей (ПК-1); основные характеристики первичных сигналов связи (ПК-3); принципы построения проводных и радиосистем передачи с частотным и временным разделением каналов (ПК-1); основные характеристики каналов и трактов (ПК-3); принципы построения ...