Основы вычислительной математики. Денисова Э.В - 148 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

Глава 10
БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ
§1. Дискретное преобразование Фурье
1.1 Дискретное преобразование Фурье (ДПФ) — это одно из преобразований Фурье, широко
применяемых в алгоритмах цифровой обработки сигналов (его гомоморфизмы применяются в сжатии звука в
mp3, сжатие изображений в jpg и др.), а также в других областях, связанных с анализом частот в дискретном
(к примеру, оцифрованном аналоговом) сигнале. Также дискретные преобразования Фурье помогают решать
частные дифференциальные уравнения и
выполнять такие операции, как свёртки. Преобразования бывают
одномерные, двумерные и даже трехмерные.
Последовательность
N действительных чисел x
0
, ..., x
N−1
преобразовывается в последовательность из N
комплексных чисел
X
0
, ..., X
N−1
с помощью дискретного преобразования Фурье по формуле:
1,...,0
1
0
2
−==
∑
−
=
−
NkexX
N
n
kn
N
i
nk
π
где
i - это мнимая единица. Обратное дискретное преобразование Фурье задается формулой
1,...,0
1
2
1
0
−==
∑
−
=
NneX
N
x
kn
N
i
N
k
kn
π
Вывод преобразования
Рассмотрим некоторый периодический сигнал x(t) c периодом равным T. Разложим его в ряд Фурье:
T
k
ectx
k
ti
k
k
k
π
ω
ω
2
,)( ==
∑
+∞
−∞=
Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в
виде отсчетов:
x
n
= x(t
n
), где , тогда ряд Фурье запишется следующим образом:
∑∑
+∞
−∞=
+∞
−∞=
==
k
kn
N
i
k
k
ti
kn
ececx
nk
π
ω
2
Используя соотношение:
, получаем:
∑∑
+∞
−∞=
+
−
=
==
l
lNkk
kn
N
i
N
k
kn
cXeXx ,
2
1
0
π
Таким образом, мы получили обратное дискретное преобразование Фурье.
Умножим теперь скалярно выражение для
x
n
на и получим:
nmk
N
i
N
k
N
n
k
mn
N
i
N
n
n
eXex
)(
2
1
0
1
0
2
1
0
−
−
=
−
=
−
−
=
∑∑∑
=
ππ
Откуда следует, что:
kn
N
i
N
n
nk
ex
N
X
π
2
1
0
1
−
−
=
∑
=
Эта формула описывает прямое дискретное преобразование Фурье.
В литературе принято писать множитель
в обратном преобразовании, и поэтому обычно пишут формулы
преобразования в следующем виде:
k
N
i
N
k
kn
N
i
N
n
nk
eX
N
xexX
ππ
2
1
0
2
1
0
1
,
∑∑
−
=
−
−
=
==

Страницы