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 4

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

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

Tham khảo tài liệu 'biến đổi fourier rời rạc part 4', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:
Lưu

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

  1. H×nh 6.8 L­u ®å thuËt to¸n gi¶m l­îc ®Çu vµo, N=4 for(iter=(m_output-m_input);iter
  2. xi[j]=Ti ; Tr=diffr*wr[l]-diffi*wi[l]; Ti=diffr*wi[l]+diffi*wr[l]; xr[i]=Tr; xi[i]=Ti; } } kk=l; incr>>=l; } } Bµi tËp 6.3 1.Cho d·y ®Çu vµo : x(k) = 1 k = 0,1,2, ... , 31. x(k) = 0 c¸c tr­êng hîp cßn l¹i. TÝnh 1024 ®iÓm trong phæ tÇn sè dïng ch­¬ng tr×nh gi¶m l­îc ®Çu vµo FFT. 2. Thªm c¸c gi¸ trÞ 0 vµo d·y ®Ó lµm cho chiÒu dµi d·y thµnh 1024. B©y giê tÝnh FFT scña d·y dïng ch­¬ng tr×nh FFT ph©n chia tÇn sè kh«ng gi¶m l­îc. So s¸nh thêi gian xö lý cña phÇn 1 vµ 2. ThuËt to¸n FFT gi¶m l­îc ®Çu ra. Gi¶i thuËt ph©n chia miÒn thêi gian th× thÝch hîp cho thuËt to¸n gi¶m l­îc ®Çu ra h¬n lµ gi¶i thuËt ph©n chia miÒn tÇn sè. Lý do lµ ®Çu ra trong gi¶i thuËt ph©n chia miÒn thêi gian kh«ng ph¶i s¾p xÕp l¹i. H×nh 6.9 giíi thiÖu tr­êng hîp víi M=4 vµ L=1. 106
  3. W W W W n=0 n=0 ®Õn 1 n=0 ®Õn 3 n=0 ®Õn 7 0 0 0 0 0 8 8 4 2 1 4 4 8 4 12 12 12 6 2 2 2 8 10 10 6 10 6 6 10 12 14 14 14 14 1 1 1 1 9 9 5 3 5 5 9 5 13 13 13 7 3 3 3 9 11 11 7 11 7 7 11 13 15 15 15 15 H×nh 6.9 L­u ®å cho gi¶m l­îc ®Çu ra FFT, N = 4. Ch­¬ng tr×nh 6.4 FFTOP.C Gi¶m l­îc ®Çu ra FFT. /***************************** * Program developed by: * * M.A.Sid-Ahmed. * * ver. 1.0 1992. * * @ 1994 * *****************************/ /* FFT - output pruning using Decimation-in-time routine. */ # define pi 3.141592654 void bit_reversal(unsigned int *, int , int); void WTS(float *, float *, int, int); void FFTP(float *xr, float *xi, float *, float *,int, int, int, int); 107
  4. void FFTP(float *xr, float *xi, float *wr, float *wi, int m, int N, int m_output, int N_output) { /* FFT output pruning algorithm using Decimation-in-time. Note : 1. N=number of input samples =2 to the power m. N-output = number of output samples =2 to the power motput. 2. The input arrays are assumed to be rearranged in bit-reverse order. You will need to use routine "bit-reversal" for that purpose. 3. The twiddle factors are assumed to be stored in LUT's wr[] and wi[]. You will need to use routine LUT for calculating and storing twiddle factors.*/ int ip,k,kk,l,incr,iter,j,i; float Tr,Ti; ip=1; kk=(N>>1 ); incr=2; for(iter=0; iter
  5. { l=k*kk-1 ; for(j=k; j>=1; ip
  6. ip
  7. 6.4.2 Mét sè tÝnh chÊt cña 2-D DFT ChuyÓn ®æi. Tõ ®Þnh nghÜa cña 2-D DFT vµ IDFT cho thÊy j 2 ( ak1  bk 2 ) (6.43) N h( k 1 , k 2 ) e  H (n1  a, n 2  b) j 2 ( n1a  n2 b ) (6.44) N h(k1  a, k 2  b)  H (n1 , n 2 )e §iÒu ®ã cã nghÜa lµ mét dÞch chuyÓn pha tuyÕn tÝnh trong mét miÒn biÓu diÔn b»ng mét dÞch chuyÓn h»ng sè trong mét miÒn kh¸c. Xem xÐt biÓu thøc (6.43), tr­êng hîp ®Æc biÖt khi a = b = N/2. h(k1 , k 2 )e j ( k1  k2 )  h(k1 , k 2 )(e j ) k1  k2 )  h(k1 , k 2 )(1) k1  k2 Hay lµ N N h(k1 , k 2 )(1) k1 k2  H (n1  (6.45) , n2  ) 2 2 Nãi c¸ch kh¸c, b»ng c¸ch nh©n vµo mçi ®iÓm (-1) k  k tr­íc khi lÊy DFT, 1 2 chóng ta sÏ rót ra ®­îc mét phæ tÇn sè mµ ®iÓm tÇn sè (0,0) cña nã sÏ n»m gi÷a m¶ng 2-D. BiÓu thøc nµy rÊt h÷u dông trong hiÓn thÞ phæ tÇn sè, phæ biªn ®é vµ läc dïng DFT. Tõ biÓu thøc (6.44) chóng ta rót ra kÕt luËn r»ng dÞch chuyÓn mét h»ng sè trong ¶nh sÏ kh«ng t¸c ®éng ®Õn phæ biªn ®é. H (n1  n2 )e  j 2 / N .( n1a  n2b)  H (n1  n2 ) (6.46) BiÓu thøc (6.46) còng quan hÖ ®Õn bé läc 2-D. Xem xÐt ®Æc tÝnh cña bé läc 2-D cho bëi H (n1 , n2 )  A(n1 , n 2 )e  j 2 / N .( n1a  n2b) ë ®©y A(n1,n2) lµ phæ biªn ®é. NÕu mét ¶nh víi phæ tÇn sè cho bëi I(n1,n2) ®­îc läc qua bé läc cã ®Æc tuyÕn pha tuyÕn tÝnh cho bëi biÓu thøc ë trªn, kÕt qu¶ sÏ lµ [| A(n1 , n2 )e  j 2 / N .( n1a n2b) ]I (n1 , n2 )  [ I (n1 , n2 ) A(n1 , n2 )]e  j 2 / N .( n1a n2b )  i f (n1 - a, n 2 - a) (6.47) ë ®©y if (n1-a, n2-b) ký hiÖu cho ¶nh ®· ®­îc läc. Mét bé läc víi ®Æc tuyÕn pha tuyÕn tÝnh cã nghÜa lµ kh«ng dÞch chuyÓn biªn ®é. Trong khi ®ã nÕu bé läc cã ®Æc tuyÕn pha kh«ng tuyÕn tÝnh th× pha cña ¶nh còng bÞ biÕn d¹ng. Lý 111
  8. do cña sù biÕn d¹ng nµy lµ tÊt c¶ c¸c ®iÓm ®Òu ph¶i chÞu mét sù dÞch chuyÓn vÞ trÝ kh¸c nhau tuú theo vÞ trÝ cña ¶nh. Tæng qu¸t, ¶nh ®· ®­îc läc cã thÓ cho bëi i f (n1 - f (n1 , n2 ), n2 - f( n1 , n 2 )) ë ®©y f lµ hµm dÞch chuyÓn vÞ trÝ. Chó ý r»ng mét ¶nh biÕn d¹ng pha sÏ xuÊt hiÖn trªn mµn h×nh nh­ mét ¶nh mê . TÝnh ®èi xøng liªn hîp vµ tuÇn hoµn. BiÕn ®æi2-D DFT vµ IDFT tuÇn hoµn víi chu kú N cã nghÜa lµ : H(n1 , n2 )  H(n1  N, n2 )  H(n1 , n2  N) (6.48)  H(n1  N, n2  N) vµ h(k 1 , k 2 )  h(k 1  N, k 2 )  h(k 1 , k 2  N) (6.49)  h(k 1  N, k 2  N) BiÕn ®æi DFT ®èi xøng liªn hîp khi (6.50) H(n1 , n 2 )  H * (-n1 , - n 2 ) hoÆc (6.51) H(n1 , n 2 )  H(-n1 , - n 2 ) Quay. NÕu chóng ta ®Æt k1 vµ k2 d­íi d¹ng k 2  r cos k1  r sin th× h(k 1 , k 2 )  h( rsin , rcos )  h (r, ) Vµ t­¬ng tù cho n1, n2 n2   cos n1   sin hoÆc H(n1 , n 2 )  H (r, ) tõ ®Þnh nghÜa cña DFT chóng ta cã thÓ cã (6.52) h(r ,   0 )  H ( ,   0 ) 112
  9. §iÒu ®ã cã nghÜa lµ nÕu ¶nh bÞ quay ®i mét gãc 0 th× phæ cña nã còng bÞ quay ®i mét gãc nh­ vËy. Ph©n phèi vµ chia ®é. Tõ biÓu thøc (6.1) chóng ta dÔ thÊy (6.53) a h1 (k 1 , k 2 )  b h2 (k 1 , k 2 )  aH 1 (n1 , n2 )  bH 2 (n1 , n 2 ) ë ®©y a,b lµ nh÷ng ®é chia. Còng nh­ vËy nn 1 H( 1 , 2 ) (6.54) h(ak1 , bk 2 )  ab ab 6.4.3 Gi¸ trÞ trung b×nh Møc c­êng ®é s¸ng trung b×nh trong mét ¶nh cho bëi : N 1 N 1 1   h( k , k (6.55) h ) N2 1 2 k1  0 k1  0 hoÆc tõ biÓu thøc (6.1) ta cã thÓ viÕt h  H (0,0) §iÒu nµy cã nghÜa lµ H(0,0) biÓu diÔn møc s¸ng cña ¶nh. 6.4.4 TÝch chËp vµ sù t­¬ng quan TÝch chËp cña tÝn hiÖu 2-D h1(k1,k2) vµ h2(k1,k2) cho bëi N 1 N 1   h (k , k (6.56) g (n1 , n2 )  )h2 (n1  k1 , n2  k 2 ) 1 1 2 k1  0 k 2  0 NÕu h1(k1,k2) ®­îc x¸c ®Þnh trªn miÒn  k     0, A  1  k1  0, B  1 1 vµ nÕu h2(k1,k2) ®­îc x¸c ®Þnh trªn miÒn k    0, C  1   k 1 0, D  1 1 th× chóng ta cã thÓ thÊy r»ng nÕu hai tÝn hiÖu cã gi¸ trÞ zero ngoµi miÒn x¸c ®Þnh cña chóng th× M = A + C - 1 vµ N = B + D - 1. TÝch chËp cña hai tÝn hiÖu 2-D ®­îc viÕt trong d¹ng ký hiÖu nh­ sau: h1 (k 1 , k 2 )* h2 (k 1 , k 2 ) Cã thÓ thÊy r»ng 113
  10. (6.57) h1 (k 1 , k 2 )* h2 (k 1 ,k 2 )  H 1 (n1 , n2 )H 2 (n1 , n2 ) §iÒu nµy cã nghÜa lµ, tÝch chËp trong miÒn kh«ng gian biÕn thµnh phÐp nh©n b×nh th­êng trong miÒn tÇn sè. TÝnh chÊt nµy cã thÓ dïng cho läc 2 -D qua DFT. Chóng ta cÇn nhí l¹i r»ng b¹n ®· dïng kü thuËt läc FIR trong c¸c ch­¬ng tr­íc cho chøc n¨ng nµy. Khi ¸p dông c¸c läc bé läc FIR cho chøc n¨ng läc b¹n cÇn lÊy tÝn hiÖu kho¶ng c¸ch 2-D ®· ®­îc biÕn thµnh tÝn hiÖu cã chu kú tr­íc khi tiÕn hµnh lÊy DFT. Sù kh«ng ®ång bé cña chu kú trong biÕn ®æi nµy còng g©y ra lçi nh­ trong biÕn ®æi 1-D. V× vËy, ®Ó tr¸nh tr­êng hîp nµy ta cÇn thªm c¸c sè 0 vµo c¶ hai c¸c hµm kh«ng gian ®Ó cho chóng cã kÝch th­íc M  N víi M  A + C - 1 vµ N  B + D - 1. T­¬ng quan hoÆc t­¬ng quan chÐo cña tÝn hiÖu 2-D ®Þnh nghÜa bëi N 1 N 1   h (k , k (6.58) g (n1 , n2 )  )h2 (n1  k1 , n2  k 2 ) 1 1 2 k1  0 k 2  0 BiÓu thøc nµy ®­îc viÕt d­íi d¹ng ký hiÖu (6.59) g (n1 , n2 )  h1 ( k1 , k 2 ) h2 ( k 1 , k 2 ) T­¬ng quan chÐo th­êng ®­îc gäi lµ läc kÕt hîp vµ dïng ®Ó ph¸t hiÖn ra phÇn ®Çu dÊu hiÖu c¸c vÕt s¾c næi trªn ¶nh. Nã cã thÓ cho thÊy r»ng (6.60) h1 ( k 1 , k 2 ) h2 ( k1 , k 2 )  H1 (n1 , n2 ). H 2 (n1 , n2 ) 6.5 2-D FFT BiÓu thøc cho 2-D DFT cã thÓ d­íi d¹ng N 1 N 1  [  h(k1 , k 2 )e  j.2 / N .n k ]e  j.2 / N .n1k1 (6.61) H (n1 , n2 )  22 k1 0 k 2 0 N 1  h(k1 , k 2 )e  j.2 / N .n 21k 21 §Æt (6.62) G (k1 , k 2 )  k2  0 víi k1 = 0,1,2,..., N-1. V× vËy mµ biÓu thøc (6.61) cã thÓ viÕt l¹i d­íi d¹ng . N 1  G( k , n )e  j .2 / N .n1k1 (6.63) H (n1 , n2 )  1 2 k1  0 víi n1=0,1,2,...,N-1. 114
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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