数字信号处理a双语chapter11-discretefouriertransformcomputationnew-140325

1、Chapter 11 DSP Algorithm Implementation,11.3 Computation of the DFT,11.3 Computation of the DFT,In order to compute the DFT or IDFT of a length-N sequence, one needs,N2 complex multiplications,N(N-1) complex additions,The complexity of the DFT grows with the square of the signal length.,It requests

2、a fast algorithm urgently.,This severely limits its practical use for lengthy signals.,for example: N=8 needs 64 complex multiplications. N=1024 needs 1,048,576 complex multiplications.,In 1965, Cooley and Tukey proposed an efficient algorithm to compute the DFT, that is DIT-FFT.,11.3 Computation of

3、 the DFT,11.3.2 Cooley-Tukey FFT Algorithms,Ways to decrease the complexity:,Using the properties of the,Decompose the long sequence into shorten sequence to compute DFT,Combine the some item of DFT computation.,Decimation in time Decimation in frequency,11.3.2 Cooley-Tukey FFT Algorithms,Radix-2 al

4、gorithm with decimation in time-DIT FFT,1. Principle of algorithm,Suppose: x(n) length N=2L,split x(n) into two parts,even-index,odd-index,2n,2n+1,11.3.2 Cooley-Tukey FFT Algorithms,N/2 points DFT,N/2 points DFT,Decompose length-N DFT into two length-N/2 DFT,However, we only compute the N/2 points o

5、f length-N DFT at beginning, and remind other N/2 points.,11.3.2 Cooley-Tukey FFT Algorithms,Now, we obtain the remind N/2 points of length-N DFT.,11.3.2 Cooley-Tukey FFT Algorithms,called basic cell of the algorithm, and its signal flow graph is,also called a butterfly,11.3.2 Cooley-Tukey FFT Algor

6、ithms,for example N=8=23,11.3.2 Cooley-Tukey FFT Algorithms,each butterfly needs,one complex multiplication two complex additions,so,after one decomposed,its number of computation is almost half of direct DFT.,11.3.2 Cooley-Tukey FFT Algorithms,Now, xe(n) and xo(n) is length N/2 sequences, and N/2 a

7、lso even,then they can be splited into even-index and odd-index parts furthermore,11.3.2 Cooley-Tukey FFT Algorithms,then, like the first decomposing,and,11.3.2 Cooley-Tukey FFT Algorithms,as the example above N=8=23, and after second decomposing,11.3.2 Cooley-Tukey FFT Algorithms,Resembly, we can d

8、ecompose it to length-2 DFT at last,expressed as,11.3.2 Cooley-Tukey FFT Algorithms,as the example above N=8=23, at last,11.3.2 Cooley-Tukey FFT Algorithms,2. Number of computation,from the signal flow graph of DIT-FFT, we can see that if N=2L, then there are L levels butterfly cells,N/2 butterflies

9、 per level,total L levels to complete length-N DFT,in fact, WN0=1 (N-1) and WN N/4=-j (N/2-1) neednt multiplication,11.3.2 Cooley-Tukey FFT Algorithms,since multiplication costs far more than addition, so we only take care of multiplication,11.3.2 Cooley-Tukey FFT Algorithms,3. Features of DIT-FFT,

10、in place computations,from the basic cell,and signal flow graph,11.3.2 Cooley-Tukey FFT Algorithms,we can see that the nodes of one section of the graph depend only on nodes of the previous section of the graph.,in place computation could save storage, and reduce the cost.,therefore, once computed,

11、the values of and can be stored in the same place as and .,11.3.2 Cooley-Tukey FFT Algorithms, bit-reversed order index,as seen in signal flow graph, the output vector is ordered sequentially while the input vector is not.,begin with decimation in time,Note: N=2L,11.3.2 Cooley-Tukey FFT Algorithms,

12、bit-reversed order index,For example, N=8 :,Normal order (decimal),Normal order (binary),Bit-reversed order (binary),Bit-reversed order (decimal),0 1 2 3 4 5 6 7,000 001 010 011 100 101 110 111,000 100 010 110 001 101 011 111,0 4 2 6 1 5 3 7,11.3.2 Cooley-Tukey FFT Algorithms, Distance between nodes

13、 of butterfly,N=8 for example,level distance,1,2,3,1,2,4,conclusion : m-th level, distance is 2m-1,11.3.2 Cooley-Tukey FFT Algorithms, Determination for WNr,m-th level DIT butterfly could be expressed as,r equals to the k left shift L-m bits, and zero padded at right.,for example,11.3.2 Cooley-Tukey

14、 FFT Algorithms,Radix-2 algorithm with decimation in frequency -DIF FFT,DIT-FFT divides the input sequence x(n) into smaller and smaller subsequences.,Suppose: x(n) length N=2L,Alternatively, we can consider dividing the output sequence X(k) in the same way.,11.3.2 Cooley-Tukey FFT Algorithms,11.3.2

15、 Cooley-Tukey FFT Algorithms,also a butterfly basic cell,Note: DIF VS DIT,one complex multiplication two complex additions,11.3.2 Cooley-Tukey FFT Algorithms,For example N=8,11.3.2 Cooley-Tukey FFT Algorithms,at last,11.3.2 Cooley-Tukey FFT Algorithms,2. Number of computation,from the signal flow gr

16、aph of DIF-FFT, we can see that if N=2L, then there are L levels butterfly cells,N/2 butterflies per level,total L levels to complete length-N DFT,in fact, WN0=1 (N-1) and WN N/4=-j (N/2-1) need not multiplication,11.3.2 Cooley-Tukey FFT Algorithms,3. Features of DIF-FFT, in place computations, bit-

17、reversed index,as seen in signal flow graph, the input vector is ordered sequentially while the output vector is bit-reversed index., Distance between nodes of butterfly,N=8 for example,conclusion : m-th level, distance is 2L-m, Determination for WNr,r equals to the k left shift m-1 bits, and zero p

18、added at right.,is similar to that of DIT-FFT,11.3.2 Cooley-Tukey FFT Algorithms,Alternative form of radix-2 DIT and DIF,follow the feature of the flow graph, we can obtain some alternative form,DIT-FFT N=8 for example,11.3.2 Cooley-Tukey FFT Algorithms,11.3.2 Cooley-Tukey FFT Algorithms,11.3.4 Inverse DFT Computation,differences are:,11.3.4 Inverse DFT Computation,for