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

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

Thêm vào BST

Báo xấu

84
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ủ đề:

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 4

H×nh 6.8 Lu ®å thuËt to¸n gi¶m lîc ®Çu vµo, N=4 for(iter=(m_output-m_input);iter
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
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 Lu ®å 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
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
{ l=k*kk-1 ; for(j=k; j>=1; ip
ip
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
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
§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
(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