1d Real-even DFTs (DCTs)

cannam@95: cannam@95: cannam@95: 1d Real-even DFTs (DCTs) - FFTW 3.3.3 cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95:

cannam@95: cannam@95: cannam@95:

cannam@95: Next: 1d Real-odd DFTs (DSTs), cannam@95: Previous: The 1d Real-data DFT, cannam@95: Up: What FFTW Really Computes cannam@95:

cannam@95:

cannam@95: cannam@95:

4.8.3 1d Real-even DFTs (DCTs)

cannam@95: cannam@95:

The Real-even symmetry DFTs in FFTW are exactly equivalent to the unnormalized cannam@95: forward (and backward) DFTs as defined above, where the input array cannam@95: X of length N is purely real and is also even symmetry. In cannam@95: this case, the output array is likewise real and even symmetry. cannam@95: cannam@95: cannam@95:

For the case of REDFT00, this even symmetry means that cannam@95: X_j = X_N-j,where we take X to be periodic so that cannam@95: X_N = X₀. Because of this redundancy, only the first n real numbers are cannam@95: actually stored, where N = 2(n-1). cannam@95: cannam@95:

The proper definition of even symmetry for REDFT10, cannam@95: REDFT01, and REDFT11 transforms is somewhat more intricate cannam@95: because of the shifts by 1/2 of the input and/or output, although cannam@95: the corresponding boundary conditions are given in Real even/odd DFTs (cosine/sine transforms). Because of the even symmetry, however, cannam@95: the sine terms in the DFT all cancel and the remaining cosine terms are cannam@95: written explicitly below. This formulation often leads people to call cannam@95: such a transform a discrete cosine transform (DCT), although it is cannam@95: really just a special case of the DFT. cannam@95: cannam@95: cannam@95:

In each of the definitions below, we transform a real array X of cannam@95: length n to a real array Y of length n: cannam@95: cannam@95:

REDFT00 (DCT-I)

cannam@95: cannam@95:

An REDFT00 transform (type-I DCT) in FFTW is defined by: cannam@95:

.Note that this transform is not defined for n=1. For n=2, cannam@95: the summation term above is dropped as you might expect. cannam@95: cannam@95:

REDFT10 (DCT-II)

cannam@95: cannam@95:

An REDFT10 transform (type-II DCT, sometimes called “the” DCT) in FFTW is defined by: cannam@95:

. cannam@95: cannam@95:

REDFT01 (DCT-III)

cannam@95: cannam@95:

An REDFT01 transform (type-III DCT) in FFTW is defined by: cannam@95:

.In the case of n=1, this reduces to cannam@95: Y₀ = X₀. Up to a scale factor (see below), this is the inverse of REDFT10 (“the” DCT), and so the REDFT01 (DCT-III) is sometimes called the “IDCT”. cannam@95: cannam@95: cannam@95:

REDFT11 (DCT-IV)

cannam@95: cannam@95:

An REDFT11 transform (type-IV DCT) in FFTW is defined by: cannam@95:

. cannam@95: cannam@95:

Inverses and Normalization

cannam@95: cannam@95:

These definitions correspond directly to the unnormalized DFTs used cannam@95: elsewhere in FFTW (hence the factors of 2 in front of the cannam@95: summations). The unnormalized inverse of REDFT00 is cannam@95: REDFT00, of REDFT10 is REDFT01 and vice versa, and cannam@95: of REDFT11 is REDFT11. Each unnormalized inverse results cannam@95: in the original array multiplied by N, where N is the cannam@95: logical DFT size. For REDFT00, N=2(n-1) (note that cannam@95: n=1 is not defined); otherwise, N=2n. cannam@95: cannam@95: cannam@95:

In defining the discrete cosine transform, some authors also include cannam@95: additional factors of cannam@95: √2(or its inverse) multiplying selected inputs and/or outputs. This is a cannam@95: mostly cosmetic change that makes the transform orthogonal, but cannam@95: sacrifices the direct equivalence to a symmetric DFT. cannam@95: cannam@95: cannam@95: cannam@95: