SYLT-FFT

DEVSOUND (I)FFT(R) LIBRARY

^{And some other funky fixed-point maths like gray-coding and pow(2, f)}

Optimized (C-level) for Keil C Compiler and GCC on Cortex-M4.

Authors:

D. Taylor 2014 (gmail: senseitg)

License:

MHG (GPL compatible) - see LICENSE

Features:

FFT (Fast Fourier Transform) and IFFT (Inverse FFT)
Fixed-point 32-bit, Radix-2
Complex or real (with slight conversion overhead) data
No plan construction required before (I)FFT
No reliance on other libraries (including libm if using precomputed tables)

Options (config.h):

DIT (decimation-in-time) or DIF (decimation-in-frequency)
Rounding on divide (-speed, +accuracy)
Saturating math (-speed, +stability)
Table size vs. max. FFT length

Resource requirements:

Minimal memory requirements (in-place)
Minimal stack use (non-recursive)
Minimal twiddle tables (512 bytes for max N=512 FFT)

Notes:

Designed for optimal performance, not optimal accuracy

Caveats:

Care must be taken with input data to ensure no overflows
Requires C99 (-std=c99 for GCC)

Performance:

Comparing against: CMSIS DSP arm_cortexM4I_math.lib(1.4.2)
Platform: Freescale Kinetis K20 (Cortex-M4/ARMv7E-M)
KEIL = Keil C Compiler 5.01 -O3
GCC = GNU Tools for ARM Embedded Processors 4.8.4 -O3

Comparisons are of speed, +N% = faster than CMSIS, -N% = slower.
Please verify and do additional tests to add to the list.

  CMSIS-DSP             SYLT-FFT      N     KEIL     GCC
* arm_cfft_radix2_q31   fft_inverse   256   +25.6%   +15.1%

Thanks to:

Wikipedia - for existing and taking donations
KATJA - for intelligible merge/split spectra algorithm
XCORE - for intelligible (I)FFT algorithm
CMLAB - for intelligible FFT algorithm breakdown
BEVAN - for intelligible DIT vs. DIF, radix-2 vs. 4 overview

stg/SYLT-FFT

SYLT-FFT

DEVSOUND (I)FFT(R) LIBRARY