Обратное преобразование Фурье аналогового сигнала определяется соотношением Главная страница сайта Об авторах сайта Контакты сайта

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


.

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

(4.2)

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

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

Примем F Tc = 1.

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

Тогда

(4.3)

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

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

Поэтому и Sk представляет собой периодическую функцию с периодом 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. Алгоритм быстрого преобразования Фурье с прореживанием во

времени

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

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

Индексы членов последовательностей xn и x1m связаны соотношением n = 2m, а индексы членов последовательностей xn и x2m - соотношением 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. На нем показано, как из двух четырехточечных последовательностей формируется од-

на восьмиточечная. Стрелочками представлены множители , на которые умножаются отсчеты S20 , S21 , S22 , S23 соответственно. Отсчеты S0 , S1 , S2, S3 получаются с использованием операции сложения, поэтому около них стоит знак “ + “, отсчеты S4 , S5 , S6 , S7 находятся после выполнения операции вычитания и около них поставлен знак “ - “.



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

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

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

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

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

Таблица 4.1

Номер шага разбиения Количество умножений на постоянный коэффициент Количество блоков ДПФ, подлежащих дальнейшему разбиению Вид последовательности на входах оставшихся блоков
N / 2 N / 2
2 ( N / 4 ) = N / 2 N / 4
4 ( N / 8 ) = N / 2 N / 8
. . . . . . . . . . . .
M -1 N / 2 2 M -1 N / 2 M -1 = 2
M N / 2 - -

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

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

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

частоте

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

Загрузка...

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

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

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

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

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

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

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

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

.


Другие страницы сайта


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

5 stars - based on 220 reviews 5
  • I. Звук, его характеристика.
  • Неправильная атака
  • Конкретные классы коллекций
  • ГЛАВА II. КУЛЬТУРА РЕЧИ
  • Стартовая актуализация жизненного (витагенного) опыта
  • Глава 7 Источник жизненного (витагенного) опыта
  • Исходные данные для расчета уровней и динамики
  • Без проведения целевого инструктажа допуск к работе не разрешается.