_{Лабораторная работа №}2. Алгоритмы быстрого дискретного преобразования Фурье

Цель: Изучение алгоритмов быстрого дискретного преобразования Фурье с прореживанием по частоте и по времени. Программная реализация алгоритмов БПФ для одномерного сигнала.

Программное обеспечение: MS Visual Studio, OpenCV 2.4.0.

Теория

Как отмечалось ранее, для вычисления одного спектрального отсчета требуется операций комплексного умножения и сложения. Таким образом, вычислительная сложность алгоритма ДПФ составляет комплексных умножений и сложений. При этом можно заметить, что если одно ДПФ на отсчетов заменить вычислением двух ДПФ по отсчетов, то это приведет к уменьшению количества операций в 2 раза. Замена -точечного ДПФ двумя -точечными представлено на рисунке 1.

Рис. 1 - Замена N-точечного ДПФ двумя N/2-точечными ДПФ

При этом каждое из – точечных ДПФ также можно вычислить путем замены -точечного ДПФ на два -точечных. В этом случае количество вычислительных операций равно . Таким образом можно продолжать разбиение исходной последовательности до тех пор, пока возможно деление последовательности на две. Очевидно, что если , – положительное целое, мы можем разделить последовательность пополам раз. Для такое разбиение представлено на рисунке 2.

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

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

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

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

Дискретное преобразование Фурье описывается формулой:

, ₍₁₎

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

(2)

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

, ₍₃₎

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

Рис.3 - Прореживание по времени для N=8

Рассмотрим ДПФ сигнала прореженного по времени:

, (4)

где .

Если рассмотреть только первую половину спектра , , а также учесть что

(5)

тогда (4) можно записать:

(6)

где и точечные ДПФ последовательностей четной и нечетной , :

(7)

(8)

Таким образом, прореживание по времени можно считать алгоритмом разбиения последовательности на две половинной длительности. Первая половина объединенного спектра есть сумма спектра четной последовательности и спектра нечетной последовательности, умноженного на коэффициенты , которые носят названия поворотных коэффициентов.

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

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

(9)

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

(10)

Учтем, что

(11)

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

(12)

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

(13)

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

(14)

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

(15)

(16)

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

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

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

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

Рис. 5 - Граф алгоритма БПФ с прореживанием по времени при N=8

На первом этапе отсчеты входного сигнала переставляются местами и исходная последовательность делится на четную и нечетную последовательности (обозначены красными и синими стрелками). Потом четная и нечетная последовательности в свою очередь делятся на четную и нечетную последовательности. При такое деление можно делать раз. В нашем случае . Данная процедура называется двоично-инверсной перестановкой, так можно выполнить перенумерацию отсчетов, переписав номер отсчета в двоичной системе в обратном направлении. Например, имеет индекс в десятичной системе счисления , если же переписать справа налево то получим , то есть после разбиения на четные нечетные перед первой операцией «Бабочка» встанет на место , которая в свою очередь встанет на место . По аналогичному правилу поменяются местами все отсчеты, при этом некоторые останутся на месте, в частности , так как если переписать справа налево, то все равно останется , аналогично . Очень важно понять, что данный метод перенумерации должен применяться при записи числа в двоичной системе, состоящей из разрядов. В приведенном примере использовалось 3 разряда двоичного числа, но если же , то необходимо записать число при использовании 4 разрядов. В этом случае и после переписывания получим , то есть при не останется на месте, а поменяется местами с .

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

После двоично-инверсной перестановки получаем четыре 2-точечных ДПФ:

(17)

На основе четырех 2-точечных ДПФ формируются два 4-точечных ДПФ:

(18)

И на последнем уровне формируется полный спектр входного сигнала.