Complex FFT Functions
- Complex FFT Tables
riscvBitRevTable
twiddleCoefF64_16
twiddleCoefF64_32
twiddleCoefF64_64
twiddleCoefF64_128
twiddleCoefF64_256
twiddleCoefF64_512
twiddleCoefF64_1024
twiddleCoefF64_2048
twiddleCoefF64_4096
twiddleCoef_16
twiddleCoef_32
twiddleCoef_64
twiddleCoef_128
twiddleCoef_256
twiddleCoef_512
twiddleCoef_1024
twiddleCoef_2048
twiddleCoef_4096
twiddleCoef_16_q31
twiddleCoef_32_q31
twiddleCoef_64_q31
twiddleCoef_128_q31
twiddleCoef_256_q31
twiddleCoef_512_q31
twiddleCoef_1024_q31
twiddleCoef_2048_q31
twiddleCoef_4096_q31
twiddleCoef_16_q15
twiddleCoef_32_q15
twiddleCoef_64_q15
twiddleCoef_128_q15
twiddleCoef_256_q15
twiddleCoef_512_q15
twiddleCoef_1024_q15
twiddleCoef_2048_q15
twiddleCoef_4096_q15
twiddleCoefF16_16
twiddleCoefF16_32
twiddleCoefF16_64
twiddleCoefF16_128
twiddleCoefF16_256
twiddleCoefF16_512
twiddleCoefF16_1024
twiddleCoefF16_2048
twiddleCoefF16_4096
twiddleCoefF16_rfft_32
twiddleCoefF16_rfft_64
twiddleCoefF16_rfft_128
twiddleCoefF16_rfft_256
twiddleCoefF16_rfft_512
twiddleCoefF16_rfft_1024
twiddleCoefF16_rfft_2048
twiddleCoefF16_rfft_4096
- Complex FFT F16
- Complex FFT F32
- Complex FFT F64
- Complex FFT Q15
- Complex FFT Q31
- Deprecated Complex FFT functions
- group Complex FFT Functions
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. 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 of1/fftLen
as part of the calculation and this matches the textbook definition of the inverse FFT.For the MVE version, the new riscv_cfft_init_f32 initialization function is mandatory. Compilation flags are available to include only the required tables for the needed FFTs. Other FFT versions can continue to be initialized as explained below.
For not MVE versions, pre-initialized data structures containing twiddle factors and bit reversal tables are provided and defined in
riscv_const_structs.h
. Include this header in your function and then pass one of the constant structures as an argument to riscv_cfft_f32. For example:riscv_cfft_f32(riscv_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 riscv_cfft_f32 function follows:
const static riscv_cfft_instance_f32 *S; ... switch (length) { case 16: S = &riscv_cfft_sR_f32_len16; break; case 32: S = &riscv_cfft_sR_f32_len32; break; case 64: S = &riscv_cfft_sR_f32_len64; break; case 128: S = &riscv_cfft_sR_f32_len128; break; case 256: S = &riscv_cfft_sR_f32_len256; break; case 512: S = &riscv_cfft_sR_f32_len512; break; case 1024: S = &riscv_cfft_sR_f32_len1024; break; case 2048: S = &riscv_cfft_sR_f32_len2048; break; case 4096: S = &riscv_cfft_sR_f32_len4096; break; }
The new riscv_cfft_init_f32 can also be used.
- 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 of1/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
riscv_const_structs.h
. Include this header in your function and then pass one of the constant structures as an argument to riscv_cfft_q31. For example:riscv_cfft_q31(riscv_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 riscv_cfft_q31 function follows:
const static riscv_cfft_instance_q31 *S; ... switch (length) { case 16: S = &riscv_cfft_sR_q31_len16; break; case 32: S = &riscv_cfft_sR_q31_len32; break; case 64: S = &riscv_cfft_sR_q31_len64; break; case 128: S = &riscv_cfft_sR_q31_len128; break; case 256: S = &riscv_cfft_sR_q31_len256; break; case 512: S = &riscv_cfft_sR_q31_len512; break; case 1024: S = &riscv_cfft_sR_q31_len1024; break; case 2048: S = &riscv_cfft_sR_q31_len2048; break; case 4096: S = &riscv_cfft_sR_q31_len4096; break; }