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

Input

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:

realPart: number | numberArray
Numeric array of the real part of the uniformly-sampled function $f_k$ . Instead of an array, it is possible to specify a single number that is interpreted as the real part of all the $f_k$ .
imaginaryPart: number | numberArray (default value: 0)
Numeric array of the imaginary part of the uniformly-sampled function $f_k$ . Instead of an array, it is possible to specify a single number that is interpreted as the imaginary part of all the $f_k$ . If this option is omitted, the imaginary part of all values is taken as zero.
domainInterval: number | numberArray
Numeric array of the sampling interval $\Delta_i$ for each dimension $i$ . If there is only one dimension, it is also valid to specify a single number that represents the sampling interval $\Delta=\Delta_0$ .
dataCount: number | numberArray
Numeric array of the data count $N_i$ for the data in each dimension $i$ . If there is only one dimension, this value can be omitted, as $N=N_0$ is deduced from the length of the input data realPart and imaginaryPart.

Output

realPart: Float64Array
The real parts of the transformed quantity.
imaginaryPart: Float64Array
The imaginary parts of the transformed quantity.
absoluteValue: Float64Array
The absolute values of the transformed quantity. The values are calculated using hypot(imaginaryPart, realPart).
argument: Float64Array
The argument of the transformed quantity. The values are calculated using atan2(imaginaryPart, realPart).
domainValue: Float64Array | array
The domain values for each dimension.
domainInterval: number | Float64Array
The interval of each output domain.
domainBinStart: number | Float64Array
The lower bin limit of the output domain for each dimension.
domainBinEnd: number | Float64Array
The upper bin limit of the output domain for each dimension.
dataCount: number | Float64Array
The number of data points for each dimension.

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.