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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	2π k (n + ϕ k )
x = ∑ C k cos		(ряд Фурье)
x = ∑ C k cos		(ряд Фурье)
k = 0

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

	2 π kn		2 π kn
x = ∑ A k cos	2 π kn	+ ∑ B k sin	2 π kn	(ряд Фурье)
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 комплексных коэффициентов спектра будут совпадать со спектром «обычного» действительного ДПФ, представленным в «комплексном» виде, а остальные коэффициенты будут их симметричным отражением относительно

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

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

(2)

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

(3)

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

(4)

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

, (5)

Только функции sin и cos c частотами k/T будут взаимно ортогональны, а это является непременным условием преобразования Фурье. Набор первых функций разложения в ряд Фурье приведен на рисунке 1. При этом длительность функций совпадает с длительностью анализа T .

Рисунок 1. Функции разложения в ряд Фурье

Теперь спектр сигнала будет выглядеть так, как это показано на рисунке 2.

Рисунок 2. Спектр функции x (t ) при анализе на ограниченном интервале времени

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

(6)

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

(7)

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

(8)

Теперь рассмотрим как изменились свойства дискретного преобразования Фурье (ДПФ) по сравнению с прямым преобразованием Фурье на ограниченном интервале времени. Когда мы рассматривали дискретизацию аналогового сигнала, мы выяснили, что спектр входного сигнала должен быть ограничен по частоте. Это требование ограничивает количество дискретных составляющих спектра сигнала. Первоначально может показаться, что мы можем ограничить спектр сигнала частотой f д /2, что соответствует количеству частотных составляющих K = N /2 . Однако это не так. Несмотря на то, что спектр сигнала для действительных отсчетов сигнала для положительных частот и отрицательных частот симметричен относительно 0, отрицательные частоты могут потребоваться для некоторых алгоритмов работы со спектрами, например, для . Еще больше отличие получается при выполнении дискретного преобразования Фурье над комплексными отсчетами входного сигнала. В результате для полного описания спектра цифрового сигнала требуется N частотных отсчетов (k = 0, ..., N/2 ).

Исследуем особенности спектрального представления дискретного сигнала, который задан на отрезке своими отсчётами
, взятыми соответственно в моменты времени
; полное число отсчётов
(- интервал дискретизации).

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

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

Воспользуемся моделью в виде последовательности дельта-импульсов. Тогда исходное колебание будет выражено формулой:

(5.1)

Где
– выборочные значения аналогового сигнала.

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

Основные свойства ДПФ

1. ДПФ- линейное преобразование т.е. сумме сигналов отвечает сумма их ДПФ

2. Число различных коэффициентов
, вычисляемых по формуле (5.4), равно числу N за период; при коэффициент

3. Коэффициент (постоянная составляющая) является средним значением всех отсчётов:

5. Пусть отсчётные значения – вещественные числа. Тогда коэффициенты ДПФ, номера которых располагаются симметрично относительно /2, образуют сопряжённые пары:

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

Таким образом, получаем формулу для вычисления отсчётных значений

(5.5)

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

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

=0, 1, 2,…,( /2)-1 (5.7)

Учтём, что последовательности коэффициентов, относящихся к чётной и нечётной частям входного массива, являются периодическими с периодом N/2:

Кроме того, входящий в формулу (5.7) множитель при
можно преобразовать так:

Отсюда находим выражение для второй половины множества коэффициентов ДПФ

(5.8)

Формулы (5.7) и (5.8) лежат в основе алгоритма БПФ. Далее вычисления строят по итерационному принципу: последовательности отсчётов с чётными и нечётными номерами вновь разбивают на две части. Процесс продолжают до тех пор, пока не получается последовательность, состоящая из единственного элемента. ДПФ этого элемента совпадает с ним самим.

Число операций, необходимых для вычисления БПФ оценивается как
.

Выигрыш в скорости вычислений по сравнению с традиционным ДПФ достигает сотен и даже тысяч при достаточных длинах входных массивов.

12.. Z - преобразование и его свойства. Применение Z - преобразования.

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

Пусть
– числовая последовательность, конечная или бесконечная, содержащая отсчётные значения некоторого сигнала. Поставим ей в однозначное соответствие сумму ряда по отрицательным степеням комплексной переменнойZ:

(5.9)

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

Данное выражение имеет смысл при |Z|> .

Обратное Z- преобразование

Пусть x(z) – функция комплексной переменной Z. Замечательное свойство Z-преобразование состоит в том, что функция x(z) определяет всю бесконечную совокупность отсчётов (
).

Действительно, умножим обе части ряда (5.9) на множитель
:

Интегралы от всех слагаемых правой части обратятся в нуль, за исключением слагаемого с номером m, поэтому:

(5.11)

Данное выражение носит название обратное Z-преобразование.

Важнейшие свойства Z -преобразования:

1. Линейность . Если
и
- некоторые дискретные сигналы, причём известны соответствующиеZ-преобразования x(z) и y(z), то сигналу
будет отвечать преобразованиепри любых постоянныхи. Доказательство проводится путём подстановки суммы в формулу (5.9).

2. Z -преобразование смещённого сигнала . Рассмотрим дискретный сигнал
, получающийся из дискретного сигнала
путём сдвига на одну позицию в сторону запаздывания, т.е. когда
. Непосредственно вычисляяZ-преобразование, получаем следующий результат:

Таким образом, символ
служит оператором единичной задержки (на один интервал дискретизации) вZ-области.

3. Z -преобразование свёртки . Пусть x(z) и y(z) – непрерывные сигналы, для которых определена свёртка:

(5.13)

Применительно к дискретным сигналам по аналогии с (5.13) принято вводить дискретную свёртку
– последовательность чисел общий член которой:

Подобную дискретную свёртку называют линейной

Вычислим Z-преобразование дискретной свёртки:

(5.15)

Итак, свёртке двух дискретных сигналов отвечает произведение Z-преобразований.

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

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 Двумерное дискретное преобразование Фурье.

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

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