Fast Fourier Transform

The fft package is a wrapper of the C language version of PocketFFT library designed to support FFT of real to complex and complex to real (arrays).

The result of a real-to-complex transform, because of mathematical symmetry of the result, is stored in the original input array rather than 2x the space.

The output is the two real values bracketing the complex pairs of conjugate negative frequencies: r0 r1 i1 r2 i2 r3 i3 ... rx

where r0 + i0 is the first complex result, r1 - i1 is the second, and so on until rx + i0 (where x is n/2) is the last. (Note the minus signs.)

The positive frequencies are the same as the negative frequencies in reverse order. See the reference for FFTW for further examples of embeddings.

fn backward_fft[T](r Fftplan, mut v T) int

backward_fft computes the backwards Fourier transform defined by the plan r.

fn create_plan[T](x T) ?Fftplan

create_plan returns a plan to compute a Fourier transform of the given array. A plan is reusable for any array of exactly this size and type. The array may be []f32, []f64, or []complx_f32 or []complex_f64.

fn forward_fft[T](p Fftplan, mut v T) int

forward_fft computes a Fourier transform defined by the plan p. The input is []f32 or []f64. The output result (r) is returned in-place, and is complex and real numbers mixed as follows: r[0] (im[0] is assumed and is 0) r[1] im[1] ... r[n/2] im[n/2] conjugate negative frequences r[n] is the magnitude at zero frequency (im[n] is assumed and is 0) Positive frequencies are excluded as these are symmetric to the negative frequencies for real inputs. (Consult any signal processing text for details.)

To generate a complete result, copy the results to a larger complex array using r[0] and i0 r[1] and i-r[2] r[3] and i*-r[4] ... r[n] and i0 at the zero frequency r[n-2] and ir[n-1] the complex conjugate negative frequencies r[n-4] and ir[n-3] in reverse order ... r[1] and ir[2]

Note: these codes allocate and free memory of the same size as the input.