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

Многие сигналы удобно анализировать, раскладывая их на синусоиды (гармоники). Тому есть несколько причин. Например, подобным образом работает человеческое ухо. Оно раскладывает звук на отдельные колебания различных частот. Кроме того, можно показать, что синусоиды являются "собственными функциями" линейных систем (т.к. они проходят через линейные системы, не изменяя формы, а могут изменять лишь фазу и амплитуду). Еще одна причина в том, что теорема Котельникова формулируется в терминах спектра сигнала.

Преобразование Фурье (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 - его спектр):

Непосредственное вычисление двумерного ДПФ по приведенным формулам требует огромных вычислительных затрат. Однако можно доказать, что двумерное ДПФ обладает свойством сепарабельности, т.е. его можно вычислить последовательно по двум измерениям.

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

При этом результаты всех одномерных комплексных ДПФ нужно записывать на место исходных данных для этих ДПФ. Например, при вычислении одномерного ДПФ первой строки изображения нужно результат ДПФ записать в первую строку этого изображения (он имеет тот же размер). Для этого нужно каждый "пиксель" хранить в виде комплексного числа.

Таким образом, эффективный алгоритм вычисления ДПФ изображения заключается в вычислении одномерных БПФ сначала от всех строк, а потом - от всех столбцов изображения.

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

Преобразование Фурье является основоположником спектрального анализа. Спектральный анализ – это способ обработки сигналов, который позволяет охарактеризовать частотный состав измеряемого сигнала. В зависимости от того, каким образом представлен сигнал, используют разные преобразования Фурье. Различают несколько видов преобразования Фурье:

– Непрерывное преобразование Фурье (в англоязычной литературе Continue Time Fourier Transform – CTFT или, сокращенно, FT );

– Дискретное преобразование Фурье (в англоязычной литературе Discrete Fourier Transform – DFT );

– Быстрое преобразование Фурье (в англоязычной литературе Fast Fourier transform – FFT ).

Непрерывное преобразование Фурье

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

Существует несколько видов записи непрерывного преобразования Фурье, отличающихся друг от друга значением коэффициента перед интегралом (две формы записи):

или

где и - Фурье-образ функцииили частотный спектр функции ;

- круговая частота.

Следует отметить, что разные виды записи встречаются в различных областях науки и техники. Нормировочный коэффициент необходим для корректного масштабирования сигнала из частотной области во временную. Нормировочный коэффициент уменьшает амплитуду сигнала на выходе обратного преобразования для того чтобы она совпадала с амплитудой исходного сигнала. В математической литературе прямое и обратное преобразование Фурье умножаются на множитель , в то время как в физике чаще всего при прямом преобразовании множитель не ставят, а при обратном ставят множитель . Если последовательно рассчитать прямое преобразование Фурье некоторого сигнала, а после взять обратное преобразование Фурье, то результат обратного преобразования должен полностью совпадать с исходным сигналом.

Если функция нечетная на интервале (−∞, +∞), то преобразование Фурье может быть представлено через синус-функцию:

Если функция четная на интервале (−∞, +∞), то преобразование Фурье может быть представлено через косинус-функцию:

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

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

или

где - Фурье-образ функцииили частотный спектр функции ;

- круговая частота.

Если функция нечетная на интервале (−∞, +∞), то обратное преобразование Фурье может быть представлено через синус-функцию:

Если функция четная на интервале (−∞, +∞), то обратное преобразование Фурье может быть представлено через косинус-функцию:

В качестве примера, рассмотрим следующую функцию . График исследуемой экспоненциальной функции представлен ниже.

Поскольку функция является четной функцией, то непрерывное преобразование Фурье будет определяться следующим образом:

В результате получили зависимость изменения исследуемой экспоненциальной функции на частотном интервале (см. ниже).

Непрерывное преобразование Фурье используют, как правило, в теории при рассмотрении сигналов, которые изменяются в соответствии с заданными функциями, но на практике обычно имеют дело с результатами измерений, которые представляют собой дискретные данные. Результаты измерений фиксируются через равные промежутки времени с определённой частотой дискретизации, например, 16000 Гц или 22000 Гц. Однако в общем случае дискретные отсчёты могут идти неравномерно, но это усложняет математический аппарат анализа, поэтому на практике обычно не применяется.

Существует важная теорема Котельникова (в иностранной литературе встречается название «теорема Найквиста-Шеннона», «теорема отсчетов»), которая гласит, что аналоговый периодический сигнал, имеющий конечный (ограниченный по ширине) спектр (0…fmax), может быть однозначно восстановлен без искажений и потерь по своим дискретным отсчётам, взятым с частотой, большей или равной удвоенной верхней частоте спектра - частота дискретизации (fдискр >= 2*fmax). Другими словами, при частоте дискретизации 1000 Гц из аналогового периодического сигнала можно восстановить сигнал с частотой до 500 Гц. Следует отметить, что дискретизация функции по времени приводит к периодизации ее спектра, а дискретизация спектра по частоте приводит к периодизации функции.

Это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов.

Прямое дискретное преобразование Фурье ставит в соответствие временной функции , которая определена N-точками измерений на заданном временном интервале, другую функцию , которая определена на частотном интервале. Следует отметить, что функция на временном интервале задается с помощью N-отсчетов, а функция на частотном интервале задается с помощью K-кратного спектра.

k ˗ индекс частоты.

Частота k-го сигнала определяется по выражению

где T - период времени, в течение которого брались входные данные.

Прямое дискретное преобразование может быть переписано через вещественную и мнимую составляющие. Вещественная составляющая представляет собой массив, содержащий значения косинусоидальных составляющих, а мнимая составляющая представляет собой массив, содержащий значения синусоидальных составляющих.

Из последних выражений видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от одного колебания за период до N колебаний за период.

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

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

Амплитуда постоянной составляющей является средним значением функции за выбранный промежуток времени и определяется следующим образом:

Амплитуды и фазы частотных составляющих сигнала определяются по следующим соотношениям:

Полученные значения амплитуды и фазы называют полярным представлением (polar notation). Результирующий вектор сигнала будет определяться следующим образом:

Рассмотрим алгоритм преобразования дискретно заданной функции на заданном интервале (на заданном периоде) с количеством исходных точек

Д искретное преобразование Фурье

В результате преобразования получаем вещественное и мнимое значение функции , которая определена на частотном диапазоне.

Обратное дискретное преобразование Фурье ставит в соответствие частотной функции , которая определена K-кратным спектром на частотном интервале, другую функцию , которая определена на временном интервале.

N ˗ количество значений сигнала, измеренных за период, а также кратность частотного спектра;

k ˗ индекс частоты.

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

Пусть 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) равно:

Для вычисления дискретных отсчетов х к по имеющимся коэффициентам ДПФ существует следующая формула:

Эта формула носит название обратного дискретного преобразования Фурье {ОДПФ).

Даётся программный код для прямого и обратного преобразования Фурье. Рассматривается быстрое преобразование Фурье.

Дискретное преобразование Фурье (ДПФ) - это мощный инструмент анализа, который широко используется в области цифровой обработки сигналов (ЦОС). Существуют прямое и обратное преобразования Фурье. Прямое дискретное преобразование Фурье переводит сигнал из временной области в частотную и служит для анализа частотного спектра сигнала. Обратное преобразование делает ровно противоположное: по частотному спектру сигнала восстанавливает сигнал во временной области.

Для расчёта преобразования Фурье обычно используется ускоренная процедура расчёта - т.н. быстрое преобразование Фурье (БПФ). Это позволяет в значительной мере сократить процессорное время на достаточно сложные и ресурсоёмкие математические расчёты.

1 Комплексные числа

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

Код класса для описания комплексных чисел (разворачивается) """

""" Комплексное число. """

Public Class ComplexNumber """

""" Действительная часть комплексного числа. """

Public Real As Double = 0 """

""" Мнимая часть комплексного числа. """

Public Imaginary As Double = 0 Public Sub New() Real = 0 Imaginary = 0 End Sub """

""" Создаёт комплексное число. """

""" Действительная часть комплексного числа. """ Мнимая часть комплексного числа. Public Sub New(ByVal r As Double, Optional ByVal im As Double = 0) Real = r Imaginary = im End Sub Private usCult As New Globalization.CultureInfo("en-US") "используем культуру "en-US" чтобы целая и дробная части разделялись точкой, а не запятой """

""" Возвращает строку, состоящую из действительной и мнимой части, разделённых символом табуляции. """

Public Overrides Function ToString() As String Return (Real.ToString(usCult) & ControlChars.Tab & Imaginary.ToString(usCult)) End Function End Class

2 Прямое дискретное быстрое преобразование Фурье

На вход функции передаётся массив комплексных чисел. Действительная часть которого представляет произвольный дискретный сигнал, с отсчётами через равные промежутки времени. Мнимая часть содержит нули. Число отсчётов в сигнале должно равняться степени двойки. Если ваш сигнал короче, то дополните его нулями до числа, кратного степени 2: 256, 512, 1024 и т.д. Чем длиннее сигнал, тем у рассчитанного спектра будет выше разрешение по частоте.

Код для расчёта прямого быстрого преобразования Фурье на VB.NET (разворачивается) """

""" Рассчитывает спектр сигнала методом быстрого преобразования Фурье. Использовать только (N/2+1) возвращаемых значений (до половины частоты дискретизации). """

""" Сигнал, содержащий количество отсчётов, кратное степени двойки, и состоящий из действительной и мнимой частей. Все мнимые части сигнала заполнены нулями. """ Возвращает массив комплексных чисел спектра. """ Значимы только первые N/2+1, остальные - симметричная часть, соответствующая отрицательным частотам. """ Первое значение спектра - это постоянная составляющая, последнее - соответствует половине частоты дискретизации (частота Найквиста). """ Значения выше половины частоты дискретизации - не использовать. """ Public Shared Function FFT(ByVal signal As ComplexNumber()) As ComplexNumber() Dim order As Integer = signal.Length "порядок ДПФ CheckFftOrder(order) "Проверяем, что порядок равен степени двойки Dim spectrumLen As Integer = order \ 2 Dim j As Integer = spectrumLen "Бит-реверсная сортировка: For i As Integer = 1 To order - 2 If (i < j) Then Dim tmpRe As Double = signal(j).Real Dim tmpIm As Double = signal(j).Imaginary signal(j).Real = signal(i).Real signal(j).Imaginary = signal(i).Imaginary signal(i).Real = tmpRe signal(i).Imaginary = tmpIm End If Dim k As Integer = spectrumLen Do Until (k > j) j -= k k \= 2 Loop j += k Next "Цикл по уровням разложения: For level As Integer = 1 To CInt(Math.Log(order) / Math.Log(2)) Dim lvl As Integer = CInt(2 ^ level) Dim lvl2 As Integer = lvl \ 2 Dim tmp As Double = Math.PI / lvl2 Dim sr As Double = Math.Cos(tmp) Dim si As Double = -Math.Sin(tmp) Dim tr As Double = 0 Dim ur As Double = 1 Dim ui As Double = 0 For jj As Integer = 1 To lvl2 "Цикл по спектрам внутри уровня For i As Integer = (jj - 1) To (order - 1) Step lvl "Цикл по отдельным "бабочкам" Dim ip As Integer = i + lvl2 tr = signal(ip).Real * ur - signal(ip).Imaginary * ui "Операция "бабочка" Dim ti As Double = signal(ip).Real * ui + signal(ip).Imaginary * ur signal(ip).Real = signal(i).Real - tr signal(ip).Imaginary = signal(i).Imaginary - ti signal(i).Real = signal(i).Real + tr signal(i).Imaginary = signal(i).Imaginary + ti Next tr = ur ur = tr * sr - ui * si ui = tr * si + ui * sr Next Next "Заполняем массив комплексных чисел, обработанных БПФ: Dim spectrum(order - 1) As ComplexNumber For i As Integer = 0 To order - 1 With signal(i) spectrum(i) = New ComplexNumber(.Real, .Imaginary) End With Next Return spectrum End Function

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

Обратное дискретное преобразование Фурье (ОДПФ) одним из этапов расчёта включает в себя прямое ДПФ на массиве комплексных чисел, где мнимая часть - это инверсия относительно оси X мнимой части спектра.

Код для расчёта обратного быстрого преобразования Фурье на VB.NET (разворачивается) """

""" Восстанавливает сигнал по его спектру методом обратного быстрого преобразования Фурье. """

""" Спектр сигнала, содержащий количество отсчётов, кратное степени двойки, и состоящий из действительной и мнимой частей. Public Shared Function InverseFFT(ByVal spectrum As ComplexNumber()) As ComplexNumber() Dim order As Integer = spectrum.Length "Порядок обратного ДПФ. CheckFftOrder(order) "Изменение арифметического знака элементов мнимой части: For i As Integer = 0 To spectrum.Length - 1 spectrum(i).Imaginary = -spectrum(i).Imaginary Next "Вычисление прямого БПФ: Dim directFFT As ComplexNumber() = FFT(spectrum) "Деление на order во временной области со сменой арифметического знака мнимой части: Dim signal(directFFT.Length - 1) As ComplexNumber For i As Integer = 0 To directFFT.Length - 1 Dim ReX As Double = directFFT(i).Real / order Dim ImX As Double = -directFFT(i).Imaginary / order signal(i) = New ComplexNumber(ReX, ImX) Next Return signal End Function

Ну и конечно же, опишем использовавшийся метод, который проверяет число элементов переданного массива:

"""

""" Проверяет, является ли порядок БПФ степенью двойки, и если нет - вызывает исключение. """

""" Порядок БПФ. Private Shared Sub CheckFftOrder(ByVal order As Integer) Dim chk As Double = Math.Abs(Math.Floor(Math.Log(order, 2)) - Math.Log(order, 2)) If (chk > 0.0001) Then Throw New ArgumentException(String.Format("Длина массива ({0}) не кратна степени двойки.", order)) End If End Sub

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(). Получим массив комплексных чисел, где действительная часть будет содержать восстановленный сигнал:

Как видно, восстановленный сигнал полностью повторяет исходный.