Лабораторная работа №6 16 Быстрое преобразование Фурье (бпф) Цель работы Целью работы является



Скачать 185,86 Kb.
Дата22.10.2016
Размер185,86 Kb.
ТипЛабораторная работа

http://antibotan.com/ - Всеукраїнський студентський архів

Лабораторная работа № 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. Домашнее задание

  1. Повторить материал по непрерывному и дискретному преобразованию Фурье.

  2. Изучить БПФ.

  3. Написать программы по определению дискретных спектров с использованием ДПФ и БПФ.


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

Лабораторная работа выполняется на персональной ЭВМ с использованием пакета MatLab. Порядок выполнения следующий:



  1. По заданным входным сигналам , , , заданной частоте дискретизации и заданному количеству отсчетов (таб.1) написать программу ДПФ прямым методом.

  2. Получить в результате выполнения программы амплитудный спектр и проанализировать его.

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

  4. Получить в результате выполнения БПФ амплитудный спектр.

  5. Сравнить амплитудный спектр, полученный прямым ДПФ, со спектром БПФ и сделать выводы.


5. Содержание отчета

1. Наименование и цель лабораторной работы.

2. Краткая характеристика ДПФ и БПФ.

3. Листинги программ по определению дискретных спектров.

4. Краткая характеристика и описания синтаксиса команд, используемых при определении спектров.

5. Анализ графиков.

6. Выводы.
6. Контрольные вопросы


  1. Написать формулу прямого непрерывного преобразования Фурье и сделать пояснения.

  2. Написать формулу обратного непрерывного преобразования Фурье и сделать пояснения.

  3. Указать связи между различными формами представления спектра: через амплитуду и фазу, через действительные и мнимые составляющие.

  4. Написать формулу прямого дискретного преобразования Фурье и сделать пояснения.

  5. Написать формулу обратного дискретного преобразования Фурье и сделать пояснения.

  6. Записать формулы БПФ.

  7. Пояснить сущность БПФ.

  8. Вывести формулы для объединения спектров двух прореженных во времени числовых последовательностей.

  9. Пояснить суть поворачивающего множителя.

  10. Нарисовать граф и пояснить порядок вычислений при сравнении восьмиточечного ДПФ к двум четырехточечным.

  11. Нарисовать граф и пояснить порядок вычислений при сравнении восьмиточечного ДПФ к четырем двухточечным.

  12. Написать программу для определения спектра ДПФ прямым методом.

  13. Написать программу БПФ, в которой 8 точечная последовательность вычисляется через две четырехточечные последовательности.

  14. Написать программу БПФ, в которой 16 точечная последовательность вычисляется через две восьмиточечные последовательности.

  15. Написать формулу для преобразования непрерывного сигнала из временной области в частотную и обратно.

  16. Написать формулу для преобразования дискретного сигнала из временной области в частотную и обратно.

  17. Докажите возможность сокращения времени определения спектральных составляющих сигналов при применении БПФ.

  18. Почему, если последовательность простое число, нельзя применить БПФ?

  19. Изобразите граф, реализующий операцию «бабочка». Какой вид принимает этот граф для элементарного двухточечного ДПФ?

  20. Какие положения ДПФ используются в БПФ, позволяющие сократить время вычислений?

  21. Каким требованиям должна удовлетворять входная последовательность, чтобы БПФ было наиболее эффективным.


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)

1

16





2

32





3

64





4

128





5

8





6

16





7

32





8

64





9

32





10

32





11

32





12

32





13

32





14

16





15

16





16

16





17

16





18

16







Каталог: data -> ukr
data -> Сборник «В поисках смыслов: успешные практики патриотического воспитания молодежи»
data -> 1. Технические спецификации как средство ограничения конкуренции на рынке государственных закупок
data -> Программа дисциплины Системы управления проектами для направления 080100. 62
data -> Лабораторная работа №1 Разработка описания и анализ информационной системы
data -> Программа дисциплины Подготовка многостраничного текста эссе и его презентация на компьютере для направления 080100. 62
data -> Использование облачных технологий Google в проектЕ «Scotland» по английскому языку
data -> Проект программы дисциплины
ukr -> Матеріал з Вікіпедії вільної енциклопедії


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал