Loading...
Please wait, while we are loading the content...
Similar Documents
The Fast Fourier Transform 7.1 Introduction 7.2 Radix-2 Fft Algorithms 7.2.1 Decimation-in-time Fft
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | In Chap. 6 we saw that the discrete Fourier transform (DFT) could be used to perform convolutions. In this chapter we look at the computational requirements of the DFT and derive some fast algorithms for computing the DFT. These algorithms are known, generically, asfast Fourier fransforms (FFTs). We begin with the radix-2 decimation-in-time FFT, an algorithm published in 1965 by Cooley and Tukey. We then look at mixed-radix FFT algorithms and the prime factor FFT. The N-point DFT of an N-point sequence s (n) is Because x(n) may be either real or complex, evaluating X(k) requires on the order of N complex multiplications and N complex additions for each value of k. Therefore, because there are N values of X(k), computing an N-point DFT requires N* complex multiplications and additions. The basic strategy that is used in the FFT algorithm is one of "divide and conquer." which involves decomposing an N-point DFT into successively smaller DFTs. To see how this works, suppose that the length of x(n) is even (i.e., N is divisible by 2). If x(n) is decin~ared into two sequences of length N/2, computing the N/2-point DFT of each of these sequences requires approximately (N 12)' multiplications and the same number of additions. Thus, the two DFTs require 2 (~ / 2) ' = { N' multiplies and adds. Therefore, if it is possible to find the N-point DFT of s (n) from these two N/2-point DFTS in fewer than N2/2 operations, a savings has been realized. The decimation-in-time FFT algorithm is based on splitting (decimating) x(n) into smaller sequences and finding X (k) from the DFTs of these decimated sequences. This section describes how this decimation leads to an efficient algorithm when the sequence length is a power of 2. Let x(n) be a sequence of length N = 2", and suppose that x(n) is split (decimated) into two subsequences, each of length N/2. As illustrated in Fig. 7-1, the first sequence, ~ (I z) , is formed from the even-index terms, and the second, h(n), is formed from the odd-index terms, |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.wbuthelp.com/chapter_file/366.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
