See also: Linear filters, IIR filter design

Fast Fourier transform

This library provides fft() and ifft() functions for fast Fourier transform.

fft	Fast Fourier transform.
ifft	Inverse fast Fourier transform.

import signals.fft-1;

Fourier transform of a signal

import signals.fft-1;

 s = fft(
	[1,2,3,4,5,6,7,8] // the signal to be transformed
	, 100 // optional: length of output vector
)
Calculate FFT

Inverse Fourier transform of a signal

import signals.fft-1;

 ifft(
	s // the signal to be transformed
	, 100 // optional: length of output vector
)
Calculate IFFT

Both fft() and ifft() functions have an optional argument "number of points". If it is specified and it is bigger than the signal length, the signal will be extended with zeros. This can help provide better resolution. If the argument is less than the number of points in the signal, it will be ignored.

There is no normalization factor included in the FFT. The normalization is done in IFFT.

NOTE: The FFT is the fastest possible for signals of power-of-2 length.