Обратное преобразование Фурье аналогового сигнала определяется соотношением

Подставив (6.2) в (6.1), получим

(4.2)

Зададимся шагом W изменения частоты w = k W , где k - целое число

Учитывая, что T_Д = T_c / N , получим W T_Д = 2 p F T_c / N.

Примем F T_c = 1.

Введем обозначение:

Тогда

(4.3)

Докажем, что функция является периодической по k с периодом, равным N.

Действительно,

Поэтому и S_k представляет собой периодическую функцию с периодом N. Следовательно, k = 0,1,2,.. N-1.

4.2. Обратное дискретное преобразование Фурье

Обратное преобразование Фурье аналогового сигнала определяется соотношением

(4.4)

Выражение для обратного преобразования (4.4) отличается от выражения для прямого преобразования (4.1) знаком в показателе экспоненты и постоянным сомножителем перед знаком интеграла.

По аналогии с (4.4) и (4.1) , учитывая (4.3), запишем выражение для обратного ДПФ

(4.5)

где а – неизвестная константа.

Для определения константы a подставим (4.3) в (4.5), предварительно заменив в (4.3) индекс суммирования n на m

При m = n имеем

При m ¹ n рассматриваемая сумма представляет собой сумму членов геометрической прогрессии, у которой первый член равен единице, последний , а знаменатель -

Поэтому при m ¹ n

В результате получим , следовательно, .

Таким образом , (4.6)

Из (4.3) и (4.6) следует, что для определения всех N отсчетов спектра по (4.3) или N отсчетов временной функции по (4.6) требуется выполнить комплексных умножений

и столько же комплексных сложений. При N больше 1000 это прямое вычисление требует больших затрат машинного времени. Поэтому возникла необходимость в разработке алгоритмов быстрого преобразования Фурье (БПФ), позволяющих уменьшить число арифметических операций.

Лекция №12

4.3. Алгоритм быстрого преобразования Фурье с прореживанием во

времени

Рассмотрим последовательность x_n , содержащую отсчётов, где M - целое число (рисунок 4.2). Разобьем члены этой последовательности на две группы. В первую

включим члены исходной последовательности с нулевым и четными индексами, во вторую - члены с нечетными индексами. Из первой группы образуем последовательность x1_m, а из второй - последовательность x2_m.

Индексы членов последовательностей x_n и x1_m связаны соотношением n = 2m, а индексы членов последовательностей x_n и x2_m - соотношением n = 2m + 1.

Рисунок 4.2 – Разбиение последовательности отсчетов x на две последовательности

x1 и x2, содержащие члены исходной последовательности x с четными

и нечетными индексами соответственно

Тогда выражение для прямого ДПФ (6.3) можно представить в виде

Учитывая, что , получим

.

Обозначим - прямое ДПФ последовательности x1 и

- прямое ДПФ последовательности x2,

где .

Учтем также, что , а .

Поэтому

при i = 0, 1, 2, .. N / 2 - 1 и k = i,

при i = 0, 1, 2, .. N / 2 - 1 и k = i+N / 2. (4.7)

Графическое представление вычислительных операций (4.7) приведено на рисунке 4.3. На нем показано, как из двух четырехточечных последовательностей формируется од-

на восьмиточечная. Стрелочками представлены множители , на которые умножаются отсчеты S2₀ , S2₁ , S2₂ , S2₃ соответственно. Отсчеты S₀ , S₁ , S₂, S₃ получаются с использованием операции сложения, поэтому около них стоит знак “ + “, отсчеты S₄ , S₅ , S₆ , S₇ находятся после выполнения операции вычитания и около них поставлен знак “ - “.

Описанная часть рисунка напоминает развернутые крылья бабочки, поэтому“ бабочкой “ называется данная операция БПФ. В виде таких же бабочек можно развернуть показанные на рисунке блоки ДПФ. Из каждого блока ДПФ получается своя бабочка и два двухточечных блока ДПФ, каждый из которых представляется своей бабочкой. Двухточечные блоки ДПФ дальнейшего разбиения не требуют.

Рисунок 4.3 - Формирование отсчетов спектра восьмиточечной последовательности

из отсчетов спектров двух четырехточечных последовательностей с

использованием прореживания во времени

Подсчитаем количество операций умножения, которые нужно выполнить, используя алгоритм БПФ. Для этого составим таблицу 4.1.

Таблица 4.1

Из таблицы видно, что на каждом шаге разбиения выполняется N / 2 умножений, а количество шагов равно M = log ₂ N. Следовательно, количество умножений равно

(N / 2) log₂ N вместо N² при ДПФ. Величина выигрыша при переходе от ДПФ к БПФ увеличивается с увеличением количества отсчетов N.

4.4. Алгоритм быстрого преобразования Фурье с прореживанием по

частоте

Вместо изложенной процедуры разбиения множества объектов на объекты с четны-

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

Пусть имеется исходная N - точечная последовательность x_n , где N = 2^M (рисунок 6.4). Разобьем члены этой последовательности на две группы. В первую включим первую половину членов исходной последовательности, а во вторую группу - вторую половину. Из первой группы образуем последовательность x1_m , а из второй - последовательность x2_m.

Рисунок 4.4 - Разбиение последовательности отсчетов x на две последовательности

x1 и x2, содержащие первую и вторую половину членов исходной

последовательности соответственно

Индексы последовательностей x_n и x1_m связаны соотношением n = m, а индексы по-

следовательностей x_n и x2_m - соотношением n = N/ 2 + m.

Тогда выражение для прямого ДПФ (6.3) можно представить в виде

.