Ch5_DFT数字信号处理.ppt

Discrete Cosine Transform A special style for DFT. DCT represents a real time-domain sequence x[n] by a real transform-domain sequence X[k]. A kind of useful tool to help process digital images. Detail algorithm in P274, please read it after the class. Homework Writing a thesis to introduce DCT , you should explain: It’s engineering background. It’s transform signification. Question put forward: DFT and IDFT definition: Where, Direct computation of all N samples of {X[k]} requires N2 complex multiplications and N(N-1) complex additions. If we reexamine the twiddle factor WN: WN= e-j(2π/N) We can see that the same values of WN are calculated many times during the DFT, since WN is a periodic function with a limited number of distinct values. The aim of the FFT and its inverse, the IFFT, is to use this redundancy to reduce the number of calculation. The properties of WN: Symmetry: Periodicity: Reduction: We can get: Decimation-in-Time FFT Given a sequence x[n] whose length is N=2L, L is an integer. And divided the sequence into odd sequences and even sequences: It’s DFT is: Decimation-in-Time FFT We get: Where X1[k] and X2[k] is N/2-point DFT, so we get only first half N/2-point result of X(k). Based on the periodicity of WN, we can get: Decimation-in-Time FFT The same as above: And: So the expression of X[k] in latter half is: Decimation-in-Time FFT Block-diagram interpretation: ?2 x[n] x0[n]=x[2n] ?2 x[n] x1[n]=x[2n+1] z x[n+1] N/2-point DFT N/2-point DFT ?2 ?2 z Decimation-in-Time FFT The computation of N-point DFT by two methods: DFT computation Complex Addition Complex Multiplication Direct computation N2-N?N2 N2 DIT to two N/2-point DFT (N2/2)+N (N2/2)+N For N?3, (N2/2)+N N2 Decimation-in-Time FFT Continuing the process we can express X0[k] and X1[k] as a weighted combination of two (N/4)-point DFTs. For example, we can write: where X00[k] and X01[k] are the (N/4)-point DFTs of the (N/4)-length sequences: x00[n]= x0[2n] and x01[n]=