Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

БПФ прореживанием по времени





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

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

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

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

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

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

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

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

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

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

__________________________________________________________________

______________________________________________________________________________________________________________________________________________________________________________________________________

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

 

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

Вывод преобразования из ДПФ

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

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

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



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

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

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

 

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

 

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

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

 


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


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

 

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

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

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

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

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

 

БПФ прореживанием по времени

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

(2)

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

(3)

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

 


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





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:



©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.