Complex FFT Functions

Detailed 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.

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

arm_cfft_f32(arm_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 arm_cfft_f32 function follows:

const static arm_cfft_instance_f32 *S; ... switch (length) { case 16: S = & arm_cfft_sR_f32_len16; break; case 32: S = & arm_cfft_sR_f32_len32; break; case 64: S = & arm_cfft_sR_f32_len64; break; case 128: S = & arm_cfft_sR_f32_len128; break; case 256: S = & arm_cfft_sR_f32_len256; break; case 512: S = & arm_cfft_sR_f32_len512; break; case 1024: S = & arm_cfft_sR_f32_len1024; break; case 2048: S = & arm_cfft_sR_f32_len2048; break; case 4096: S = & arm_cfft_sR_f32_len4096; break; }

Q15 and Q31

The library provides radix-2 and radix-4 FFT algorithms for fixed-point data. The radix-2 algorithm supports lengths of [16, 32, 64, ..., 4096]. The radix-4 algorithm supports lengths of [16, 64, 256, ..., 4096]. When possible, you should use the radix-4 algorithm since it is faster than the radix-2 of the same length.

The forward FFTs include scaling in order to prevent results from overflowing. Intermediate results are scaled down during each butterfly stage. In the radix-2 algorithm, a scale of 0.5 is applied during each butterfly. In the radix-4 algorithm, a scale of 0.25 is applied. The scaling applies to both the forward and the inverse FFTs. Thus the forward FFT contains an additional scale factor of 1/fftLen as compared to the standard textbook definition of the FFT. The inverse FFT also scales down during each butterfly stage and this corresponds to the standard textbook definition.

A separate instance structure must be defined for each transform used but twiddle factor and bit reversal tables can be reused.

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 should be manually initialized as follows:

   
arm_cfft_radix2_instance_q31 S = {fftLen, ifftFlag, bitReverseFlag, pTwiddle, pBitRevTable, twidCoefModifier, bitRevFactor};   
arm_cfft_radix2_instance_q15 S = {fftLen, ifftFlag, bitReverseFlag, pTwiddle, pBitRevTable, twidCoefModifier, bitRevFactor};   
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};    
arm_cfft_instance_f32 S = {fftLen, pTwiddle, pBitRevTable, bitRevLength};
 

where fftLen length of CFFT/CIFFT; ifftFlag Flag for selection of forward or inverse transform. When ifftFlag is set the inverse transform is calculated. 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 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;

The Q15 and Q31 FFT functions use a large bit reversal and twiddle factor table. The tables are defined for the maximum length transform and a subset of the coefficients are used in shorter transforms.

Function Documentation