[deutsch]

# 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:

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

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}.

## 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.