Дискретное преобразование фурье. Свойство комплексной сопряженности. Многомерное преобразование Фурье

Введение

На лабораторном занятии были изучены возможности по дискретному тригонометрическому преобразованию (ДТП) со следующих точек зрения:

1. Проверили свойство обратимости заданного ДТП.

2. Исследовали линейность предложенного ДТП.

3. Изучили особенности повтора спектра у проверяемого ДТП.

4. Определили наличие симметричного отражения спектра у ДТП, а именно

4.1. наличие центральной симметрии,

4.2. наличие осевой (вертикальной) симметрии.

5. Рассмотрели влияние фазовых сдвигов сигнала на результирующее ДТП.

6. Проверили наличие свойства подобия для заданного преобразования.

7. Исследовали возможность фильтрации сигналов с помощью заданного ДТП.

8. Проверили экспериментально сохранение энергии исследуемым ДТП.

9. Обнаружили связь данного ДТП с дискретным преобразованием Фурье.

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

Наиболее известным среди дискретных функциональных преобразований является дискретное преобразование Фурье (ДПФ)

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

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

ДПФ служит для анализа периодических функций, и его можно получить исходя из теории рядов Фурье. Пусть x0(t) - непрерывная периодическая функция с периодом Р и частотой f0 = 1/P так что

Функцию x0(t) можно разложить в ряд Фурье:

где коэффициенты разложения Х0(n) заданы формулой

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

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

где n1 - целое значение n, задающее частоту f1.

На фиг. 1 показаны такой ограниченный спектр и колебание, которому он соответствует.

интервал дискретизации Т равен

так что число отсчетов на период будет

Фиг. 1. Периодическая функция x0(t) с ограниченной полосой частот и ее спектр X0(n).

1В результате дискретизации получаем периодическое, нормализованное относительно Т колебание вида

Это колебание определено на интервале, равном его периоду, т. е.

Поскольку x(t/T) – периодическая функция для расчета коэффициентов ряда Фурье используется соотношение (2)

(Замена Р на /V в делителе и пределах интегрирования соответствует переходу к нормализованной переменной.) Подставляя выражение (3), получаем

Известно, что

Окончательно с учетом того, что по определению

Соотношение, связывающее x(k) с Х(n), может быть получено непосредственно из формулы (1), если подставить t=kT и учесть, что при ограниченной ширине спектра функции x0(t) сумма содержит конечное число членов. Итак,

Следует заметить, что x(k) -периодическая функция, т. е.

и аналогично

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

Итак, при дискретизации периодической функции x0(t) соотношение (4) позволяет по выборкам x0(t) найти спектр Х(n), который на интервале 0 ≤ n ≤ N - 1 в точности равен спектру Х0(n) исходной периодической функции. Функция x(k) и ее спектр графически представлены на фиг. 2. Поскольку соотношение (5.4) получено на основании теоремы отсчетов, оно является точным и экономичным (при расчетах) эквивалентом исходного интегрального соотношения (2) и может быть использовано для вычисления коэффициентов разложения на ЭВМ. Соотношения (4) и (5) будем называть дискретным преобразованием Фурье (ДПФ) и обратным дискретным преобразованием Фурье (ОДПФ) соответственно. Заметим, что переменная n меняется здесь от нуля до N-1. Получаемый спектр можно интерпретировать следующим образом. Первые (N/2-1) точек Х(n) -соответствуют (N/2 - 1) спектральным линиям Х0(n) на положительных частотах, как показано на фиг. 5.3, а последние (N/2-1) точек Х(n) соответствуют (N/2-1) спектральным линиям на отрицательных частотах.

Пара преобразований, заданная соотношениями (4) и (5), встречается и в другом виде. Например, множитель 1 / N и знак минус у экспоненты могут быть записаны как в прямом, так и в обратном преобразовании, общий смысл при этом не меняется.

Естественно, спектр в этом случае нельзя непосредственно отождествлять с тем, который определен формулой (2). Иногда оба преобразования приводятся с одинаковыми множителями (1 / N)1/2.

Фиг. 2. Дискретизированная периодическая функция x(k) и ее периодический спектр Х(n).

Фиг. 3. Соотношение между коэффициентами ряда Фурье и ДПФ.

Свойства ДПФ

Некоторые свойства ДПФ играют в практических вопросах обработки сигналов важную роль.

Линейность

Если xр(n) и ур(n) - периодические последовательности (с периодом в N отсчетов каждая), а Хр(k) и Yp(k) - их ДПФ, то дискретное преобразование Фурье последовательности хр(n) + + ур(n) равно Хр(k) + Yp(k). Это положение справедливо и для последовательностей конечной длины.

Сдвиг

Если последовательность хр(n) периодическая с периодом в N отсчетов, а ее ДПФ равно Хр(k), то ДПФ периодической последовательности вида хр(n-n0) будет равно.

Фиг. 4. К определению ДПФ сдвинутой последовательности.

При анализе последовательностей конечной длины необходимо учитывать специфический характер временного сдвига последовательности. Так, на фиг. 4, а изображена конечная последовательность х (п) длиной в N отсчетов. Там же крестиками изображены отсчеты эквивалентной периодической последовательности хр(n), имеющей то же ДПФ, что и х(n). Чтобы найти ДПФ сдвинутой последовательности х(n - n0), причем n0 < N, следует рассмотреть сдвинутую периодическую последовательность Хр(n - n0) и в качестве эквивалентной сдвинутой конечной последовательности (имеющей ДПФ j принять отрезок последовательности хр(n - n0) в интервале 0 ≤ n ≤ N - 1. Таким образом, с точки зрения ДПФ последовательность х(n – n0) получается путем кругового сдвига элементов последовательности х(n) на n0 отсчетов

Свойства симметрии

Если периодическая последовательность хр(n) с периодом в./V отсчетов является действительной, то ее ДПФ Хр(k) удовлетворяет следующим условиям симметрии:

Аналогичные равенства справедливы и для конечной действительной последовательности х(n), имеющей N-точечное ДПФ X(k). Если ввести дополнительное условие симметрии последовательности хp(n), т. е. считать, что

то окажется, что Хр(k) может быть только действительной.

Поскольку чаще всего приходится иметь дело с действительными последовательностями, то, вычислив одно ДПФ, можно получить ДПФ двух последовательностей, используя свойства симметрии (6). Рассмотрим действительные периодические последовательности хр(n) и ур(n) с периодами в N отсчетов и N-точечными ДПФ Хр(k) и Yp(k) соответственно. Введем комплексную последовательность zp(n) вида

Ее ДПФ равно

Выделяя действительную и мнимую части равенства (10), получим

Действительные части Хр(k) и Yp(k) симметричны, а мнимые - антисимметричны, поэтому их легко разделить, используя операции сложения и вычитания:

Итак, вычисляя одно 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 ):

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

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

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

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

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

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

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

(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 ).

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

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

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

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

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

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

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

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

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

(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-преобразование, получаем следующий результат: