Лабораторная работа № 6_16 Быстрое преобразование Фурье (БПФ) 1. Цель работы Целью работы является: 1. Изучить алгоритм БПФ с прореживанием по времени. 2. Получить навыки по составлению программ с использованием БПФ. 2. Быстрое преобразование Фурье (БПФ) БПФ существенно сокращает время частотного анализа. Чтобы убедиться в этом, запишем формулу - точечного ДПФ . (1) Рассмотрим алгоритм БПФ с прореживанием по времени. Пусть N-четное число. Представим сумму ряда (1) в виде суммы двух рядов, в первый из которых войдут элементы с четными номерами n, а во второй – с нечетными номерами n . (2) Введем обозначения и , а также вынесем из второй суммы общий множитель . (3) Обозначим сумму с четными номерами через , а с нечетными - . С учетом принятых обозначений выражения (3) запишется в комплексной форме . (4) Так как n изменяется от 0 до , то выражения (3) и (4) позволяют определить только составляющих Фурье. Для остальных n () следует воспользоваться периодичностью спектра дискретного сигнала и, следовательно, периодичностью ДПФ. Для определения ДПФ во второй части спектра, рассмотрим выражение (3) для отсчетов . (5) Введем стандартные обозначения и упростим соотношение (5)
. (6) С учетом преобразований (6) и введенных обозначений, выражение (3) и (4) принимает компактный вид:
В развернутой форме вид вышеприведенных выражений усложняется: . (7) . (8) Для того, чтобы вычислить составляющие спектра от 0 до необходимо выполнить два - точечных ДПФ, а затем использовать уже полученные результаты для вычисления последующих отсчетов. Формула (8) определяет составляющие спектра для последующих значений . При этом нет нужды выполнять умножения входной последовательности на синусы и косинусы. Для этого следует воспользоваться результатом формулы (7), а затем изменить знак в множителе . В самом деле, и могут быть вычислены прямым методом с помощью операций каждая, а, соединив их, определяем , которое потребует дополнительно только операций, что в сумме составляет операций (под операциями понимается комплексное сложение и умножение). Но при прямом вычислении потребуется операций. Поэтому соотношения (7) и (8) значительно сокращают время вычислений. Соотношения между , и изображены на рис.1. С помощью сигнального графа, который иллюстрирует сведения восьмиточечного ДПФ к двум четырехточечным. Основой построения графа являются точки (окружности) и стрелки (линии передач). Окружности выполняют алгебраические операции выражений (7) и (8), стрелки – умножение на поворачивающий множитель . Таким образом, один выход окружности будет определяться выражением (7) (определять спектральные составляющие анализируемого сигнала от 0 до ), а второй выход окружности – выражением (8) (определяет спектральные составляющие анализируемого сигнала от до ).
Рис.1. Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ. Данная операция получила название «бабочки». Расшифровка ее структуры представлена на рис. 2
Рис.2. Элемент схемы, используемый в БПФ (А – условное обозначение; В – структурная схема). Применение вместо одного 8-точечного ДПФ двух 4-точечных ДПФ сократило объем вычислений. В свою очередь каждое из 4-точечных ДПФ может быть получена из двух 2-точечного ДПФ.
Рис.3. Бабочка для элементарного 2-точечного ДПФ. Таким образом, ДПФ 2-точечной последовательности является элементарным блоком (рис.3), в котором поворачивающие множители принимают единичные значения Количество отсчетов входного сигнала выбирают так, чтобы имелась возможность путем последовательного деления на 2 получить элементарный блок (рис. 3). В этом случае алгоритм БПФ позволяет ускорить вычисление в 100 и более раз по сравнению с методом прямого вычисления ДПФ. Поэтому если число отсчетов не определяется выражением , то входную последовательность либо усекают, либо добавляют нулями. В Matlab этот прием выполняется по умолчанию. Если количество отсчетов простое число, то алгоритм БПФ не может быть применен и тогда спектр вычисляется только по прямой формуле ДПФ. Вычисление восьмиточечного ДПФ с помощью двух 4-точечных ДПФ выполнено в Программе 1 Программа 1 (fur. Bpf_01.m). 0 N=8; n1=0:1:7; t=1/8000; x=sin(2*pi*1000*n1*t)+0.5*sin(2*pi*2000*n1*t+3*pi/4) y=fft(x) figure(1) stem(n1,abs(y)),grid on n=0:2:6; x1=sin(2*pi*1000*n*t)+0.5*sin(2*pi*2000*n*t+3*pi/4); y1=fft(x1) n=1:2:7; x2=sin(2*pi*1000*n*t)+0.5*sin(2*pi*2000*n*t+3*pi/4); y2=fft(x2) w=[0,0.7071-j*0.7071,-j,-0.7071-j*0.7071] r=y2.*w X1=y1+r X2=y1-r X=[X1,X2] figure(2) stem(n1,abs(X)),grid on Программа состоит из 4 блоков. В первом блоке вычисляется по прямой формуле. Во втором блоке вычисляется ДПФ для составляющих последовательности с четными номерами n, а в третьем блоке – с нечетными номерами n. В четвертом блоке определяются все составляющие спектра по выражениям (7) и (8). Причем, предварительно вычисляется вектор комплексного поворачивающего множителя , где m=0, …, . Результаты выполнения Программы 1 представлены на рис. 4.
Рис.4. Спектр входной последовательности (1 – прямой метод ДПФ; 2- алгоритм БПФ). Идентичность графиков указывает, что БПФ не является приближенным алгоритмом. При отсутствии вычислительной погрешности он дает такой же результат как и прямой метод ДПФ. Ускорение достигается исключительно за счет оптимизации вычислений. 3. Домашнее задание Повторить материал по непрерывному и дискретному преобразованию Фурье. Изучить БПФ. Написать программы по определению дискретных спектров с использованием ДПФ и БПФ. 4. Порядок выполнения работы Лабораторная работа выполняется на персональной ЭВМ с использованием пакета MatLab. Порядок выполнения следующий: По заданным входным сигналам , , , заданной частоте дискретизации и заданному количеству отсчетов (таб.1) написать программу ДПФ прямым методом. Получить в результате выполнения программы амплитудный спектр и проанализировать его. В соответствии с таб. 2 написать программу БПФ, в которой - точечная последовательность представлена в виде двух - точечных последовательностей (при усложнении задания размерность блоков можно уменьшать). Получить в результате выполнения БПФ амплитудный спектр. Сравнить амплитудный спектр, полученный прямым ДПФ, со спектром БПФ и сделать выводы. 5. Содержание отчета 1. Наименование и цель лабораторной работы. 2. Краткая характеристика ДПФ и БПФ. 3. Листинги программ по определению дискретных спектров. 4. Краткая характеристика и описания синтаксиса команд, используемых при определении спектров. 5. Анализ графиков. 6. Выводы. 6. Контрольные вопросы Написать формулу прямого непрерывного преобразования Фурье и сделать пояснения. Написать формулу обратного непрерывного преобразования Фурье и сделать пояснения. Указать связи между различными формами представления спектра: через амплитуду и фазу, через действительные и мнимые составляющие. Написать формулу прямого дискретного преобразования Фурье и сделать пояснения. Написать формулу обратного дискретного преобразования Фурье и сделать пояснения. Записать формулы БПФ. Пояснить сущность БПФ. Вывести формулы для объединения спектров двух прореженных во времени числовых последовательностей. Пояснить суть поворачивающего множителя. Нарисовать граф и пояснить порядок вычислений при сравнении восьмиточечного ДПФ к двум четырехточечным. Нарисовать граф и пояснить порядок вычислений при сравнении восьмиточечного ДПФ к четырем двухточечным. Написать программу для определения спектра ДПФ прямым методом. Написать программу БПФ, в которой 8 точечная последовательность вычисляется через две четырехточечные последовательности. Написать программу БПФ, в которой 16 точечная последовательность вычисляется через две восьмиточечные последовательности. Написать формулу для преобразования непрерывного сигнала из временной области в частотную и обратно. Написать формулу для преобразования дискретного сигнала из временной области в частотную и обратно. Докажите возможность сокращения времени определения спектральных составляющих сигналов при применении БПФ. Почему, если последовательность простое число, нельзя применить БПФ? Изобразите граф, реализующий операцию «бабочка». Какой вид принимает этот граф для элементарного двухточечного ДПФ? Какие положения ДПФ используются в БПФ, позволяющие сократить время вычислений? Каким требованиям должна удовлетворять входная последовательность, чтобы БПФ было наиболее эффективным. 7. Исходные данные для выполнения лабораторной работы Таблица 1
Гц
Гц
Гц
Гц
Фазовый сдвиг
1 1000 2000 4000 16 16000 2 4 5 - - -
2 500 2500 5000 32 16000 3 5 10 45 90 -
3 1000 3000 6000 64 16000 0,5 1 5 120 180 90
4 2000 4000 6000 128 16000 3 0,5 5 45 45 90
5 1000 2000 3000 8 8000 4 2 1 - 45 120
6 2000 3000 6000 16 16000 3 0,5 10 120 - -
7 1000 4000 8000 32 32000 4 0,5 2 - 120 -
8 10000 20000 40000 64 64000 1 5 10 - 120 45
9 312,5 625 1562,5 32 10000 5 2 1 - 150 45
10 1250 2500 5000 32 20000 0,5 1 5 - 150 120
11 937,5 2812,5 5625 32 30000 2 0,1 4 - 45 90
12 1250 3750 11250 32 40000 2 1 2 90 -45 -45
13 1562,5 3125 6250 32 50000 4 0,5 1 15 -30 -45
14 625 1875 3750 16 10000 3 2 1 30 30 45
15 1250 2500 5000 16 20000 1 2 3 30 45 120
16 1875 3750 7500 16 30000 5 10 20 30 90 150
17 2500 4000 8000 16 40000 1 4 5 120 -60 -
18 3125 6250 12500 16 50000 0,5 2 5 30 -45 100
Таблица 2 N/N Число отсчетов N БПФ (вар. 1) БПФ(вар. 2)
