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

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

Thêm vào BST

Báo xấu

64
lượt xem 6
download

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

Nén ảnh lμ một kỹ thuật mã hoá hiệu suất cao ảnh số nhằm lμm giảm số bit cần cho biểu diễn ảnh. Chức năng của kỹ thuật nμy lμ giảm độ lớn dữ liệu phải lu trữ cùng với thời gian truyền trong khi vẫn giữ nguyên chất lợng của ảnh.

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 3

/* Taking FFT. */ FFT(xr, xi, wr, wi, m, N); printf("Enter file name for storing FFT output.--->"); scanf("%s",file_name); fptr=fopen(file_name,"w"); for(i=0;i
float theta; n2=(N>>1)-1; /* Generate look-up tables for twiddle factor. */ theta=2.0*pi/((float)N); for(i=0;i
{ for(j=0; j
Chó ý r»ng trong ch¬ng tr×nh 6.1 chóng ta gi¶ thiÕt lµ d÷ liÖu ®îc lu nh d·y cña c¸c ký tù kh«ng dÊu. NÕu b¹n muèn xö lý trªn mét sè dÊu phÈy ®éng b¹n cÇn thay ®æi c¸c c©u lÖnh më vµ ®äc d÷ liÖu trong file d÷ liÖu. Ch¬ng tr×nh nµy còng cho phÐp lùa chän FFT hoÆc IFFT. Cho FFT, ch¬ng tr×nh con "WTS(...) " tÝnh to¸n vµ lu c¸c hÖ sè dÞch xoay trong mét LUT ®îc gäi lªn vãi tham sè "sign" ®îc g¸n gi¸ trÞ -1, vÝ dô, WTS(wr,wi,N,-1) vµ cho IFFT, WTS(wr,wi,N,1). Víi IFFT, b¹n cÇn chia d·y ra cho N trong ch¬ng tr×nh gäi hoÆc lµ ch¬ng tr×nh chÝnh. Bµi tËp 6.2 KiÓm tra ch¬ng tr×nh FFT b»ng c¸ch lµm l¹i ch¬ng tr×nh 6.1. Chó ý r»ng trong trêng hîp nµy b¹n ph¶i thªm c¸c gi¸ trÞ 0 ®Ó lµm cho c¸c d·y cã chiÒu dµi 24 = 16 vµ tÊt nhiªn lµ lín h¬n chiÒu dµi d·y nhá nhÊt ®ßi hái lµ (6 + 5 - 1). Mèi t¬ng quan cña hai d·y cho kÕt qu¶ trong mét tÝn hiÖu tuÇn hoµn cã chu kú b»ng 16. 6.3.2 ThuËt to¸n ph©n chia tÇn sè. Thay v× chia d·y vµo thµnh c¸c vÞ trÝ ch½n vµ lÎ, chóng ta sÏ ®a ra mét ch¬ng tr×nh gièng nh ch¬ng tr×nh trªn nhng lÇn nµy ta b¾t ®Çu tõ d·y ra. Ch¬ng tr×nh nµy bao gåm c¸c bíc sau: N / 2 1 N 1  kn  kn  f (k )W  f (k )W F ( n)   N N k 0 k N / 2 N / 2 1 N   f (k )  W nN / 2 f (k  )W N kn    2  k 0 B©y giê, chia d·y F(n) thµnh hai d·y dùa trªn gi¸ trÞ ch½n vµ lÎ cña n. N / 21 N  [ f (k )  W ( 2n).N / 2 f (k  )]W N kn  F ( 2n)  /2 2 k 0 N / 2 1 N )]WN k 22 n1) (  [ f (k )  W (2n 1).N / 2 f (k  F (2n  1)  / 2 k 0 W N nN  e  j 2n  1.0  Chó ý r»ng W N (2n1).N / 2  e  j (2 1)n  1.0  V× vËy 98
N / 21 N )]WN kn   [ f (k )  f (k  F ( 2n)  /2 2 k 0 N / 21 N ) WN k ]WN kn     [ f (k )  f (k  F (2n  1)  /2 2 k 0 N §Æt f 10 ( k )  f ( k )  f ( k  ) 2 N )]WN k  f 11 ( k )  [ f ( k )  f ( k  2 V× vËy N / 21  f10 (k ).W N kn  F ( 2n)  /2 (6.39) k 0 N / 2 1  f11 (k ).W N kn  F (2n  1)  /2 (6.40) k 0 C¸c biÓu thøc (6.39) vµ (6.40) cã thÓ biÓu diÔn b»ng díi d¹ng biÓu ®å bím nh trong h×nh 6.6. Chóng ta cã thÓ tiÕp tôc chia nhá c¸c tæng cho trong c¸c biÓu thøc (6.39) vµ (6.40), tiÕp tôc lµm nh vËy cho tíi khi mçi tæng gi¶m xuèng chØ cßn l¹i mét phÇn tö. Gi¶i thuËt nµy gièng nh gi¶i thuËt thuËt to¸n ph©n chia thêi gian vµ ®Ó l¹i cho b¹n nh mét bµi tËp cho b¹n. Mét lu ®å cho FFT ph©n chia tÇn sè víi N = 4 tr×nh bµy trong h×nh 6.7. B¹n cÇn chó ý ®Õn bËc cña d÷ liÖu ®Çu ra lµ bit ®îc ®¶o. PhÇn mÒm thùc hiÖn thuËt to¸n trªn th× rÊt gièng phÇn mÒm thùc hiÖn FFT ph©n chia miÒn thêi gian, vµ mét ch¬ng tr×nh C ®îc cung cÊp ë Ch¬ng tr×nh 6.2. Cã lÏ b¹n sÏ tù hái: nÕu ph©n chia miÒn thêi gian ®· thùc hiÖn ®îc c«ng viÖc th× t¹i sao l¹i ph¶i xem xÐt thªm FFT ph©n chia tÇn sè. §Ó tr¶ lêi c©u hái nµy, chóng ta sÏ cÇn xem xÐt phÇn kÕ tiÕp, FFT gi¶m lîc. Ch¬ng tr×nh 6.2 FFTDF FFT ph©n chia tÇn sè. 99
/**************************** * Program developed by: * * M.A.Sid-Ahmed. * * ver. 1.0 1992.1994 * *****************************/ /* FFT - Decimation-in-frequency routine.*/ #define pi 3.141592654 void bit_reversal (unsigned int *, int, int); void WTS(float *, float *, int, int) ; void FFT(float *xr, float *xi , float, float, int, int); void FFT (float *xr, float *xi, float *wr, float *wi, int m, int N) { /* FFT algorithm. Decimation-in-frequency algorithm. Note : 1. N=2 to the power of m. 2. The output arrays are left in bit-reverse order. You will need to use routine "bit-reversal" to place them in normal ascending order. 3. The twiddle factors are assumed to be stored in LUT's wr[j and wiEj. 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,diffr,diffi; 100
W n W 2 n W 4 n W 8 n 0 0 0 0 0 0 1 2 4 8 8 0 0 2 4 8 4 4 4 0 3 6 12 12 12 2 0 4 8 2 2 2 4 5 10 6 10 10 0 6 0 6 12 12 6 6 4 7 14 14 14 14 0 8 1 1 1 1 0 9 3 5 9 9 1 0 0 10 5 9 5 5 2 4 0 11 7 13 13 13 3 0 2 12 9 3 3 3 4 4 13 11 7 11 11 5 0 0 6 14 13 11 7 7 6 4 15 15 15 15 15 7 H×nh 6.7 N = 4, ph©n chia miÒn tÇn sè FFT. ip= (N>>1) ; kk=1; incr=N; for(iter=0; iter
xr[j]=xr[j]+Tr; xi[j]=xi[j]+Ti; } for(k=1;k=1; } } 6.3.3 FFT gi¶m lîc VÊn ®Ò cã thÓ b¾t ®Çu tõ: cho 2M ®iÓm d÷ liÖu, chóng ta sÏ ph¶i lµm thÕ nµo tÝnh to¸n nhanh nhÊt khi dïng FFT cã 2L ®iÓm ra víi M  L? NÕu M < L, cã mét sè bím sÏ bÞ gi¶m lîc (xem h×nh 6.8). Mét gi¶i thuËt dùa trªn tÝnh to¸n c¸c phÇn tö cña bím khi viÖc tÝnh to¸n tÊt c¶ c¸c phÐp tÝnh lµ kh«ng cÇn thiÕt trong trêng hîp M < L gäi lµ gi¶i thuËt gi¶m lîc ®Çu vµo FFT. Trong trêng hîp M > L thuËt to¸n gäi lµ thuËt to¸n gi¶m lîc ®Çu ra FFT. 102
ThuËt to¸n gi¶m lîc ®Çu vµo FFT. Trêng hîp nµy sÏ lµm hoµn thiÖn h¬n thuËt to¸n ph©n chia tÇn sè. H×nh 6.8 giíi thiÖu trêng hîp M = 1 vµ L = 4. Tõ h×nh 6.8 chóng ta nhËn thÊy (L-M) bíc ®Çu tiªn cã c¸c phÇn tö bím vµ L bíc cuèi cïng cã toµn bé c¸c bím. S¬ ®å nµy gióp chóng ta thay ®æi ch¬ng tr×nh 6.2 thµnh ch¬ng tr×nh 6.3. Ch¬ng tr×nh 6.3 "FFTIP.C". Gi¶m lîc ®Çu vµo FFT. /**************************** * Program developed by: * * M.A.Sid-Ahmed. * * ver. 1.0 1992. * * @ 1994 * ***************************/ /* FFT - input pruning routine. */ 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); void FFTP(float *xr, float *xi, float *wr, float *wi, int m_output, int N_output, int m_input, int N_input ) { /* FFT pruning algorithm. Deimation-in-frequency algorithm. Note: 1. Noutput=2 to the power of m_output. N_output=Number of samples in the output sequence. M_input=Number of samples in the input sequence. This should also be a multiple of 2. 2. The output arrays are left in bit-reverse order. You will need to use routine "bit-reversal" to place them in normal ascending order. 103
3. The twiddle factors are assumed to be stored in LUT's wr[I and wi[I. You will need to use routine LUT for calculating and storing twiddle factors. */ int ip,k,kk,l,inc r,iter,j,i; float Tr,Ti,diffr,diffi; ip=N_output>>1; kk=l ; incr=N_output; for(iter=0; iter