The Origin Problem

The definition of the discrete Fourier transform (DFT) creates an origin problem in the frequency and in the spatial domain. The fundamental period of the spectrum is located symmetrical around the origin. But most FFT libraries, like the FFTW [9] implementation, use a version of the DFT, see Equation 5.1 and Equation 5.2,

$$\hat{F}_N[\mu] = \sum_{n=0}^{N-1} \hat{f}_N[n] e^{-in \frac{2\pi \mu}{N}}$$ (5.1)

$$\hat{f}_N[n] = \frac{1}{N} \sum_{\mu=0}^{N-1} \hat{F}_N[\mu] e^{i\mu \frac{2\pi n}{N}}$$ (5.2)

where the data is managed asymmetrically.

Figure: Asymmetric indexing scheme for an even (a) and an odd (b) number of samples.

[] []

The origin of the spectrum, the constant component of the signal, is located at the index $0$ of the sample array. Then with increasing index the higher frequencies are captured. Up to half of the array where through the periodicity of the spectrum the negative edge of the first replica starts. The values for $k$ are used when applying the shifting theorem and the derivative theorem. This situation is illustrated by Figure 5.1(a) for an even and by Figure 5.1(b) for an odd number of samples. In both figures the dotted line indicates the fundamental period, of the periodic spectrum, which is symmetric around the origin. The additional samples on the right represent the replicas of the fundamental period in the frequency domain, see Figure 2.6. The blue scheme displays the symmetric indexing of the fundamental period. The second scheme starts with the constant value at the first index position, and is used by most implementations. The reason for distinguishing an even and an odd case is that in the even case the two replicas share one sample in the middle of the array. This overlapping index of the replicas creates problems when applying Fourier transform theorems, like the shifting theorem, the derivative theorem or the packing theorem in the frequency domain. These problems are addressed in detail in Section 5.2.