Это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать частные дифференциальные уравнения и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Преобразования бывают одномерные, двумерные и даже трёхмерные.
Прямое преобразование:
Обратное преобразование:
Обозначения:
§ N - количество значений сигнала, измеренных за период, а также количество компонент разложения;
§ - измеренные значения сигнала (в дискретных временных точках с номерами , которые являются входными данными для прямого преобразования и выходными для обратного;
§ - N комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;
§ - обычная (вещественная) амплитуда k-го синусоидального сигнала;
§ arg(X k ) - фаза k-го синусоидального сигнала (аргумент комплексного числа);
§ k - частота k-го сигнала, равная , где T - период времени, в течение которого брались входные данные.
Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от N колебаний за период до одного колебания за период. Поскольку частота дискретизации сама по себе равна N отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены - возникает муаров эффект. Это приводит к тому, что вторая половина из N комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.
Рассмотрим некоторый периодический сигнал x (t ) c периодом равным T. Разложим его в ряд Фурье:
Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: x n = x (t n ), где , тогда эти отсчеты через ряд Фурье запишутся следующим образом:
Используя соотношение: , получаем:
где 
Таким образом, мы получили обратное дискретное преобразование Фурье.
Умножим теперь скалярно выражение для x n на и получим:
Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:
Эта формула описывает прямое дискретное преобразование Фурье .
В литературе принято писать множитель в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:
Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов в вектор спектральных отсчётов той же длины. Таким образом, преобразование может быть реализовано как умножение квадратной матрицы на вектор:
Даётся программный код для прямого и обратного преобразования Фурье. Рассматривается быстрое преобразование Фурье.
Дискретное преобразование Фурье (ДПФ) - это мощный инструмент анализа, который широко используется в области цифровой обработки сигналов (ЦОС). Существуют прямое и обратное преобразования Фурье. Прямое дискретное преобразование Фурье переводит сигнал из временной области в частотную и служит для анализа частотного спектра сигнала. Обратное преобразование делает ровно противоположное: по частотному спектру сигнала восстанавливает сигнал во временной области.
Для расчёта преобразования Фурье обычно используется ускоренная процедура расчёта - т.н. быстрое преобразование Фурье (БПФ). Это позволяет в значительной мере сократить процессорное время на достаточно сложные и ресурсоёмкие математические расчёты.
1 Комплексные числа
Для начала нам потребуется вспомогательный класс, который будет описывать комплексные числа. Комплексные числа - это особый вид чисел в математике. Каждое комплексное число состоит из двух частей - действительной и мнимой. Сейчас нам достаточно знать о комплексных числах применительно к ДПФ то, что действительная часть комплексного числа хранит информацию об амплитуде сигнала, а мнимая - о фазе.
Код класса для описания комплексных чисел (разворачивается) """2 Прямое дискретное быстрое преобразование Фурье
На вход функции передаётся массив комплексных чисел. Действительная часть которого представляет произвольный дискретный сигнал, с отсчётами через равные промежутки времени. Мнимая часть содержит нули. Число отсчётов в сигнале должно равняться степени двойки. Если ваш сигнал короче, то дополните его нулями до числа, кратного степени 2: 256, 512, 1024 и т.д. Чем длиннее сигнал, тем у рассчитанного спектра будет выше разрешение по частоте.
Код для расчёта прямого быстрого преобразования Фурье на VB.NET (разворачивается) """3 Обратное дискретное быстрое преобразование Фурье
Обратное дискретное преобразование Фурье (ОДПФ) одним из этапов расчёта включает в себя прямое ДПФ на массиве комплексных чисел, где мнимая часть - это инверсия относительно оси X мнимой части спектра.
Код для расчёта обратного быстрого преобразования Фурье на VB.NET (разворачивается) """Ну и конечно же, опишем использовавшийся метод, который проверяет число элементов переданного массива:
"""
4 Проверка прямого и обратного преобразования Фурье
Теперь давайте проверим, что наши функции работают. Для этого пропустим произвольный сигнал через механизм прямого преобразования Фурье, а затем «соберём» его обратно с помощью обратного преобразования Фурье. Восстановленный сигнал должен практически совпадать с исходным. Ошибки округления, возникающие при работе с числами в компьютере, имеют место быть, поэтому сигналы не будут идентичны полностью, но их отклонение друг от друга должно быть пренебрежимо малым.
Для примера в качестве исходного сигнала возьмём функцию синуса и сформируем данные длиной 128 отсчётов вот таким образом:
Dim cn(127) As ComplexNumber For i As Integer = 0 To cn.Length - 1 cn(i) = New ComplexNumber(Math.Sin(i * 3 * Math.PI / 180)) Next
Получим вот такой сигнал:
Здесь по оси X - номера отсчётов во временной области, по оси Y - амплитуда. Обратим внимание, что сигнал состоит только из действительных частей, а мнимая часть на всём отрезке равна "0".
Теперь передадим этот сигнал на вход функции FFT(). По полученным в ходе прямого преобразования Фурье массивам комплексных чисел построим два графика - действительной (Re) и мнимой (Im) частей спектра:
Здесь по оси X - отсчёты в частотной области, по оси Y - амплитуда. Чтобы получить реальные значения частоты, необходимо рассчитать их, учитывая, что "0" оси Y соответствует нулевой частоте, максимум оси Y соответствует частоте дискретизации.
Полученный спектр сигнала передадим функции обратного преобразования Фурье IFFT(). Получим массив комплексных чисел, где действительная часть будет содержать восстановленный сигнал:
Как видно, восстановленный сигнал полностью повторяет исходный.
Многие сигналы удобно анализировать, раскладывая их на синусоиды (гармоники). Тому есть несколько причин. Например, подобным образом работает человеческое ухо. Оно раскладывает звук на отдельные колебания различных частот. Кроме того, можно показать, что синусоиды являются "собственными функциями" линейных систем (т.к. они проходят через линейные системы, не изменяя формы, а могут изменять лишь фазу и амплитуду). Еще одна причина в том, что теорема Котельникова формулируется в терминах спектра сигнала.
Преобразование Фурье (Fourier transform) - это разложение функций на синусоиды (далее косинусные функции мы тоже называем синусоидами, т.к. они отличаются от "настоящих" синусоид только фазой). Существует несколько видов преобразования Фурье.
1. Непериодический непрерывный сигнал можно разложить в интеграл Фурье.
2. Периодический непрерывный сигнал можно разложить в бесконечный ряд Фурье.
3. Непериодический дискретный сигнал можно разложить в интеграл Фурье.
4. Периодический дискретный сигнал можно разложить в конечный ряд Фурье.
Компьютер способен работать только с ограниченным объемом данных, следовательно, реально он способен вычислять только последний вид преобразования Фурье. Рассмотрим его подробнее.
Комплексное ДПФ
До сих пор мы рассматривали ДПФ от действительных сигналов. Обобщим теперь ДПФ на случай комплексных сигналов. Пусть x[n], n=0,…,N-1 - исходный комплексный сигнал, состоящий из N комплексных чисел. Обозначим X[k], k=0,…N-1 - его комплексный спектр, также состоящий из N комплексных чисел. Тогда справедливы следующие формулы прямого и обратного преобразований Фурье:
Если по этим формулам разложить в спектр действительный сигнал, то первые N/2+1 комплексных коэффициентов спектра будут совпадать со спектром "обычного" действительного ДПФ, представленным в "комплексном" виде, а остальные коэффициенты будут их симметричным отражением относительно половины частоты дискретизации. Для косинусных коэффициентов отражение четное, а для синусных - нечетное.
Двумерное ДПФ
Для изображений, представляющих собой двумерный сигнал, спектром является также двумерный сигнал. Базисные функции преобразования Фурье имеют вид:
причем фазы также могут быть различны. На изображении каждая из этих базисных функций представляют собой волну определенной частоты, определенной ориентации и определенной фазы.
Здесь N 1 xN 2 - размер исходного сигнала, он же - размер спектра. k 1 и k 2 - это номера базисных функций (номера коэффициентов двумерного ДПФ, при которых эти функции находятся). Поскольку размер спектра равен размеру исходного сигнала, то k 1 = 0,…,N 1 -1; k 2 = 0,…,N 2 -1.
n 1 и n 2 - переменные-аргументы базисных функций. Поскольку область определения базисных функций совпадает с областью определения сигнала, то n 1 = 0,…,N 1 -1; n 2 = 0,…,N 2 -1.
Двумерное ДПФ (в комплексной форме) определяется следующими формулами (здесь x - исходный сигнал, а X - его спектр):
Непосредственное вычисление двумерного ДПФ по приведенным формулам требует огромных вычислительных затрат. Однако можно доказать, что двумерное ДПФ обладает свойством сепарабельности, т.е. его можно вычислить последовательно по двум измерениям.
Для вычисления двумерного ДПФ достаточно вычислить одномерные комплексные ДПФ всех строк изображения, а затем вычислить в результирующем "изображении" одномерные комплексные ДПФ всех столбцов.
При этом результаты всех одномерных комплексных ДПФ нужно записывать на место исходных данных для этих ДПФ. Например, при вычислении одномерного ДПФ первой строки изображения нужно результат ДПФ записать в первую строку этого изображения (он имеет тот же размер). Для этого нужно каждый "пиксель" хранить в виде комплексного числа.
Таким образом, эффективный алгоритм вычисления ДПФ изображения заключается в вычислении одномерных БПФ сначала от всех строк, а потом - от всех столбцов изображения.
Пусть f (x 1 , x 2) – функция двух переменных. По аналогии с одномерным преобразованием Фурье можно ввести двумерное преобразование Фурье:
Функция при фиксированных значениях ω 1 , ω 2 описывает плоскую волну в плоскости x 1 , x 2 (рисунок 19.1).
Величины ω 1 , ω 2 имеют смысл пространственных частот и размерность мм −1 , а функция F(ω 1 , ω 2) определяет спектр пространственных частот. Сферическая линза способна вычислять спектр оптического сигнала (рисунок 19.2). На рисунке 19.2 введены обозначения: φ - фокусное расстояние,
Рисунок 19.1 – К определению пространственных частот
Двумерное преобразование Фурье обладает всеми свойствами одномерного преобразования, кроме того отметим два дополнительных свойства, доказательство которых легко следует из определения двумерного преобразования Фурье.
Рисунок 19.2 – Вычисление спектра оптического сигнала с использованием
сферической линзы
Факторизация . Если двумерный сигнал факторизуется,
то факторизуется и его спектр:
Радиальная симметрия . Если двумерный сигнал радиально-симметричен, то есть
Где – функция Бесселя нулевого порядка. Формулу, определяющую связь между радиально-симметричным двумерным сигналом и его пространственным спектром называют преобразованием Ганкеля.
ЛЕКЦИЯ 20. Дискретное преобразование Фурье. Низкочастотный фильтр
Прямое двумерное дискретное преобразование Фурье (ДПФ) преобразует изображение, заданное в пространственной координатной системе (x, y ), в двумерное дискретное преобразование изображения, заданное в частотной координатной системе (u,v ):
Обратное дискретное преобразование Фурье (ОДПФ) имеет вид:
Видно, что ДПФ является комплексным преобразованием. Модуль этого преобразования представляет амплитуду спектра изображения и вычисляется как корень квадратный из суммы квадратов действительной и мнимой частей ДПФ. Фаза (угол сдвига фазы) определяется как арктангенс отношения мнимой части ДПФ к действительной. Энергетический спектр равен квадрату амплитуды спектра, или сумме квадратов мнимой и действительной частей спектра.
Теорема о свертке
В соответствии с теоремой о свертке, свертка двух функций в пространственной области может быть получена ОДПФ произведения их ДПФ, то есть
Фильтрация в частотной области позволяет по ДПФ изображения подобрать частотную характеристику фильтра, обеспечивающую необходимое преобразование изображения. Рассмотрим частотные характеристики наиболее распространенных фильтров.
В радиотехнике часто применяется понятие свертки двух сигналов. Так, например, сигнал на выходе четырехполюсника можно найти с помощью свертки входного сигнала и импульсной характеристики четырехполюсника. Поскольку были рассмотрены дискретные и цифровые сигналы, то определим понятие свертки для дискретных сигналов , или дискретной свертки.
Пусть имеется дискретный сигнал х Д (t) , состоящий из N отсчетов х к , и дискретный сигнал у д (Г), состоящий из N отсчетов у к, тогда дискретной сверткой этих двух сигналов называется сигнал z A (t) , для которого
Дискретные сигналы получили широкое распространение при создании систем с импульсной модуляцией.
Устройство дискретизации в простейшем случае представляет собой стробируемый каскад (ключ), открывающийся на время т и с периодом А (рис. 4.7).
Рис. 4.
Интервал дискретизации А может быть постоянным (равномерная дискретизация) или переменным (адаптивная дискретизация). Наиболее распространенной формой дискретизации является равномерная, в основе которой лежит теорема Котельникова.
Импульсный модулятор - это устройство с двумя входами, на один из которых подается аналоговый сигнал, а на второй поступают короткие синхронизирующие импульсы с периодом повторения А. При этом в момент поступления синхроимпульса происходит измерение мгновенного значения сигнала лс(г). На выходе модулятора возникает последовательность импульсов, каждый из которых имеет площадь, пропорциональную соответствующему отсчетному значению аналогового сигнала (рис. 4.7).
Сигнал Хмпн (t ) на выходе импульсного модулятора называют модулированной импульсной последовательностью (МИП). Математически МИП записывается так
а спектральная плотность МИП выражается через спектральную плотность аналогового сигнала следующим образом:
Модель дискретного сигнала предполагает, что отсчетные значения аналогового сигнала могут быть получены в неограниченном числе точек на оси времени. Практически же обработка всегда ведется на конечном интервале времени.
Рассмотрим особенности спектрального представления дискретного сигнала, заданного на интервале своими отсчетами x 0 ,x x ,...,x N _ x . Полное число отсчетов N - Т / А.
Методика изучения таких дискретных сигналов состоит в том, что полученная выборка отсчетных значений мысленно повторяется бесконечное число раз. В результате сигнал становится периодическим (рис. 4.8).
Сопоставив такому сигналу математическую модель, можно воспользоваться разложением в ряд Фурье и найти соответствующие амплитудные коэффициенты. Совокупность этих коэффициентов образует спектр дискретного периодического сигнала.
Рис. 4.8.
Запишем модель ограниченного периодического сигнала в виде последовательности дельта-импульсов:
Разложим сигнал Хмип (0 в ряд Фурье:
здесь замена переменных? = f / А. Окончательно получаем
Эта формула определяет последовательность коэффициентов, образующих дискретное преобразование Фурье (ДПФ) рассматриваемого сигнала.
ДПФ обладает следующими свойствами:
1. ДПФ есть линейное преобразование, т. е. если z k = а х к + /? у к, то
С"Z П ~ ^ С Х п Р Су п .
2. Число различных коэффициентов Cq,Ci,...,C n _i равно числу N отсчетов за период, при n = N коэффициент C N = С 0 .
3. С 0 является средним значением всех отсчетов С 0 = - ^х к.
N к =о
- 4. Если N- четное число, то С N = -^(-1) к х к.
- 7 ^ ?=о
- 5. Если отсчеты х к - вещественные числа и N - четное число, то C N = C* N , / = 0; Л/7 2 -1.
- -+i - -i
- 6. Если y k =x k+m , m = l;JV-l,TO C, t =C, * e ~ j2rrkm,N .
- 2 tf-l
- 7. Если z k = - > T0 C z к =C X k C y k
iy/ i =0
ДПФ применяется для вычисления спектров функций, заданных таблицами или графиками, обработки экспериментальных данных, нахождения сигнала на выходе дискретного фильтра и т. д.
Если на основе отсчетов x 0 ,x l ,...,x N _ l некоторого сигнала найдены коэффициенты ДПФ C 0 ,Ci,... 9 C n/2 , то по ним можно восстановить аналоговый сигнал с ограниченным спектром x(t). Ряд Фурье такого сигнала имеет вид (при четном N)
где |Q| - модуль коэффициентов ДПФ; =arg - фазовый угол (аргумент)
коэффициентов ДПФ. Частота первой гармоники: f= - / в = - = -/i- нечетном N последнее слагаемое в формуле (4.17) равно:
Для вычисления дискретных отсчетов х к по имеющимся коэффициентам ДПФ существует следующая формула:
Эта формула носит название обратного дискретного преобразования Фурье {ОДПФ).
