Отчет по лабораторной работе № 3 «Быстрое преобразование Фурье (БПФ)»
дата	Оценка (max 5)	Бонус за сложность	подпись

Цель работы:

Изучение алгоритма быстрого преобразования Фурье, основ языка программирования С.

Задачи работы

-написать программу на языке С реализующую один из алгоритмов быстрого преобразования Фурье.

Краткий конспект теоретической части

О сновной алгоритм преобраования Фурье сложности О(N²)

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Перечислите виды алгоритмов БПФ

______________________________________________________________________________________________________________________________________________________________________________________________________ Опишите организацию цикла в языке С

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Опишите алгоритм БПФ прореживанием по времени и алгоритм прореживанием по частоте

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

__________________________________________________________________

______________________________________________________________________________________________________________________________________________________________________________________________________

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

1. Теоретические сведения

Быстрое преобразование Фурье (БПФ, FFT) — это быстрый алгоритм вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем N², требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющего сложность O(Nlog(N))

Вывод преобразования из дпф

Дискретное преобразование Фурье для вектора , состоящего из N элементов, имеет вид:

элементы матрицы имеют вид: .

Пусть N четно, тогда ДПФ можно переписать следующим образом:

Коэффициенты и можно переписать следующим образом (M=N/2):

В результате получаем:

То есть дискретное преобразование Фурье от вектора, состоящего из N отсчетов, свелось к линейной композиции двух ДПФ от отсчетов, и если для первоначальной задачи требовалось N² операций, то для полученной композиции — .

Таким образом, можно продолжать разбиение исходной последовательности до тех пор, пока возможно деление последовательности на две. Очевидно, что если  ,   – положительное целое, мы можем разделить последовательность пополам   раз. Для   ( ) такое разбиение представлено на рисунке.

Граф алгоритма БПФ с прореживанием по времени. Двоично-инверсная перестановка

Представим в виде графа алгоритм БПФ с прореживанием по времени основанный на разбиении — объединении при  (рисунок 1).

Рисунок 4: Граф алгоритма БПФ с прореживанием по времени при N=8

Разбиение и объединение последовательностей при N = 8

Так вот, если N является степенью двух, то это разделение можно продолжать рекурсивно до тех пор, пока не дойдем до двух точечного преобразования Фурье, которое вычисляется по следующим формулам:

Каждое разбиение делит последовательность на две половинной длительности (красную и синюю), а каждое объединение «собирает » из двух последовательностей одну удвоенной длительности.

Алгоритмы БПФ, которые используют выборки длиной  , называются «алгоритмами БПФ по основанию 2». Данные алгоритмы получили наибольшее распространение, из-за того что в машинной арифметике   является «круглым» числом.

Очевидно что делить последовательности на две можно по-разному, однако от этого зависит сможем ли мы при объединении получить неискаженный спектр сигнала и чего с точки зрения вычислительных затрат это будет нам стоить. Можно сказать, что эффективность алгоритма БПФ полностью зависит от способа разбиения и объединения последовательности, поскольку если не учитывать операции на разбиение-объединение, то для расчета спектра требуется   раз посчитать ДПФ на 2 точки, в результате общее количество вычислительных операций составит  , то есть количество операций линейно зависит от величины выборки.

Рассмотрим два способа разбиения — объединения: прореживание по времени и прореживание по частоте

Бпф прореживанием по времени

Для начала комплексную экспоненту в выражении (1) обозначим как:

(2)

Тогда выражение (1) принимает вид:

	(3)

Прореживание по времени заключается в разбиении исходной последовательности отсчетов  ,   на две последовательности длительности     и  ,  , таких что  , а ,  . Другими словами, последовательность   содержит отсчеты последовательности   с четными индексами, а   - с нечетными. Прореживание по времени для N = 8 наглядно представлено на рисунке 2.

Рисунок 2: Прореживание по времени для N=8

Процедура объединения. Граф «Бабочка»

Теперь рассмотрим вторую половину спектра  ,  :

	(8)

Рассмотрим подробнее множитель

.	(9)

Учтем что

,	(10)

тогда выражение (10) справедливо для любого целого  , тогда (9) можно записать с учетом (10):

.	(11)

Рассмотрим теперь поворотный коэффициент в (8):

.	(12)

Тогда выражение (8) с учетом (11) и (12) принимает вид:

	(13)

Таким образом, окончательно можно записать:

	(14)

Выражение (14) представляет собой алгоритм объединения при прореживании по времени. Данную процедуру объединения можно представить в виде графа (рисунок 3), который называется «Бабочка».

Рисунок 3: Процедура объединения на основе графа « Бабочка »