ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------***------------
TRẦN QUỐC HỘI
BIẾN ĐỔI FOURIER
NHANH VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên – Năm 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------***------------
TRẦN QUỐC HỘI
BIẾN ĐỔI FOURIER NHANH
VÀ ỨNG DỤNG
Chuyên nghành: Toán ứng dụng
Mã số: 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. NGUYỄN VĂN NGỌC
Thái Nguyên – Năm 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------***------------
TRẦN QUỐC HỘI
BIẾN ĐỔI FOURIER
NHANH VÀ ỨNG DỤNG
Chuyên nghành: Toán ứng dụng
Mã số: 60.46.36
TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên – Năm 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Công trình được hoàn thành tại
TRƯỜNG ĐẠI HỌC KHOA HỌC - ĐẠI HỌC THÁI NGUYÊN
Người hướng dẫn khoa học: TS. NGUYỄN VĂN NGỌC
Phản biện 1.
…………………………………………………………………………………………
……………………………..…………………………………………………………..
Phản biện 2.
…………………………………………………………………………………………
……………………………..…………………………………………………………..
Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn họp tại
TRƯỜNG ĐẠI HỌC KHOA HỌC - ĐẠI HỌC THÁI NGUYÊN
Ngày…….tháng…….năm 2010
Có thể tìm hiểu luận văn tại: Trung tâm học liệu Đại học Thái Nguyên
Thư viện trường Đại học Khoa Học
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1
Möc löc
Möc löc . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Mð đ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chương 1. Bi¸n đêi Fourier ríi r¤c
1.1. Căn bªc N cõa đơn và và các tính ch§t . . . . . . . . . .
1.1.1. Đành nghĩa . . . . . . . . . . . . . . . . . . . . .
1.1.2. Các tính ch§t cõa WN . . . . . . . . . . . . . . .
1.2. Hàm ríi r¤c tu¦n hoàn trong không gian Unita CN . . .
1.3.
1.4.
1.5.
1.6.
1.7.
1.8.
1.2.1. Hàm ríi r¤c tu¦n hoàn . . . . . . . . . . . . . . .
1.2.2. Không gian Unita CN . . . . . . . . . . . . . . .
Bi¸n đêi Fourier ríi r¤c cõa dãy tu¦n hoàn . . . . . . . .
1.3.1. D¨n luªn . . . . . . . . . . . . . . . . . . . . . .
1.3.2. Đành nghĩa bi¸n đêi Fourier ríi r¤c . . . . . . . .
Công thùc bi¸n đêi Fourier ríi r¤c ngưñc cõa dãy tu¦n hoàn
Các tính ch§t cõa bi¸n đêi Fourier ríi r¤c đèi vîi dãy tu¦n
hoàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1. Tính tuy¸n tính. . . . . . . . . . . . . . . . . . .
1.5.2. Tích chªp. . . . . . . . . . . . . . . . . . . . . . .
1.5.3. Đ¯ng thùc Parseval . . . . . . . . . . . . . . . . .
1.5.4. Tính tu¦n hoàn . . . . . . . . . . . . . . . . . . .
1.5.5. Dàch chuyºn và bi¸n đi»u . . . . . . . . . . . . . .
Các ví dö . . . . . . . . . . . . . . . . . . . . . . . . . .
Bi¸n đêi Fourier ríi r¤c cõa dãy không tu¦n hoàn có chi·u
dài húu h¤n . . . . . . . . . . . . . . . . . . . . . . . . .
Bi¸n đêi cosine và sine ríi r¤c . . . . . . . . . . . . . . .
1.8.1. Đành nghĩa bi¸n đêi ríi r¤c têng quát . . . . . . .
1.8.2. Các phép bi¸n đêi DCT - 1 và DCT - 2 . . . . . .
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http:////wwwlrc- tn/uldwulnn/
1
3
6
7
7
7
8
8
9
11
11
12
13
14
14
14
16
16
17
18
21
22
22
23
2
Chương 2. Bi¸n đêi Fourier nhanh
25
2.1. Thuªt toán bi¸n đêi Fourier nhanh rút gån theo thíi gian
k
đèi vîi N = 2 . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Mô t£ thuªt toán FFT . . . . . . . . . . . . . . .
2.1.2. Sơ đç thuªt toán FFT theo thíi gian đèi vîi N = 23
2.2. Hi»u qu£ tính toán cõa thuªt toán FFT . . . . . . . . .
2.3. Thuªt toán Fourier nhanh rút gån theo t¦n sè . . . . . .
2.3.1. Nëi dung cõa thuªt toán rút gån theo t¦n sè . . .
2.3.2. Sơ đç thuªt toán FFT theo t¦n sè vîi N = 23 . .
2.4. Bi¸n đêi Fourier nhanh đèi vîi trưíng hñp N = RC . . .
2.4.1. Trưíng hñp N = 6 = 3.2 . . . . . . . . . . . . . .
2.4.2. D¤ng nhân tû FFT têng quát . . . . . . . . . . .
Chương 3. Mët sè ùng döng
3.1. Gi£i phương trình vi phân thưíng . . . . . . . . . . . . .
3.2. Bài toán biên Dirichlet cho phương trình Helmholz . . .
3.2.1. Đ°t bài toán . . . . . . . . . . . . . . . . . . . . .
3.2.2. Ríi r¤c hóa bài toán . . . . . . . . . . . . . . . .
3.2.3. Fourier ríi r¤c cà Fourier nhanh . . . . . . . . . .
3.3. Tín hi»u ti¸ng hót . . . . . . . . . . . . . . . . . . . . . .
3.3.1. Đành nghĩa . . . . . . . . . . . . . . . . . . . . .
3.3.2. Các tính ch§t cơ b£n . . . . . . . . . . . . . . . .
3.4. Mët sè h» thèng tuy¸n tính trong lý thuy¸t tín hi»u sè .
K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tài li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . .
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
26
26
28
28
31
31
33
33
34
36
39
39
41
41
41
42
43
43
44
47
61
62
3
Mð đ¦u
Lñi ích cõa xû lý sè các tín hi»u ngày càng đưñc kh¯ng đành rõ
ràng. Nó cũng đưñc ùng döng ð nhi·u d¤ng khác nhau vîi nhúng
hi»u qu£ đ°c bi»t là trong các ngành khoa håc chù không ph£i
ch¿ là mët môn håc. Vîi mùc đë phát triºn ngày càng cao v· cơ b£n,
v· phương pháp và kh£ năng ùng döng nó đã lôi cuèn đưñc nhi·u kÿ
sư, các nhà vªt lý cũng như các nhà toán håc quan tâm nghiên cùu.
Trong lĩnh vüc xû lý tín hi»u, bi¸n đêi Fourier ríi r¤c (DFT) chi¸m và
trí hàng đ¦u nhí sü tçn t¤i các thuªt toán hi»u qu£ cõa bi¸n đêi Fourier
ríi r¤c. Bi¸n đêi Fourier nhanh (FFT) là công cö húu hi»u đº tính các
bi¸n đêi Fourier ríi r¤c và Fourier ríi r¤c ngưñc. Thuªt toán F F T đưñc
ùng döng trong nhi·u lĩnh vüc khác nhau, tø các phép toán sè håc cõa
sè phùc đ¸n lý thuy¸t tín hi»u, lý thuy¸t nhóm và lý thuy¸t sè.v.v...
Tø khi Cooley và Tukey phát hi»n ra thuªt toán tính nhanh các bi¸n
đêi Fourier ríi r¤c vào năm 1965 (ngưíi ta quen gåi là bi¸n đêi Fourier
nhanh - FFT), thuªt toán này ngày càng kh¯ng đành vai trò cõa mình,
đ°c bi»t là xû lý tín hi»u sè. Đº tính DFT chi·u dài N c¦n sè phép nhân là
2
N và N(N − 1) phép toán cëng. Thíi gian tính toán s³ r§t đáng kº n¸u N
đõ lîn. Mët thuªt toán nhanh hơn nhi·u đã đưñc phát triºn bði Cooley và
Tukey kho£ng năm 1965 gåi là thuªt toán FFT. Đòi häi b-t buëc thuªt
s
toán này là chi·u dài N ph£i là lũy thøa cõa 2, tùc là N có d¤ng N = 2 .
Thuªt toán này düa vào trên vi»c khai triºn bi¸n đêi Fourier ríi r¤c cõa
s
dãy có chi·u dài N = 2 thành các t¦ng lîp nhä hơn. Cách mà trong đó
nguyên t-c này thüc hi»n đưa đ¸n nhi·u thuªt toán khác nhau, t§t c£ đ·u
có möc đích là c£i thi»n kh£ năng tăng tèc đë tính toán. Đó là thuªt
toán FFT phân tích theo thíi gian, thuªt toán FFT phân tích theo t¦n
sè.v.v... Đèi vîi các thuªt toán FFT chi·u dài N thì ch¿ c¦n
phép toán nhân và N log2N phép cëng. Ngoài ra, còn
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
N
2 log2N
4
trình bày thuªt toán bi¸n đêi Fourier nhanh cho trưíng hñp N = RC,
trong đó R ho°c C không ph£i là lũy thøa cõa 2. Đèi vîi thuªt toán
bi¸n đêi Fourier nhanh cho trưíng hñp N = RC thì ch¿ c¦n N(R + C)
phép nhân.
Luªn văn trình bày cơ sð lý thuy¸t cõa bi¸n đêi Fourier ríi r¤c và
cõa thuªt toán Fourier nhanh. Ngoài ra, cũng giîi thi»u mët sè ùng
döng cõa bi¸n đêi trên vào các bài toán v· phương trình vi phân
thưíng, bài toán biên Dirichlet cõa phương trình Poisson trong hình
chú nhªt, xû lý tín hi»u ti¸ng hót trong Rada. Ngoài ra, luªn văn trình
bày mët sè bài toán v· hàm h» và tín hi»u đ¦u ra cõa các h» thèng
tuy¸n tính trong lý thuy¸t tín hi»u sè.
Hi»n nay tài li»u b¬ng ti¸ng Anh v· DFT và FFT r§t phong phú. Tuy
nhiên, tài li»u b¬ng ti¸ng Vi»t v· lĩnh vüc này còn r§t h¤n ch¸ và chõ
y¸u đưñc trình bày trong các sách kÿ thuªt dành cho các kÿ sư.
Ngoài ph¦n mð đ¦u, ph¦n k¸t luªn, luªn văn gçm 3 chương.
Chương 1 Bi¸n đêi Fourier ríi r¤c.
Trong chương này trình bày lý thuy¸t cõa bi¸n đêi Fourier ríi r¤c cho
dãy sè tu¦n hoàn.
Chương 2 Bi¸n đêi Fourier nhanh.
Trong chương này trình bày hai thuªt toán bi¸n đêi Fourier nhanh, đó
là thuªt toán bi¸n đêi Fourier nhanh rút gån theo thíi gian và thuªt
toán bi¸n đêi Fourier nhanh rút gån theo t¦n sè. Ngoài ra, trình bày
thuªt toán bi¸n đêi Fourier nhanh cho trưíng hñp N = RC, trong đó R
ho°c C không ph£i là lũy thøa cõa 2.
Chương 3 Mët sè ùng döng.
Trong chương này trình bày mët sè ùng döng cõa bi¸n đêi Fourier ríi
r¤c vào các bài toán v· phương trình vi phân thưíng, bài toán biên
Dirichlet cõa phương trình Poisson trong hình chú nhªt. Xû lý tín
hi»u ti¸ng hót trong Rada và mët sè bài toán v· hàm h» và tín hi»u
đ¦u ra cõa các h» thèng tuy¸n tính trong lý thuy¸t tín hi»u sè.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
Luªn văn này đưñc hoàn thành vîi sü hưîng d¨n và ch¿ b£o tªn
tình cõa TS. Nguy¹n Văn Ngåc - Vi»n Toán Håc Hà Nëi. Tø đáy lòng
mình, em xin đưñc bày tä lòng bi¸t ơn sâu s-c đèi vîi sü quan tâm,
đëng viên và sü ch¿ b£o hưîng d¨n cõa th¦y.
Tôi xin c£m ơn tîi các Th¦y Cô trong Trưíng Фi Håc Khoa Håc Фi Håc Thái Nguyên, phòng Đào T¤o Trưíng Фi Håc Khoa Håc.
Đçng thíi tôi xin gûi líi c£m ơn tîi tªp thº lîp Cao Håc Toán K2 Trưíng
Фi Håc Khoa Håc đã đëng viên giúp đï tôi trong quá trình håc tªp và
làm luân văn này.
Tôi xin c£m ơn tîi Sð GD - ĐT T¿nh L¤ng Sơn, Ban Giám hi»u,
các đçng nghi»p Trưíng THPT Vũ L¹ - B-c Sơn, Trưíng THPT Vi»t
B-c - TP. L¤ng Sơn đã t¤o đi·u ki»n cho tôi håc tªp và hoàn thành k¸
ho¤ch håc tâp.
Tuy nhiên do sü hiºu bi¸t cõa b£n thân và khuôn khê cõa luªn văn
th¤c sĩ, nên ch-c r¬ng trong quá trình nghiên cùu không tránh khäi
nhúng thi¸u sót, tôi r§t mong đưñc sü ch¿ d¤y và đóng góp ý ki¸n
cõa các Th¦y Cô và đëc gi£ quan tâm tîi luªn văn này.
Thái Nguyên, ngày 10 tháng 9 năm
2010
Tác gi£
Tr¦n Quèc Hëi
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
Chương 1
Bi¸n đêi Fourier ríi r¤c
Trong chương này trình bày lý thuy¸t cõa bi¸n đêi Fourier ríi r¤c
cho dãy sè tu¦n hoàn. Nëi dung chõ y¸u cõa chương này đưñc hình
thành tø các tài li»u [1], [2], [3] và [8].
Mð đ¦u
1
Bi¸n đêi tích phân Fourier cõa hàm f(t) ∈ L (R) thưíng đưñc đành
nghĩa bði công thùc
ˆ
Z ∞
f(t)e
f (ω) =
−iωt
dt,
ω ∈ R,
−∞
còn bi¸n đêi Fourier ngưñc đưñc cho bði công thùc
f(t) =
1Z∞
2π
iωt
fˆ(ω)e dω.
−∞
Mët trong các phương pháp tính g¦n đúng các tích phân trên có
thº ti¸n hành như sau. Trưîc h¸t ta gi£ thi¸t r¬ng vîi các sè a, b có trà
tuy»t đèi đõ lîn: a < 0, b > 0 tích phân
Z b
a
f(t)e
−iωt
dt,
là x§p x¿ tèt cõa tích phân Fourier. Tø đó đi đ¸n đành nghĩa bi¸n đêi
Fourier ríi r¤c.
Trong chương này trình bày mët sè tính ch§t cõa bi¸n đêi Fourier
ríi r¤c.
Tø nay v· sau ta luôn luôn hiºu N là sè nguyên dương, z là sè
N
phùc liên hñp cõa sè phùc z, còn Z là tªp các sè nguyên. Ký hi»u R
N
và C tương ùng là các không gian vectơ thüc và phùc.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
1.1.
1.1.1.
Căn bªc N cõa đơn và và các tính ch§t
Đành nghĩa
N
Đành nghĩa 1.1.1. Nghi»m cõa phương trình z − 1 = 0 đưñc gåi là
căn bªc N cõa đơn và.
Trong lý thuy¸t sè phùc ta bi¸t r¬ng đơn và có N căn bªc N khác
nhau và chúng đưñc xác đành bði công thùc
k
(k = 0, 1, ..., N − 1),
(1.1)
εk = W N ,
2πi
2π
2π
=
cos
+
i
sin
WN = e N
,
N
N
(1.2)
2
trong đó i là đơn và £o: i = −1. D¹ th§y r¬ng ε1 = WN . Công thùc
(1.2), như chúng bi¸t là công thùc Euler. Sau này chúng ta s³ gåi W N
là h¤ch Euler.
1.1.2.
Các tính ch§t cõa WN
M»nh đ· 1.1.1. H¤ch Euler WN có các tính ch§t cơ b£n sau đây
kN
(1.3)
1) WN = 1,
2) WN WN = 1,
k
3) WN = WN
−k
(1.4)
N +k
= WN
= WN
N −k
,
k(N −n)
4) WN
= WNkn,
5) WNkn = WNk(n+N ) = WN(k+N )n,
2
N −1
6) 1 + WN + WN + ...WN
= 0,
1 N −1
1, n¸u n = pN,
X
6
WNmn =
7) N
(
0,
(1.5)
(1.6)
(1.7)
(1.8)
n¸u n = pN.
(1.9)
m=0
Chùng minh. Các tính ch§t tø 1) đ¸n 5) là hiºn nhiên. Tính ch§t 6) là
trưíng hñp đ°c bi»t cõa tính ch§t 7), vì vªy ta ch¿ c¦n chùng minh
tính ch§t 7). Thªt vªy, ta có
N
WN = e
2πi
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
= 1.
http://www.lrc-tnu.edu.vn
8
1
N −1
X
N
1
WN
mpN
1
= N
m=0
N −1
N X
W mn =
N
m=0
N WN
N mp
X
(WN )
m=0
1 . WN
n
N −1
1
N −1
Nn
−1
− 1
=
X
N
1 = 1.
m=0
= 0, (n = pN).
6
Vªy công thùc (1.9) đưñc chùng minh.
1.2.
1.2.1.
Hàm ríi r¤c tu¦n hoàn trong không gian Unita C
N
Hàm ríi r¤c tu¦n hoàn
Cho N là mët sè nguyên dương cè đành. Khi đó måi sè nguyên m
∈ Z đ·u có thº biºu di¹n ð d¤ng
m = n + kN,
n = 0, 1, ..., N − 1,
k ∈ Z.
Đành nghĩa 1.2.1. Cho hàm ríi r¤c f(m) vîi m ∈ Z. Hàm f(m) đưñc
gåi là hàm tu¦n hoàn chu kỳ N, n¸u vîi måi m = n + kN thì
f(n + kN) = f(n),
n = 0, 1, 2, ..., N − 1, k ∈ Z.
Tªp xác đành cõa các hàm ríi r¤c bi¸n sè nguyên tu¦n hoàn chu kỳ
N đưñc ký hi»u là ZN là nhóm cyclic cõa các sè nguyên theo
modulo sè nguyên dương N
ZN = Z/(N) (Z modulo N); (N) = {kN : k ∈ Z}.
Tªp hñp cõa các hàm ríi r¤c bi¸n sè nguyên tu¦n hoàn chu kỳ N đưñc
ký hi»u là L(ZN ).
D¹ th§y r¬ng hàm
m
ω(m) := WN = e
m2πi/N
, m∈Z
là hàm tu¦n chu kỳ N. Thªt vªy, vîi m = n + kN ta có
ω(n + kN) = e(n+kN )2πi/N = en2πi/N ek2πi = en2πi/N = ω(n).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
1.2.2.
Không gian Unita C
N
Đành nghĩa 1.2.2. Gi£ sû f, g là nhúng hàm tu¦n hoàn ríi r¤c trong không
N
N
gian C . Trong C , ta đành nghĩa tích vô hưîng hay là tích ngoài
N −1
Xk
< f, g >=
f(k)g(k).
(1.10)
=0
Chu©n cõa ph¦n tû f đưñc xác đành theo công thùc
||f|| =
Xét các hàm
ω j( m ) = W −jm =
N
p
< f, f >.
e−jm2πi/N ,
(1.11)
m, j
, , , ..., N − 1
=012
và các vectơ
uj = √
=
1
(ωj(0), ωj(1), ..., ωj(N − 1))
N
√
1
N
, √
1
N
e−2πij.1/N , √
1
N
e−2πij.2/N , ..., √
1
e−2πij.(N
.
−1)/N
N
Bê đ· 1.2.1. Các hàm uj, j = 0, 1, ..., N − 1 là cơ sð trüc chu©n cõa
N
không gian Unita C .
Chùng minh. Trưîc h¸t ta chùng minh tính trüc chu©n cõa h» {uj}.
Ta -ó
||uj|| =< uj, uj >2 =
n=0
1
N −1
X
−
e
√N
2πjn/N
N −1
√ N
e 2πjn/N
1
2
=
n=0
N −1
X
N
1
1
N −1
WN(k−j)n.
< uj , uk >=
= 1.
2
(1.12)
u j (n).u k (n) =
X
X
n=0
n=0
Theo công thùc (1.9), tø (1.12) suy ra
< uj, uk >= 0, j 6= k.
Ta chùng minh hå {uj, j = 0, 1, ..., N − 1} là đëc lªp tuy¸n tính trong
N
C . Thªt vªy, xét đ¯ng thùc
couo + c1u1 + ... + cN −1uN −1 = 0, cj ∈ C, j = 0, 1, ..., N − 1.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
Đã bi¸t
uj = √
1
= √
ωj(0), ωj(1), ..., ωj(N − 1)
N
1
N
0
−j
−j(N −1)
(WN , WN , ..., WN
),
nên ta có h»
c0 + c1 + c2 + ... + cN −1 = 0, c0 +
−1
−2
c1WN
−(N −1)
−2(N −1)
c0 + c1WN
−(N −1)
+ c2WN ... + cN −1WN
+ c2WN
= 0,
lllllllllllllllllllllllllllllllll
−(N −1)(N −1)
... + cN −1WN
= 0.
H» trên có d¤ng Ac = 0, trong đó: c = (c0, c1, ..., cN −1)T nà
1
1
WN
WN
1
1
2
A= 1
N
.
1
.
W
.
2
W
.
N
4
.
N −1
...WN
...1
. . . N2(N −1)
W
.
.
..
.
W (NN −1) W 2(NN −1) . . . W (NN −1)(N −1)
T
Ma trªn A là ma trªn đèi xùng nên c = (c0, c1, ..., cN −1) = 0, do đó
hå {uj, j = 0, 1, ..., N − 1} là đëc lªp tuy¸n tính.
Đành lý 1.2.1. Måi vectơ f ∈ CN , tu¦n hoàn chu kỳ N phân tích đưñc
thàn/h tên/g
N −1
Xj
f=
(1.13)
< f, uj > uj.
=0
Chùng minh. Vì hå các vectơ {uj} là cơ sð trüc chu©n trong không gian
Unita CN , nên måi vectơ f ∈ CN phân/ t-h đưñ- thdo -ơ sð, wo đó ta -ó
N −1
Xj
f=
(1.14)
Cjuj.
=0
L§y tích ngoài hai v¸ cõa (1.14), ta có (1.13).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
1.3.
Bi¸n đêi Fourier ríi r¤c cõa dãy tu¦n hoàn
1.3.1.
D¨n luªn
Bi¸n đêi tích phân Fourier cõa hàm f(t) ∈ L 1(R) thưín/g đưñ- đàn/h n/ghĩa bði
-ôn/g thù-
Z∞
ˆ
f (ω) =
f(t)e
−iωt
dt, ω ∈ R,
(1.15)
−∞
còn bi¸n đêi Fourier ngưñc đưñc cho bði công thùc
∞
1
f(t) =
(1.16)
2π Z fˆ(ω)eiωtdω.
−∞
Các tích phân (1.15), (1.16) nói chung là không thº tính đưñc ð d¤ng
đóng. Mët trong các phương pháp tính g¦n đúng các tích phân trên
có thº ti¸n hành như sau. Ta ch¿ xét tích phân (1.15). Trưîc h¸t ta gi£
thi¸t r¬ng vîi các sè a, b có trà tuy»t đèi đõ lîn: a < 0, b > 0 tích phân
Zb
−iωt
f(t)e dt, (1.17)
a
là x§p x¿ tèt cõa tích phân (1.15). Đº tính g¦n đúng tích phân (1.17)
ta phân ho¤ch đo¤n [a, b] bði các điºm
to = a < t1 < t2 < .... < tN −1 = b.
Đ°t
b−a
t=
,
N
tk = a + k t,
k = 0, 1, ..., N.
ˆ
Khi đó x§p x¿ Φ cõa f đưñc cho bði công thùc
N −1
N −1
X
Φ(ω) =
k=0
Đ°t
Xk
−iωt
f(tk)e
k
t = e−iaω
=0
f(tk)e−iωk(b−a)/N t.
(1.18)
2πn
ωn = b − a , n = 0, 1, ..., N − 1
và trong (1.18) cho ω = ωn, ta đưñc
−iaω b − a N −1
Φ(ωn) = e
n
N
Xk
f(tk)e−i2πkn/N .
=0
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
(1.19)
12
Biºu thùc ð v¸ ph£i cõa (1.19) d¨n đ¸n bi¸n đêi sau đây
N −1
Xk
FN [f](n) =
(1.20)
f(tk)e−i2πkn/N .
=0
Công thùc (1.20) d¨n đ¸n bi¸n đêi Fourier ríi r¤c dưîi đây.
1.3.2. Đành nghĩa bi¸n đêi Fourier ríi r¤c D¤ng
dãy cõa bi¸n đêi Fourier ríi r¤c.
Đành nghĩa 1.3.1. Chúng ta đành nghĩa bi¸n đêi Fourier ríi r¤c (DFT)
cõa hàm tu¦n hoàn f(n) chu kỳ N như sau
N −1
Fn ) = F
(
N
[
fk n )=
( )](
Xk
fkW
−kn
()
n = 0 , , , ..., N − 1 .
12
,
N
(1.21)
=0
Chúng ta cũng sû döng ký hi»u
f(k) ↔N F (n).
Chú ý 1.3.1. Ngoài công thùc (1.21) bi¸n đêi Fourier ríi r¤c còn đưñc
đành nghĩa bði công thùc
1 NX−1
k
Fn
F fk n
f k W −kn, n
, , , ..., N
.
N
=0
( ) = N [ ()](
()
=0 1 2
−1
) = √N
(1.22)
D¤ng ma trªn cõa bi¸n đêi Fourier ríi r¤c.
Ký hi»u f và FN[f] rà -á- nd-tơ
f(1)
FN [f](0)
FN [f](1)
f(0)
.
f = f(N
.
1),
FN[f] =
1
1
1
1
W
.
−
.
FN [f](..N − 1)
và ma trªn
WN =
W
2
1
W
.
.
.
..
.
.
1
4
...W
N −1
...1
. . . W 2(N −1)
,
W
.
WN
2
.
−1
W
2(N −1)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
...W
(N −1)(N −1)
http://www.lrc-tnu.edu.vn
13
trong đó W = WN = e2πi/N . Sû döng các tính ch§t cõa WN ta có thº
bi¸n đêi ma trªn WN n· w¤n/g
2
W
W
1
. . . W N −1
1
1
1
...1
2
WN = 1
.
4
W
W
.
.
.
..
.
.
.
.
N
1 W
N −2
...
W
.
−
1
N 2
−
W
, W = WN .
(1.23)
.
...W
Khi đó ta có d¤ng ma trªn cõa bi¸n đêi Fourier ríi r¤c
(1.24)
FN[f] = WNf.
1.4.
Công thùc bi¸n đêi Fourier ríi r¤c ngưñc cõa dãy tu¦n hoàn
Trong möc này s³ trình bày mët sè đành lý v· công thùc bi¸n đêi
Fourier ríi r¤c ngưñc.
Đành lý 1.4.1. Gi£ sû f(k) là hàm ríi r¤c tu¦n hoàn chu kỳ N. Vîi
bi¸n đêi Fourier ríi r¤c
N −1
X
Fn
(
)
=FN [f
n
k
fk
]( ) =
= 0 ,1 , ..., N − 1
(1.25)
, m = 0, 1, ..., N − 1.
(1.26)
W −kn, n
()
N
=0
N −1
ta có
1
f(m) =
N
X
mn
n=0
F (n)WN
Chùng minh. Nhân hai v¸ cõa (1.25) vîi WNnm/N rçi l§y têng hai v¸
theo n tø 0 đ¸n N − 1, ta đưñN −1
1 N −1
1 N −1
X
N
F (n)W
nm
N
X
=
n=0
N −1
=
f(k)
1 N −1
N
=0
N
X
f(k)W
−kn
N
=0
n=0
N −1
n(m−k)
WN
Xk
Xk
W nm
N
f(k)δ mk .
=
X
k=0
n=0
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
(1.27)
14
Theo công thùc (1.9) têng bên trong ð v¸ trái cõa (1.28) b¬ng ký
hi»u Kronecker δmk. Do đó ta có
N −1
1 N −1
X
=0
nm
X
k
f(k)δmk =
N
F (n)WN .
n=0
Tø đây suy ra công thùc (1.26). Công thùc (1.26) đưñc gåi là công
thùc bi¸n đêi Fourier ríi r¤c ngưñc cõa bi¸n đêi Fourier ríi r¤c (1.25).
Trong kÿ thuªt công thùc (1.25) thưíng đưñc gåi là công thùc phân
tích, còn công thùc (1.26) đưñc gåi là công thùc têng hñp.
Chú ý 1.4.1. N¸u bi¸n đêi Fourier ríi r¤c đưñc đành nghĩa bði công thùc
(1.25) thì bi¸n đêi Fourier ríi r¤c ngưñc đưñc xác đành theo công thùc
f(m) = √
1.5.
1
N −1
N
n=0
X
mn
F (n)WN
, m = 0, 1, ..., N − 1.
(1.28)
Các tính ch§t cõa bi¸n đêi Fourier ríi r¤c đèi vîi dãy tu¦n hoàn
Các tính ch§t sau đây cõa bi¸n đêi Fourier ríi r¤c đưñc suy ra tø
đành nghĩa.
1.5.1.
Tính tuy¸n tính.
Rõ ràng là FN và FN
1.5.2.
−1
là các ánh x¤ tuy¸n tính.
Tích chªp.
Đành nghĩa 1.5.1. Tích chªp cõa các hàm f, g ∈ L(Z N ) đưñc ký hi»u
là f ∗ g nà đưñ- xá- đàn/h thdo -ôn/g thù-
N −1
Xk
f ∗ g(m) =
f(k)g(m − k).
=0
M»nh đ· 1.5.1. Gi£ sû f, g, h ∈ L(ZN ). Khi đó
a)
b)
c)
f ∗ g = g ∗ f,
f ∗ δ = f, trong đó δ là tín hi»u xung ,
f ∗ (g ∗ h) = (f ∗ g) ∗ h,
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
(1.29)
15
λ(f ∗ g) = (λf) ∗ (λg), ∀λ = const,
f ∗ (g + h) = f ∗ g + f ∗ h.
d)
e)
Chùng minh. a). Theo đành nghĩa tích chªp ta có
N −1
k−N +1
X
f ∗ g(k) =
X
f(k − m)g(m)
f(j)g(k − j) =
j=0
m=k
−(N −1)
N −1
X
=
m=0
X
f(k − m)g(m) = (g ∗ f)(k).
f(k − m)g(m) =
m=0
b) Ta có
N −1
X
f ∗ δ(k) =
f(j)δ(k − j) = f(1)δ(k − 1) + f(2)δ(k − 2) + ...
j=0
+ f(k)δ(k − k) + ... + f(N − 1)δ(k − N + 1) = f(k)δ(0) = f(k),
nghĩa là
f ∗ δ = f,
∀f ∈ L(ZN ).
Các tính ch§t c)-e) đưñc chùng minh tương tü.
M»nh đ· 1.5.2. Vîi måi f, g ∈ L(ZN ) có đ¯ng thùc
FN [f ∗ g](n) = FN [f](n)FN [g](n).
(1.30)
Chùng minh. 1 Theo đành nghĩa ta có
N −1
F [f ∗ g](n) =
N
f g(k)W
k=0
∗
−kn
N
N −1 N −1
=
k=0
X
f(j)g(k − j)
XX
N −1
N −1
X
X
−kn
=
f(j)g(k − j)WN
j=0
N −1
=
j=0
X
f(j)WN
j=0
k=0
N −1
−jn
X
g(k − j)WN
k=0
= FN [f](n)FN [g](n).
−(k−j)n
−nk
WN
- Xem thêm -