BIẾN ĐỔI FOURIER RỜI RẠC FOURIER NHANH VÀ ỨNG DỤNG
1. Tínhcấpthiếtcủađềtài
Nhiềuvấnđềtrong khoahọcvà công nghệđưađếnviệc giải phương trình vi phân hay phương trìnhđạohàm riêng. Những bài toánvềtínhđộlệchđứng củadầm, các daođộngcủadây, sóng âm, sóngtạora do thủy triều, sóng đàn hồi, sóngđiệntrường và tìm phương trìnhđườngđi cho các phương trình sóng. Vấnđềđặtraởđâylà tìmlờigiải cho các bài toánđó.Có nhiều phương pháp khác nhauđểgiải quyếtvấnđề,trongsốđókhôngthểkhông nóiđếnvai tròđặc biệt quan trọngcủaphép biếnđổiFourier.
Mộtkhái niệm không kémtầmquan trọngcủaphép biếnđổiFourier là biếnđổiFourierrờirạc(DFT). Trong toán học, biếnđổiFourierrờirạccònđược gọilà phép biếnđổiFourierhữuhạn, làmộtbiếnđổitrong giải tích Fourier với các tín hiệu trong thời gianrờirạc. Nó là côngcụlýtưởngđểxửlý thông tin vàđượcsửdụng rộng rãi trongxửlý tín hiệu và các ngành liên quanđếnphân tích tầnsố,tìm hình dạng đi lýtưởngcho phương trình truyền sóng, các bài toán sơcấp, ma trận và các phép toán như tích chập.
Việcứngdụng hiệuquảbiếnđổiFourierrờirạctrong thựctếđặcbiệt làviệc phân tíchphổnhư trong các ngànhxửlý tín hiệu tiếng nói,địachất,vậtlý, ytế,sóng âm, các bài toánvềma trận,phép nhân đa thức. . .ngườitađãquan tâmđếnviệc rút ngắn thời gian vàđộphứctạptính toán. Năm 1965, Cooley vàTukeyđãtìm ra thuật toán tính các biếnđổiFourierrờirạcnhanh chóng và hiệu quảhơnđượcgọilà biếnđổiFourier nhanh (FFT). BiếnđổiFourier nhanh làthuật toán cho phép tính DFT nhanh chóng bằng cách giảmđộphứctạpvà thời gian tính toán.Kểtừkhi rađời,biếnđổiFFTđãtạoramộtbướcngoặclớnvàthựcsựđóngmộtvai tròhếtsứcquan trọng trong việcxửlý tín hiệu, các bài toán ma trận và bài toán sơ cấp.
2.Mụctiêu nghiêncứu
Mụctiêucủađềtài là nhằm giúpngườiđọchiểu đúngbảnchấtcủabiếnđổi
2
Fourierrờirạc, hiệuquảcủabiếnđổiFourierrờirạcvà thuật toán FFTcủanó. Quađócóthểáp dụngđểtìmlờigiải chomộtsốbài toán sơ cấp, những bài toán liên quanđếnma trận và phương trình truyền sóng.Mộtsốđiểmcốgắngđưavào trong luận văn là:
-Mộtsốđịnhnghĩa liên quanđếnbiếnđổiDFT, chứng minh chặtchẽcácđịnhlí liên quan.
– Làm rõ tính hiệuquảcủabiếnđổinhanh FFT, đi sâumộtsốthuật toáncụthể.
-Đưanhiều vídụvà bàitậpáp dụngđểlàmnổibậttính hiệu quả, tính nhanh chóngcủabiếnđổiDFT và FFT.
3.Đốitượngvà phạm vi nghiêncứu
Đốitượngnghiêncứucủađềtài là phép biếnđổiFourier. Phạm vi nghiên cứucủađềtài là biếnđổiFourierrờirạc, Fourier nhanh vàứngdụng.
4. Phương pháp nghiêncứu
Thu thập các bài báo khoahọcvà tài liệucủacác tácgiảnghiêncứuliên quanđếnbiếnđổiDFT,vấnđềquan trọng trong khi áp dụng biếnđổiDFT vàFFT vào giải toán.
Tham gia các buổi seminarcủathầyhướngdẫnđểtraođổicáckếtquảđang nghiên cứu. Traođổiqua email, blog, forumvớicác chuyên giavềcácứngdụng củabiếnđổiDFT và FFT trong giải toán.
5.Bốcụccủađềtài
Luận văngồmphầnmởđầu,hai chương,kếtluận vàphụlục.
Chương 1 trình bàymộtsốtích chất cơbảncủabiếnđổiFourierrờirạc, Fourier nhanh.
Chương 2đưaramộtsốứngdụng cơbảncủabiếnđổiFourierrờirạcvàbiếnđổiFourier nhanh.
6. Tổng quan tài liệu nghiêncứu
Luận vănđãtham khảomộtsốtài liệu khoahọctiếng Việt và tiếng AnhvềbiếnđổiFourierđặcbiệt là biếnđổiFourierrờirạcvà Fourier nhanh. Hiện tại trong và ngoàinướcđãcó các công trình nghiêncứuvềbiếnđổiFourierrờirạc, biếnđổiFourier nhanh và cácứngdụng thựctếhữuíchcủachúng.
Tuy nhiên các công trình khoahọcvẫnchưa tổnghợpđượcnhiều cácứng
3
dụngcủabiếnđổiFourierrờirạc, biếnđổiFourier nhanh trong sơcấpvà trong thựctếhoặc có nhưngvẫncònhạnchế.
Vìvậyviệc nghiên cứu, tổnghợpcácứngdụngcủaphép biếnđổiFourier rờirạc, Fourier nhanhmộtcách rõ ràng,hệthống làcầnthiết.Kếtquảnghiên cứucủađềtàisẽgiúpngườihọctoándễdàng hơn trong việc hình dung tính hữuíchcủaphép biếnđổiFourier trong toánhọccũng như trong thực tiễn.
4
CHƯƠNG 1
KIẾN THỨC CHUẨNBỊ
1.1 BIẾNĐỔIFOURIERRỜIRẠC 1.1.1 Địnhnghĩa
Địnhnghĩa 1.1.1. Cho dãy x(n),n = 0, 1, .., N−1. KhiđóbiếnđổiFourier rờirạccủadãy x(n), viếttắtlà DFTđượcxácđịnhbởicông thức:
N−1
∑
n=0
, k = 0, 1, …, N−1. (1.1)
BiếnđổiFourierrờirạcngượcviếttắtlà IDFTđượcxácđịnhbởicông thức:
N−1
1
x(n) =
∑
N
X(k)WN−kn, n = 0, 1, …, N−1. (1.2)
k=0
−i2π.kn
ỞđâyWNkn = e N và eia
= cos a+isin a.
Vídụ1.1.1.
1.1.2 Biểu diễn DFTdướidạng ma trận
Địnhnghĩa ma trận Fourier
Mộtma trận vuôngcấpN mà phầntửthứ(k,n) là Wkn(0≤k,n≤N−1)đượcgọilà ma trận FouriercấpN, ký hiệu WN.Tứclà:
WN =
1 1 1 … 1 1 WN1 WN2 … WNN−1
. . . … .
1 WNN−1 WN2(N−1) … WN(N−1)(N−1)
.
5
BiếnđổiDFTdướidạng ma trận
Đặt:xN =
x(0)
x(1)
.
.
.
x(N−1)
; XN =
X(0) X(1)
.
.
.
X(N−1)
∗
1 1 1 … 1
1 WN−1 WN−2 … WN−(N−1)
WN = .
.
.
.
−(N−1)
. …
−(2(N−1))
.
−(N−1)(N−1)
.
1 WN WN … WN
KhiđóbiếnđổiDFTcủaXN và biếnđổingượcIDFTđượcviết lại:
1
XN =WN.xN; xN =
N
N.XN. W∗
Mệnhđề1.1.1.GọiWN−1là ma trận nghịchđảocủama trận WN. Khiđó:
WN−1= N1
Vídụ1.1.2.
.W∗.
Vídụ1.1.3. Giải Vídụ1.1.1 bằng cáchsửdụng ma trận Fourier.
Mệnhđề1.1.2. Cho vectơ x(n,1), tích WN.xđượcgọilà phép biếnđổiFourier
rờirạccủavectơ x và WN−1.x là phép biếnđổinghịchđảocủax. Phầntửởvịtrík trong WN.x và WN−1.xđượcxácđịnhbởicông thức:
N−1
[WN.x]k = xiwik
∑
i=0
Vídụ1.1.4.
1 N−1
; [WN−1.x]k = N i=0 xiw−ik
∑
.
1.1.3 BiếnđổiDFT cho toántửunita
Trướckia, biếnđổiDFT và biếnđổingượcIDFTcủadãy x(n)đượcviết dướidạng:
1 N−1
X(k) =√
∑
N n=0
x(n)WNkn, k = 0, 1, …, N−1. (1.5)
6
1 N−1
x(n) =√
∑
N k=0
X(k)WN−kn, n = 0, 1, …, N−1. (1.6)
1.1.4 Tính chấtcủabiếnđổiDFT
Tính tuần hoàn
Cho X(k)↔x(n), khiđóX(k) và x(n) tuần hoànvớichukỳNtứclà:
X(k+N) = X(k),∀k = 0, 1, …, N−1. x(n+K) = x(n),∀n = 0, 1, …, N−1.
Vídụ1.1.5.
Tính tuyến tính
Cho x1(n)↔X1(k) và x2(n)↔X2(k) thìvớimọia1,a2 ta có:
a1x1(n)+a2x2(n)↔a1X1(k)+a2X2(k).
Dịch vòng
Cho x(n)↔X(k) thì x(n+h)↔X(k).W−hk. Khiđóx(n+h)đượcdịch chuyển theo vòng trònvềbên tráibởikhoảng thời gian h trong miền thời gian.Ởđâyxn+k = (xh,xh+1,…, xN−1,x0,…, xh−1).
Vídụ1.1.6.
Độnkhông
Vềnguyên tắc, chiều dài L và chiều dài NcủabiếnđổiDFT cóthểkhác nhau.HầuhếtcácvấnđềvềDFTđềugiảsửL = N. Tuy nhiên không nhất thiếtđiềunày luônxảyra.
NếuL < N ta cóthểđộnN – Lsố0ởcuốicủabảnghidữliệuđểnó có chiều dài N.Độnbấtkỳsố0 nào vào phần đuôicủatín hiệuđềukhôngảnhhưởnggìđếnbiếnđổiDFT.
NếuL > N ta cóthểgiảm chiều dàicủabảnghi thành N theokỹthuật rút gọnmodN.
Đểcóđượcphép chập không tròn hoặc không tuần hoàncủahai dãy (một dãy có chiều dài L và dãy khác có chiều dài M) bằng cáchsửdụng phương pháp
7
biếnđổiDFT hay IDFT, ta thấy hai dãy phảiđộn0 vào phần đuôicủachúng vàsao cho chiều dài lúc này là L+M−1≤N. Hiệuquảthểhiện rõ trong miền tần số.
Cho (x(n)) = (x0,x1,…, xM−1), dãy MđiểmđượcđộnN−Msố0 vào x(n), khiđódãy sau khiđộnlà: (xe(n)) = (x0,x1,…, xM−1,0, …, 0).ỞđâyXe(n) = 0, M≤n≤N−1.
Và DFTcủa(xe(n)) là:
N−1
Xe(k) = xe(n)WNnk
|
n=0
M−1
= x(n)WNnk
|
(k = 0, 1, …, N−1).
n=0
Vídụ1.1.7.
1.1.5 Mộtsốđịnhlí liên quan
Địnhlý 1.1.1.(Địnhlí Parseval)
Tính chất này đúngvớimọibài toán biếnđổiunita
N−1 1 x(n)x∗(n) =
|
n=0 N
N−1
X(k)X∗
|
n=0
(k). (1.9)
Khiđónănglượngcủadãy x(n)đượcbảotồntrongmọibiếnđổiDFT.
Địnhlý 1.1.2.(Địnhlísốphức liên hợp)
Cho DFT Nđiểm,khi x(n) là chuỗi thực, ta có:
N
X(
2
N
+k) = X∗(
2
N
−k), k = 0, 1, …,
2
.
Địnhlý 1.1.3.Địnhlí chập
Cho x(n),y(n) là hai dãy thựcvớichukỳN. Chập vòngcủachúng ký hiệu là x(n)∗y(n)đượcchobởicông thức:
1
Zcon(m) =
N
N−1
x(n)y(m−n), (m = 0, 1, …, N−1) (1.10)
|
n=0
8
=x(n)∗y(n).
Trong miền Fourierrờirạc,điềunày tươngđươngvới:
1
Zcon(k) =
N
X(k)Y(k).
Ởđâyx(n)↔X(k),y(n)↔Y(k) và Zcon(m)↔Zcon(k).
Địnhnghĩa 1.1.2. (Tích chập giữa hai vectơ)
a0
Cho hai vectơ: a = a .1
an−1
b0
và b = b .1
bn−1
. Tích chập giữa hai vectơ
a và b làmộtvectơ ký hiệu là [a∗b] mà các phầntửcủanóđượcxácđịnhbởi
công thức: [a∗b]k =∑ki=0aibk−i (k = 0, 1, …, 2n−1).Ởđâyan = an+1 = … =
a2n−1= bn = bn+1 = … = b2n−1= 0. Khiđó:
[a∗b] =
a0b0 a0b1+a1b0
a0b2+a1b1+a2b0
…. an−2bn−1+an−1bn−2
an−1bn−1
0
.
a0
Địnhnghĩa 1.1.3. Cho hai vectơ: a = a .1
an−1
b0
; b = b .1
bn−1
.
Tích trongcủahai vectơ a và b làmộtvectơ ký hiệu là a×b vàđượcxác
địnhbởicông thức: a×b =
a0b0 a1b1
a2b2
.
.
.
an−1bn−1
F:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\LUAN VAN KY THUAT\LUAN VAN 2014\LUAN VAN TOAN SO CAP\NGUYEN THI THU THUY
