d@0: d@0: d@0: 1d Real-even DFTs (DCTs) - FFTW 3.2.1 d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0:
d@0:

d@0: d@0: d@0: Next: , d@0: Previous: The 1d Real-data DFT, d@0: Up: What FFTW Really Computes d@0:

d@0:
d@0: d@0:

4.8.3 1d Real-even DFTs (DCTs)

d@0: d@0:

The Real-even symmetry DFTs in FFTW are exactly equivalent to the unnormalized d@0: forward (and backward) DFTs as defined above, where the input array d@0: X of length N is purely real and is also even symmetry. In d@0: this case, the output array is likewise real and even symmetry. d@0: d@0: For the case of REDFT00, this even symmetry means that d@0: Xj = XN-j,where we take X to be periodic so that d@0: XN = X0. Because of this redundancy, only the first n real numbers are d@0: actually stored, where N = 2(n-1). d@0: d@0:

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

REDFT00 (DCT-I)
d@0: d@0:

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

.
Note that this transform is not defined for n=1. For n=2, d@0: the summation term above is dropped as you might expect. d@0: d@0:
REDFT10 (DCT-II)
d@0: d@0:

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

.
d@0: d@0:
REDFT01 (DCT-III)
d@0: d@0:

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

.
In the case of n=1, this reduces to d@0: Y0 = X0. 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”. d@0: d@0: d@0:
REDFT11 (DCT-IV)
d@0: d@0:

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

.
d@0: d@0:
Inverses and Normalization
d@0: d@0:

These definitions correspond directly to the unnormalized DFTs used d@0: elsewhere in FFTW (hence the factors of 2 in front of the d@0: summations). The unnormalized inverse of REDFT00 is d@0: REDFT00, of REDFT10 is REDFT01 and vice versa, and d@0: of REDFT11 is REDFT11. Each unnormalized inverse results d@0: in the original array multiplied by N, where N is the d@0: logical DFT size. For REDFT00, N=2(n-1) (note that d@0: n=1 is not defined); otherwise, N=2n. d@0: d@0: In defining the discrete cosine transform, some authors also include d@0: additional factors of d@0: √2(or its inverse) multiplying selected inputs and/or outputs. This is a d@0: mostly cosmetic change that makes the transform orthogonal, but d@0: sacrifices the direct equivalence to a symmetric DFT. d@0: d@0: d@0: d@0: