Discrete Fourier transform

Kontrast includes the methods discreteFourierTransform and inverseDiscreteFourierTransform to compute the (inverse) discrete Fourier transform of a (one- or multidimensional) data set.

The discrete Fourier transform of uniformly-sampled data

The following is intended as a reference for sign and factor conventions, as they are not consistently used throughout different software packages, books and papers.

The input data for the discrete Fourier transform are N values of the function f sampled with the sampling interval \Delta:

f_k = f(k\Delta)\quad\text{with}\quad k=0, 1, 2, \dots, N-1

The first sample (k=0) corresponds to t=0.

The discrete Fourier transform is defined as:

F_n = \sum_{k=0}^{N-1} f_k \exp(-2\pi i k n/N)

The resulting F_n correspond to the domain values

\nu_n = \frac{n}{N\Delta}\quad\text{with}\quad n=-\frac{N}{2}, \dots, \frac{N}{2}-1

The inverse discrete Fourier transform is defined as:

f_k = \frac{1}{N}\sum_{n=0}^{N-1} F_n \exp(+2\pi i k n/N)

Note the normalization factor that is different from the forward transform.

The multi-dimensional discrete Fourier transform

The multidimensional discrete Fourier transform for L dimensions is defined as:

F_{n_0, \dots, n_{L-1}} = \sum_{k_{L-1}=0}^{N_{L-1}-1} \exp(-2\pi i k_{L-1} n_{L-1}/N_{L-1})\cdots \sum_{k_{0}=0}^{N_{0}-1} \exp(-2\pi i k_{0} n_{0}/N_{0})\cdot f_{k_0, \dots, k_{L-1}}

The inverse of the above transform has a plus sign instead of a minus sign in each of the exponents. The normalization factor of the inverse Fourier transform is N_0 \cdot N_1 \cdots N_{L-1}.

Interactive code examples


Kontrast exposes the two functions kontrast.discreteFourierTransform(options) and kontrast.inverseDiscreteFourierTransform(options). Both functions require a single option object as input and return an object as output.

Both functions accept the same keys in their options object:


If the input did not use an array for domainInterval (because a one-dimensional transform was computed) the output properties domainValue, dataCount, ... are numbers (and not arrays) as well.

Memory layout

One-dimensional transform

One-dimensional input data is simply stored in a contiguous way starting from the lowest index to the highest index.

The output of the Fourier transform is stored in the same way and has the same number of data points as the input. There is a separate output array for the real part, imaginary part, absolute value and argument value. The corresponding domain values are stored in domainValue. To visualize the result, one can directly plot, e. g., the absolute value versus the domainValue.

Two-dimensional transforms

Two-dimensional data (i.e., an image) is stored in a single array. The data corresponding to f_{k_0, k_1} is stored at array position k_0+k_1 N_0, where N_0 is the data count for the first dimension. The output data uses the same memory layout.

Note that when visualizing the data using tiles, one should use the bin edges from the output object of the discrete Fourier transform.

Fourier transforms of higher-dimensional data

The memory layout for the two-dimensional transform is generalized for higher dimensions by using the convention: the first dimension is the one where the index changes most rapidly when going through the array, the last dimension is the one with where the index changes least rapidly.