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

Chia sẻ: Asg Ahsva | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

51
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 đồ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 lu ®å 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 lu ®å. 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 lu ®å 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 lu ®å. 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 tiªn hÖ sè xoay W0 = 1 vµ trong c¸c bíc cßn l¹i chóng ta còng cã c¸c bím víi hÖ sè xoay = 1. 87
Xem xÐt trêng hîp N = 1024 = 210. Sè phÐp nh©n cÇn dïng cho FFT lµ (N/2).10 = 1024  5 = 5120 so víi 1 triÖu phÐp nh©n cho tÝnh trùc tiÕp biÕn ®æi DFT, ®©y lµ ph¬ng ph¸p tiÕt kiÖm thùc sù cho tÝnh to¸n. B©y giê, chóng ta sÏ v¹ch ra thuËt to¸n FFT. §ã kh«ng ®¬n thuÇn chØ lµ sù ph¸t triÓn mét ch¬ng tr×nh tõ lu ®å. Tuy nhiªn, chóng ta cã thÓ nghiªn cøu lu ®å vµ v¹ch ra c¸c bíc cã thÓ dïng ®Ó ph¸t triÓn mét ch¬ng tr×nh. Tõ lu ®å cña h×nh 6.5 chóng ta cã thÓ viÕt: Bíc thø nhÊt. Trong bíc nµy ta cã t¸m bím víi träng lîng (hÖ sè xoay) W0 = 1. Chóng ta cã thÓ viÕt (xem h×nh 6.6) for (j=0 ®Õn 15 víi bíc t¨ng 2) { T=X(j+1); X(j+1)=X(j) - T; X(j)=X(j) + T; } Bíc thø hai. Chóng ta cã: 1.Bèn bím víi träng lîng b»ng 1. for (j=0 ®Õn 15 víi bíc t¨ng 4) { T=X(j); X(j+2)=X(j) - T; X(j)=X(j) + T; } 2. Bèn bím víi träng lîng W4 = W(3). Chó ý r»ng chóng ta coi r»ng c¸c hÖ sè xoay W, W2 , ... , W7 ®· ®îc tÝnh vµ ®îc chøa trong W(0), W(1), ...W(6). for (j=0 ®Õn 15 víi bíc t¨ng 4) { T=X(j)W(3);X(j+2)=X(j) - T; X(j)=X(j) + T; } Bíc thø ba. Chóng ta cã : 88
1. Hai bím víi träng lîng b»ng 1. for (j=0 ®Õn 15 víi bíc t¨ng 8) { T=X(j); X(j+4)=X(j) - T; X(j)=X(j) + T; } W 8n W 4n W 2n W n n=0 n=0 ®Õn 1 n=0 ®Õn 3 n=0 ®Õn 7 0000 0 0 0 0 0 0000 1000 8 8 4 2 1 0001 0 0 0100 4 4 8 4 2 0010 4 1100 12 12 12 6 3 0011 0 0010 2 2 2 8 4 0100 0 1010 10 10 6 10 5 0101 2 0 0110 6 6 12 12 6 0110 4 0 1110 14 14 14 14 7 0111 6 0 4 0001 1 1 1 1 8 1000 0 1001 9 9 5 3 9 1001 1 0 0101 5 5 9 5 10 1010 2 0 1101 13 13 13 7 11 1011 3 0 4 0011 3 3 3 9 12 1100 4 0 1011 11 11 7 11 13 1101 5 2 0 0111 7 7 11 13 14 1110 6 4 0 1111 15 15 15 15 15 1111 7 6 0 4 bíc 0 bíc 1 bíc 2 bíc 3 BËc cña d·y vµo biÓu diÔn BËc cña d·y ra biÓu diÔn d¹ng nhÞ ph©n d¹ng nhÞ ph©n H×nh 6.5 Lu ®å thuËt to¸n thuËt to¸n ph©n chia miÒn thêi gian. 89
2. Hai bím víi träng lîng b»ng W (1) = W2. for (j=1 ®Õn 15 víi bíc t¨ng 8) { T=X(j)W(1); X(j+4)=X(j) - T; X(j)=X(j) + T; } 3. Hai bím víi träng lîng b»ng W(3) = W4. for (j=2 ®Õn 15 víi bíc t¨ng 8) { T=X(j)W(3); X(j+4)=X(j) - T; X(j)=X(j) + T; } f10 (k ) f10 (k ) F(2n) F(2n) F(2n+1) F(2n+1) f11 (k ) f11 (k ) (a) (b) H×nh 6.6 (a) Bím cho thuËt to¸n ph©n chia miÒn tÇn sè;(b) Mét bím ®¬n gi¶n. 4. Hai bím víi träng lîng b»ng W (5) = W6 . for (j=3 ®Õn 15 víi bíc t¨ng 8) { T=X(j)W(5); X(j+4)=X(j) - T; 90
X(j)=X(j) + T; } Bíc thø t vµ lµ bíc cuèi cïng. 1.Mét bím víi träng lîng b»ng 1. T = X(0) X(8)= X(0) - T X(0) = X(8) +T 2. Mét bím víi träng lîng b»ng W (0) = W. T = X(1)W(0) X(1+8)= X(1) - T X(1) = X(1) +T 3. Mét bím víi träng lîng b»ng W (1) = W2. T = X(1)W(1) X(2+8)= X(0) - T X(2) = X(2) +T . . . 8. Mét bím víi träng lîng b»ng W (6) = W7. T = X(7)W(6) X(7+8)= X(7)-T X(7) = X(7) +T C¸c bíc dÉn chóng ta ®Õn thuËt to¸n víi N = 16. ThuËt to¸n ip=1 kk=8 incr=2 cho iter=0 ®Õn 3 trong c¸c bíc cña 1 { cho j=0 ®Õn 15 trong c¸c bíc cña incr 91
{ i = j + ip T = X(j) X(i) = X(j) - T X(j) = X(j) +T nÕu (iter kh«ng b»ng 0) th× { cho k=1 ®Õn ip-1 trong c¸c bíc cña 1 { r = k*kk - 1 cho j=k ®Õn 15 trong c¸c bíc cña 15 { i=j+ip T=X(i)*W(r) X(i)=X(j)-1 X(j)=X(j)+T } } } kk=kk/2 ip= ip*2 inc=inc*2 } ThuËt to¸n trªn cã thÓ dÔ dµng më réng cho tÊt c¶ c¸c trêng hîp cña N. ChØ cã mét lÜnh vùc cßn l¹i cÇn ph¶i gi¶i thÝch lµ sù s¾p xÕp l¹i c¸c d·y d÷ liÖu ®Çu vµo. §iÒu nµy cã thÓ t¹o ra dÔ dµng nÕu chóng ta t¹o ra mét b¶ng (LUT) L(i), L(i) lµ c¸c gi¸ trÞ ®¶o ngîc bit cña i. NÕu d÷ liÖu ®îc ®äc tõ mét file th× tÊt c¶ c¸c viÖc mµ chóng ta ph¶i lµm lµ chuyÓn ®Þa chØ vïng cña chóng trong file qua b¶ng LUT vµ lu c¸c d÷ liÖu nµy trong ®Þa chØ chøa kÕt qu¶ trong d·y ®Çu vµo, X. Bíc nµy cã thÓ chuyÓn sang ng«n ng÷ C nh sau: for (i=0; i
Ch¬ng tr×nh 6.1 FFTDT.C FFT 1-D ThËp ph©n trong miÒn thêi gian. /*********************************** * Program developed by: * * M.A.Sid-Ahmed. * * ver. 1.0 1992. * * @ 1994 * *********************************/ /* FFT - Decimation-in-time routine with examplemain programing proper usage. */ #define pi 3.141592654 #include #include #include #include void bit_reversal(unsigned int *, int , int); void WTS(float *, float *, int, int); void FFT(float *xr, float *xi, float *, float *, int , int); void main() { int i,k,m,N,n2,sign; unsigned int *L; float *wr,*wi,*xr,*xi; char file_name[14]; FILE *fptr; printf("\nEnter name of file containing data points-> "); scanf("%s",file_name); if((fptr=fopen(file_name,"rb"))==NULL) { printf("file %s does not exist."); exit(1); 93
} printf("Enter # of data points to be read -->"); scanf("%d",&N); m=(int)(log10((double)N)/log10((double)2.0)); k=1; for(i=0;i