- Introduction
- Installation
- FFT/IFFT Functions
- Signal Window Functions
- Multiprocessing Notes
- Revision History
- Contact

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. This is the manual for version 2 of the library.

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.

Functions and types documented in this manual are 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 GitHub at https://github.com/ahefner/bordeaux-fft.

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.

Function
**fft**
*source* ⇒ *result*

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*).

Function
**fft!**
*source dest* ⇒ *dest*

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*.

Function
**sfft**
*source *`&optional` len ⇒ *result*

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.

Function
**ifft**
*source* ⇒ *result*

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*).

Function
**ifft!**
*source dest* ⇒ *dest*

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*.

Function
**sifft**
*source *`&optional` len ⇒ *result*

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.

Function
**windowed-fft**
*signal-vector center length *`&optional` (window-fn 'hann) ⇒ *result*

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)`.

Function
**window-vector**
*function length* ⇒ *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`.

Function
**gaussian**
*sigma* ⇒ *window-function*

Returns a *window-function* for evaluating a Gaussian window, given the parameter *sigma.* The result is memoized.

Function
**gaussian*bartlett^x**
*sigma triangle-exponent* ⇒ *window-function*

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.

- Version 1.0.1: Fixes infinite recursion when a non-power of two window size is passed to
`windowed-fft` - Version 1.0.0: Initial public release.