intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

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

53
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ủ đề:
Lưu

Nội dung Text: Biến đổi fourier rời rạc part 2

  1. -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
  2. H×nh 6.3 B­íc thø hai sau b­íc cuèi cïng trong thuËt to¸n FFT. 86
  3. 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 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
  4. 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õ l­u ®å. Tuy nhiªn, chóng ta cã thÓ nghiªn cøu l­u ®å vµ v¹ch ra c¸c b­íc cã thÓ dïng ®Ó ph¸t triÓn mét ch­¬ng tr×nh. Tõ l­u ®å 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
  5. 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 L­u ®å thuËt to¸n thuËt to¸n ph©n chia miÒn thêi gian. 89
  6. 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
  7. 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
  8. { 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µ l­u 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
  9. 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
  10. } 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2