Efficient Computation of Subset of Output Points of FFT
Abstract
This paper presents efficient pruning algorithms for computing the length q x 2p DFT for a subset of output points based on transform decomposition method and in new results in computation of FFT.
References
J.W. Cooley and J.W. Tukey, “An algorithm for the machine computation of the complex Fourier series", Math. Computation, pp. 297-301, 1965.
R. Blahut, Fast Algorithms for Digital Signal Processing. Addison-Wesley, 1985.
R. Yavne, “An economical method for calculating the discrete Fourier transform, "Proc. AFIPS Fall Joint Computer Conf., pp. 115-125, 1968.
M. Frigo and S.G. Johnson, “A modified split-radix FFT with fewer arithmetic operations", IEEE Trans. Signal Proccessing, - vol. 55, pp. 111-119, 2007.
H. Sarukhanyan, R. Barseghyan, “New Efficient FFT with Fewer Operations", CSIT, pp. 351-354, 2009.
G. Goertzel, “An Algorithm for the evaluation of finite trigonometric series", Amer. Math. Monthly, pp. 34-35, 1958.
C.G. Boncelet, “A rear ranged DFT algorithm requiring N2/6 multiplications, "IEEE Trans. Acoust., Speech, Signal Processing, pp. 1658-1659, 1986.
R. de Wild, “Method for partial spectrum computation, "Proc. Inst. Elec. Eng., pp. 659-666, 1987.
J.D. Markel, “FFT pruning," IEEE Trans. Audio Electroacoust, pp. 305-311, 1971.
H.V. Sorensen, C.S. Burrus, and D.L.Jones, “A new efficient algorithm for computing a few DFT points, "Proc. IEEE Int., pp. 1915-1918, 1988.
R. Barseghyan, “Split-radix FFT algorithm with lifting steps, "Vestnik RAU, Series: Physics-mathematics and natural science pp. 41-51, 2009.
H. Sarukhanyan, R. Barseghyan, “New Approach to FFT algorithms", Mathematical Problems of Computer Science, vol. 33, pp. 24-34, 2010.
G. Bi and Y.Q. Chen, "Fast DFT algorithms for length," IEEE Trans. Circuits and Syst.-II: Analog and Digital Signal Processing, pp. 685-690, 1998.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
