ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
«Сибирский государственный аэрокосмический университет
имени академика М.Ф. Решетнева»
(СибГАУ)
УТВЕРЖДАЮ
Заведующий кафедрой
Ф.И.О. (подпись)
« » 2011г.
Кафедра ЭТТ
Реферат
Преобразование Фурье
Проверил:
Филимонов
Выполнил:
ст.группы БТК-92
Батаркин А.А.
Красноярск, 2011г.
Преобразования Фурье.
Преобразование Фурье — операция, сопоставляющая функции вещественной переменной другую функцию вещественной переменной. Эта новая функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами.
Преобразование Фурье общего вида функции f вещественной переменной можно представить интегральным преобразованием:
Преобразование Фурье используется во многих областях науки — в физике, теории чисел, комбинаторике, обработке сигналов, теории вероятностей, статистике, криптографии, акустике, океанологии, оптике, геометрии, и многих других. В обработке сигналов и связанных областях преобразование Фурье обычно рассматривается как декомпозиция сигнала на частоты и амплитуды, то есть, обратимый переход от временного пространства в частотное пространство. Богатые возможности применения основываются на нескольких полезных свойствах преобразования:
Преобразования являются линейными операторами и, с соответствующей нормализацией, также являются унитарными (свойство, известное как теорема Парсеваля или, в более общем случае как теорема Планшереля, или в наиболее общем как дуализм Понтрягина).
Преобразования обратимы, причём обратное преобразование имеет практически такую же форму, как и прямое преобразование.
Синусоидальные базисные функции являются собственными функциями дифференцирования, что означает, что данное представление превращает линейные дифференциальные уравнения с постоянными коэффициентами в обычные алгебраические. (Например, в линейной стационарной системе частота — консервативная величина, поэтому поведение на каждой частоте может решаться независимо.)
По теореме о свёртке, преобразование Фурье превращает сложную операцию свёртки в простое умножение, что означает, что они обеспечивают эффективный способ вычисления основанных на свёртке операций, таких как умножение многочленов и умножение больших чисел.
Разновидности преобразования Фурье
Многомерное преобразование Фурье
Обратное преобразование Фурье
Для обратного
преобразования Фурье можно применять
алгоритм прямого преобразования Фурье
— нужно лишь использовать
вместо
(или применить операцию комплексного
сопряжения в начале к входным данным,
а затем к результату, полученному после
прямого преобразования Фурье) и
окончательный результат поделить на
N.
Общий случай
Общий случай может
быть сведён к предыдущему. Пусть
.
Заметим, что
.
Обозначим
.
Тогда
, если положить
при
.
Таким образом задача
сведена к вычислению свёртки, но это
можно сделать с помощью трёх преобразований
Фурье для 2k элементов. Выполняем прямое
преобразование Фурье для
и
, перемножаем поэлементно результаты
и выполняем обратное преобразование
Фурье.
Вычисления всех
и ci требуют O(N) действий, три преобразования
Фурье требуют O(Nlog(N)) действий, перемножение
результатов преобразований Фурье
требует O(N) действий, вычисление всех
bi зная значения свертки требует O(N)
действий. Итого для дискретного
преобразования Фурье требуется O(Nlog(N))
действий для любого N.
Дискретное преобразование Фурье
Дискретное преобразование Фурье — преобразование конечных последовательностей (комплексных) чисел, которое, как и в непрерывном случае, превращает свёртку в поточечное умножение. Используется в цифровой обработке сигналов и в других ситуациях, где необходимо быстро выполнять свёртку, например, при умножении больших чисел.
Пусть
— последовательность комплексных
чисел. Рассмотрим многочлен
.
Выберем какие-нибудь n точек на комплексной
плоскости
. Теперь многочлену f(t) мы можем сопоставить
новый набор из n чисел:
.
Заметим, что это
преобразование обратимо: для любого
набора чисел
существует единственный многочлен
f(t) степени не выше n − 1 с такими значениями
в
соответственно.
Набор {fk} и называется
дискретным преобразованием Фурье
исходного набора {xk}. В качестве точек
zk обычно выбирают корни n-й степени из
единицы:
.
Такой выбор продиктован тем, что в этом случае обратное преобразование принимает простую форму, а также тем, что вычисление преобразования Фурье может быть выполнено особенно быстро. Так, в то время как вычисление свёртки двух последовательностей длины n напрямую требует порядка n2 операций, переход к их преобразованию Фурье и обратно по быстрому алгоритму может быть выполнен за O(nlogn) операций. Для преобразований Фурье свёртке соответствует покомпонентное умножение, которое требует лишь порядка n операций.
Быстрое преобразование Фурье
Быстрое преобразование Фурье (БПФ) — это быстрый алгоритм вычисления дискретного преобразования Фурье. То есть алгоритм вычисления за количество действий, меньшее чем O(N2), требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющего сложность O(Nlog(N)).
Основной алгоритм
Покажем как выполнить
дискретное преобразование Фурье за
действий при
.
В частности, при N = 2n понадобится
O(Nlog(N)) действий.
Дискретное преобразование
Фурье преобразует набор чисел
в набор чисел
,
такой, что
, где
и
при 0 < k < n. Алгоритм быстрого
преобразования Фурье применим к любым
коммутативным ассоциативным кольцам
с единицей. Чаще всего этот алгоритм
применяют к полю комплексных чисел (c
) и к кольцам вычетов.
Основной шаг алгоритма
состоит в сведении задачи для N чисел к
задаче для p = N / q числам, где q — делитель
N. Пусть мы уже умеем решать задачу для
N / q чисел. Применим преобразование Фурье
к наборам
для
. Покажем теперь, как за O(Np) действий
решить исходную задачу.
Заметим, что
.
Выражения в скобках нам уже известны —
это i(mod p)-тое число после преобразования
Фурье j-той группы. Таким образом, для
вычисления каждого bi нужно O(q) действий,
а для вычисления всех bi — O(Nq) действий,
что и требовалось получить.
Оконное преобразование Фурье
где
даёт (вообще говоря несколько искажённое)
распределение частот части оригинального
сигнала f(t) в окрестности времени t.
Классическое преобразование Фурье имеет дело со спектром сигнала, взятым во всем диапазоне существования переменной. Нередко интерес представляет только локальное распределение частот, в то время как требуется сохранить изначальную переменную (обычно время). В этом случае используется обобщение преобразования Фурье, так называемое оконное преобразование Фурье. Для начала необходимо выбрать некоторую оконную функцию W, эта функция должна иметь хорошо локализованный спектр.
На практике дискретный спектральный анализ реализован в современных цифровых осциллографах и анализаторах спектра. Используется, как правило, выбор окна из 3—10 типов окон. Применение окон принципиально необходимо, поскольку в реальных приборах исследуется всегда некоторая вырезка из исследуемого сигнала. При этом разрывы сигнала вследствие вырезки резко искажают спектр из-за наложения спектров скачков на спектр сигнала.
Некоторые анализаторы спектра используют быстрое (или кратковременное) оконное преобразование. При нём сигнал заданной длительности разбивается на ряд интервалов с помощью скользящего окна того или иного типа. Это позволяет получать, исследовать и строить в виде спектрограмм динамические спектры и анализировать их поведение во времени. Спектрограмма строится в трёх координатах — частота, время и амплитуда. При этом амплитуда задаётся цветом или оттенком цвета каждого прямоугольника спектрограммы. Подобные анализаторы спектра называют анализаторами спектра реального времени. Основным их производителем является корпорация Tetronix (США). Такие анализаторы появились в конце прошлого века и ныне бурно развиваются. Частотный диапазон исследуемых ими сигналов достигает сотен ГГц.
Указанные методы спектрального анализа реализуются и в системах компьютерной математики, например, Mathcad, Mathematica, Maple и MATLAB.