cannam@167: cannam@167: cannam@167: cannam@167: cannam@167:
cannam@167:cannam@167: Next: The Discrete Hartley Transform, Previous: The Halfcomplex-format DFT, Up: More DFTs of Real Data [Contents][Index]
cannam@167:The Fourier transform of a real-even function f(-x) = f(x) is cannam@167: real-even, and i times the Fourier transform of a real-odd cannam@167: function f(-x) = -f(x) is real-odd. Similar results hold for a cannam@167: discrete Fourier transform, and thus for these symmetries the need for cannam@167: complex inputs/outputs is entirely eliminated. Moreover, one gains a cannam@167: factor of two in speed/space from the fact that the data are real, and cannam@167: an additional factor of two from the even/odd symmetry: only the cannam@167: non-redundant (first) half of the array need be stored. The result is cannam@167: the real-even DFT (REDFT) and the real-odd DFT (RODFT), also cannam@167: known as the discrete cosine and sine transforms (DCT and cannam@167: DST), respectively. cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167: cannam@167:
cannam@167: cannam@167:(In this section, we describe the 1d transforms; multi-dimensional cannam@167: transforms are just a separable product of these transforms operating cannam@167: along each dimension.) cannam@167:
cannam@167:Because of the discrete sampling, one has an additional choice: is the cannam@167: data even/odd around a sampling point, or around the point halfway cannam@167: between two samples? The latter corresponds to shifting the cannam@167: samples by half an interval, and gives rise to several transform cannam@167: variants denoted by REDFTab and RODFTab: a and cannam@167: b are 0 or 1, and indicate whether the input cannam@167: (a) and/or output (b) are shifted by half a sample cannam@167: (1 means it is shifted). These are also known as types I-IV of cannam@167: the DCT and DST, and all four types are supported by FFTW’s r2r cannam@167: interface.3 cannam@167:
cannam@167:The r2r kinds for the various REDFT and RODFT types supported by FFTW,
cannam@167: along with the boundary conditions at both ends of the input
cannam@167: array (n
real numbers in[j=0..n-1]
), are:
cannam@167:
FFTW_REDFT00
(DCT-I): even around j=0 and even around j=n-1.
cannam@167:
cannam@167:
cannam@167: FFTW_REDFT10
(DCT-II, “the” DCT): even around j=-0.5 and even around j=n-0.5.
cannam@167:
cannam@167:
cannam@167: FFTW_REDFT01
(DCT-III, “the” IDCT): even around j=0 and odd around j=n.
cannam@167:
cannam@167:
cannam@167:
cannam@167: FFTW_REDFT11
(DCT-IV): even around j=-0.5 and odd around j=n-0.5.
cannam@167:
cannam@167:
cannam@167: FFTW_RODFT00
(DST-I): odd around j=-1 and odd around j=n.
cannam@167:
cannam@167:
cannam@167: FFTW_RODFT10
(DST-II): odd around j=-0.5 and odd around j=n-0.5.
cannam@167:
cannam@167:
cannam@167: FFTW_RODFT01
(DST-III): odd around j=-1 and even around j=n-1.
cannam@167:
cannam@167:
cannam@167: FFTW_RODFT11
(DST-IV): odd around j=-0.5 and even around j=n-0.5.
cannam@167:
cannam@167:
cannam@167: Note that these symmetries apply to the “logical” array being cannam@167: transformed; there are no constraints on your physical input cannam@167: data. So, for example, if you specify a size-5 REDFT00 (DCT-I) of the cannam@167: data abcde, it corresponds to the DFT of the logical even array cannam@167: abcdedcb of size 8. A size-4 REDFT10 (DCT-II) of the data cannam@167: abcd corresponds to the size-8 logical DFT of the even array cannam@167: abcddcba, shifted by half a sample. cannam@167:
cannam@167:All of these transforms are invertible. The inverse of R*DFT00 is cannam@167: R*DFT00; of R*DFT10 is R*DFT01 and vice versa (these are often called cannam@167: simply “the” DCT and IDCT, respectively); and of R*DFT11 is R*DFT11. cannam@167: However, the transforms computed by FFTW are unnormalized, exactly cannam@167: like the corresponding real and complex DFTs, so computing a transform cannam@167: followed by its inverse yields the original array scaled by N, cannam@167: where N is the logical DFT size. For REDFT00, cannam@167: N=2(n-1); for RODFT00, N=2(n+1); otherwise, N=2n. cannam@167: cannam@167: cannam@167:
cannam@167: cannam@167:Note that the boundary conditions of the transform output array are cannam@167: given by the input boundary conditions of the inverse transform. cannam@167: Thus, the above transforms are all inequivalent in terms of cannam@167: input/output boundary conditions, even neglecting the 0.5 shift cannam@167: difference. cannam@167:
cannam@167:FFTW is most efficient when N is a product of small factors; note
cannam@167: that this differs from the factorization of the physical size
cannam@167: n
for REDFT00 and RODFT00! There is another oddity: n=1
cannam@167: REDFT00 transforms correspond to N=0, and so are not
cannam@167: defined (the planner will return NULL
). Otherwise, any positive
cannam@167: n
is supported.
cannam@167:
For the precise mathematical definitions of these transforms as used by cannam@167: FFTW, see What FFTW Really Computes. (For people accustomed to cannam@167: the DCT/DST, FFTW’s definitions have a coefficient of 2 in front cannam@167: of the cos/sin functions so that they correspond precisely to an cannam@167: even/odd DFT of size N. Some authors also include additional cannam@167: multiplicative factors of cannam@167: √2 cannam@167: for selected inputs and outputs; this makes cannam@167: the transform orthogonal, but sacrifices the direct equivalence to a cannam@167: symmetric DFT.) cannam@167:
cannam@167: cannam@167:Since the required flavor of even/odd DFT depends upon your problem, cannam@167: you are the best judge of this choice, but we can make a few comments cannam@167: on relative efficiency to help you in your selection. In particular, cannam@167: R*DFT01 and R*DFT10 tend to be slightly faster than R*DFT11 cannam@167: (especially for odd sizes), while the R*DFT00 transforms are sometimes cannam@167: significantly slower (especially for even sizes).4 cannam@167:
cannam@167:Thus, if only the boundary conditions on the transform inputs are cannam@167: specified, we generally recommend R*DFT10 over R*DFT00 and R*DFT01 over cannam@167: R*DFT11 (unless the half-sample shift or the self-inverse property is cannam@167: significant for your problem). cannam@167:
cannam@167:If performance is important to you and you are using only small sizes cannam@167: (say n<200), e.g. for multi-dimensional transforms, then you cannam@167: might consider generating hard-coded transforms of those sizes and types cannam@167: that you are interested in (see Generating your own code). cannam@167:
cannam@167:We are interested in hearing what types of symmetric transforms you find cannam@167: most useful. cannam@167:
cannam@167:There are also type V-VIII transforms, which
cannam@167: correspond to a logical DFT of odd size N, independent of
cannam@167: whether the physical size n
is odd, but we do not support these
cannam@167: variants.
R*DFT00 is cannam@167: sometimes slower in FFTW because we discovered that the standard cannam@167: algorithm for computing this by a pre/post-processed real DFT—the cannam@167: algorithm used in FFTPACK, Numerical Recipes, and other sources for cannam@167: decades now—has serious numerical problems: it already loses several cannam@167: decimal places of accuracy for 16k sizes. There seem to be only two cannam@167: alternatives in the literature that do not suffer similarly: a cannam@167: recursive decomposition into smaller DCTs, which would require a large cannam@167: set of codelets for efficiency and generality, or sacrificing a factor of cannam@167: 2 cannam@167: in speed to use a real DFT of twice the size. We currently cannam@167: employ the latter technique for general n, as well as a limited cannam@167: form of the former method: a split-radix decomposition when n cannam@167: is odd (N a multiple of 4). For N containing many cannam@167: factors of 2, the split-radix method seems to recover most of the cannam@167: speed of the standard algorithm without the accuracy tradeoff.
cannam@167:cannam@167: Next: The Discrete Hartley Transform, Previous: The Halfcomplex-format DFT, Up: More DFTs of Real Data [Contents][Index]
cannam@167: