A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms
HTML articles powered by AMS MathViewer
- by G. Steidl and M. Tasche PDF
- Math. Comp. 56 (1991), 281-296 Request permission
Abstract:
The discrete Fourier-cosine transform $(\cos {\text {-DFT}})$, the discrete Fourier-sine transform $(\sin {\text {-DFT}})$ and the discrete cosine transform (DCT) are closely related to the discrete Fourier transform (DFT) of real-valued sequences. This paper describes a general method for constructing fast algorithms for the $(\cos {\text {-DFT}})$, the $(\sin {\text {-DFT}})$ and the DCT, which is based on polynomial arithmetic with Chebyshev polynomials and on the Chinese Remainder Theorem.References
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592 G. Bruun, z-transform DFT filters and FFTs, IEEE Trans. Acoust. Speech Signal Process. 26 (1978), 56-63.
- Pierre Duhamel, Implementation of “split-radix” FFT algorithms for complex, real, and real-symmetric data, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), no. 2, 285–295. MR 835552, DOI 10.1109/TASSP.1986.1164811
- Dietmar Garbe, On the level of irreducible polynomials over Galois fields, J. Korean Math. Soc. 22 (1985), no. 2, 117–124. MR 826437 I. S. Gradshteĭn and I. M. Ryzhik, Tables of integrals, sums, series and products, Nauka, Moscow, 1971. (Russian)
- Michael T. Heideman and C. Sidney Burrus, On the number of multiplications necessary to compute a length-$2^n$ DFT, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), no. 1, 91–95. MR 832319, DOI 10.1109/TASSP.1986.1164785 H. S. Hou, A fast recursive algorithm for computing the discrete cosine transform, IEEE Trans. Acoust. Speech Signal Process. 35 (1987), 1455-1462. B. G. Lee, A new algorithm to compute the discrete cosine transform, IEEE Trans. Acoust. Speech Signal Process. 32 (1984), 1243-1245. M. J. Narasimha and A. M. Peterson, On computing the discrete cosine transform, IEEE Trans. Comm. 26 (1978), 934-936.
- Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. MR 606376 S. Paszkowski, Numerical application of Chebyshev polynomials and series, Nauka, Moscow, 1983. (Russian)
- Theodore J. Rivlin, The Chebyshev polynomials, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0450850
- Henrik V. Sorensen, Douglas L. Jones, C. Sidney Burrus, and Michael T. Heideman, On computing the discrete Hartley transform, IEEE Trans. Acoust. Speech Signal Process. 33 (1985), no. 5, 1231–1238. MR 811328, DOI 10.1109/TASSP.1985.1164687 H. V. Sorensen, D. J. Jones, M. T. Heideman, and C. S. Burrus, Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech Signal Process. 35 (1987), 849-863.
- Martin Vetterli and Henri J. Nussbaumer, Simple FFT and DCT algorithms with reduced number of operations, Signal Process. 6 (1984), no. 4, 267–278 (English, with French and German summaries). MR 760430, DOI 10.1016/0165-1684(84)90059-8
- S. Winograd, On computing the discrete Fourier transform, Math. Comp. 32 (1978), no. 141, 175–199. MR 468306, DOI 10.1090/S0025-5718-1978-0468306-4
- Shmuel Winograd, Arithmetic complexity of computations, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 33, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1980. MR 565260
Additional Information
- © Copyright 1991 American Mathematical Society
- Journal: Math. Comp. 56 (1991), 281-296
- MSC: Primary 65T20; Secondary 94A11
- DOI: https://doi.org/10.1090/S0025-5718-1991-1052103-1
- MathSciNet review: 1052103