Fourier

Fourier implements functionality for performing Discrete Fourier Transforms (DFTs). The core functionality of the package is a highly optimized set of routines for performing forward and reverse DFTs of 2D data using the matrix triple product method as described in Soummer et al (2007). The routines work for any NxM matrix for N, M > 1 include square and nonsquare dimensions of even or odd size. Performance is at worst on par with the FFTW invocation:

using FFTW
N=2; M=3;
a = rand(N,M);
b = a |> ifftshift |> fft |> fftshift;

for any N*M <= 1024*1024.

Installation

Fourier is a registered Julia package, it may be installed the usual way:

julia> Pkg.add("Fourier")

Functions

Fourier.mdft — Function

mdft(ary, samples[, shift, Q])

Compute and return the 2D DFT via a matrix triple product. Equivalent to fftshift(fft(ifftshift(ary))) if shift==0, samples=size(ary), Q=1.

samples is the number of samples in the output domain. If it is an integer, it is broadcast to both dimensions. Otherwise it may be a tuple to provide each.

shift is used to move the origin. If the output grid with shift=0 spanned -10:1:9 Hz, shift=10 will move the output grid to 0:1:19Hz. The unit is samples, not hertz. The first argument is along x, or the columns of the matrix, not dim 0.

Q controls the oversampling factor. It is equivalent to zero padding the input array by the same factor. E.g. mdft of a 256x256 array with Q=2 is the same as zero padding it to 512x512 and FFTing that.

Utilities

Fourier.fftrange — Function

fftrange(n)

Computes a range that always matches FFT expectations. I.e., for even N ranges matches the example n=4 => -2:1:1 and for odd N matches the example 5 => -2:1:2.

This can be understood as "the output range shall always contain zero, if there may be only one value for n÷2, it will be the negative one."

The range is always centered; frequency or sampling bins align to it with fftshift. It can be fftshifted to be placed in post-FFT coordinates.

source