Real FFT Functions

Modules
	Real FFT F16 Functions
	Real FFT F64 Functions
	Real FFT Q15 Functions
	Real FFT Q31 Functions
	Real FFT Tables
	Real FFT F32 Functions
	Deprecated Real FFT Functions

Detailed Description

The NMSIS DSP library includes specialized algorithms for computing the FFT of real data sequences. The FFT is defined over complex data but in many applications the input is real. Real FFT algorithms take advantage of the symmetry properties of the FFT and have a speed advantage over complex algorithms of the same length.

The Fast RFFT algorithm relays on the mixed radix CFFT that save processor usage.

The real length N forward FFT of a sequence is computed using the steps shown below.

Real Fast Fourier Transform

The real sequence is initially treated as if it were complex to perform a CFFT. Later, a processing stage reshapes the data to obtain half of the frequency spectrum in complex format.

The input for the inverse RFFT should keep the same format as the output of the forward RFFT. A first processing stage pre-process the data to later perform an inverse CFFT.

Real Inverse Fast Fourier Transform

The algorithms for floating-point, Q15, and Q31 data are slightly different and we describe each algorithm in turn.

Floating-point

The main functions are riscv_rfft_fast_f32() and riscv_rfft_fast_init_f32(). The older functions riscv_rfft_f32() and riscv_rfft_init_f32() have been deprecated but are still documented. For f16, the functions are riscv_rfft_fast_f16() and riscv_rfft_fast_init_f16(). For f64, the functions are riscv_rfft_fast_f64() and riscv_rfft_fast_init_f64().

The FFT of a real N-point sequence has even symmetry in the frequency domain. The second half of the data equals the conjugate of the first half flipped in frequency. This conjugate part is not computed by the float RFFT. As consequence, the output of a N point real FFT should be a N//2 + 1 complex numbers so N + 2 floats.

It happens that the first complex of number of the RFFT output is actually all real. Its real part represents the DC offset. The value at Nyquist frequency is also real.

Those two complex numbers can be encoded with 2 floats rather than using two numbers with an imaginary part set to zero.

The implementation is using a trick so that the output buffer can be N float : the last real is packaged in the imaginary part of the first complex (since this imaginary part is not used and is zero).

The real FFT functions pack the frequency domain data in this fashion. The forward transform outputs the data in this form and the inverse transform expects input data in this form. The function always performs the needed bitreversal so that the input and output data is always in normal order. The functions support lengths of [32, 64, 128, ..., 4096] samples.

Q15 and Q31

The real algorithms are defined in a similar manner and utilize N/2 complex transforms behind the scenes.

But warning, contrary to the float version, the fixed point implementation RFFT is also computing the conjugate part (except for MVE version) so the output buffer must be bigger. Also the fixed point RFFTs are not using any trick to pack the DC and Nyquist frequency in the same complex number. The RIFFT is not using the conjugate part but it is still using the Nyquist frequency value. The details are given in the documentation for the functions.

The complex transforms used internally include scaling to prevent fixed-point overflows. The overall scaling equals 1/(fftLen/2). Due to the use of complex transform internally, the source buffer is modified by the rfft.

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.
• Initializes the internal complex FFT data structure.

Use of the initialization function is optional except for MVE versions where it is mandatory. If you don't use the initialization functions, then the structures should be initialized with code similar to the one below:

      riscv_rfft_instance_q31 S = {fftLenReal, fftLenBy2, ifftFlagR, bitReverseFlagR, twidCoefRModifier, pTwiddleAReal, pTwiddleBReal, pCfft};
      riscv_rfft_instance_q15 S = {fftLenReal, fftLenBy2, ifftFlagR, bitReverseFlagR, twidCoefRModifier, pTwiddleAReal, pTwiddleBReal, pCfft};
  

where fftLenReal is the length of the real transform; fftLenBy2 length of the internal complex transform (fftLenReal/2). ifftFlagR Selects forward (=0) or inverse (=1) transform. bitReverseFlagR Selects bit reversed output (=0) or normal order output (=1). twidCoefRModifier stride modifier for the twiddle factor table. The value is based on the FFT length; pTwiddleARealpoints to the A array of twiddle coefficients; pTwiddleBRealpoints to the B array of twiddle coefficients; pCfft points to the CFFT Instance structure. The CFFT structure must also be initialized.

Note that with MVE versions you can't initialize instance structures directly and must use the initialization function.