Biến đổi fourier rời rạc part 2

Các biểu thức từ (6.29) đến (6.36) cho kết quả trong bước thứ ba của thuật toán và biểu diễn trong lưu đồ hình 6.4.Mỗi phần tử từ F30(n) đến F37(n) có thể chia tiếp thành hai phần tử nữa và bước này tạo thành sơ đồ cuối cùng (bước đầu tiên) trong lưu đồ.
Nội dung trích xuất từ tài liệu:
Biến đổi fourier rời rạc part 2 -4n (6.35) F23 (n)  F36 (n)  W16 F37 (n) -4n (6.36) F23 (n  2)  F36 (n) - W16 F37 (n) ë ®©y 1 F30 (n)   f 30 ( k )W2 nk (6.37) k 0 3 F31 (n)   f 31 ( k )W2 nk (6.38) k 0 ..., vv. C¸c biÓu thøc tõ (6.29) ®Õn (6.36) cho kÕt qu¶ trong b­íc thø ba cña thuËt to¸n vµ biÓu diÔn trong l­u ®å h×nh 6.4.Mçi phÇn tö tõ F30(n) ®Õn F37(n) cã thÓ chia tiÕp thµnh hai phÇn tö n÷a vµ b­íc nµy t¹o thµnh s¬ ®å cuèi cïng (b­íc ®Çu tiªn) trong l­u ®å. X(k) W-2n X(k) HÖ sè xoay n=0 ®Õn 3 0 0 1 1 F20(n) 2 2 3 3 F10(n) 0 4 0 1 5 2 F21(n) 2 6 4 3 7 6 0 0 1 1 F22(n) 2 2 3 3 F11(n) 0 4 0 1 F23(n) 5 2 2 6 4 3 7 6 85 H×nh 6.3 B­íc thø hai sau b­íc cuèi cïng trong thuËt to¸n FFT. 86 X(k) X(k) 0 F30(n) 1 0 0 F31(n) 1 D·y 0 ®Çu 0 1 F32(n) vµo 0 ®· 0 1 ®­îc F33(n) 0 s¾p 1 0 xÕp 0 F34(n) l¹i 1 0 0 F35(n) 1 0 0 F36(n) 1 0 0 1 F37(n) 0 H×nh 6.4 B­íc ®Çu tiªn cña l­u ®å FFT. H×nh 6.5 giíi thiÖu s¬ ®å thuËt to¸n FFT cho N = 16. Chó ý r»ng do yªu cÇu ban ®Çu cña ch­¬ng tr×nh mµ d·y vµo ®­îc s¾p xÕp l¹i vµ chøa ë X(k), vÝ dô X(k)  x(q) k = 0 ®Õn 15 B¹n sÏ chó ý trªn s¬ ®å r»ng q lµ gi¸ trÞ bit cña k. Cho N = 24 = 16 chóng ta ph¶i cã bèn b­íc trong l­u ®å. Trong mçi b­íc cÇn ph¶i cã t¸m b­ím. Trong mçi b­ím chØ cã mét phÐp nh©n phøc, hai phÐp céng hoÆc trõ phøc. Tæng sè phÐp nh©n phøc lµ 8/2 . 4. Tæng qu¸t cho N = 2r sè phÐp nh©n phøc lµ (N/2) . r = (N/2 ) log2 N vµ sè phÐp céng lµ Nlog2N. Chó ý, thùc tÕ sè phÐp nh©n sÏ gi¶m xuèng mét Ýt, v× trong b­íc ®Çu t ...