Попался, который кусался

Литература

1. А.Л. Дмитриев. Оптические методы обработки информации. Учебное пособие. СПб. СПюГУИТМО 2005. 46 с.
2. А.А.Акаев, С.А.Майоров «Оптические методы обработки информации» М.:1988
3. Дж.Гудмен «Введение в Фурье-оптику» М.: Мир 1970

Мы рассмотрели две формы преобразования Фурье:

1) Преобразование Фурье в непрерывном времени с непрерывным изменением частоты

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

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

Введем ДПФ, основываясь на преобразовании Фурье в дискретном времени (2). Поскольку теперь мы имеем дело с конечной последовательностью (длиной N), то положим, что временная последовательность x(n)=0 при n<0 и при n>N-1. Как будет видно из дальнейшего, дискретизация частотного интервала, т.е. вычисление Фурье-образа только в кратных значениях частот приведет также к периодическому продолжению исходной временной последовательности по оси времени. Чтобы опять избежать наложения, пользуясь аналогией с временной дискретизацией, дискретизуем ось частот с интервалом, где NT -полный временной интервал задания исходной функции. Тогда значение частоты на k-ом частотном отсчете, а k изменяется от 0 до N-1(т.к. , согласно теореме дискретизации). Таким образом, число отсчетов по частоте равно также N.

Если это сделано, то преобразование Фурье (2) примет вид:

• 7.2 Ортогональность системы комплексных экспонент на множестве равноотстоящих точек.

Чтобы перейти от прямого преобразования Фурье к обратному,

докажем ортогональность комплексных экспонент

(или что тоже самое, систем синусов и косинусов) на множестве равноотстоящих N точек.

Обозначая разность n-n’ за m , получим в правой части (4) геометрическую прогрессию со знаменателем, при этом отметим очевидное равенство. Находя по известной формуле сумму этой геометрической прогрессии, получим

При этом мы использовали тот факт, что

в случае m=0,±N, ±2N,....

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

Отметим, что приведенная система экспонент ортогональна на системе любых отсчитанных подряд N точек, независимо от выбора начальной. Действительно, взяв за начальную точку с индексом -l делая замену переменной суммирования k’=k+l, получим:

т.к. , а при остальных k значение суммы равно нулю.

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

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

Умножим обе части выражения ДПФ (3) на и просуммируем по k от 0 до N-1.

При этом мы учли, что поскольку суммирование по k ведется в пределах от 0 до N-1, то, согласно (5) сумма будет отлична от нуля только при n-n’=0 т.е. при n=n’. Переобозначив n’ на n и выразив из (6) x(n) , получим выражение для ОДПФ, которое совместно с выражением (3) для ДПФ дает дискретную форму преобразования Фурье:

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

Введя для комплексной экспоненты обозначение, дискретное преобразование Фурье представим в виде:

Последняя форма будет выглядеть еще проще в матричном представлении:

где элементами матрицы T являются комплексные экспоненты, а матрицы Т’ .

Очевидна связь между матрицами T и Т’:

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

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

• 1. Поскольку система экспонент ортогональна на дискретном множестве N точек, независимо от выбора начальной точки этого множества, то начальное значение индексов суммирования в (7) и (9) могут быть любыми, лишь бы разность между начальными и конечными значениями была равна N.
• 2. Последовательности x(n) и X(k), определяемые формулами 7 или 9, вне множества 0....N-1 являются N-периодическими, т.е.

где р-любое число, n и k -целое в промежутке от 0 до N-1. Это свойство является следствием N-периодичности экспонент (8): Так, например, для ОДПФ получим

3. Согласно предыдущему замечанию, X(-k)=X(n-k).

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

Т.е. X(-1)=X(N-1);X(-2)=X(N-2) и т.д.

Таким образом, второй половине преобразования Фурье, т.е. значениям X(k) при k>N/2 соответствуют отрицательные частоты.

Чтобы увидеть непрерывный аналог преобразования Фурье, рассчитанного дискретным способом, когда n и k изменяются от 0 до N-1, нужно “ разрезать” дискретный образ Фурье в точке N/2 и часть X(k), соответствующую k>N/2 поставить перед первой половиной. При этом чтобы перейти к реальным значениям частот при формировании оси частот нужно умножать частотный отсчет k на величину частотного интервала в герцах. Таким образом, значение частоты на k-ом отсчете равно.

то x 3 (n)~X 3 (k), где X 3 (k)=X 1 (k)+X 2 (k).

Если последовательности x 1 (n) и x 2 (n) имеют разную длину, соответственно N 1 и N 2 , то длина N 3 =max(N 1 ,N 2).

Последовательность меньшей длительности следует дополнить нулями.

• 2. Свойство сдвига.
• 2.1 Сдвиг во временной области.

Если x(n)~X(k) , то x(n-h)~W -kh X(k)

Доказательство:

Используя определение прямого ДПФ в виде (9б) и делая замену переменной суммирования n-h =r или n=r+h, получим:

2.2 Сдвиг в частотной области.

Если x(n)~X(k) , то x(n)W nf ~ X(k-f)

Доказательство этого свойства, аналогичное предыдущему, основано на определении ОДПФ (7б) или (9б).

3. Свойство комплексной сопряженности

Если x(n), где n=0,1,2,..N-1- п

оследовательность действитель- *

ных чисел,а N-четное,и x(n)~X(k) , то X(N/2+r)=X (N/2-r), где

Доказательство:

1) Коэффициенты ДПФ последовательности 8-ми действительных чисел соответственно равны X(0)=5, X(1)=i, X(2)=1+i,X(3)=2+3i,X(4)=2.

Найти значения коэффициентов X(k), k=5,6,7.

Ответ: Согласно свойству (3) X(5)=2+3i,X(6)=1+i,X(7)=i.

2) Показать, что ДПФ N-точечной последовательности

{x(n)}={А,А,...А} есть последовательность N-точечная последовательность {X(k)}={NА,0,0...)}.

Согласно определению прямого ДПФ (7а) и свойству ортогональности экспонент (4)

7.5Теорема Парсеваля. Спектр мощности

Теорема Парсеваля для конечной временной последовательности имеет вид:

Величину

мы назвали спектром мощности.

В силу свойства 3 комплексной сопряженности, спектр мощности будет симметричным относительно k=N/2. Т.к. значения N/2

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

соответствующего положительным частотам, т.е. значениям 0

Важной особенностью спектра мощности является ее инвариантность к сдвигам N-периодической временной последовательности x(n).

Действительно, т.к. согласно свойству сдвига 2.1 x(n-h) ~ W -kh X(k), то

C помощью спектра мощности определяется амплитудный спектр:

Амплитудный спектр также инвариантен к сдвигам временной последовательности x(n) т.к.

p(k) как и Р(k) симметрична относительно k=N/2.

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

где I(k) и R(k) - действительная и мнимая части X(k).

Согласно свойству 3 комплексной сопряженности R(N/2+r)=R(N/2-r), a I(N/2+r)=-I(N/2-r). Поэтому фазовый спектр оказывается нечетной Функцией относительно k=N/2 т.е. Ф(N/2+r)=-Ф(N/2-r).

Из (14), а также из выражения для ДПФ (7а-9а) следует фундаментальное свойство фазового спектра, заключающееся в инвариантности его относительно умножения на константу.

Если известны амплитудный (13) и фазовый (14) спектры сигнала, позволяющие совместно рассчитать образ Фурье

то с помощью ОДПФ (7б-9б) можно восстановить исходный сигнал.

7.6 Дискретная свертка .

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

x(n) и y(n), каждая длины N ка

к следующую сумму

При этом может оказаться, что аргумент n-r будет вне пределов . В зависимости от того, как определим в этом случае значение x(n-r) или y(n-r) получим разные типы сверток: циклическую и линейную.

Если такие значения находятся из свойства N-периодичности (цикличности) последовательностей x(n) и y(n), то полученная свертка называется циклической.

При этом говорят, что индекс n-i понимается по модулю N, что как раз и означает, если i-n=k+pN, то x(i-n)=x(k),y(i-n)=y(k). Чтобы отметить этот факт, аргумент n-i заключают в двойные скобки, помечая их одновременно нижним индексом N:

Следующий рисунок иллюстрирует сущность циклической свертки,

Рис.1 Циклическая свертка. Члены последовательности y(i) располагаются в обратном порядке по отношению к x(i) порядке, причем напротив y(i) располагается x(0). Одно значение h(i) получается суммированием всех попарных произведений противостоящих значений.

Отметим еще один важный факт, касающийся дискретной циклической свертки.

В силу N-периодичности последовательностей x(n) и y(n) и свертка их будет также периодична с периодом N. Действительно

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

Если положить, что вне пределов 0....N-1 последовательности x(n) и y(n) равны нулю, и, следовательно x(i-n) и y(i-n) равны нулю при отрицательных значениях

То полученная форма свертки называется линейной.

На рис.2 иллюстрируется, как вычисляется линейная свертка.

Рис.2 Линейная свертка. Индексы последовательности y(i) возрастают в направлении убывания индексов последовательности x(i). Одно значение h(i) получается суммированием всех попарных произведений пересекающихся противостоящих значений.

При этом, в отличие от циклической, можно производить свертку последовательностей различной длины. Длина линейной свертки будет равна N 1 +N 2 -1.

Действительно, для вычисления n-го элемента линейной свертки находятся произведения элементов сворачиваемых последовательностей, сумма индексов которых равна n. Поэтому минимальный индекс линейной свертки равен 0, а максимальный - N 1 -1+N 2 -1=N 1 +N 2 -2 и количество элементов N 1 +N 2 +1.

Вычисление линейной свертки последовательностей длины N 1 и N 2 можно свести к вычислению циклической свертки, если дополнить обе последовательности до длины N 1 +N 2 -1 добавлением нулей.

Пример 1: Вычислить линейную свертку последовательностей

{x(n)}={1 2 3 4} и {y(n)}={5 4 3 2 1 }. Ответ:

Пример 2: Вычислить циклическую свертку последовательностей:

{x(n)}={1,2,-1,3} и {y(n)}={-1,1,4,1}.

h(0)=x(i)y(-i)=x(0)y(0)+x(1)y(-1)+x(2)y(-2)+x(3)y(-3)= x(0)y(0)+x(1)y(3)+x(2)y(2)+

h(1)=x(i)y(1-i)=x(0)y(1)+x(1)y(0)+x(2)y(-1)+x(3)y(-2)= x(0)y(1)+x(1)y(0)+x(2)y(3)

h(2)= x(r)y(2-r) = x(0)y(2)+x(1)y(1)+x(2)y(0)+ x(3)y(-1) = x(0)y(2)+x(1)y(1)+x(2)y(0)+ x(3)y(3) = 10

h(3)= x(r)y(3-r) = x(0)y(3)+x(1)y(2)+x(2)y(1)+ x(3)y(0) =

При этом учтено, что согласно свойству периодичности

4-х точечной последовательности y(n) с периодом N=4, y(-l)=y(4-l).

Пример 3: Вычислить циклическую и линейную свертки последовательностей:

{x(n)}={1,1,1,1} и {y(n)}={1,1,1,1}.

Теорема 1 .

x(n)*y(n)~X(k)Y(k). (14)

Другими словами, свертка временных последовательностей x(n) и

y(n) длины N эквивалентна умножению их образов ДПФ.

Доказательство:

Используя определение прямого ДПФ (9a), дискретной свертки (12) и

свойства сдвига ДПФ 2.1, получим:

Теорема 2.

x(n)~X(k) , y(n)~Y(k), где n,k=0,1,.....N-1.

x(n)y(n)~X(k)*Y(k). (15)

Доказательство:

При этом мы воспользовались определением прямого и обратного ДПФ (7-9),

свойством ортогональности комплексных экспонент на системе равноотстоящих точек (4), а также определением свертки.

7 .8 Двумерное дискретное преобразование Фурье.

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

Двумерное ДПФ определяется следующим образом:

Массив данных образует матрицу размером,т.е.

Рассмотрим в выражении (16) внутреннюю сумму, которая определяется как

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

Коэффициенты в (20) можно записать в форме матрицы размером

В результате подстановки (20) в (16) имеем

Это означает, что коэффициенты получаются путем вычисления ДПФ каждой строки матрицы , определенной выражением (21).

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

Из этих рассуждений следует, что двумерное ДПФ можно рассматривать как кратное использование одномерного ДПФ.

Это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в 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 на и получим:

Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:

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

В литературе принято писать множитель в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:

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