Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: FFTW 3.3.5: 1d Real-odd DFTs (DSTs) Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42:
Chris@42:

Chris@42: Next: , Previous: , Up: What FFTW Really Computes   [Contents][Index]

Chris@42:
Chris@42:
Chris@42: Chris@42:

4.8.4 1d Real-odd DFTs (DSTs)

Chris@42: Chris@42:

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

Chris@42: Chris@42: Chris@42:

For the case of RODFT00, this odd symmetry means that Chris@42: Xj = -XN-j,where we take X to be periodic so that Chris@42: XN = X0.Because of this redundancy, only the first n real numbers Chris@42: starting at j=1 are actually stored (the j=0 element is Chris@42: zero), where N = 2(n+1). Chris@42:

Chris@42:

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

Chris@42: Chris@42:

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

Chris@42: Chris@42:

RODFT00 (DST-I)

Chris@42: Chris@42:

An RODFT00 transform (type-I DST) in FFTW is defined by: Chris@42:

.

Chris@42: Chris@42:

RODFT10 (DST-II)

Chris@42: Chris@42:

An RODFT10 transform (type-II DST) in FFTW is defined by: Chris@42:

.

Chris@42: Chris@42:

RODFT01 (DST-III)

Chris@42: Chris@42:

An RODFT01 transform (type-III DST) in FFTW is defined by: Chris@42:

.
In the case of n=1, this reduces to Chris@42: Y0 = X0.

Chris@42: Chris@42:

RODFT11 (DST-IV)

Chris@42: Chris@42:

An RODFT11 transform (type-IV DST) in FFTW is defined by: Chris@42:

.

Chris@42: Chris@42:

Inverses and Normalization

Chris@42: Chris@42:

These definitions correspond directly to the unnormalized DFTs used Chris@42: elsewhere in FFTW (hence the factors of 2 in front of the Chris@42: summations). The unnormalized inverse of RODFT00 is Chris@42: RODFT00, of RODFT10 is RODFT01 and vice versa, and Chris@42: of RODFT11 is RODFT11. Each unnormalized inverse results Chris@42: in the original array multiplied by N, where N is the Chris@42: logical DFT size. For RODFT00, N=2(n+1); Chris@42: otherwise, N=2n. Chris@42: Chris@42:

Chris@42: Chris@42:

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

Chris@42:
Chris@42:
Chris@42:

Chris@42: Next: , Previous: , Up: What FFTW Really Computes   [Contents][Index]

Chris@42:
Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: