Книга по вейвлетам / glava21

N -ой

N -ой

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

Врезультате дискретизации непрерывного колебания f (t) получается дискретная последовательность f [n]. Предположим, что эта последова-

тельность имеет конечную длину			N .	Ее можно	рассматривать как дис-
кретный	сигнал,	заданный	при	всех	n Z , причем	при
n [0, N −1]	f [n]= 0 ,	или как периодическую функцию с периодом				N ,

т.е. f (n) = f (n + lN ), l Z . В зависимости от этого будут иметь место различные дискретные преобразования Фурье: дискретное во времени преобразование Фурье или дискретно-временные ряды Фурье.

В дискретных преобразованиях особое значение имеет корень

− j2π

степени из единицы N1 = e N и обозначаемый как WN . Корень

степени из единицы обладает следующими очевидными свойствами:

WNN = 1,

(2.4а)

WNkN +i = WNi при k ,i Z ,					(2.4б)
N −1	N , n = lN ,		l Z ,	.	(2.4в)
∑WNkn =		0, в других	случаях.
k =0

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

Рассмотрим последовательность {f [n]}n Z . Дискретное во времени

преобразование Фурье (обозначается как DTFT – Discrete-Time Fourier

Transform) имеет вид:

F (e jω )= ∑∞	f [n]e− jω n ,	(2.4.2a)
n=−∞

78

где аргумент e jω введен для того, чтобы не путать это преобразование с

преобразованием Фурье (2.2.1б).

Легко проверить, что F (e jω )− 2π -периодическая функция, так как

e− jω n = e− j(ω+2π l )n . Тогда, в соответствии с выражением (2.1.2a) для коэф-

фициентов ряда Фурье этой функции получим:

	f [n] =	1	π∫ F (e jω )e jω n dω .	(2.4.2б)
		2π
			−π

Достаточным условием для сходимости ряда (2.4.2a) является абсолютная суммируемость последовательности f [n], т.е.

∑ f [n] < ∞ .

n z

Если это условие выполняется, то ряд сходится единственным обра- зом к непрерывной функции от ω . Если последовательность f [n] квадра-

тично суммируемая, то имеет место сходимость в среднеквадратическом. Предположим, что f [n] = e jωon , где DTFT такого комплексного коле-

бания с учетом периодичности имеет вид

F (e jω )= ∑∞ e− j(ω−ωo +2π n) .

(2.4.3)

n=−∞

На основании (2.3.6б), получим

∞

e jωon ↔ 2π ∑δ (ω −ωo + 2π n).

n=−∞

Вформулах (2.4.2а-в) частота ω , вообще говоря, не имеет размерно-

сти. Но часто возникает необходимость выразить спектр последовательно- сти f [n] в единицах частоты, связанных с интервалом дискретизации ∆t , т.е. рассматривать f [n] = f (n∆t ).

В соответствии с (2.3.18) и (2.3.19) Фурье-преобразование дискрети-

зированного колебания

79

	(ω ) =	∞	f (n∆ )e− jn∆tω =	1	∞			2π
F		∑				F	ω −		k ,	(2.4.4)
				∆				∆
∆			t		∑ c
		n=−∞		t k=−∞				t

где для удобства спектр непрерывного колебания обозначен как Fc (ω ).

С другой стороны, рассматривая (2.4.2а) в точках n∆t , будем иметь

			∞					∞
	F (e jω ∆t )= ∑ f (n∆t				)e− jn∆tω		= ∑f		[n]e − j2π nω ωs		(2.4.5а)
			n=−∞				n=−∞
и, используя (2.4.4), получим
	jω t∆	1	∞		2π		ω	∞
F (e	t )=		∑ Fc	ω −		k =	s	∑Fc		(ω − kωs ).	(2.4.5.б)
		∆			∆		2π
		t	k=−∞		t			k=−∞

Вформулах (2.4.4) и (2.4.5) частота ω выражается в радиа-

нах/секунду, функция F (e jω∆t )					периодична по частоте ω	с периодом
ωs	=	2π	. Формула обращения (2.4.2.б) будет иметь вид
		∆t
			f [n] =	1	ω∫s F (e jω )e− j2π ω ωs .	(2.4.5в)
			ωs
					−ωs

Приведем два важных свойства DTFT. Возьмем две последовательно- сти g[n] и f [n] и пусть их DTFT будут, соответственно, G(e jω ) и F (e jω ),

тогда свертка:

	∞
	f [n] g[n] = ∑f [(n − l)]g[l] =
	l=−∞	(2.4.6)
	∞
	= ∑f [l]g[n − l]↔ F(e jω )G(e jω ).
	l=−∞

При тех же обозначениях, что и выше, справедливо соотношение Парсева-

ля:
∞		π
∑ f [n]g[n] =	1	∫ F(e jω )G (e jω )e jω dω .	(2.4.7)
	2π
n=−∞		−π

80

	В частности, при g[n]= f [n]
	∞						π
	∑		f [n]		2 =	1	∫		F (e jω )	2dω .
						2π
	n=−∞
							−π

2.4.2. Дискретно-временные ряды Фурье

Рассмотрим теперь периодическую последовательность f0 [n] с пе- риодом N такую, что f0 [n] = f0 [n + lN ], l Z . Эта последовательность об-

разована периодическим продолжением последовательности конечной длины f [n] на всю ось (рис. 2.6), т.е.

∞

f0 [n] = ∑f [n − lN ].

l=−∞

Такая дискретная во времени функция представима рядом Фурье, а само

преобразование обозначается как DTFS (Discrete-Time Fourier Series). Из

формулы (2.1.1а) для ряда Фурье при t = n∆t					имеем
				∞		2π
		fo (n∆t ) = fo (n) = ∑F0 [k]e jk					n∆t .
						T
			k =−∞
	Предположим, что в периоде T умещается N отсчетов функции f (t),
т.е.	T	= N , тогда
	∆
	t
		∞	2π k n	∞
		fo (n∆t ) = ∑Fo [k]e j		= ∑Fo (k )WNk n .
			N					(2.4.8)
		k=−∞		k=−∞

81

Рис. 2.6.

Периодизация дискретной последовательности f [n]

В выражении (2.4.8) частоты спектральных составляющих, образующих

f [n], принимают дискретные значения ωk

=

2πk

. Легко проверить, что

N

j

2π

kn

= e

j

2π

(k±mN )n

e N

N

,

W kn

= W (k ±mN )n .

N

N

Тогда (2.4.8) можно переписать как

∞ N

∞

2π

N −1

[n] =

[n] W

(k±mN )n =

− j

[k]W nk .

f

o

F

∑

e

N mNn

F

∑∑ o

N

∑ o

N

m=o k=o

m=−∞

k=o

Первая сумма при любом значении n		равна единице, поэтому ее можно
опустить:
N −1		]WNnk .
fo [n] = ∑Fo	[k		(2.4.9а)

k=o

Иногда пользуются другим выражением для f0 [n], отличающимся ко-

эффициентом, а именно

N −1

fo [n] = 1 ∑Fo [k]WNnk . (2.4.9б)

N k=o

Чтобы найти коэффициенты F0 [k], умножим (2.4.9б) слева и справа на WN−nm и просуммируем результат по n :

82

N −1

∑ fo [n]WN−mn n=o

	N −1	N −1
=	F	[k]	W n(k−m) .
	∑ o	∑	N
	k =o	n=o

Учитывая, что

N −1		n(k −m)	N ,
	W
∑		N	=
			O,
n=o

получим окончательно

при

при

k = m, k ≠ m,

N −1

Fo [m] = 1 ∑ fo [n]WN−mn . (2.4.10)

N n=o

Следует отметить, что эту же формулу можно получить из (2.1.1б),

заменяя интеграл интегральной суммой.

Из (2.4.9) и (2.4.10) следует, что обе последовательности периодичны с периодом в N отсчетов. Из (2.4.9) и (2.4.10) следует, кроме того, важный

вывод о том, что коэффициенты DTFS полностью определяются одним пе- риодом f0 [n] и, наоборот, коэффициенты DTFS конечной длины одно-

значно определяют саму последовательность. Итак, хотя все соотношения

DTFS выведены для периодических последовательностей, ими можно пол-

ностью представлять последовательности конечной длины. На этом осно-

вании преобразования (2.4.9а-б) и (2.4.10) иногда называют просто дис-

кретным преобразованием Фурье (DFT – Discrete Fourier Transform), имея ввиду, что в вычислениях по этим формулам вместо периодических после-

довательностей f0 [n] и F0 [n] участвуют последовательности	конечной
длины f [n] и F[n].
DTFS (так же как и DFT) обладают теми же свойствами, что и класси-
ческое преобразование Фурье. Напомним некоторые из них.
Линейность. Если f0 [n] и g0 [n] – две периодические последователь-
ности (с периодом N отсчетов) и F0 [k] и G0 [k] – их DTFS, то:
fo [n]+ go [n]↔ Fo [k]+ Go [k].	(2.4.11)

83

Это же справедливо и для DFT.

Сдвиг.

Для

периодической

последовательности

вида

f0 [n − n0 ]

справедливо следующее

f

o

[n − n

o

]↔ F

[k]W −n0k (2.4.12)

o

N

Естественно, что в силу периодич-

ности

целесообразно

рассматривать

сдвиг

на

величину

n0 < N .

Нетрудно

показать, что DFT сдвинутой последова-

тельности (конечной длины)

f [n − n0 ]

получается

путем

кругового

сдвига

Рис. 2.7.

элементов последовательности

f [n] на

Круговой сдвиг последовательности

n0

отсчетов. Круговой сдвиг имеет ме-

а) исходная последовательность;

б) сдвинутая последовательность

сто,

когда

в

результате

сдвига

при n0 = 3

последние

элементы

последователь-

ности f [n] становятся соответственно

первыми

в последовательности

f [n − n0 ], что иллюстрируется на рис. 2.7.

Свертка. Свертка двух периодических последовательностей стано-

вится теперь круговой (периодической) сверткой:
N −1	N −1
fo [n]* go [n] = ∑ f0	[n − l]g[l] = ∑ f [(n − l)mod N ]g[l].
l=o	l=o

Здесь последовательность f [n], также как и выше, сдвигается "по кругу",

давая название свертке. Для свертки справедливо соотношение:

fo [n] go [n] = f [n] p g[n]↔ F[k]G[k],

(2.4.13)

где индекс ( p ) обозначает круговую свертку.

Формула Парсеваля. Для формулы Парсеваля справедливо, как и прежде,

84

	N −1			N −1
	∑ f [n]g[n] =		1	∑F[k]G [k].	(2.4.14)
			N
	n=0			k=0
	Коэффициенты DTFS могут быть получены из DTFT следующим образом.
	Пусть F (e jω ) – DTFT последовательности конечной длины				f [n]. Сравни-
	вая (2.4.2а) и (2.4.10), получим
	∞			N −1
	F (e jω )= ∑ f [n]e	− jω n = ∑ fo [n]e− jω n .
	n=−∞			n=o

Отсюда следует, что

Fo [k] = F (e jω )ω =k 2π / N .

Таким образом, мы имеем с учетом (2.4.9б) и последнего равенства

f [n] =

∞

f [n − lN ] =

1

N −1 F [k]e j

2π

nk

=

N

∑

N

o

∑

o

l=−∞

k=o

(2.4.15)

N −1

2π

2π

1

=

∑

F e j

k

e j

kn .

N

N

N k =o

Сравнивая (2.4.15) и (2.3.12) можно видеть, что (2.4.15) является дис-

кретно-временной версией формулы суммирования Пуассона. Для точки

n = 0 из (2.4.15) получим

∞				N −1		2π
∑ f [lN ] =		1		∑F e j			k	.
						N
	N
l=−∞				k=o
Напомним, что здесь f [n] –			последовательность конечной длины

n = 0,1,2,..., N −1, а F e

j	2π	k		2π
			– ее DTFT, при ω =
	N				k .
				N

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

кретные) переменных время-частота.

85

Таблица 2.1. Фурье-преобразования с различными комбинациями непрерывно-

го/дискретного времени и частоты. Аббревиатурой СТ и DТ обозначены непрерывное и дискретное время, а FT и FS – преобразование Фурье и ряды Фурье соответственно.

Другие обозначения: С, D – непрерывные или дискретные переменные; Р – периодиче-

ский сигнал; ωs – частота дискретизации, ωs =

2π

∆t

Преобразование

Время

Частота

Анализ, синтез

а) Фурье-

С

С

F (ω ) = ∫ f (t )e− jωt dt

преобразование

f (t) =

t

∫ F (ω )e dω

1

CTFT

jωt

2π

ω

б) Ряд Фурье CFTS

C

D

F[k] =

1

T / 2

P

∫ f (t)e− j2πkt / T dt

T

−T / 2

f (t) = ∑F[k ]e j2πkt / T

k

в) Дискретное

D

C

F [e

jω

]=

∑F[k]e

− j2π nω /ωs

во времени преоб-

P

n

ω / 2

разование Фурье

f [n] =

1

s∫ F (e jω )e− j2π nω /ωs dω

DTFT

ω

s

−ωs / 2

г) Дискретный

D

D

N −1

во времени ряд

P

P

F[k] = ∑ f [n]e− j2πnk / N

n =0

Фурье DTFS

f [n] =

1

N −1

∑F[k]e− j2πnk / N

N

k =0

Различные виды преобразований Фурье иллюстрируются на рис. 2.8.

86

Рис. 2.8.

Преобразование Фурье при различных комбинациях непрерывно- го/дискретного переменных времени и частоты.

а) Непрерывное во времени преобразование Фурье (формулы 2.2.1 - CTFT). б) Непрерывный во времени ряд Фурье (формулы 2.2.1 - CTFS).

в) Дискретное во времени преобразование Фурье (формулы 2.4.2 - DTFT). г) Дискретный во времени ряд Фурье (формулы 2.4.9, 2.4,10 - DTFST)

87