The Bordeaux-FFT library provides a reasonably efficient implementation of the Fast Fourier Transform and its inverse for complex-valued inputs, in portable Common Lisp.
It was originally written by Robert Strandh, Sylvain Marchand, Martin Raspaud. Andy Hefner added the signal windowing code, other minor improvements, and wrote the manual. Paul Khuong contributed performance enhancements.
All symbols mentioned in this manual will be exported from the BORDEAUX-FFT package.
Bordeaux-FFT can be loaded either by compiling and loading the fft.lisp file directly, or using ASDF. An ASDF system definition file is included. Under typical ASDF configurations, a symbolic link to the file bordeaux-fft.asd should be created in a path included in your ASDF:*CENTRAL-REGISTRY*. For SBCL users, ~/.sbcl/systems/ is a common choice. You will then be able to load the BORDEAUX-FFT system using ASDF as follows: (asdf:oos 'asdf:load-op :bordeaux-fft)
The most current version of Bordeaux-FFT may be obtained from http://vintage-digital.com/hefner/software/bordeaux-fft/bordeaux-fft-current.tar.gz.
The FFT and IFFT functions each come in three variations: a simple version which handles converting its input to the required format, and two more efficient versions which assume the input is a complex-sample-array. Versions are available which allocate a new output vector, or write into an existing output vector. In all cases, the input vector must have a size which is a power of two.
(deftype complex-sample () `(complex double-float))
(deftype complex-sample-array () `(simple-array complex-sample (*)))
Returns the Fourier transform of source (a complex-sample-array of a power of two in size), allocating a new array for the result (a complex-sample-array of the same size as the source).
Desctructive version of fft. Computes the Fourier transform of source, writing the result into dest. The source and dest vectors must both be of type complex-sample-array and have a size which is a power of two. Additionally, dest cannot be smaller than source.
Simple version of fft. It can take any kind of array as input. If len is supplied, only the first len elements of source are used.
Returns the inverse Fourier transform of source (a complex-sample-array of a power of two in size), allocating a new array for the result (a complex-sample-array of the same size as the source).
Desctructive version of ifft. Computes the inverse Fourier transform of source, writing the result into dest. The source and dest vectors must both be of type complex-sample-array and have a size which is a power of two. Additionally, dest cannot be smaller than source.
Simple version of ifft. It can take any kind of array as input. If len is supplied, only the first len elements of source are used.
Returns the FFT of a window of length samples from signal-vector (a complex-sample-array), centered on the offset center. Areas where the window would extend outside the bounds of the array are taken to be zeros. Before being computing the FFT, the specified region of the signal is multiplied by the result of a window function, window-fn, which takes as arguments an array index (from 0 below length) and length, the window size, and must return a double float. Windows for a given window-fn and length are memoized, so the cost of computing the window is paid only once for any particular combination. Several built-in choices for window-fn are presented below. A new result vector is allocated; the original signal-vector is not modified.
The following expressions produce equivalent results: (windowed-fft vector 256 512 'rectangular) and (fft vector).
Compute and return a vector of length samples by evaluating function at 0, 1, 2, ..., length. The resulting vector for a given function and length is memoized so that it is computed only once, and subsequent requests will return the same vector again.
Several window functions are provided. These can be used as arguments to windowed-fft or window-vector.
Returns the i-th point of the n-point rectangular window.
Returns the i-th point of the n-point triangular window.
Returns the i-th point of the n-point Hann window.
Returns the i-th point of the n-point Blackman window (with α=0.16).
Returns the i-th point of the n-point Bartlett window.
Returns the i-th point of the n-point Blackman-Harris window.
Returns a window-function for evaluating a Gaussian window, given the parameter sigma. The result is memoized.
Returns a window-function to evaluate< i-th point from the product of the n-point Gaussian (with parameter sigma) and Bartlett (raised to triangle-exponent) windows.
Coefficients and temporary buffers are saved and reused between calls to fft and ifft. These are contained in fft-instance and ifft-instance objects, which are stored in the variables *fft-instance* and *ifft-instance*, respectively. In a multiprocessing environment, simultaneous use of the same fft-instance or ifft-instance object will produce corrupted results. For this reason, a program performing simultaneous FFT/IFFT operations in multiple threads should ensure that each thread establishes its own dynamic binding of the *fft-instance* and *ifft-instance* variables, containing unique instances. It is sufficient to bind these to nil initially.
Report bugs to Andy Hefner <ahefner at gmail dot com>