Discrete and Fast Fourier Transform algorithms

Functions
int	dspl_dft (double *xR, double *xI, int n, double *yR, double *yI)
	Discrete Fourier Transform. More...
int	dspl_fft (double *xR, double *xI, int n, void *pdspl, double *yR, double *yI)
	Fast Fourier Transform. More...
int	dspl_goertzel (double *xR, double *xI, int n, int *ind, int k, double *yR, double *yI)
	Goertzel algorithm of discrete Fourier transform. More...
int	dspl_ifft (double *xR, double *xI, int n, void *pdspl, double *yR, double *yI)
	Inverse Fast Fourier Transform. This function calculates IFFT by using Cooley - Tukey decimation in time algorithm. More...
int	dspl_pwelch (double *xR, double *xI, int n, int win_type, double win_param, int npsd, int noverlap, void *pdspl, double fs, double *ppsd, double *pfrq)

Detailed Description

This group includes algorithms for Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT).

Function Documentation

dspl_dft()

int dspl_dft	(	double *	xR,
		double *	xI,
		int	n,
		double *	yR,
		double *	yI
	)

Discrete Fourier Transform.

This function calculates $n$-point DFT of real or complex input signal

\[ Y(k) = \sum_{m = 0}^{n-1} x(m) \cdot \exp \left( -j \cdot \frac{2\pi}{n} \cdot m \cdot k \right), \]

Parameters

[in]	xR	Input signal vector real part pointer. Vector size is [n x 1].
[in]	xI	Input signal vector image part pointer. Vector size is [n x 1]. This pointer can be NULL if DFT is calculated for a real signal
[in]	n	DFT size (input and output vectors size).
[out]	yR	DFT vector real part pointer. Vector size is [n x 1]. Memory must be allocated.
[out]	yI	DFT vector image part pointer. Vector size is [n x 1]. Memory must be allocated.

Returns

DSPL_OK if DFT is calculated successfully.
DSPL_ERROR_PTR if xR == NULL or yR == NULL or yI == NULL.
DSPL_ERROR_SIZE if n<1.

Note

This function uses naive DFT calculation method. You can use FFT algorithms if you need to calculate DFT more faster.

Author

Sergey Bakhurin. www.dsplib.org

Examples:

dft_freq_fig1.c, and dft_freq_fig4.c.

dspl_fft()

int dspl_fft	(	double *	xR,
		double *	xI,
		int	n,
		void *	pdspl,
		double *	yR,
		double *	yI
	)

Fast Fourier Transform.

This function calculates DFT by using Cooley - Tukey decimation in time algorithm.

Parameters

[in]	xR	Input signal vector real part pointer. Vector size is [n x 1].
[in]	xI	Input signal vector image part pointer. Vector size is [n x 1]. This pointer can be NULL if FFT is calculated for a real signal
[in]	n	FFT size (input and output vectors size).
[in]	pdspl	DSPL object pointer. DSPL object keeps some internal DSPL data. This object can be created by dspl_obj_create function before using and should be destroyed by dspl_obj_free before exit.
[out]	yR	FFT vector real part pointer. Vector size is [n x 1]. Memory must be allocated.
[out]	yI	FFT vector image part pointer. Vector size is [n x 1]. Memory must be allocated.

Returns

DSPL_OK if FFT is calculated successfully <BR> DSPL_ERROR_PTRifxR == NULLoryR == NULLoryI == NULL<BR> DSPL_ERROR_SIZEifn<1.<BR> DSPL_ERROR_FFT_SIZEifn` is not radix-2

Author

Sergey Bakhurin dsplib.org

dspl_goertzel()

int dspl_goertzel	(	double *	xR,
		double *	xI,
		int	n,
		int *	ind,
		int	k,
		double *	yR,
		double *	yI
	)

Goertzel algorithm of discrete Fourier transform.

Goertzel algorithm calculates k spectral samples of n-points DFT corresponds to indexes ind.

Parameters

[in]	xR	Input signal real part vector pointer. Vector size is [n x 1].
[in]	xI	Input signal image part vector pointer. Vector size is [n x 1]. This pointer can be NULL if input signal is real.
[in]	n	Input signal vector size.
[in]	ind	Spectral samples indexes vector pointer Vector size is [k x 1].
[in]	k	Spectral samples indexes vector size.
[out]	yR	DFT spectral samples real part vector pointer corresponds to indexes ind. Vector size is [k x 1]. Memory must be allocated.
[out]	yI	DFT spectral samples image part vector pointer corresponds to indexes ind. Vector size is [k x 1]. Memory must be allocated.

Returns

DSPL_OK Function has be finished successfully .
DSPL_ERROR_PTR Pointer is wrong. Pointers xR, ind, yR and yI cannot be as NULL.
DSPL_ERROR_SIZE Vector size is wrong. Parameters n ans k must be more than zero.

Author

Sergey Bakhurin. www.dsplib.org

Examples:

goertzel_dtmf.c.

dspl_ifft()

int dspl_ifft	(	double *	xR,
		double *	xI,
		int	n,
		void *	pdspl,
		double *	yR,
		double *	yI
	)

Inverse Fast Fourier Transform. This function calculates IFFT by using Cooley - Tukey decimation in time algorithm.

Parameters

[in]	xR	Input spectrum vector real part pointer. Vector size is [n x 1].
[in]	xI	Input spectrum vector image part pointer. Vector size is [n x 1]. This pointer can be NULL if IFFT is calculated for a real spectrum.
[in]	n	FFT size (input and output vectors size).
[in]	pdspl	DSPL object pointer. DSPL object keeps some internal DSPL data. This object can be created by dspl_obj_create function before using and should be destroyed by dspl_obj_free before exit.
[out]	yR	IFFT vector real part pointer. Vector size is [n x 1]. Memory must be allocated.
[out]	yI	IFFT vector image part pointer. Vector size is [n x 1]. This pointer can be NULL. Function will return only IFFT real part in this case

Returns

DSPL_OK if FFT is calculated successfully DSPL_ERROR_PTRifxR == NULLoryR == NULL. DSPL_ERROR_SIZEifn<1. DSPL_ERROR_FFT_SIZEifn` is not radix-2.

Author

Sergey Bakhurin dsplib.org

dspl_pwelch()

int dspl_pwelch	(	double *	xR,
		double *	xI,
		int	n,
		int	win_type,
		double	win_param,
		int	npsd,
		int	noverlap,
		void *	pdspl,
		double	fs,
		double *	ppsd,
		double *	pfrq
	)

Estimate two-side power spectral density (PSD) by the Welch periodogram/FFT method.

The PSD is the mean of the periodograms, scaled so that area under the spectrum is the same as the mean square of the data.

Parameters

[in]	xR	Input signal real part pointer. Vector size is [n x 1].
[in]	xI	Input signal vector image part pointer. Vector size is [n x 1]. This pointer can be NULL if PSD is calculated for a real signal.
[in]	n	Input signal size (input and output vectors size).
[in]	win_type	Bit string for set window function type. This parameter is bit masks combination DSPL_WIN_MASK | DSPL_WIN_SYM_MASK. Bit mask DSPL_WIN_MASK sets window function type: Value DSPL_WIN_MASK Description DSPL_WIN_BARTLETT Non-parametric Bartlett window DSPL_WIN_BARTLETT_HANN Non-parametric Bartlett-Hann window DSPL_WIN_BLACKMAN Non-parametric Blackman window DSPL_WIN_BLACKMAN_HARRIS Non-parametric Blackman-Harris window DSPL_WIN_BLACKMAN_NUTTALL Non-parametric Blackman-Nuttall window DSPL_WIN_COS Non-parametric cosine window DSPL_WIN_FLAT_TOP Non-parametric flat top window DSPL_WIN_GAUSSIAN Parametric Gaussian window DSPL_WIN_HAMMING Non-parametric Hamming window DSPL_WIN_HANN Non-parametric Hann window DSPL_WIN_LANCZOS Non-parametric Lanczos window DSPL_WIN_NUTTALL Non-parametric Nuttall window DSPL_WIN_RECT Non-parametric rectangular window Bit mask DSPL_WIN_SYM_MASK sets symmetric or periodic window: Value DSPL_WIN_SYM_MASK Description DSPL_WIN_SYMMETRIC Symmetric window (by default) DSPL_WIN_PERIODIC Periodic window
[in]	win_param	Window function parameter (for parametric windows only). This parameter is ignored for non-parametric windows.
[in]	npsd	PSD size.
[in]	noverlap	PSD overlap size. This number must be from 1 to npsd.
[in]	pdspl	DSPL object pointer. DSPL object keeps some internal DSPL data. This object can be created by dspl_obj_create function before using and should be destroyed by dspl_obj_free before exit.
[in]	fs	Input signal sample rate (Hz).
[out]	ppsd	PSD vector pointer. Vector size is [npsd x 1]. Memory should be allocated.
[out]	pfrq	PSD frequency vector pointer. Vector size is [npsd x 1]. Memory should be allocated.

Author

Sergey Bakhurin. www.dsplib.org

Examples:

hilbert_fft.c.