Module Fourier

module Fourier: sig .. end

Fourier Transform

val pi : float

Constant $\pi$ .

val dft_aux : float -> Complex.t list -> Complex.t list

An auxiliary routine for dft and idft.

val dft : Complex.t list -> Complex.t list

A naive implementation of Discrete Fourier Transform (DFT). DFT is defined as

$y_k = \sum^{N-1}_{t = 0} x_t \exp\left( -i \frac{2 \pi tk}{N} \right) \quad (k = 0, \dots, N-1)$

where $x_1, x_2 \dots, x_{N-1}$ are time-domain data points, $y_1, y_2 \dots, y_{N-1}$ are frequency-domain data points.

val idft : Complex.t list -> Complex.t list

A naive implementation of Inverse Discrete Fourier Transform (IDFT), the inverse transformation of DFT:

$x_t = \sum^{N-1}_{k = 0} y_k \exp\left( i \frac{2 \pi tk}{N} \right) \quad (t = 0, \dots, N-1)$

val fft_aux : float -> Complex.t list -> Complex.t list

An auxiliary routine for fft and ifft.

val fft : Complex.t list -> Complex.t list

An implementation of Cooley-Tukey Fast Fourier Transform (FFT) algorithm. dft takes $O(n^2)$

time, but fft takes $O(n \log n)$ time!

val ifft : Complex.t list -> Complex.t list

An implementation of Inverse Fast Fourier Transform (IFFT). idft takes $O(n^2)$

time, but ifft takes $O(n \log n)$ time!