cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: FFTW 3.3.8: 1d Real-even DFTs (DCTs) cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167:
cannam@167:

cannam@167: Next: , Previous: , Up: What FFTW Really Computes   [Contents][Index]

cannam@167:
cannam@167:
cannam@167: cannam@167:

4.8.3 1d Real-even DFTs (DCTs)

cannam@167: cannam@167:

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

cannam@167: cannam@167: cannam@167:

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

cannam@167:

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

cannam@167: cannam@167:

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

cannam@167: cannam@167:

REDFT00 (DCT-I)

cannam@167: cannam@167:

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

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

cannam@167: cannam@167:

REDFT10 (DCT-II)

cannam@167: cannam@167:

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

.
cannam@167:

cannam@167: cannam@167:

REDFT01 (DCT-III)

cannam@167: cannam@167:

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

.
cannam@167: In the case of n=1, this reduces to cannam@167: Y0 = X0. cannam@167: 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@167: cannam@167:

cannam@167: cannam@167:

REDFT11 (DCT-IV)

cannam@167: cannam@167:

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

.
cannam@167:

cannam@167: cannam@167:

Inverses and Normalization

cannam@167: cannam@167:

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

cannam@167: cannam@167:

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

cannam@167:
cannam@167:
cannam@167:

cannam@167: Next: , Previous: , Up: What FFTW Really Computes   [Contents][Index]

cannam@167:
cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: