Bordeaux-FFT User Manual

Table of Contents

  1. Introduction
  2. Installation
  3. FFT/IFFT Functions
  4. Signal Window Functions
  5. Multiprocessing Notes
  6. Contact

Introduction

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.

Installation

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.

FFT / IFFT Functions

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.

Type complex-sample
(deftype complex-sample () `(complex double-float))
Type complex-sample-array
(deftype complex-sample-array ()  `(simple-array complex-sample (*)))
Function fft sourceresult

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 destdest

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 lenresult

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 sourceresult

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 destdest

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 lenresult

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.

Signal Window Functions

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 lengthvector

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 rectangular i nresult

Returns the i-th point of the n-point rectangular window.

Function triangle i nresult

Returns the i-th point of the n-point triangular window.

Function hann i nresult

Returns the i-th point of the n-point Hann window.

Function blackman i nresult

Returns the i-th point of the n-point Blackman window (with α=0.16).

Function bartlett i nresult

Returns the i-th point of the n-point Bartlett window.

Function blackman-harris i nresult

Returns the i-th point of the n-point Blackman-Harris window.

Function gaussian sigmawindow-function

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

Function gaussian*bartlett^x sigma triangle-exponentwindow-function

Returns a window-function to evaluate the i-th point from the product of the n-point Gaussian (with parameter sigma) and Bartlett (raised to triangle-exponent) windows.

Multiprocessing Notes

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>