Complex FFT Functions

Content
	Radix-8 Complex FFT Functions
	Complex FFT Tables

Functions
void	csky_cfft_f32 (const csky_cfft_instance_f32 *S, float32_t *p1, uint8_t ifftFlag, uint8_t bitReverseFlag)
	Processing function for the floating-point complex FFT. More...
void	csky_cfft_q15 (const csky_cfft_instance_q15 *S, q15_t *p1, uint8_t ifftFlag, uint8_t bitReverseFlag)
	Processing function for the Q15 complex FFT. More...
void	csky_cfft_q31 (const csky_cfft_instance_q31 *S, q31_t *p1, uint8_t ifftFlag, uint8_t bitReverseFlag)
	Processing function for the fixed-point complex FFT in Q31 format. More...

Description

The Fast Fourier Transform (FFT) is an efficient algorithm for computing the Discrete Fourier Transform (DFT). The FFT can be orders of magnitude faster than the DFT, especially for long lengths. The algorithms described in this section operate on complex data. A separate set of functions is devoted to handling of real sequences.

There are separate algorithms for handling floating-point, Q15, and Q31 data types. The algorithms available for each data type are described next.

The FFT functions operate in-place. That is, the array holding the input data will also be used to hold the corresponding result. The input data is complex and contains 2*fftLen interleaved values as shown below.

 {real[0], imag[0], real[1], imag[1],..} 

The FFT result will be contained in the same array and the frequency domain values will have the same interleaving.

Floating-point

The floating-point complex FFT uses a mixed-radix algorithm. Multiple radix-8 stages are performed along with a single radix-2 or radix-4 stage, as needed. The algorithm supports lengths of [16, 32, 64, ..., 4096] and each length uses a different twiddle factor table.

The function uses the standard FFT definition and output values may grow by a factor of fftLen when computing the forward transform. The inverse transform includes a scale of 1/fftLen as part of the calculation and this matches the textbook definition of the inverse FFT.

Pre-initialized data structures containing twiddle factors and bit reversal tables are provided and defined in csky_const_structs.h. Include this header in your function and then pass one of the constant structures as an argument to csky_cfft_f32. For example:

csky_cfft_f32(csky_cfft_sR_f32_len64, pSrc, 1, 1)

computes a 64-point inverse complex FFT including bit reversal. The data structures are treated as constant data and not modified during the calculation. The same data structure can be reused for multiple transforms including mixing forward and inverse transforms.

Earlier releases of the library provided separate radix-2 and radix-4 algorithms that operated on floating-point data. These functions are still provided but are deprecated. The older functions are slower and less general than the new functions.

An example of initialization of the constants for the csky_cfft_f32 function follows:

const static csky_cfft_instance_f32 *S;
...
  switch (length) {
    case 16:
      S = &csky_cfft_sR_f32_len16;
      break;
    case 32:
      S = &csky_cfft_sR_f32_len32;
      break;
    case 64:
      S = &csky_cfft_sR_f32_len64;
      break;
    case 128:
      S = &csky_cfft_sR_f32_len128;
      break;
    case 256:
      S = &csky_cfft_sR_f32_len256;
      break;
    case 512:
      S = &csky_cfft_sR_f32_len512;
      break;
    case 1024:
      S = &csky_cfft_sR_f32_len1024;
      break;
    case 2048:
      S = &csky_cfft_sR_f32_len2048;
      break;
    case 4096:
      S = &csky_cfft_sR_f32_len4096;
      break;
  }

Q15 and Q31

The floating-point complex FFT uses a mixed-radix algorithm. Multiple radix-4 stages are performed along with a single radix-2 stage, as needed. The algorithm supports lengths of [16, 32, 64, ..., 4096] and each length uses a different twiddle factor table.

The function uses the standard FFT definition and output values may grow by a factor of fftLen when computing the forward transform. The inverse transform includes a scale of 1/fftLen as part of the calculation and this matches the textbook definition of the inverse FFT.

Pre-initialized data structures containing twiddle factors and bit reversal tables are provided and defined in csky_const_structs.h. Include this header in your function and then pass one of the constant structures as an argument to csky_cfft_q31. For example:

csky_cfft_q31(csky_cfft_sR_q31_len64, pSrc, 1, 1)

computes a 64-point inverse complex FFT including bit reversal. The data structures are treated as constant data and not modified during the calculation. The same data structure can be reused for multiple transforms including mixing forward and inverse transforms.

Earlier releases of the library provided separate radix-2 and radix-4 algorithms that operated on floating-point data. These functions are still provided but are deprecated. The older functions are slower and less general than the new functions.

An example of initialization of the constants for the csky_cfft_q31 function follows:

const static csky_cfft_instance_q31 *S;
...
  switch (length) {
    case 16:
      S = &csky_cfft_sR_q31_len16;
      break;
    case 32:
      S = &csky_cfft_sR_q31_len32;
      break;
    case 64:
      S = &csky_cfft_sR_q31_len64;
      break;
    case 128:
      S = &csky_cfft_sR_q31_len128;
      break;
    case 256:
      S = &csky_cfft_sR_q31_len256;
      break;
    case 512:
      S = &csky_cfft_sR_q31_len512;
      break;
    case 1024:
      S = &csky_cfft_sR_q31_len1024;
      break;
    case 2048:
      S = &csky_cfft_sR_q31_len2048;
      break;
    case 4096:
      S = &csky_cfft_sR_q31_len4096;
      break;
  }

Function Documentation

void csky_cfft_f32	(	const csky_cfft_instance_f32 *	S,
		float32_t *	p1,
		uint8_t	ifftFlag,
		uint8_t	bitReverseFlag
	)

Parameters

[in]	*S	points to an instance of the floating-point CFFT structure.
[in,out]	*p1	points to the complex data buffer of size 2*fftLen. Processing occurs in-place.
[in]	ifftFlag	flag that selects forward (ifftFlag=0) or inverse (ifftFlag=1) transform.
[in]	bitReverseFlag	flag that enables (bitReverseFlag=1) or disables (bitReverseFlag=0) bit reversal of output.

Returns

none.

void csky_cfft_q15	(	const csky_cfft_instance_q15 *	S,
		q15_t *	p1,
		uint8_t	ifftFlag,
		uint8_t	bitReverseFlag
	)

Parameters

[in]	*S	points to an instance of the Q15 CFFT structure.
[in,out]	*p1	points to the complex data buffer of size 2*fftLen. Processing occurs in-place.
[in]	ifftFlag	flag that selects forward (ifftFlag=0) or inverse (ifftFlag=1) transform.
[in]	bitReverseFlag	flag that enables (bitReverseFlag=1) or disables (bitReverseFlag=0) bit reversal of output.

Returns

none.

void csky_cfft_q31	(	const csky_cfft_instance_q31 *	S,
		q31_t *	p1,
		uint8_t	ifftFlag,
		uint8_t	bitReverseFlag
	)

Parameters

[in]	*S	points to an instance of the fixed-point CFFT structure.
[in,out]	*p1	points to the complex data buffer of size 2*fftLen. Processing occurs in-place.
[in]	ifftFlag	flag that selects forward (ifftFlag=0) or inverse (ifftFlag=1) transform.
[in]	bitReverseFlag	flag that enables (bitReverseFlag=1) or disables (bitReverseFlag=0) bit reversal of output.

Returns

none.