A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms

Authors:
G. Steidl and M. Tasche

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

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The discrete Fourier-cosine transform , the discrete Fourier-sine transform 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 , the and the DCT, which is based on polynomial arithmetic with Chebyshev polynomials and on the Chinese Remainder Theorem.

**[1]**A. V. Aho, J. E. Hopcroft, and J. D. Ullmann,*The design and analysis of computer algorithms*, Addison-Wesley, Reading, Mass., 1976. MR**0413592 (54:1706)****[2]**G. Bruun,*z-transform*DFT*filters and*FFTs, IEEE Trans. Acoust. Speech Signal Process.**26**(1978), 56-63.**[3]**P. Duhamel,*Implementation of "split-radix"*FFT*algorithms for complex, real and realsymmetric data*, IEEE Trans. Acoust. Speech Signal Process.**34**(1986), 285-295. MR**835552 (87e:94006)****[4]**D. Garbe,*On the level of irreducible polynomials over Galois fields*, J. Korean Math. Soc.**22**(1985), 117-124. MR**826437 (87d:11093)****[5]**I. S. Gradshteĭn and I. M. Ryzhik,*Tables of integrals, sums, series and products*, Nauka, Moscow, 1971. (Russian)**[6]**M. T. Heideman and C. S. Burrus,*On the number of multiplications necessary to compute a length*- DFT, IEEE Trans. Acoust. Speech Signal Process.**34**(1986), 91-95. MR**832319 (87e:94007)****[7]**H. S. Hou,*A fast recursive algorithm for computing the discrete cosine transform*, IEEE Trans. Acoust. Speech Signal Process.**35**(1987), 1455-1462.**[8]**B. G. Lee,*A new algorithm to compute the discrete cosine transform*, IEEE Trans. Acoust. Speech Signal Process.**32**(1984), 1243-1245.**[9]**M. J. Narasimha and A. M. Peterson,*On computing the discrete cosine transform*, IEEE Trans. Comm.**26**(1978), 934-936.**[10]**H. J. Nussbaumer,*Fast Fourier transform and convolution algorithms*, Springer, Berlin-Heidelberg-New York, 1981. MR**606376 (83e:65219)****[11]**S. Paszkowski,*Numerical application of Chebyshev polynomials and series*, Nauka, Moscow, 1983. (Russian)**[12]**T. J. Rivlin,*The Chebyshev polynomials*, Wiley, New York-London-Sydney-Toronto, 1974. MR**0450850 (56:9142)****[13]**H. V. Sorensen, D. L. Jones, C. S. Burrus, and M. T. Heideman,*On computing the discrete Hartley transform*, IEEE Trans. Acoust. Speech Signal Process.**33**(1985), 1231-1238. MR**811328 (87e:94008)****[14]**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.**[15]**M. Vetterli and H. J. Nussbaumer,*Simple*FFT*and*DCT*algorithms with reduced number of operations*, Signal Process.**6**(1984), 267-278. MR**760430 (85m:65128)****[16]**S. Winograd,*On computing the discrete Fourier transform*, Math. Comp.**32**(1978), 175-199. MR**0468306 (57:8142)****[17]**-,*Arithmetic complexity of computations*, CBMS Regional Conf. Ser. in Math., vol. 33, SIAM, Philadelphia, 1980. MR**565260 (81k:68039)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65T20,
94A11

Retrieve articles in all journals with MSC: 65T20, 94A11

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1991-1052103-1

Keywords:
Discrete Fourier-cosine transform,
discrete Fourier-sine transform,
discrete cosine transform,
polynomial arithmetic,
Chebyshev polynomials,
computational complexity,
discrete Fourier transform

Article copyright:
© Copyright 1991
American Mathematical Society