Материал: Фарфоровская Ю. Б. Математика. Дискретное и быстрое преобразование Фурье

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«САНКТ-ПЕТЕРБУРГСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ им. проф. М. А. БОНЧ-БРУЕВИЧА»

Ю. Б. Фарфоровская, Е. Л. Рабкин

МАТЕМАТИКА

ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

СПбГУТ)))

САНКТ-ПЕТЕРБУРГ

2013

УДК 51(077) ББК 22.1я73 Ф25

Рецензент заведующий кафедрой высшей математики СПбГЭТУ,

доктор физико-математических наук Н. А. Бодунов

Рекомендовано к печати редакционно-издательским советом СПбГУТ

Фарфоровская, Ю. Б.

Ф25 Математика. Дискретное преобразование Фурье и быстрое преобразование Фурье : методические указания / Ю. Б. Фарфоровская, Е. Л. Рабкин ; СПбГУТ. – СПб., 2013. – 32 с.

Написаны в соответствии с рабочим планом дисциплины «Математика».

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

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

210700, 230400, 231000.

УДК 51(077) ББК 22.1я73

©Фарфоровская Ю. Б., Рабкин Е. Л., 2013

©Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича», 2013

2

3

ВВЕДЕНИЕ

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

ДПФ используется и для сжатия (компрессии) информации, передаваемой по каналам связи. Огромное значение имеет возможность быстрого вычисления свертки двух временных последовательностей. (В этом случае ДПФ этой свертки вычисляется как покоординатное произведение двух ДПФ от каждой из последовательностей). Это позволяет «быстро» решать очень важную «обратную» задачу, а именно, быстро находить последовательность, круговая свертка которой с данной последовательностью дает требуемую последовательность (то есть, грубо говоря, это означает, что можно быстро находить «переходную характеристику» предполагаемого устройства). Именно это мы рассматриваем как пример применения ДПФ в п. 4. Разумеется, мы не можем здесь коснуться всех многочисленных приложений ДПФ. Наша цель – дать математический аппарат основных понятий ДПФ, не касаясь огромного количества алгоритмов, связанных с реальными применениями ДПФ.

4

1. ОПРЕДЕЛЕНИЕ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (ДПФ) И ЕГО ПРОСТЕЙШИЕ СВОЙСТВА

Пусть имеется пространство последовательностей комплексных чисел длины п, которое будем обозначать Сn. Тогда элементы этого пространства

являются п-мерными векторами при этом вектор z = {z1, z2, …, zn} где zk – комплексные координаты вектора Z.

Естественным образом здесь определяются две линейные операции:

а) сложение векторов – при сложении векторов соответствующие координаты складываются, т. е. z + w = {z1 + w1, …, zn + wn};

б) умножение на комплексное число αz = {αz1, αz2,…, αzn}.

Эти две линейные операции обладают привычными свойствами линейных операций (можно их перечислить).

Более того, в Сп можно ввести скалярное произведение. Именно, если

n

z, w Cn , то (z, w) zk wk , где wk – комплексные числа, сопряженные с wk,

и что wk имеет тот же модуль, что и wk, а аргумент отличается знаком. Можно доказать следующие свойства скалярного произведения:

1)(z, w) (w, z) ; если z и w – вещественны, то (z, w) = (w, z);

2)(αz1+βz2, w) = α(z1, w) + β(z2, w); (z, w1 w2 ) (z, w1) (z, w2 ) .

Следствие: постоянный множитель из 1-го множителя выносится сам,

аиз 2-го сомножителя – как сопряженное число.

k 1

–нулевой вектор: z = 0 = {0, 0, …, 0} – нулевой вектор.

4)Неравенство Коши-Буняковского: модуль скалярного произведения не превосходит произведения модулей сомножителей, т. е.

5