Реферат: Алгоритм фильтрации, пример на основе БПФ

(2.8)

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

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

\ (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, . .., n0 ) запоминается в ячейке памяти с номером =(n0, . .., пv-1 ). Так, число х(4) с номером в двоичном представлении 4(10) = 100(2) запоминается в ячейке с номером 001(2) =1(10) , а число х(3), где 3(10) =011(2) , запоминается в ячейке с номером 110(з) =6(10) и т. д. Итак, можно считать, что начальная ступень преобразования Х0 (k), k=0,I... 7, получатся просто в результате прореживания (в указанном смысле) исходной временной последовательности х(пТ), п=0, I...7, т. е Х0 (k) = х ( T), где k = - двоично-инверсное представление номера п.

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

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

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


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

Ниже при водится программа вычисления БПФ с прореживанием по времени по способу с замещением и рассматриваются при меры реализации этой программы.

Программа 1 - быстрое преобразование Фурье с основанием два и прореживанием по времени. Программа осуществляет алгоритм БПФ с основанием два и прореживанием по времени комплексной или вещественной последовательности х(п) длиной N отсчетов. Вещественные составляющие отсчетов исходной последовательности записываются в массив А1(N), а мнимые - массив А2(N). В программе для ознакомления с ее работой предусмотрено формирование входной последовательности, соответствующей отсчетам полигармонического сигнала


(3.1)

строки (80-240). При использовании программы для выполнения БПФ произвольной последовательности необходимо заменить строки 80-240, организовав ввод исходной последовательности.


Основными этапами обработки являются: ввод исходных данных (строки 50-240), двоично-инверсная перестановка исходной последовательности (строки 250-350), собственно алгоритм БПФ (строки 360-510), расчет амплитуд и фаз анализируемого сигнала по результатам БПФ (строки 520-590) и вывод результатов (строки 600-690). Пользователю выводятся в виде таблицы значения номера компоненты (гармоники) БПФ, вещественная и мнимая ее составляющие [Аl (1) и А2 (1)], амплитуда и фаза соответствующей гармоники [R (1) и Fl (1) ].

Пример 2. Реализация БПФ вещественного сигнала содержащего три составляющие при значениях параметров: А0 =2, w0 =0 =0, А1 =I, w1 =0,125, 1 =0,7854, А2 =3, w2 =0,3125, 2 =1,57.

В качестве исходных данных последовательно вводятся значения:

N= 16; J=3; А(0)=2; w(0)=0; w1(0)=0; A(1)= 1; w(1)=0,125; w1 (1)=0,7854; А (2)=З; w(2)=0,3125; w1 (2)= 1,57; I 9= 1;

Пример 3. Реализация БПФ комплексного сигнала (3.1), содержащего три составляющие (J =3), при значениях параметров Ak , wk и k таких же, как

К-во Просмотров: 370
Бесплатно скачать Реферат: Алгоритм фильтрации, пример на основе БПФ