Tài liệu Luận văn thạc sĩ toán học biến đổi fourier nhanh và ứng dụng

  • Số trang: 72 |
  • Loại file: DOC |
  • Lượt xem: 64 |
  • Lượt tải: 0
hoangtuavartar

Tham gia: 05/08/2015

Mô tả:

ĐẠ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 -