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

💖 Нравится? Поделись с друзьями ссылкой

Пусть 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 ):

Обратное дискретное преобразование Фурье (ОДПФ) имеет вид:

Видно, что ДПФ является комплексным преобразованием. Модуль этого преобразования представляет амплитуду спектра изображения и вычисляется как корень квадратный из суммы квадратов действительной и мнимой частей ДПФ. Фаза (угол сдвига фазы) определяется как арктангенс отношения мнимой части ДПФ к действительной. Энергетический спектр равен квадрату амплитуды спектра, или сумме квадратов мнимой и действительной частей спектра.



Теорема о свертке

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

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

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

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

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

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


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

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

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

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

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

Обозначим через

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

. (3.21)

Если сигнал существует только внутри прямоугольника со сторонами элементов (рис. 3.4.а), то сигнал определен на всей плоскости и является на ней прямоугольно-периодическим (рис. 3.4.б).

Рис. 3.4. Реальное (а) и периодически продолженное (б) изображения

Любой периодический сигнал может быть представлен в виде ряда Фурье, но, в отличие от одномерных сигналов, двумерные описываются двумерным рядом Фурье, имеющим вид:

Базисные функции этого двумерного представления - двумерные комплексные экспоненты (иногда называемые комплексными синусоидами)

(3.23)

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

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

(3.24)

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

Заметим, что для точного представления дискретного сигнала с двумерным периодом элементов согласно формулам БПФ достаточно конечного числа базисных функций (3.23) - ряд (3.22) является конечным. Это и понятно, поскольку сам представляемый сигнал содержит в одном периоде конечное число точек, т.е. имеет конечное число степеней свободы. Ясно, что число степеней свободы в спектре не может отличаться от числа степеней свободы в самом сигнале.

Остановимся на наиболее существенных свойствах двумерного дискретного спектра Фурье. Вычислим спектральные коэффициенты (3.24) в частотных точках :

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

,

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

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

,

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

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

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

Преобразования Фурье

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

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

1. Непериодический непрерывный сигнал можно разложить в интеграл Фурье.

2. Периодический непрерывный сигнал можно разложить в бесконечный ряд Фурье.

3. Непериодический дискретный сигнал можно разложить в интеграл Фурье.

4. Периодический дискретный сигнал можно разложить в конечный ряд Фурье.

Компьютер способен работать только с ограниченным объемом данных, следовательно, реально он способен вычислять только последний вид преобразования Фурье. Рассмотрим его подробнее.

ДПФ вещественного сигнала

Пусть дискретный сигнал x имеет периодN точек. В этом случае его можно представить в виде конечного ряда (т.е. линейной комбинации) дискретных синусоид:

2π k (n + ϕ k )

x = ∑ C k cos

(ряд Фурье)

k = 0

Эквивалентная запись (каждый косинус раскладываем на синус и косинус, но теперь – без фазы):

2 π kn

2 π kn

x = ∑ A k cos

+ ∑ B k sin

(ряд Фурье)

k = 0

k = 0

Рис. 6 . Базисные функции ряда Фурье для 8-точеченого дискретного сигнала. Слева – косинусы, справа – синусы. Частоты увеличиваются сверху вниз.

Базисные синусоиды имеют кратные частоты. Первый член ряда (k =0) – это константа, называемаяпостоянной составляющей (DC offset ) сигнала. Самая первая синусоида (k =1) имеет такую частоту, что ее период совпадает с периодом самого исходного сигнала. Самая высокочастотная составляющая (k =N /2) имеет такую частоту, что ее период равен двум отсчетам. КоэффициентыA k и

B k называютсяспектром сигнала (spectrum ). Они показывают амплитуды си-

нусоид, из которых состоит сигнал. Шаг по частоте между двумя соседними синусоидами из разложения Фурье называется частотным разрешением спектра.

На рис. 6 показаны синусоиды, по которым происходит разложение дискретного сигнала из 8 точек. Каждая из синусоид состоит из 8 точек, то есть является обычным дискретным сигналом. Непрерывные синусоиды показаны на рисунке для наглядности.

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

Алгоритм обратного преобразования Фурье очевиден (он содержится в формуле ряда Фурье; для проведения синтеза нужно просто подставить в нее коэффициенты). Рассмотрим алгоритм прямого преобразования Фурье, т.е. нахождения коэффициентов A k иB k .

2 π kn

2 π kn

от аргумента n является ор-

Система функций

K = 0,...,

тогональным базисом в пространстве периодических дискретных сигналов с периодом N . Это значит, что для разложения по ней любого элемента пространства (сигнала) нужно посчитать скалярные произведения этого элемента со всеми функциями системы, и полученные коэффициенты нормировать. Тогда для исходного сигнала будет справедлива формула разложения по базису с коэффициентамиA k иB k .

Итак, коэффициенты A k иB k вычисляются как скалярные произведения (в не-

прерывном случае – интегралы от произведения функций, в дискретном случае

– суммы от произведения дискретных сигналов):

N − 1

2 π ki , приk = 1,...,

A k=

∑ x cos

−1

N i = 0

N − 1

A k=

∑ x cos2 π ki , приk = 0,

N i = 0

N − 1

2 π ki

NB 0 иB N 2 всегда равны нулю (т.к. соответствующие им «базисные»

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

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

Вычисление преобразований Фурье требует очень большого числа умножений (около N 2 ) и вычислений синусов. Существует способ выполнить эти преобразования значительно быстрее: примерно заN log2 N операций умножения.

Этот способ называется быстрым преобразованием Фурье(БПФ, FFT, fast Fourier transform). Он основан на том, что среди множителей (синусов) есть много повторяющихся значений (в силу периодичности синуса). Алгоритм БПФ группирует слагаемые с одинаковыми множителями, значительно сокращая число умножений. В результате быстродействие БПФ может в сотни раз превосходить быстродействие стандартного алгоритма (в зависимости от N). При этом следует подчеркнуть, что алгоритм БПФ является точным. Он даже точнее стандартного, т.к. сокращая число операций, он приводит к меньшим ошибкам округления.

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

N называется размеромили длиной БПФ(FFT size).

Комплексное ДПФ

До сих пор мы рассматривали ДПФ от действительных сигналов. Обобщим теперь ДПФ на случай комплексных сигналов. Пусть x , n =0,…,N -1 – исходный комплексный сигнал, состоящий изN комплексных чисел. ОбозначимX , k =0,…N -1 – его комплексный спектр, также состоящий изN комплексных чисел. Тогда справедливы следующие формулы прямого и обратного преобразо-

ваний Фурье (здесь j = − 1):

N − 1

X [ k] = ∑ x[ n] e− jnk (2 π N )

n= 0

N − 1

∑ X [ k ] e jnk(2 π N)

N k = 0

Если по этим формулам разложить в спектр действительный сигнал, то первые N /2+1 комплексных коэффициентов спектра будут совпадать со спектром «обычного» действительного ДПФ, представленным в «комплексном» виде, а остальные коэффициенты будут их симметричным отражением относительно

Рассказать друзьям