fft.h File Reference

#include <math.h>
#include "xcomplex.h"
#include "align8.h"

Include dependency graph for fft.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	AllocateFFTBuffer(_WID, _LDATA, _W, _X)
#define	FreeFFTBuffer(_LDATA)   free8(_LDATA);
#define	RFFTC(Input, Amp, Arg, Order, W, X, hbitinv)   RFFTC_ual(Input, Amp, Arg, Order, W, X, hbitinv);

Functions
void	CFFTCbii (int Order, cdouble *W, cdouble *X)
void	CFFTC (int Order, cdouble *W, cdouble *X, int *bitinv=0)
void	CFFTC (cdouble *Input, double *Amp, double *Arg, int Order, cdouble *W, cdouble *X, int *bitinv=0)
void	CFFTCW (double *Window, int Order, cdouble *W, cdouble *X, int *bitinv=0)
void	CFFTCW (cdouble *Input, double *Window, double *Amp, double *Arg, int Order, cdouble *W, cdouble *X, int *bitinv=0)
void	CIFFTC (int Order, cdouble *W, cdouble *X, int *bitinv=0)
void	CIFFTC (cdouble *Input, int Order, cdouble *W, cdouble *X, int *bitinv=0)
void	RFFTC_ual (double *Input, double *Amp, double *Arg, int Order, cdouble *W, cdouble *X, int *hbitinv=0)
void	RFFTC_ual_old (double *Input, double *Amp, double *Arg, int Order, cdouble *W, double *XR, double *XI, int *bitinv=0)
void	RFFTCW (double *Input, double *Window, double *Amp, double *Arg, int Order, cdouble *W, cdouble *X, int *hbitinv=0)
void	RFFTCW (__int16 *Input, double *Window, double *Amp, double *Arg, int Order, cdouble *W, cdouble *X, int *hbitinv=0)
void	CIFFTR (cdouble *Input, int Order, cdouble *W, double *X, int *hbitinv=0)
void	CMFTC (double *xR, double *xI, int Order, cdouble **X, cdouble *W)
void	RDCT1 (double *Input, double *Output, int Order, cdouble *qW, cdouble *qX, int *qbitinv=0)
void	RDCT4 (double *Input, double *Output, int Order, cdouble *hW, cdouble *hX, int *hbitinv=0)
void	RIDCT1 (double *Input, double *Output, int Order, cdouble *qW, cdouble *qX, int *qbitinv=0)
void	RIDCT4 (double *Input, double *Output, int Order, cdouble *hW, cdouble *hX, int *hbitinv=0)
void	RLCT (double **spec, double *data, int Count, int Order, int wid, double *g)
void	RILCT (double *data, double **spec, int Fr, int Order, int wid, double *g)
double	Atan2 (double, double)
int	Log2 (int)
int *	CreateBitInvTable (int Order)
void	SetTwiddleFactors (int N, cdouble *w)

Detailed Description

• fast Fourier and cosine transforms

Arguments of the function in this unit roughly follow the following rules: Wid : size of transform Order : log2(Wid) W : FFT buffer: twiddle factors, standard size Wid/2 X : FFT buffer: data buffer, standard size Wid bitinv: FFT buffer: table of bit-inversed integers, standard size Wid Window: window function, standard size Wid spec : complex spectrogram Amp : amplitude spectrogram Arg : phase spectrogram prefix h- : half-size prefix q- : quarter-size

Macro Definition Documentation

#define AllocateFFTBuffer	(		_WID,
			_LDATA,
			_W,
			_X
	)

Value:

double *_LDATA=(double*)malloc8(sizeof(double)*_WID*4); \
  cdouble *_X=(cdouble*)&_LDATA[_WID]; \
  cdouble *_W=(cdouble*)&_X[_WID]; \
  SetTwiddleFactors(_WID, _W);

macro AllocateFFTBuffer: allocates FFT buffers X and W of given length with an extra LDATA buffer the right size for hosting such arrays as the standard-size window function or output amplitude spectrum.

This macro allocates buffer with 64-bit alignment, which must be freed with free8() or FreeFFTBuffer macro.

Function Documentation

double Atan2	(	double	y,
		double	x
	)

function Atan2: (0, 0)-safe atan2

Returns 0 is x=y=0, atan2(x,y) otherwise.

void CFFTC	(	int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	bitinv
	)

function CFFTC: in-place complex FFT

In: Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors X[Wid]: complex waveform bitinv[Wid]: bit-inversion table Out: X[Wid]: complex spectrum

No return value.

void CFFTC	(	cdouble *	Input,
		double *	Amp,
		double *	Arg,
		int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	bitinv
	)

function CFFTC: complex FFT

In: Input[Wid]: complex waveform Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors bitinv[Wid]: bit-inversion table Out:X[Wid]: complex spectrum Amp[Wid]: amplitude spectrum Arg[Wid]: phase spectrum

No return value.

void CFFTCbii	(	int	Order,
		cdouble *	W,
		cdouble *	X
	)

function CFFTCbii: basic complex DIF-FFT module, applied after bit-inversed ordering of inputs

In: Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors X[Wid]: complex waveform Out: X[Wid]: complex spectrum

No return value.

void CFFTCW	(	double *	Window,
		int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	bitinv
	)

function CFFTCW: complex FFT with window

In: Window[Wid]: window function Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors X[Wid]: complex waveform bitinv[Wid]: bit-inversion table Out:X[Wid], complex spectrum

No return value.

void CFFTCW	(	cdouble *	Input,
		double *	Window,
		double *	Amp,
		double *	Arg,
		int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	bitinv
	)

function CFFTCW: complex FFT with window

In: Input[Wid]: complex waveform Window[Wid]: window function Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors X[Wid]: complex waveform bitinv[Wid]: bit-inversion table Out:X[Wid], complex spectrum Amp[Wid], amplitude spectrum Arg[Wid], phase spectrum

No return value.

void CIFFTC	(	int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	bitinv
	)

function CIFFTC: in-place complex IFFT

In: Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors X[Wid]: complex spectrum bitinv[Wid]: bit-inversion table Out: X[Wid]: complex waveform

No return value.

void CIFFTC	(	cdouble *	Input,
		int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	bitinv
	)

function CIFFTC: complex IFFT

In: Input[Wid]: complex spectrum Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors bitinv[Wid]: bit-inversion table Out:X[Wid]: complex waveform

No return value.

void CIFFTR	(	cdouble *	Input,
		int	Order,
		cdouble *	W,
		double *	X,
		int *	hbitinv
	)

function CIFFTR: complex-to-real IFFT

In: Input[Wid/2+1]: complex spectrum, imaginary parts of Input[0] and Input[Wid/2] are ignored Order: integer, equals log2(Wid) W[Wid/2]: twiddle factors hbitinv[Wid/2]: half bit-inversion table Out:X[Wid]: real waveform

No return value.

int* CreateBitInvTable

(

int

Order

)

function CreateBitInvTable: creates a table of bit-inversed integers

In: Order: interger, equals log2(size of table)

Returns a pointer to a newly allocated array containing the table. The returned pointer must be freed using free(), NOT delete[].

int Log2

(

int

x

)

function Log2: Log2

Returns x for Log2(2^x) if x is integer.

void RDCT1	(	double *	Input,
		double *	Output,
		int	Order,
		cdouble *	qW,
		cdouble *	qX,
		int *	qbitinv
	)

function RDCT1: fast DCT1 implemented using FFT. DCT-I has the time scale 0.5-sample shifted from the DFT.

In: Input[Wid]: real waveform Order: integer, equals log2(Wid) qW[Wid/8]: quarter table of twiddle factors qX[Wid/4]: quarter FFT data buffer qbitinv[Wid/4]: quarter bit-inversion table Out:Output[Wid]: DCT-I of Input.

No return value. Content of qW is destroyed on return. On calling the fft buffers should be allocated to size 0.25*Wid.

void RDCT4	(	double *	Input,
		double *	Output,
		int	Order,
		cdouble *	hW,
		cdouble *	hX,
		int *	hbitinv
	)

function RDCT4: fast DCT4 implemented using FFT. DCT-IV has both the time and frequency scales 0.5-sample or 0.5-bin shifted from DFT.

In: Input[Wid]: real waveform Order: integer, equals log2(Wid) hW[Wid/4]: half table of twiddle factors hX[Wid/2]: hal FFT data buffer hbitinv[Wid/2]: half bit-inversion table Out:Output[Wid]: DCT-IV of Input.

No return value. Content of hW not affected. On calling the fft buffers should be allocated to size 0.5*Wid.

void RFFTC_ual	(	double *	Input,
		double *	Amp,
		double *	Arg,
		int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	hbitinv
	)

function RFFTC_ual: unaligned real-to-complex FFT

In: Input[Wid]: real waveform Order; integer, equals log2(Wid) W[Wid/2]: twiddle factors hbitinv[Wid/2]: half bit-inversion table Out:X[Wid}: complex spectrum Amp[Wid]: amplitude spectrum Arg[Wid]: phase spetrum

No return value.

void RFFTCW	(	double *	Input,
		double *	Window,
		double *	Amp,
		double *	Arg,
		int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	hbitinv
	)

function RFFTCW: real-to-complex FFT with window

In: Input[Wid]: real waveform Window[Wid]: window function Order; integer, equals log2(Wid) W[Wid/2]: twiddle factors hbitinv[Wid/2]: half bit-inversion table Out:X[Wid}: complex spectrum Amp[Wid]: amplitude spectrum Arg[Wid]: phase spetrum

No return value.

void RFFTCW	(	__int16 *	Input,
		double *	Window,
		double *	Amp,
		double *	Arg,
		int	Order,
		cdouble *	W,
		cdouble *	X,
		int *	hbitinv
	)

function RFFTCW: real-to-complex FFT with window

In: Input[Wid]: real waveform as _int16 array Window[Wid]: window function Order; integer, equals log2(Wid) W[Wid/2]: twiddle factors hbitinv[Wid/2]: half bit-inversion table Out:X[Wid}: complex spectrum Amp[Wid]: amplitude spectrum Arg[Wid]: phase spetrum

No return value.

void RIDCT1	(	double *	Input,
		double *	Output,
		int	Order,
		cdouble *	qW,
		cdouble *	qX,
		int *	qbitinv
	)

function RIDCT1: fast IDCT1 implemented using FFT.

In: Input[Wid]: DCT-I of some real waveform. Order: integer, equals log2(Wid) qW[Wid/8]: quarter table of twiddle factors qX[Wid/4]: quarter FFT data buffer qbitinv[Wid/4]: quarter bit-inversion table Out:Output[Wid]: IDCT-I of Input.

No return value. Content of qW is destroyed on return. On calling the fft buffers should be allocated to size 0.25*Wid.

void RIDCT4	(	double *	Input,
		double *	Output,
		int	Order,
		cdouble *	hW,
		cdouble *	hX,
		int *	hbitinv
	)

function RIDCT4: fast IDCT4 implemented using FFT.

In: Input[Wid]: DCT-IV of some real waveform Order: integer, equals log2(Wid) hW[Wid/4]: half table of twiddle factors hX[Wid/2]: hal FFT data buffer hbitinv[Wid/2]: half bit-inversion table Out:Output[Wid]: IDCT-IV of Input.

No return value. Content of hW not affected. On calling the fft buffers should be allocated to size 0.5*Wid.

void RILCT	(	double *	data,
		double **	spec,
		int	Fr,
		int	Order,
		int	wid,
		double *	g
	)

function RILCT: inverse local cosine transform of equal frame widths Wid=2^Order

In: spec[Fr][Wid]: the local cosine transform Order: integer, equals log2(Wid), Wid being the cosine atom size g[wid]: lap window, designed so that g[k] increases from 0 to 1 and g[k]^2+g[wid-1-k]^2=1. example: wid=4, g[k]=sin(pi*(k+0.5)/8). Out:data[Count]: real waveform

No return value.

void RLCT	(	double **	spec,
		double *	data,
		int	Count,
		int	Order,
		int	wid,
		double *	g
	)

function RLCT: real local cosine transform of equal frame widths Wid=2^Order

In: data[Count]: real waveform Order: integer, equals log2(Wid), Wid being the cosine atom size g[wid]: lap window, designed so that g[k] increases from 0 to 1 and g[k]^2+g[wid-1-k]^2=1 example: wid=4, g[k]=sin(pi*(k+0.5)/8). Out:spec[Fr][Wid]: the local cosine transform

No return value.

void SetTwiddleFactors	(	int	N,
		cdouble *	w
	)

function SetTwiddleFactors: fill w[N/2] with twiddle factors used in N-point complex FFT.

In: N Out: array w[N/2] containing twiddle factors

No return value.