Computation of an odd-length DCT from a real-valued DFT of the same length

Author

Heideman, Michael T.

Author_Institution

Etak Inc., Menlo Park, CA, USA

Volume

40

Issue

1

fYear

1992

fDate

1/1/1992 12:00:00 AM

Firstpage

54

Lastpage

61

Abstract

The discrete cosine transform (DCT) is often computed from a discrete Fourier transform (DFT) of twice or four times the DCT length. DCT algorithms based on identical-length DFT algorithms generally require additional arithmetic operations to shift the phase of the DCT coefficients. It is shown that a DCT of odd length can be computed by an identical-length DFT algorithm, by simply permuting the input and output sequences. Using this relation, odd-length DCT modules for a prime factor DCT are derived from corresponding DFT modules. The multiplicative complexity of the DCT is then derived in terms of DFT complexities

Keywords

fast Fourier transforms; DCT algorithms; DCT coefficients; DCT modules; DFT modules; discrete Fourier transform; discrete cosine transform; identical-length DFT algorithms; input sequences; multiplicative complexity; odd length DCT; output sequences; prime factor DCT; real valued DFT; Arithmetic; Data compression; Discrete Fourier transforms; Discrete cosine transforms; Discrete transforms; Fourier transforms; Helium; Polynomials;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.157181

Filename

157181