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

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

Thêm vào BST

Báo xấu

89
lượt xem 8
download

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

Biến đổi Fourier rời rạc 6.1 Chỉ dẫn Trong chương 2,chúng ta đã chứng minh rằng đáp ứng tần số của hệ thống của hệ thống tuyến tính bất biến (LSI ) 2-D

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 1

Ch¬ng 6 BiÕn ®æi Fourier rêi r¹c 6.1 ChØ dÉn Trong ch¬ng 2,chóng ta ®· chøng minh r»ng ®¸p øng tÇn sè cña hÖ thèng cña hÖ thèng tuyÕn tÝnh bÊt biÕn (LSI ) 2-D ®îc cho bëi:    j (1k1  2 k 2 )   h ( k , k )e (6.1) H (1 ,  2 )  1 2 k1   k 2   NÕu h(k1,k2) chØ cã chØ tån t¹i víi k1  0, k 2  0 vµ tæng qu¸t ®îc x¸c ®Þnh trong miÒn h÷u h¹n cã kÝch thíc N  N th× N 1 N 1   h(k1, k 2 )e  j ( k  k ) (6.2) H (1 ,  2 )  11 22 k1 0k 2 0 C«ng thøc nµy chøng tá r»ng H ( 1 ,  2 ) lµ tuÇn hoµn, chu kú tuÇn hoµn lµ 2. NÕu chóng ta lÊy mÉu díi d¹ng 1, 2, vµ miÒn x¸c ®Þnh lµ (0  1  2) vµ (0  2  2), N  N mÉu, chóng ta cã thÓ viÕt: 2 2 vµ  2  (6.3) 1  n1 n2 N N N 1 N 1  j 2  n1k1  n2 k 2  H (n1 , n 2 )    h(k 1 , k 2 )e v× thÕ (6.4) N k1  0 k 2  0 BiÓu thøc (6.4) ®îc gäi lµ biÕn ®æi Fourier rêi r¹c 2-D hay cßn gäi lµ DFT. C«ng thøc nµy ®îc ¸p dông vµo nhiÒu øng dông nh läc, nÐn ¶nh, phãng ®¹i ¶nh. Trong ch¬ng nµy chóng ta sÏ nghiªn cøu 2 -D DFT vµ c¸c kü thuËt tÝnh to¸n. §Çu tiªn, chóng ta sÏ xem xÐt 1-D DFT, sau ®ã më réng ra cho 2-D. 6.2 BiÕn ®æi Fourier 1-D BiÕn ®æi Fourier 1-D cho tÝn hiÖu thêi gian rêi r¹c f(kT) tÝnh theo c«ng thøc : 75
N 1  j 2 nk F (n)   f (kT )e (6.5) N k 0 C«ng thøc nµy cã thÓ viÕt l¹i díi d¹ng N 1  f (k ) ¦ W N nk  (6.6) F (n)  n 0 ë ®©y f(k) = f(kT) vµ WN = e- j2 /N . WN ®îc gäi lµ h¹t nh©n cña phÐp biÕn ®æi. Tæng qu¸t, F(n) cã d¹ng F (n)  A(n)e j ( n) (6.7) Ký hiÖu A(n),  (n) gäi lµ phæ khuyÕch ®¹i vµ phæ pha cña F(n). 6.2.1 BiÕn ®æi ngîc DFT Hµm f(k) lµ biÕn ®æi ngîc DFT cña F(n) cho bëi theo biÓu thøc 2 N 1 j nk 1 N  F ( n )e (6.8) f (k )  N n 0 Chøng minh: Tõ ®Þnh nghÜa cña DFT N 1 N 1 N 1 1 1   kn nk  nm  F (n)W   f (m)W WN  N N N N   n 0 n 0 m 0 (6.9) N 1 N 1 1 n(k m)  f ( m ) W  N N m 0 n 0 N 1  W N (k m ) n §Æt S n0 NÕu (k = m) th× S = N. NÕu (k  m), chóng ta cã thÓ viÕt: (k -m ) 2(k -m ) (N-1)(k -m ) S = 1 + WN + WN + ... + WN hoÆc 76
1 - WN -m) N(k S 1 - WN -m) (k 1  e j ( 2 ( k  m ))  2 j ( k  m ) N 1 e Khi e j2(k-m) = 1 vµ e j2/N. (k-m)  1 víi (k  m), v× vËy S = 0 víi (k  m ). V× vËy, biÓu thøc (6. 9) cã thÓ rót gän thµnh 1 N 1 1   F (n)WNnk  f(k).N N n 0 N KÕt qu¶ nµy gièng nh biÓu thøc (6.8). Khi f(k) cã thÓ rót ra tõ F(n) vµ ngîc l¹i, chóng gäi lµ cÆp biÕn ®æi. CÆp biÕn ®æi nµy cã d¹ng f ( k )  F ( n) Chó ý tõ biÓu thøc (6.8) ta cã thÓ dÔ dµng chøng minh: 2 N 1 1 j n ( k  N )  F ( n )e N  f (k  N ) N n 0 2 N 1 1 j .nk   F ( n )e N N n 0  f (k ) (6.10) MÆc dï f(k) ®îc x¸c ®Þnh trªn miÒn k  [0,N], nã vÉn lµ tÝn hiÖu tuÇn hoµn víi chu kú NT. (T ®îc bao hµm vµ rót ra tõ biÓu thøc 6.5). 6.2.2 Mét vµi tÝnh chÊt cña DFT TuyÕn tÝnh. NÕu ta cã hai d·y tuÇn hoµn cïng f1(n) vµ f2(n), vµ c¶ hai d·y nµy tuÇn hoµn víi chu kú N, ®îc dïng ®Ó tÝnh f3(k) = af1(k) + bf2(k) (6.11) lµ kÕt qu¶ cña biÕn ®æi DFT f3(n) cho bëi F3(n) = aF1(n) + bF2(n) (6.12) ë ®©y a, b lµ h»ng sè vµ 77
F1(n) = DFT cña f1(k) F2(n) = DFT cña f2(k) TÝnh ®èi xøng. TÝnh ®èi xøng cña DFT rÊt hay ®îc dïng. N 1 F ( N  n)   f (k )WN k ( N  n )  k 0 2 2 N 1 j N j nk   f ( k )e N N e k 0 2 N 1 j nk   f ( k )e e N k 0 NÕu f(k) lµ thùc th×  2  N 1  j .nk  F ( N  n )    f ( k )e N   F ( n )  (6.13)  k 0    DÊu * cã nghÜa lµ liªn hîp phøc. TÝch chËp tuÇn hoµn. Coi f1(k) vµ f2(k) lµ hai d·y tuÇn hoµn cã chu kú N, víi biÕn ®æi Fourier rêi r¹c lµ F1(n) vµ F2(n). Xem xÐt tÝch F(n1).F(n2) N 1  f1 (k1 )W N n k  khi 11 F1 (n1 )  k1 0 N 1  f 2 (k 2 )WN n k  22 F2 (n 2 )  k2 0 N 1 N 1 F1 (n1 ).F1 (n1 ) =  f 1 (k1 )W N n1k1 .  f 2 (k1 )W N n2 k 2  k1  0 k 2 0 N 1 N 1 =   f 1 (k1 ) f 2 (k 2 )W N n1k1 WNn 2 k 2 - k1  0 n1  0 vµ t¹i c¸c vÞ trÝ n1 = n2 = n 78
§Æt f3(k) = IDFT cña F1(n).F2(n) N 1 1  F1 (n).F2 (n)W nk hay f3 (k )  N n0 v× vËy N 1 N 1 N 1  1  n ( k1  k 2 ) nk     f1 (k1 ) f 2 (k 2 )W N f 3 (k)  W N N n  0  k1 0k2 0    N 1 N 1 N 1 1  W N n(k  k k )    f1 (k1 )  f 2 (k 2 ) 1 2  N    k1  0 k2 0 n 0 Chó choý = k1 + k2 + lN lµ k N 1 1 1 c¸c trêng hîp cßn l¹i.  W  n ( k  k  k )  0 1 2 N  n 0 ë ®©y l lµ sè nguyªn. V× vËy mµ N 1  f1 (k1 ) f 2 (k  k1  lN ) (6.14) f 3 (k )  k10 ë ®©y k = 0 ®Õn 2N - 1. BiÓu thøc trªn biÓu diÔn tÝch chËp cña hai tÝn hiÖu tuÇn hoµn. Chó ý r»ng biªñ thøc nµy chØ ¸p dông cho hai d·y cã chung mét chu kú, vµ chiÒu dµi cña d·y tÝnh theo biÓu thøc trªn lµ 2N - 1. KÕt qu¶ nµy chøng minh r»ng trong DFT, tÝn hiÖu cã sè mÉu lín h¬n N sÏ ®îc biÕn ®æi thµnh d·y tuÇn hoµn cã chu kú N. Khi dïng DFT cho mét tÝn hiÖu kh«ng cã chu kú, mµ kÕt qu¶ thu ®îc tõ tÝch hai d·y, ta sÏ ph¹m mét sai lÇm gäi lµ lçi wraparound. §ã lµ lý do ta ph¶i lµm cho c¶ hai d·y cã chu kú b»ng nhau. §Ó söa lçi nµy, mét sè sè 0 cÇn ph¶i thªm vµo c¶ hai d·y ®Ó chiÒu dµi hai d·y b»ng nhau. VÝ dô, nÕu mét d·y cã chiÒu dµi A, mét d·y cã chiÒu dµi B, kÕt qu¶ ta ph¶i A + B - 1. thªm c¸c sè 0 cho c¶ hai d·y cã chiÒu dµi Ýt nhÊt lµ Bµi tËp 6.1 Cho hai d·y sau 0  k1 4 1 f1 ( k )   c¸c trêng hîp cßn l¹i. 0 79
0  k1  5 1 f 2 (k )   c¸c trêng hîp cßn l¹i. 0 1. TÝnh b»ng tay tÝch chËp cña hai d·y trªn. VÏ mét lu ®å biÓu diÔn thuËt to¸n. 2. Lµm l¹i phÇn 1, nhng lÇn nµy sö dông tÝch chËp tuÇn hoµn. 3. LËp mét ch¬ng tr×nh C rót ra f3(k) tõ biÓu thøc f3(k) = IDFT DFT[f1(k)]. DFT[f1(k)] . So s¸nh kÕt qu¶ cña phÇn 1 vµ phÇn hai. 4. B©y giê thªm c¸c sè kh«ng vµo f1(k) vµ f2(k) ®Ó chu kú cña chóng = 5 + 6 - 1. Lµm l¹i phÇn 3 vµ so s¸nh kÕt qu¶. 6.3 ThuËt to¸n biÕn ®æi nhanh Fourier TÝnh trùc tiÕp gi¸ trÞ cña DFT bao gåm N phÐp nh©n phøc vµ N - 1 phÐp céng phøc cho mçi gi¸ trÞ cña F(n). Khi N gi¸ trÞ ®îc tÝnh to¸n th× N2 phÐp nh©n vµ N(N - 1) phÐp céng ®îc tÝnh to¸n. Còng nh vËy, cho N cã gi¸ trÞ rÊt lín, tÝnh trùc tiÕp gi¸ trÞ cña DFT sÏ ®ßi hái mét sè phÐp tÝnh lín ®Õn møc kh«ng thÓ chÊp nhËn ®îc. §Ó vÝ dô, cho N = 1024 = 210 ta sÏ ph¶i tÝnh 220 = 1,048,576 phÐp nh©n sè phøc vµ mét sè gÇn b»ng nh vËy c¸c phÐp céng. Hoµn thiÖn cã nghÜa lµ ph¶i gi¶m sè phÐp tÝnh trong biÕn ®æi Fourier xuèng. Díi ®©y chóng ta sÏ giíi thiÖu hai thuËt to¸n hay dïng lµ thuËt to¸n ph©n chia thêi gian vµ thuËt to¸n ph©n chia tÇn sè. DFT dïng c¸c thuËt to¸n trªn gäi lµ Fast Fourier transform (FFT). 6.3.1 ThuËt to¸n ph©n chia thêi gian Xem xÐt tÝnh to¸n cña DFT cho bëi (5.6) víi N= 2r (r lµ mét sè nguyªn bÊt kú). C¬ së cña thuËt to¸n ph©n chia thêi gian th× râ rµng. Tuy nhiªn, viÖc thiÕt kÕ phÇn mÒm còng ®ßi hái mét sè ph©n tÝch chi tiÕt. §Ó lµm râ c¸c bíc cña thuËt to¸n nµy chóng ta sÏ b¾t ®Çu ph©n tÝch víi N = 16 vµ sau ®ã më réng ra ¸p dông cho N bÊt kú. C¬ së cña thuËt to¸n ph©n chia thêi gian dùa trªn c¬ së chiÕn lîc chia vµ chiÕm. C¸c bíc sau sÏ lµm s¸ng tá thuËt to¸n. V× trong trêng hîp nµy N =16; nªn, 80
15  f (k )W16nk  F (n)  k 0 Chia d·y f(k) thµnh hai d·y, mét d·y ®îc rót ra tõ phÇn tö ch½n vµ mét d·y tõ nh÷ng phÇn tö lÎ. §ã lµ, 15 15 (k )W16nk    f (k )W16nk  f F (n)  k 0 k 0 k ch½n k lÎ Chóng cã thÓ viÕt thµnh 7 7 f (2k )W16n ( 2k )   f (2k  1)W16n( 2k 1)    (6.15) F (n)  k 0 k 0 Chó ý lµ 2 2 j .n ( 2 k ) j .nk W16n ( 2k )  16 8 e e  W8nk 7 7  f (2k )W8nk  W16n  f (2k  1)W8nk  v× thÕ F (n)  k 0 k 0 ®Æt f 10 (k)  f(2k) f 11 (k)  f(2k  1) Ta ®îc 7 7  f10 (k )W8nk  W16n  f11 (k )W8nk  (6. F (n)  k 0 k 0 16) 7  f10 (k )W8nk §Æt (6.17) F10 (n)  k 0 81
7  f11 (k )W8nk (6.18) F11 (n)  k 0 ViÕt l¹i biÓu thøc (6.16) chóng ta ®îc -n (6.19) F(n)  F10 (n)  W16 F11 (n) Còng nh vËy, ph¸t triÓn cho mét biÓu thøc -n (6.20) F(n  8)  F10 (n) - W16 F11 (n) BiÓu thøc (6.19) vµ (6.20) ®Þnh d¹ng nh÷ng ®¬n vÞ tÝnh to¸n gäi lµ bím. H×nh 6.1 lµ biÓu ®å cña phÇn tö bím. Ký hiÖu W16-n thêng gäi lµ träng lîng hay hÖ sè xoay. Hai biÓu thøc nµy biÓu diÔn bíc cuèi cïng trong lu ®å tÝnh to¸n cña h×nh 6.2. B©y giê xem xÐt biÓu thøc 7  f10 (k )W8nk F10 (n)  k 0 Xö lý nh trªn chóng ta cã 3 7 f10 (2k )W4nk  W8n  f10 (2k  1)W4nk  F10 (n)  k 0 k 0 DÔ thÊy -n -2n W8  W16 ®Æt f 20 (k)  f 10 (2k) f 21 (k)  f 10 (2k  1) F10(n) F(n) F10(n) F(n) 82 W16-n n F11(n) F(n+8) F11(n) F(n+8)
X(k) X(k) 0 0 1 1 2 2 3 3 F10(n) 4 4 5 5 6 6 7 7 F(n) 0 8 1 9 2 10 3 11 F11(n) 4 12 5 13 6 14 7 15 H×nh 6.1 (a) Bím; (b) BiÓu diÔn rót gän. H×nh 6.2 Bíc cuèi cïng cña thuËt to¸n biÕn ®æi FFT ph©n chia miÒn thêi gian. X(k) ký hiÖu vector chøa gi¸ trÞ ®îc tÝnh qua phÐp biÕn ®æi FFT. 3 3 F10 (n)   f 20 (k )W4 nk  W16 2 n  f 21 (k )W4 nk  V× vËy, k 0 k 0 -2n (6.21) F10 (n)  F20 (n)  W16 F21 (n) -2n (6.22) F10 (n  4)  F20 (n) - W16 F21 (n) 83
3 F20 (n)   f 20 (k )W4 nk ë ®©y (6.23) k 0 3 F21 (n)   f 21 (k )W4 nk (6.24) k 0 T¬ng tù -2n F11 (n)  F22 (n)  W16 F23 (n) (6.25) -2n (6.26) F11 (n  4)  F22 (n) - W F23 (n) 16 3 F22 (n)   f 22 (k )W4 nk ë ®©y k 0 (6.27) 3  f 23 (k )W4nk (6.28) F23 (n)  k 0 vµ f 22 (k)  f 11 (2k) f 23 (k)  f 11 (2k  1) BiÓu thøc (6.21), (6.22), (6.25) vµ (6.26) cã thÓ biÓu diÔn b»ng s¬ ®å h×nh 6.3. BiÓu thøc (6.23), (6.24), (6.27) vµ (6.28) cã thÓ tiÕp tôc chia nhá ra nh c¸c bíc ®· lµm ë trªn nh sau: -4n (6.29) F20 (n)  F30 (n)  W16 F31 (n) -4n (6.30) F20 (n  2)  F30 (n) - W16 F31 (n) -4n (6.31) F21 (n)  F32 (n)  W16 F33 (n) -4n (6.32) F21 (n  2)  F32 (n) - W16 F33 (n) -4n (6.33) F22 (n)  F34 (n)  W16 F35 (n) -4n (6.34) F22 (n  2)  F34 (n) - W16 F35 (n) 84