.cannam@167: Next: 1d Discrete Hartley Transforms (DHTs), Previous: 1d Real-even DFTs (DCTs), Up: What FFTW Really Computes [Contents][Index]
cannam@167:The Real-odd 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 odd symmetry. In cannam@167: this case, the output is odd symmetry and purely imaginary. cannam@167: cannam@167: cannam@167:
cannam@167: cannam@167: cannam@167:For the case of RODFT00, this odd 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
cannam@167: starting at j=1 are actually stored (the j=0 element is
cannam@167: zero), where N = 2(n+1).
cannam@167:
The proper definition of odd symmetry for RODFT10,
cannam@167: RODFT01, and RODFT11 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 odd symmetry, however,
cannam@167: the cosine terms in the DFT all cancel and the remaining sine terms are
cannam@167: written explicitly below. This formulation often leads people to call
cannam@167: such a transform a discrete sine transform (DST), although it is
cannam@167: really just a special case of the DFT.
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:An RODFT00 transform (type-I DST) in FFTW is defined by:
cannam@167:
.An RODFT10 transform (type-II DST) in FFTW is defined by:
cannam@167:
.An RODFT01 transform (type-III DST) in FFTW is defined by:
cannam@167:
.An RODFT11 transform (type-IV DST) in FFTW is defined by:
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 RODFT00 is
cannam@167: RODFT00, of RODFT10 is RODFT01 and vice versa, and
cannam@167: of RODFT11 is RODFT11. Each unnormalized inverse results
cannam@167: in the original array multiplied by N, where N is the
cannam@167: logical DFT size. For RODFT00, N=2(n+1);
cannam@167: otherwise, N=2n.
cannam@167:
cannam@167:
In defining the discrete sine 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 an antisymmetric DFT. cannam@167:
cannam@167:cannam@167: Next: 1d Discrete Hartley Transforms (DHTs), Previous: 1d Real-even DFTs (DCTs), Up: What FFTW Really Computes [Contents][Index]
cannam@167: