Быстрое преобразование Фурье (Лабораторная работа № 2), страница 2

На всех этапах выполнения БПФ используются коэффициенты W_N^k, k=0,1,...N–1. Обычно указанные коэффициенты вычисляют до выполнения БПФ и хранят в таблице, к которой можно обращаться в процессе счета.

Количество этапов БПФ равно , количество "бабочек" на каждом этапе – N/2. Так как в процессе БПФ используются комплексные числа, то каждая «бабочка» БПФ сопровождается четырьмя операциями умножения и сложения. Поэтому количество парных операций умножение–сложение равно . При больших N применение алгоритма БПФ существенно сокращает количество операций, требуемых для вычисления ДПФ.

Процедура перестановки входных значений (прореживание по времени) – битинверсия в MathCad может выглядеть следующим образом:

В этой подпрограмме в качестве массива X выступают действительные части значений выборки сигнала, а в качестве Y – мнимые, которые просто обнуляются, т.к. исходный сигнал представлен действительной последовательностью. Алгоритм БПФ рассчитан на комплексный входной сигнал и при наличии мнимых частей функцию Swap() необходимо было бы применить и для массива Y.

Порядок выполнения работы

Данная работа выполняется на ПЭВМ с использованием программы MathCAD 2000. В первой части работы необходимо реализовать операцию «бабочка». Во второй – используя «бабочку» получить БПФ для 32 точечной измеренной последовательности.

1.  Считать с диска с помощью функции READ отсчеты измеренного сигнала.

2.  Построить график полученного сигнала: меню Вставка > График > X-Y зависимость

Используя формулы, приведенные в теоретической части, найти Быстрое преобразование Фурье по алгоритму с прореживанием по времени. Необходимо учесть, что исходная последовательность действительная, результат – комплексная.

3.  Выполнить перестановку входных значений (используя подпрограмму).

4.  Коэффициенты W_N^k при реализации алгоритма можно представить в виде действительной (cos) и мнимой (sin) частей и хранить их в разных ячейках (переменных). Аналогично нужно представлять входную последовательность X (с нулевыми мнимыми частями Y), выходную и промежуточные результаты.

5.  Расписать базовую операцию – бабочку, выделить в результате действительную и мнимую части и хранить их отдельно.

6.  БПФ выполняется в несколько этапов. На первом этапе (после сортировки) L=1 или L =2⁰ используется двухточечное БПФ (т.е. в каждом домене количество точек M=2, а k в домене изменяется от 0 до M/2-1=0). Количество бабочек на домен- 1 (L) или иначе – половина точек домена. Если за базовую точку принять верхнюю с индексом k, то пару ей в бабочке составит точка с индексом k+ M/2. Количество доменов равно N/M.

7.  На втором этапе L=2*L или L =2¹ используется четырехточечное БПФ т.е. в каждом домене количество точек M=4, а k в домене изменяется от 0 до M/2-1=1). Количество бабочек на домен- 2 (L). Количество доменов также равно N/M. И т.д.

8.  Легко заметить, что абсолютный номер точки входного массива складывается из k – номера бабочки в домене и i*M, где i – номер домена, изменяется от 0 до (N/M)-1. Переход в новый домен осуществляется или увеличением i на 1, или вводом переменной I с начальным значением равным 0 путем ее увеличения на M. При переходе переменная k обнуляется (начинается новый цикл).

9.  Определить закономерности в изменении индексов ячеек (элементов массива), участвующих в бабочке, индексов верхних элементов бабочки, переменной k – степени в W и нижнего индекса W (точечность БПФ) в зависимости от этапа БПФ.

10.  Разработать программный блок.

11.  Найти модуль спектральных коэффициентов (т.к. в результате выполнения программного блока будет два массива – действительные и мнимые части).

12.  С помощью команды WRITE записать результаты на диск, например WRITE(d:\stud\3381\result_2_ номер бригады.prn):=G_j .

13.  Используя встроенную функцию fft, построить график, на котором должны быть результаты работы программы и встроенной функции fft.

Оформление отчета

В отчете необходимо представить программу БПФ выполненную в MathCAD и график совмещенных результатов БПФ, выполненных с использованием программы и встроенной функции fft.