FFT code and related material

• an amorphous FFT bucket
• FFT intro and remarks section

The FXT library

The amorphous FFT bucket

fix_fft: FFTs using fixed point arthmetic in C, includes test routine
fix_fft.tar.gz Written by Tom Roberts (1989), improved by Malcolm Slaney (1994), made portable (ix86 assembly removed) by Dimitrios P. Bouras (2006).

C source for an FFT-generator for integer FFTs for asm (80x86, 68k and 32k processors) and for C-code. fftgen.tgz first read the fftgen-doc.txt

C++ source (template) for complex FFT you can supply a class complex (e.g. based on fixed point floats) with the operators =,+,-,* and this code gives you a FFT for it. cplxfft.h

FFTReal: FFTs for real data
in C++ and Delphi: http://ldesoras.free.fr/prod.html by Laurent de Soras. Delphi port by Frederic Vanmol.

2dim Hartley transform code
in C++ mogenet-2dimfht.cc by Emmanuel Mogenet

1dim and 2dim DCT (cosine transform) code
dct.tgz, here is the doc: dct-doc.txt
This was from the server that disappeared from the net (ftp://ftp.crs4.it/mpeg/misc-progs/). Find a local copy here

C source for Prime Factor Algorithm (PFA) FFT, convolution, Hankel transform, Hilbert transform, Abel transform and much more, worth a closer look
cwplib.tgz first read the cwplib-doc.txt
A double precision version (with 'reverse engineered' magic constants) of the pfafft is here

FORTRAN code for General Prime Factor Algorithm (GPFA) FFT: 1,2,3-dim, by C.Temperton.
gpfa.tgz first read the gpfa-doc.txt. This code really needs a doc, test failed on my machine ...

C code n-dimensional FFTs: FFTEASY: by Gary Felder and Jiří Janáček: here. Local copies of the description (pdf) and the code ffteasyjj.c

FORTRAN (and f2c'd C) source for Glassman's General N FFT, length doesn't need to be a power of 2, degenerates into a DFT for prime lengths. glassman-fft.f (FORTRAN) and glassman-fft.c (C).
Author unknown (cf. glassman-note.txt), I received the code from Reginald Beardsley. Thanks to him!

C (and FORTRAN) source for n-dim FFT, length doesn't need to be a power of 2, split radix algorithm, test program included, corrected version of 8-jan-1996: fft-n.tgz first read the fft-n-doc.txt.

C source for n-dim FFT fftn.tgz first read the fftn-doc.txt
Peter Schuck found a typo: fftnfix.txt

C source for 2-dim FFT modernized and cleaned up by Stefan Gustavson: first read kube-gustavson-fft.txt, then grab kube-gustavson-fft.c and kube-gustavson-fft.h
The old version (as reference, superseded by the above): code: kube_fft.c and mini-doc: kube_fft-doc.txt

FORTRAN source for (complex and real) split radix FFT (by Henrik Sorensen): sorensen.tgz or sorensen.shar first read the sorensen-doc.txt

C source for split radix FFT (data length may be not a power of 2). fftsing.tgz first read the fftsing-doc.txt

C source for split radix real FFT (data length a power of 2) rsplitfft.c.

FORTRAN source for 2-dim FFT (data length may be not a power of 2).
ten_eyke.f first read the ten_eyke-doc.txt. No further doc available.

C source for real and complex FFTs not only for data length a power of two fft2.tgz first read the fft2-doc.txt

FFTW: benchmarks & C code
FFTW, the authors claim that it's one of the fastest.

C source by Jens Jørgen Nielsen for FFTs not only for data length a power of two, see Mix FFT.

C source for real and complex FFTs + sine/cosine transforms + special code for even/odd sequences based on Schwartztraubers FORTRAN fftpack (in netlib), see the index below. Taken from Pekka Janhunen's tela-package (original site is ftp.funet.fi). Warning: read tela-bugreport.txt.
The files after some cosmetic changes: telafft.tgz (no doc)
Almost original version plus my modification script: telaffto.tgz (no doc)
The untouched original files from the package: telafftx.tgz (no doc)
Index of the single prec fortran original: fftpack.my.index
Get the FORTRAN original (float: fftpack, double: bihar) from netlib. Netlib is: netlib@XXX where XXX is in europe: nac.no, in USA: ornl.gov (others exist). Send an email with subject 'send help'.
Now there is a www-netlib site, there see fftpack and vfftpack

More FORTRAN code (trig/hankel transforms-, convolution-, correlation- and wavelet code in the packages IMSL, NAG, SCILIB, TOMS and VECLIB) at http://gams.nist.gov/serve.cgi/Class/J/

FORTRAN source and C source for the FFTpack from Schwartztrauber: rfft-1.2-ss-9.01.tgz, first read the rfft-doc.txt.

FFT tutorials and remarks

• The corresponding chapters in the fxtbook
• Bibliography about FFT papers: fftnote.txt.
• A tutorial about the FFT: fftguru.com.
• A pointer to a book on realtime FFT (from the news net): realtime-fft-book.txt.
• Learn about C++ templates and numbertheoretic transforms: source code and a german (!) thesis: studie.tgz (about 100k). First read the studie-doc.txt.
• About errors in the code in Bracewell's book on the Hartley transform: brace_err.txt.

A remark on real valued FFTs: realfft.txt

miscellaneous

DSP-links

• www.dsprelated.com
• www.dspGuru.com
• Interactive Digital Filter Design

convolution code: read conv.txt then get the code: conv-v1.1.tar.gz