819信号系统与信号处理教学课件chapter9b.fast algorithms for discrete fourier transform

1、B. Fast Algorithms for Discrete Fourier TransformB.1. Introduction (9.0, 9.1)B.2. Radix-2 Decimation-in-Time FFT (9.3, 9.5)B.3. Radix-2 Decimation-in-Frequency FFT (9.4, 9.5)B.4. FFT for a More General N (9.5)B.5. Inverse Fast Fourier TransformB.1. Introduction The discrete Fourier transform (DFT) c

2、an be computed by using a class of fast algorithms called the fast Fourier transform (FFT). The principle of the FFT is to pose the DFT into shorter DFTs and butterfly operations, which can be carried out more efficiently. The FFT algorithms apply when the length of the sequence is a composite integ

3、er initially or after zero padding.B.2. Radix-2 Decimation-in-Time FFTB.2.1. Principle Let us assume that x(n) is a finite-length sequence over 0nN-1, where N=2m (m2) initially or after zero-padding. The DFT of x(n) is defined as(B.1)x(n) is separated into two sequences. One consists of even-numbere

4、d samples, and the other consists of odd-numbered samples. Thus,(B.2)X(k) is halved. The first half is(B.3)(B.5)The second half is(B.4)which is also written asThe radix-2 decimation-in-time FFT is based on (B.3) and (B.5). According to (B.3) and (B.5), the DFT can be computed using the following alg

5、orithm (figure B.1): (1) Find the DFT of N/2 the even-numbered samples and the DFT of the N/2 odd-numbered samples. (2) Compute the DFT of the original sequence using (B.3) and (B.5). The above position is continued until each DFT has only 1 point. The 1-point DFTs contain no operation and do not ha

6、ve to be carried out. The number of complex multiplications required in this algorithm is N(log2N)/2. This number is less than N2, the number of complex multiplications required in the direct DFT. The following table gives a few typical cases.N51210242048N226214410485764194304N(log2N)/22304512011264

7、DFT(N/2)Figure B.1. Radix-2 Decimation-in-Time FFT.x(0)x(2)x(N-2)DFT(N/2)exp-j2(N/2-1)/Nexp-j20/Nexp-j21/Nx(1)x(3)x(N-1)-X(0)X(1)X(N/2-1)X(N/2)X(N/2+1)X(N-1)B.2.2. Several Details This algorithm consists of two steps: the sequence reordering and the butterfly operation. The time sequence is reordere

8、d in the bit-reversed way. That is, the sample at position bm-1bm-2b0 (binary index) is transferred to position b0b1bm-1 (binary index). The above table shows the case of N=8.x(n)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)OldPosition00000011010201131004101511061117NewPosition00001004010211060011101501131117 Th

9、e butterfly operation can be carried out using three nested loops or recursively. It is an in-place operation. That is, in each stage of computation, the output sequence and the input sequence can use the same memory space. A few variations of this algorithm can be obtained by changing the orders of

10、 the input sequence and of the output sequence.B.3. Radix-2 Decimation-in-Frequency FFTB.3.1. Principle Let us assume that x(n) is a finite-length sequence over 0nN-1, where N=2m (m2) initially or after zero-padding. The DFT of x(n) is defined as(B.6)X(k) is separated into two sequences. One consist

11、s of even-numbered(B.7)(B.8)x(n) is halved. (B.7) es(B.9)andsamples, and the other consists of odd-numbered samples. Thus,which is also written as(B.10)and further(B.11)(B.8) es(B.12)which is also written as(B.13)and further(B.14)The radix-2 decimation-in-frequency FFT is developed according to (B.1

12、1) and (B.14). According to (B.11) and (B.14), the DFT can be computed using the following algorithm (figure B.2): (1) Find sequences x(n)+x(n+N/2) and x(n)-x(n+N/2)exp(-j2n/N), where 0nN/2-1. (2) Find the DFTs of the two sequences. The above position is continued until each DFT has only 1 point. Th

13、e 1-point DFTs contain no operation and do not have to be carried out. The number of complex multiplications required in this algorithm is N(log2N)/2. This number is less than N2, the number of complex multiplications required in the direct DFT. The following table gives a few typical cases.N5121024

14、2048N226214410485764194304N(log2N)/22304512011264Figure B.2. Radix-2 Decimation-in-Frequency FFT.x(0)x(1)x(N/2-1)x(N/2)x(N/2+1)x(N-1)-exp-j2(N/2-1)/Nexp-j20/Nexp-j21/NDFT(N/2)DFT(N/2)X(0)X(2)X(N-2)X(1)X(3)X(N-1)B.3.2. Several Details This algorithm consists of two steps: the butterfly operation and

15、the sequence reordering. The butterfly operation can be carried out by three nested loops or recursively. It is an in-place operation. That is, in each stage of computation, the output sequence and the input sequence can use the same memory space.X(k)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)OldPosition000010

16、04010211060011101501131117NewPosition00000011010201131004101511061117 The frequency sequence is reordered in the bit-reversed way. That is, the sample at position bm-1bm-2b0 (binary index) is transferred to position b0b1bm-1 (binary index). The above table gives the case of N=8. A few variations of

17、this algorithm can be obtained by changing the orders of the input sequence and of the output sequence.B.4. FFT for a More General N When the length of the sequence is a composite integer initially or after zero padding, the FFT applies. Assume that x(n) is a finite-length sequence over 0nN-1, where

18、 N=N1N2 (N1 and N2 are two positive integers not equal to 1) initially or after zero-padding. The DFT of x(n) is defined as(B.15)Letting n=n1N2+n2, 0n1N1-1, 0n2N2-1 and k=k2N1+k1, 0k1N1-1, 0k2N2-1, we obtain(B.16)which is further written as(B.17)Changing the order of the summations, we obtain(B.18)

19、According to (B.18), the DFT can be computed by the following algorithm: (1) For each n2, compute the DFT of x(n1N2+n2) with respect to n1 to obtain p(k1,n2). (2) Multiply p(k1,n2) by exp(-j2k1n2/N) to obtain q(k1,n2). (3) For each k1, compute the DFT of q(k1,n2) with respect to n2 to obtain X(k2N1+

20、k1). The number of complex multiplications required in this algorithm is N(N1+N2+1). This number is less than N2, the number of complex multiplications required in the direct DFT. The above position can be continued and the computation can be further reduced until each DFT has a prime number of points.B.5. Inverse Fast Fourier Transform A class of fast algorithms called the inverse fast Fourier transform (IFFT) can be used to compute the inverse disc