Functions
void	arm_cfft_radix4_f32 (const arm_cfft_radix4_instance_f32 S, float32_t pSrc)
	Processing function for the floating-point CFFT/CIFFT.
arm_status	arm_cfft_radix4_init_f32 (arm_cfft_radix4_instance_f32 *S, uint16_t fftLen, uint8_t ifftFlag, uint8_t bitReverseFlag)
	Initialization function for the floating-point CFFT/CIFFT.
arm_status	arm_cfft_radix4_init_q15 (arm_cfft_radix4_instance_q15 *S, uint16_t fftLen, uint8_t ifftFlag, uint8_t bitReverseFlag)
	Initialization function for the Q15 CFFT/CIFFT.
arm_status	arm_cfft_radix4_init_q31 (arm_cfft_radix4_instance_q31 *S, uint16_t fftLen, uint8_t ifftFlag, uint8_t bitReverseFlag)
	Initialization function for the Q31 CFFT/CIFFT.
void	arm_cfft_radix4_q15 (const arm_cfft_radix4_instance_q15 S, q15_t pSrc)
	Processing function for the Q15 CFFT/CIFFT.
void	arm_cfft_radix4_q31 (const arm_cfft_radix4_instance_q31 S, q31_t pSrc)
	Processing function for the Q31 CFFT/CIFFT.
Variables
const uint16_t	armBitRevTable [256]
static const float32_t	twiddleCoef [2048]
static const q15_t	twiddleCoefQ15 [2048]
static const q31_t	twiddleCoefQ31 [2048]

Detailed Description

: Complex Fast Fourier Transform(CFFT) and Complex Inverse Fast Fourier Transform(CIFFT) is an efficient algorithm to compute Discrete Fourier Transform(DFT) and Inverse Discrete Fourier Transform(IDFT). Computational complexity of CFFT reduces drastically when compared to DFT.

: This set of functions implements CFFT/CIFFT for Q15, Q31, and floating-point data types. The functions operates on in-place buffer which uses same buffer for input and output. Complex input is stored in input buffer in an interleaved fashion.

: The functions operate on blocks of input and output data and each call to the function processes 2*fftLen samples through the transform. pSrc points to In-place arrays containing 2*fftLen values.

The pSrc points to the array of in-place buffer of size 2*fftLen and inputs and outputs are stored in an interleaved fashion as shown below.

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

Lengths supported by the transform:

: Internally, the function utilize a radix-4 decimation in frequency(DIF) algorithm and the size of the FFT supported are of the lengths [16, 64, 256, 1024].

Algorithm:

Complex Fast Fourier Transform:

Input real and imaginary data:

  
 x(n) = xa + j * ya  
 x(n+N/4 ) = xb + j * yb  
 x(n+N/2 ) = xc + j * yc  
 x(n+3N 4) = xd + j * yd

where N is length of FFT

Output real and imaginary data:

  
 X(4r) = xa'+ j * ya'  
 X(4r+1) = xb'+ j * yb'  
 X(4r+2) = xc'+ j * yc'  
 X(4r+3) = xd'+ j * yd'

Twiddle factors for radix-4 FFT:

  
 Wn = co1 + j * (- si1)  
 W2n = co2 + j * (- si2)  
 W3n = co3 + j * (- si3)

: Radix-4 Decimation-in Frequency Complex Fast Fourier Transform

: Output from Radix-4 CFFT Results in Digit reversal order. Interchange middle two branches of every butterfly results in Bit reversed output.

Butterfly CFFT equations:

  
 xa' = xa + xb + xc + xd  
 ya' = ya + yb + yc + yd  
 xc' = (xa+yb-xc-yd)* co1 + (ya-xb-yc+xd)* (si1)  
 yc' = (ya-xb-yc+xd)* co1 - (xa+yb-xc-yd)* (si1)  
 xb' = (xa-xb+xc-xd)* co2 + (ya-yb+yc-yd)* (si2)  
 yb' = (ya-yb+yc-yd)* co2 - (xa-xb+xc-xd)* (si2)  
 xd' = (xa-yb-xc+yd)* co3 + (ya+xb-yc-xd)* (si3)  
 yd' = (ya+xb-yc-xd)* co3 - (xa-yb-xc+yd)* (si3)

Complex Inverse Fast Fourier Transform:

: CIFFT uses same twiddle factor table as CFFT with modifications in the design equation as shown below.

Modified Butterfly CIFFT equations:

  
 xa' = xa + xb + xc + xd  
 ya' = ya + yb + yc + yd  
 xc' = (xa-yb-xc+yd)* co1 - (ya+xb-yc-xd)* (si1)  
 yc' = (ya+xb-yc-xd)* co1 + (xa-yb-xc+yd)* (si1)  
 xb' = (xa-xb+xc-xd)* co2 - (ya-yb+yc-yd)* (si2)  
 yb' = (ya-yb+yc-yd)* co2 + (xa-xb+xc-xd)* (si2)  
 xd' = (xa+yb-xc-yd)* co3 - (ya-xb-yc+xd)* (si3)  
 yd' = (ya-xb-yc+xd)* co3 + (xa+yb-xc-yd)* (si3)

Instance Structure: A separate instance structure must be defined for each Instance but the twiddle factors and bit reversal tables can be reused. There are separate instance structure declarations for each of the 3 supported data types.

Initialization Functions

There is also an associated initialization function for each data type. The initialization function performs the following operations:

Sets the values of the internal structure fields.
Initializes twiddle factor table and bit reversal table pointers

Use of the initialization function is optional. However, if the initialization function is used, then the instance structure cannot be placed into a const data section. To place an instance structure into a const data section, the instance structure must be manually initialized. Manually initialize the instance structure as follows:

  
arm_cfft_radix4_instance_f32 S = {fftLen, ifftFlag, bitReverseFlag, pTwiddle, pBitRevTable, twidCoefModifier, bitRevFactor, onebyfftLen};  
arm_cfft_radix4_instance_q31 S = {fftLen, ifftFlag, bitReverseFlag, pTwiddle, pBitRevTable, twidCoefModifier, bitRevFactor};  
arm_cfft_radix4_instance_q15 S = {fftLen, ifftFlag, bitReverseFlag, pTwiddle, pBitRevTable, twidCoefModifier, bitRevFactor};

: where fftLen length of CFFT/CIFFT; ifftFlag Flag for selection of CFFT or CIFFT(Set ifftFlag to calculate CIFFT otherwise calculates CFFT); bitReverseFlag Flag for selection of output order(Set bitReverseFlag to output in normal order otherwise output in bit reversed order); pTwiddlepoints to array of twiddle coefficients; pBitRevTable points to the array of bit reversal table. twidCoefModifier modifier for twiddle factor table which supports all FFT lengths with same table; pBitRevTable modifier for bit reversal table which supports all FFT lengths with same table. onebyfftLen value of 1/fftLen to calculate CIFFT;

Fixed-Point Behavior: Care must be taken when using the fixed-point versions of the CFFT/CIFFT function. Refer to the function specific documentation below for usage guidelines.

Function Documentation

void arm_cfft_radix4_f32	(	const arm_cfft_radix4_instance_f32 *	S,
		float32_t *	pSrc
	)

Processing function for the floating-point CFFT/CIFFT.

Parameters:

[in]	*S	points to an instance of the floating-point CFFT/CIFFT structure.
[in,out]	*pSrc	points to the complex data buffer of size `2*fftLen`. Processing occurs in-place.

Returns:: none.

Definition at line 174 of file arm_cfft_radix4_f32.c.

arm_status arm_cfft_radix4_init_f32	(	arm_cfft_radix4_instance_f32 *	S,
		uint16_t	fftLen,
		uint8_t	ifftFlag,
		uint8_t	bitReverseFlag
	)

Initialization function for the floating-point CFFT/CIFFT.

Parameters:

[in,out]	*S	points to an instance of the floating-point CFFT/CIFFT structure.
[in]	fftLen	length of the FFT.
[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:: The function returns ARM_MATH_SUCCESS if initialization is successful or ARM_MATH_ARGUMENT_ERROR if fftLen is not a supported value.

Description:

: The parameter ifftFlag controls whether a forward or inverse transform is computed. Set(=1) ifftFlag for calculation of CIFFT otherwise CFFT is calculated

: The parameter bitReverseFlag controls whether output is in normal order or bit reversed order. Set(=1) bitReverseFlag for output to be in normal order otherwise output is in bit reversed order.

: The parameter fftLen Specifies length of CFFT/CIFFT process. Supported FFT Lengths are 16, 64, 256, 1024.

: This Function also initializes Twiddle factor table pointer and Bit reversal table pointer.

Definition at line 1115 of file arm_cfft_radix4_init_f32.c.

arm_status arm_cfft_radix4_init_q15	(	arm_cfft_radix4_instance_q15 *	S,
		uint16_t	fftLen,
		uint8_t	ifftFlag,
		uint8_t	bitReverseFlag
	)

Initialization function for the Q15 CFFT/CIFFT.

Parameters:

[in,out]	*S	points to an instance of the Q15 CFFT/CIFFT structure.
[in]	fftLen	length of the FFT.
[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:: The function returns ARM_MATH_SUCCESS if initialization is successful or ARM_MATH_ARGUMENT_ERROR if fftLen is not a supported value.

Description:

: The parameter ifftFlag controls whether a forward or inverse transform is computed. Set(=1) ifftFlag for calculation of CIFFT otherwise CFFT is calculated

: The parameter bitReverseFlag controls whether output is in normal order or bit reversed order. Set(=1) bitReverseFlag for output to be in normal order otherwise output is in bit reversed order.

: The parameter fftLen Specifies length of CFFT/CIFFT process. Supported FFT Lengths are 16, 64, 256, 1024.

: This Function also initializes Twiddle factor table pointer and Bit reversal table pointer.

Definition at line 350 of file arm_cfft_radix4_init_q15.c.

arm_status arm_cfft_radix4_init_q31	(	arm_cfft_radix4_instance_q31 *	S,
		uint16_t	fftLen,
		uint8_t	ifftFlag,
		uint8_t	bitReverseFlag
	)

Initialization function for the Q31 CFFT/CIFFT.

Parameters:

[in,out]	*S	points to an instance of the Q31 CFFT/CIFFT structure.
[in]	fftLen	length of the FFT.
[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:: The function returns ARM_MATH_SUCCESS if initialization is successful or ARM_MATH_ARGUMENT_ERROR if fftLen is not a supported value.

Description:

: The parameter ifftFlag controls whether a forward or inverse transform is computed. Set(=1) ifftFlag for calculation of CIFFT otherwise CFFT is calculated

: The parameter bitReverseFlag controls whether output is in normal order or bit reversed order. Set(=1) bitReverseFlag for output to be in normal order otherwise output is in bit reversed order.

: The parameter fftLen Specifies length of CFFT/CIFFT process. Supported FFT Lengths are 16, 64, 256, 1024.

: This Function also initializes Twiddle factor table pointer and Bit reversal table pointer.

Definition at line 605 of file arm_cfft_radix4_init_q31.c.

void arm_cfft_radix4_q15	(	const arm_cfft_radix4_instance_q15 *	S,
		q15_t *	pSrc
	)

Processing function for the Q15 CFFT/CIFFT.

Parameters:

[in]	*S	points to an instance of the Q15 CFFT/CIFFT structure.
[in,out]	*pSrc	points to the complex data buffer. Processing occurs in-place.

Returns:: none.

Input and output formats:

: Internally input is downscaled by 2 for every stage to avoid saturations inside CFFT/CIFFT process. Hence the output format is different for different FFT sizes. The input and output formats for different FFT sizes and number of bits to upscale are mentioned in the tables below for CFFT and CIFFT:

: Input and Output Formats for Q15 CFFT

Input and Output Formats for Q15 CIFFT

Definition at line 63 of file arm_cfft_radix4_q15.c.

void arm_cfft_radix4_q31	(	const arm_cfft_radix4_instance_q31 *	S,
		q31_t *	pSrc
	)

Processing function for the Q31 CFFT/CIFFT.

Parameters:

[in]	*S	points to an instance of the Q31 CFFT/CIFFT structure.
[in,out]	*pSrc	points to the complex data buffer of size `2*fftLen`. Processing occurs in-place.

Returns:: none.

Input and output formats:

: Internally input is downscaled by 2 for every stage to avoid saturations inside CFFT/CIFFT process. Hence the output format is different for different FFT sizes. The input and output formats for different FFT sizes and number of bits to upscale are mentioned in the tables below for CFFT and CIFFT:

: Input and Output Formats for Q31 CFFT

Input and Output Formats for Q31 CIFFT

Definition at line 63 of file arm_cfft_radix4_q31.c.

Variable Documentation

const uint16_t armBitRevTable[256]

: Pseudo code for Generation of Bit reversal Table is

for(l=1;l <= N/4;l++)  
 {  
   for(i=0;i<logN2;i++)  
   {   
     a[i]=l&(1<<i);  
   }  
   for(j=0; j<logN2; j++)  
   {  
     if (a[j]!=0)  
     y[l]+=(1<<((logN2-1)-j));  
   }  
   y[l] = y[l] >> 1;  
  }

: where N = 1024 logN2 = 10

: N is the maximum FFT Size supported

Definition at line 66 of file arm_common_tables.c.

const float32_t twiddleCoef[2048] [static]

: Example code for Floating-point Twiddle factors Generation:

for(i = 0; i< N; i++)  
 {  
	twiddleCoef[2*i]= cos(i * 2*PI/(float)N);  
	twiddleCoef[2*i+1]= sin(i * 2*PI/(float)N);  
 }

: where N = 1024 and PI = 3.14159265358979

: Cos and Sin values are in interleaved fashion

Definition at line 67 of file arm_cfft_radix4_init_f32.c.

const q15_t twiddleCoefQ15[2048] [static]

: Example code for Q15 Twiddle factors Generation::

for(i = 0; i< N; i++)  
 {  
	twiddleCoefQ15[2*i]= cos(i * 2*PI/(float)N);  
	twiddleCoefQ15[2*i+1]= sin(i * 2*PI/(float)N);  
 }

: where N = 1024 and PI = 3.14159265358979

: Cos and Sin values are interleaved fashion

: Convert Floating point to Q15(Fixed point 1.15): round(twiddleCoefQ15(i) * pow(2, 15))

Definition at line 69 of file arm_cfft_radix4_init_q15.c.

const q31_t twiddleCoefQ31[2048] [static]

: Example code for Q31 Twiddle factors Generation::

for(i = 0; i< N; i++)  
 {  
    twiddleCoefQ31[2*i]= cos(i * 2*PI/(float)N);  
    twiddleCoefQ31[2*i+1]= sin(i * 2*PI/(float)N);  
 }

: where N = 1024 and PI = 3.14159265358979

: Cos and Sin values are interleaved fashion

: Convert Floating point to Q31(Fixed point 1.31): round(twiddleCoefQ31(i) * pow(2, 31))

Definition at line 68 of file arm_cfft_radix4_init_q31.c.

Type:	Library
Created:	10 Mar 2011
Imports:	907
Forks:	1
Commits:	3
Dependents:	5
Dependencies:	0
Followers:	35

Complex FFT Functions
[Transform Functions]

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation

Repository toolbox

Repository details

Important Information for this Arm website

Complex FFT Functions [Transform Functions]

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning

Complex FFT Functions
[Transform Functions]