fft.c File Reference

a good (fast, accurate, simple-to-use) FFT algorithm More...

Functions
float *	spr_f32_fht1 (float *restrict x, int N)
float *	spr_f32_fht2 (float *restrict x, int N)
float *	spr_f32_fht4 (float *restrict x, int N)
float *	spr_f32_fft_c2c (float *restrict x, int N)
float *	spr_f32_ifft_c2c (float *restrict x, int N)
float *	spr_f32_fft_r2c (float *restrict x, int N)
float *	spr_f32_ifft_c2r (float *restrict x, int N)
double *	spr_f64_fht1 (double *restrict x, int N)
double *	spr_f64_fht2 (double *restrict x, int N)
double *	spr_f64_fht4 (double *restrict x, int N)
double *	spr_f64_fft_c2c (double *restrict x, int N)
double *	spr_f64_ifft_c2c (double *restrict x, int N)
double *	spr_f64_fft_r2c (double *restrict x, int N)
double *	spr_f64_ifft_c2r (double *restrict x, int N)

Variables
const char	spr_f32_fft_implementation []
const char	spr_f64_fft_implementation []

Detailed Description

a good (fast, accurate, simple-to-use) FFT algorithm

This module provides a good (fast, accurate, simple-to-use) FFT algorithm based on the fast Hartley transform (FHT). Some properties of this implementation:

• There is no need to pre-allocate cos/sin tables: all required trigoniometric values are computed on-the-fly using the tri-goniometrix rules for cos(a+b)=... and sin(a+b)=...
  For accuracy reasons, these computations are done in double precision.
• The use of the FHT reduces the number of on-the-fly computations for cos/sin evaluations a tiny little bit.
• The use of the FHT makes it easier to vectorize the FFT; for example a real to complex FFT is done with 4 parallel FHTs + 1 merge pass.
• The FHT is also a bit more economic when computing ||FFT(x)||^2.
• The FHT (should) allow a cleaner implementation of the cosine transform (TODO).

Author

Kris Demuynck

Date

23 Apr 2015

Revision History:

23/04/2015 - Kris Demuynck

implementation

07/07/2015 - Kris Demuynck

added to SPRAAK