The Algorithm Of DFT With A Subset Of Output Points Based On TS101 And Its Software Implementation

A lot of fast Fourier transform algorithms have been developed after the discovery of the radix-2 FFT by Cooley and Tukey in 1965.These algorithms make different assumptions about the transform length, N , but they all assume that the input and the output sequence lengths are equal. For most applications this is a reasonable assumption, but there remain some applications where the number of input and output points differ significantly, such as computing a high-resolution spectrum of eigenvalues in array processing or computing the transition-region (between the passband and stopband)response in a filter design. Moreover, the conflict between the computation and transform length of FFT makes it restricted in application. Because if you want to improve the resolution of the fast Fourier transform, you had to increase the sampling points and it will take more computation. Otherwise, we may don't need all the output frequency points, when the data is long enough, we just need part of the frequency band or a subset of the output points. Then the computation on the output points that we don't need is redundant. How to found a more efficient algorithm to compute the DFT with a subset of output points has caught many researchers'attention.First, this paper introduces several kind of algorithms about the DFT with a subset of output points such as Goertzel algorithm, FFT Pruning algorithm and transform decomposition algorithm, and gets their formulas of computation complexity in theory, then compares their computation complexity in theory.Then, combining with split-radix FFT algorithm, Goertzel algorithm we improve on transform decomposition algorithm, and improve the efficiency of transform decomposition algorithm further. After that, this paper introduces the method of software design of correlate algorithm, and run emulated computation took TS101 as the target processor. That validates the conclusion of theory derivation. The result shows that After that transform decomposition algorithm is the most efficient algorithm for the DFT a subset of output points. Moreover, we discuss the effect on total computation by different value of P in the algorithm of transform decomposition. Considering the addressing operations, we get the optimum value formula of P. While P gets its optimum value, for a DFT with 1024 points transform length and 16 points output the transform decomposition algorithm can decrease about 36% running time comparing with radix-2 FFT.At the end of the paper, we discuss the DFT algorithm when the input value is real, and using the real split-radix FFT algorithm we improve the algorithm for the DFT with a subset of output points further.