Complex-to-Complex FFT (Floating & Fixed Point)

Functions
ne10_fft_cfg_float32_t	ne10_fft_alloc_c2c_float32_c (ne10_int32_t nfft)
	Specific implementation of ne10_fft_alloc_c2c_float32 for ne10_fft_c2c_1d_float32_c. More...
ne10_fft_cfg_float32_t	ne10_fft_alloc_c2c_float32_neon (ne10_int32_t nfft)
	Specific implementation of ne10_fft_alloc_c2c_float32 for ne10_fft_c2c_1d_float32_neon. More...
void	ne10_fft_c2c_1d_float32_c (ne10_fft_cpx_float32_t *fout, ne10_fft_cpx_float32_t *fin, ne10_fft_cfg_float32_t cfg, ne10_int32_t inverse_fft)
	Specific implementation of ne10_fft_c2c_1d_float32 using plain C. More...
void	ne10_fft_c2c_1d_float32_neon (ne10_fft_cpx_float32_t *fout, ne10_fft_cpx_float32_t *fin, ne10_fft_cfg_float32_t cfg, ne10_int32_t inverse_fft)
	Specific implementation of ne10_fft_c2c_1d_float32 using NEON SIMD capabilities. More...
void	ne10_fft_destroy_c2c_float32 (ne10_fft_cfg_float32_t cfg)
	Destroys the configuration structure allocated by variants of ne10_fft_alloc_c2c_float32 (frees memory, etc.) More...
ne10_fft_cfg_int32_t	ne10_fft_alloc_c2c_int32_c (ne10_int32_t nfft)
	Specific implementation of ne10_fft_alloc_c2c_int32 for ne10_fft_c2c_1d_int32_c. More...
ne10_fft_cfg_int32_t	ne10_fft_alloc_c2c_int32_neon (ne10_int32_t nfft)
	Specific implementation of ne10_fft_alloc_c2c_int32 for ne10_fft_c2c_1d_int32_neon. More...
void	ne10_fft_c2c_1d_int32_c (ne10_fft_cpx_int32_t *fout, ne10_fft_cpx_int32_t *fin, ne10_fft_cfg_int32_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)
	Specific implementation of ne10_fft_c2c_1d_int32 using plain C. More...
void	ne10_fft_c2c_1d_int32_neon (ne10_fft_cpx_int32_t *fout, ne10_fft_cpx_int32_t *fin, ne10_fft_cfg_int32_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)
	Specific implementation of ne10_fft_c2c_1d_int32 using NEON SIMD capabilities. More...
void	ne10_fft_destroy_c2c_int32 (ne10_fft_cfg_int32_t cfg)
	Destroys the configuration structure allocated by variants of ne10_fft_alloc_c2c_int32 (frees memory, etc.) More...
ne10_fft_cfg_int16_t	ne10_fft_alloc_c2c_int16 (ne10_int32_t nfft)
	Creates a configuration structure for variants of ne10_fft_c2c_1d_int16. More...
void	ne10_fft_c2c_1d_int16_c (ne10_fft_cpx_int16_t *fout, ne10_fft_cpx_int16_t *fin, ne10_fft_cfg_int16_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)
	Specific implementation of ne10_fft_c2c_1d_int16 using plain C. More...
void	ne10_fft_c2c_1d_int16_neon (ne10_fft_cpx_int16_t *fout, ne10_fft_cpx_int16_t *fin, ne10_fft_cfg_int16_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)
	Specific implementation of ne10_fft_c2c_1d_int16 using NEON SIMD capabilities. More...
void	ne10_fft_destroy_c2c_int16 (ne10_fft_cfg_int16_t cfg)
	Destroys the configuration structure allocated by ne10_fft_alloc_c2c_int16 (frees memory, etc.) More...

Variables
ne10_fft_cfg_float32_t(*	ne10_fft_alloc_c2c_float32 )(ne10_int32_t nfft)
	Creates a configuration structure for ne10_fft_c2c_1d_float32. More...
void(*	ne10_fft_c2c_1d_float32 )(ne10_fft_cpx_float32_t *fout, ne10_fft_cpx_float32_t *fin, ne10_fft_cfg_float32_t cfg, ne10_int32_t inverse_fft)
	Mixed radix-2/3/4/5 complex FFT/IFFT of single precision floating point data. More...
ne10_fft_cfg_int32_t(*	ne10_fft_alloc_c2c_int32 )(ne10_int32_t nfft)
	Creates a configuration structure for ne10_fft_c2c_1d_int32. More...
void(*	ne10_fft_c2c_1d_int32 )(ne10_fft_cpx_int32_t *fout, ne10_fft_cpx_int32_t *fin, ne10_fft_cfg_int32_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)
	Mixed radix-2/4 complex FFT/IFFT of 32-bit fixed point Q31 data. More...
void(*	ne10_fft_c2c_1d_int16 )(ne10_fft_cpx_int16_t *fout, ne10_fft_cpx_int16_t *fin, ne10_fft_cfg_int16_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)
	Mixed radix-2/4 complex FFT/IFFT of 16-bit fixed point Q15 data. More...

Detailed Description

A Fast Fourier Transform (FFT) is an efficient method of computing the Discrete Fourier Transform (DFT), or its inverse. This set of functions implement complex-to-complex 1D FFTs, and the complementary inverse transforms (IFFTs).

Where scaling controls are not provided, these functions scale the data by in the inverse transformation only. This is a common convention, but may contrast with typical usage in some fields, where this scale factor may instead be applied in the forwards transformation only, or where a scale factor of may be applied in both transformations.

Separate versions are provided for floating point (FP32) and fixed point (Q31, Q15) data, each with a plain C implementation, a NEON implementation, and a function pointer to select between these at runtime (see ne10_init). More detailed descriptions of these functions can be found alongside the relevant function pointers:

• FP32: ne10_fft_c2c_1d_float32
• INT32 (Q31): ne10_fft_c2c_1d_int32
• INT16 (Q15): ne10_fft_c2c_1d_int16

Supported lengths

Internally, the functions primarily utilize a mixed radix 2/4 decimation-in-time algorithm, supporting input sizes of the form 2^N (for integers N > 0). Some functions also support non-power-of-two input sizes using additional radices, and this is noted in the relevant function descriptions where it applies.

Memory layout

These functions operate out-of-place, using different buffers for their input and output. An additional temporary buffer is also used internally to store intermediate results. The input and output buffers should be allocated by the user, and must be of a size greater than or equal to (fftSize * sizeof(ne10_fft_cpx_float32_t)) bytes, while the temporary buffer is reserved during allocation of a "configuration structure" (for instance, via ne10_fft_alloc_c2c_float32).

Input and output buffers interleave the real and imaginary parts of each complex element, storing these contiguously.

Format: { Re[0], Im[0], Re[1], Im[1], Re[2], Im[2], ..., Re[fftSize - 2], Im[fftSize - 2], Re[fftSize - 1], Im[fftSize - 1] }

Example usage

A single precision floating point FFT/IFFT example code snippet follows.

#include "NE10.h"

...

{
    ne10_int32_t fftSize = 1024;
    ne10_fft_cfg_float32_t cfg = ne10_fft_alloc_c2c_float32_neon(fftSize);          // Allocate a configuration structure for C2C FP32 NEON FFTs of size fftSize
    ne10_fft_cpx_float32_t *in  = malloc(fftSize * sizeof(ne10_fft_cpx_float32_t)); // Allocate an input array of samples
    ne10_fft_cpx_float32_t *out = malloc(fftSize * sizeof(ne10_fft_cpx_float32_t)); // Allocate an output array of samples

    ...

    // FFT
    ne10_fft_c2c_1d_float32_neon(out, in, cfg, 0); // Call the FP32 C2C NEON implementation directly

    ...

    // IFFT
    ne10_fft_c2c_1d_float32_neon(out, in, cfg, 1); // Call the FP32 C2C NEON implementation directly (reusing the configuration structure!)

    ...

    NE10_FREE(out);                    // Free the allocated input array
    NE10_FREE(in);                     // Free the allocated output array
    ne10_fft_destroy_c2c_float32(cfg); // Free the allocated configuration structure
}

The ne10_fft_cfg_float32_t variable cfg is a pointer to a configuration structure. For different inputs of the same size, the same configuration structure can (and should, where possible) be reused.

The contents of these configuration structures include:

• cfg->twiddles: a pointer to a table of "twiddle factors" that are used in computing the FFT/IFFT
• cfg->factors: a buffer of "factors", which suggests to the core algorithm how the input can be broken down into smaller calculations
• cfg->buffer: a pointer to a temporary buffer used internally in calculations that is allocated when the configuration structure is set up

Function Documentation

ne10_fft_cfg_float32_t ne10_fft_alloc_c2c_float32_c

(

ne10_int32_t

nfft

)

Specific implementation of ne10_fft_alloc_c2c_float32 for ne10_fft_c2c_1d_float32_c.

Definition at line 828 of file NE10_fft_float32.c.

ne10_fft_cfg_float32_t ne10_fft_alloc_c2c_float32_neon

(

ne10_int32_t

nfft

)

Specific implementation of ne10_fft_alloc_c2c_float32 for ne10_fft_c2c_1d_float32_neon.

Definition at line 348 of file NE10_fft.c.

ne10_fft_cfg_int16_t ne10_fft_alloc_c2c_int16

(

ne10_int32_t

nfft

)

Creates a configuration structure for variants of ne10_fft_c2c_1d_int16.

Parameters

[in]

nfft

input length

Return values

st	pointer to an FFT configuration structure (allocated with malloc), or NULL to indicate an error

Allocates and initialises an ne10_fft_cfg_int16_t configuration structure for the complex-to-complex 16-bit integer fixed point FFT/IFFT. As part of this, it reserves a buffer used internally by the FFT algorithm, factors the length of the FFT into simpler chunks, and generates a "twiddle table" of coefficients used in the FFT "butterfly" calculations.

To free the returned structure, call ne10_fft_destroy_c2c_int16.

Definition at line 1071 of file NE10_fft_int16.c.

ne10_fft_cfg_int32_t ne10_fft_alloc_c2c_int32_c

(

ne10_int32_t

nfft

)

Specific implementation of ne10_fft_alloc_c2c_int32 for ne10_fft_c2c_1d_int32_c.

Definition at line 1054 of file NE10_fft_int32.c.

ne10_fft_cfg_int32_t ne10_fft_alloc_c2c_int32_neon

(

ne10_int32_t

nfft

)

Specific implementation of ne10_fft_alloc_c2c_int32 for ne10_fft_c2c_1d_int32_neon.

Definition at line 451 of file NE10_fft.c.

void ne10_fft_c2c_1d_float32_c	(	ne10_fft_cpx_float32_t *	fout,
		ne10_fft_cpx_float32_t *	fin,
		ne10_fft_cfg_float32_t	cfg,
		ne10_int32_t	inverse_fft
	)

Specific implementation of ne10_fft_c2c_1d_float32 using plain C.

Definition at line 888 of file NE10_fft_float32.c.

void ne10_fft_c2c_1d_float32_neon	(	ne10_fft_cpx_float32_t *	fout,
		ne10_fft_cpx_float32_t *	fin,
		ne10_fft_cfg_float32_t	cfg,
		ne10_int32_t	inverse_fft
	)

Specific implementation of ne10_fft_c2c_1d_float32 using NEON SIMD capabilities.

Additionally requires that inputs are sized such that fftSize % 4 == 0 if fftSize > 2.

Definition at line 665 of file NE10_fft_float32.neon.c.

void ne10_fft_c2c_1d_int16_c	(	ne10_fft_cpx_int16_t *	fout,
		ne10_fft_cpx_int16_t *	fin,
		ne10_fft_cfg_int16_t	cfg,
		ne10_int32_t	inverse_fft,
		ne10_int32_t	scaled_flag
	)

Specific implementation of ne10_fft_c2c_1d_int16 using plain C.

Definition at line 1137 of file NE10_fft_int16.c.

void ne10_fft_c2c_1d_int16_neon	(	ne10_fft_cpx_int16_t *	fout,
		ne10_fft_cpx_int16_t *	fin,
		ne10_fft_cfg_int16_t	cfg,
		ne10_int32_t	inverse_fft,
		ne10_int32_t	scaled_flag
	)

Specific implementation of ne10_fft_c2c_1d_int16 using NEON SIMD capabilities.

Definition at line 775 of file NE10_fft_int16.neon.c.

void ne10_fft_c2c_1d_int32_c	(	ne10_fft_cpx_int32_t *	fout,
		ne10_fft_cpx_int32_t *	fin,
		ne10_fft_cfg_int32_t	cfg,
		ne10_int32_t	inverse_fft,
		ne10_int32_t	scaled_flag
	)

Specific implementation of ne10_fft_c2c_1d_int32 using plain C.

Definition at line 1106 of file NE10_fft_int32.c.

void ne10_fft_c2c_1d_int32_neon	(	ne10_fft_cpx_int32_t *	fout,
		ne10_fft_cpx_int32_t *	fin,
		ne10_fft_cfg_int32_t	cfg,
		ne10_int32_t	inverse_fft,
		ne10_int32_t	scaled_flag
	)

Specific implementation of ne10_fft_c2c_1d_int32 using NEON SIMD capabilities.

Definition at line 1204 of file NE10_fft_int32.neon.c.

void ne10_fft_destroy_c2c_float32

(

ne10_fft_cfg_float32_t

cfg

)

Destroys the configuration structure allocated by variants of ne10_fft_alloc_c2c_float32 (frees memory, etc.)

Parameters

[in]

cfg

pointer to the FFT configuration structure

Examples:

NE10_sample_complex_fft.c.

Definition at line 556 of file NE10_fft.c.

void ne10_fft_destroy_c2c_int16

(

ne10_fft_cfg_int16_t

cfg

)

Destroys the configuration structure allocated by ne10_fft_alloc_c2c_int16 (frees memory, etc.)

Parameters

[in]

cfg

pointer to the FFT configuration structure

Definition at line 576 of file NE10_fft.c.

void ne10_fft_destroy_c2c_int32

(

ne10_fft_cfg_int32_t

cfg

)

Destroys the configuration structure allocated by variants of ne10_fft_alloc_c2c_int32 (frees memory, etc.)

Parameters

[in]

cfg

pointer to the FFT configuration structure

Definition at line 566 of file NE10_fft.c.

Variable Documentation

ne10_fft_cfg_float32_t(* ne10_fft_alloc_c2c_float32) (ne10_int32_t nfft)

Creates a configuration structure for ne10_fft_c2c_1d_float32.

Parameters

[in]

nfft

input length

Return values

st	pointer to an FFT configuration structure (allocated with malloc), or NULL to indicate an error

Allocates and initialises an ne10_fft_cfg_float32_t configuration structure for the complex-to-complex single precision floating point FFT/IFFT. As part of this, it reserves a buffer used internally by the FFT algorithm, factors the length of the FFT into simpler chunks, and generates a "twiddle table" of coefficients used in the FFT "butterfly" calculations. Points to ne10_fft_alloc_c2c_float32_c or ne10_fft_alloc_c2c_float32_neon.

To free the returned structure, call ne10_fft_destroy_c2c_float32.

Examples:

NE10_sample_complex_fft.c.

Definition at line 114 of file NE10_init_dsp.c.

ne10_fft_cfg_int32_t(* ne10_fft_alloc_c2c_int32) (ne10_int32_t nfft)

Creates a configuration structure for ne10_fft_c2c_1d_int32.

Parameters

[in]

nfft

input length

Return values

st	pointer to an FFT configuration structure (allocated with malloc), or NULL to indicate an error

Allocates and initialises an ne10_fft_cfg_int32_t configuration structure for the complex-to-complex 32-bit integer fixed point FFT/IFFT. As part of this, it reserves a buffer used internally by the FFT algorithm, factors the length of the FFT into simpler chunks, and generates a "twiddle table" of coefficients used in the FFT "butterfly" calculations. Points to ne10_fft_alloc_c2c_int32_c or ne10_fft_alloc_c2c_int32_neon.

To free the returned structure, call ne10_fft_destroy_c2c_int32.

Definition at line 115 of file NE10_init_dsp.c.

void(* ne10_fft_c2c_1d_float32) (ne10_fft_cpx_float32_t *fout, ne10_fft_cpx_float32_t *fin, ne10_fft_cfg_float32_t cfg, ne10_int32_t inverse_fft)

Mixed radix-2/3/4/5 complex FFT/IFFT of single precision floating point data.

Parameters

[out]	*fout	pointer to the output buffer
[in]	*fin	pointer to the input buffer
[in]	cfg	pointer to the configuration structure (allocated via a variant of ne10_fft_alloc_c2c_float32)
[in]	inverse_fft	whether this is an FFT or IFFT (0: FFT, 1: IFFT)

Implements a mixed radix-2/3/4/5 complex FFT/IFFT, supporting input lengths of the form 2^N*3^M*5^K (N > 0). Points to ne10_fft_c2c_1d_float32_c or ne10_fft_c2c_1d_float32_neon, the latter of which has the additional constraint that fftSize % 4 == 0 must hold if fftSize > 2. This is an out-of-place algorithm. For usage information, please check test/test_suite_fft_float32.c.

Examples:

NE10_sample_complex_fft.c.

Definition at line 117 of file NE10_init_dsp.c.

void(* ne10_fft_c2c_1d_int16) (ne10_fft_cpx_int16_t *fout, ne10_fft_cpx_int16_t *fin, ne10_fft_cfg_int16_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)

Mixed radix-2/4 complex FFT/IFFT of 16-bit fixed point Q15 data.

Parameters

[out]	*fout	pointer to the output buffer
[in]	*fin	pointer to the input buffer
[in]	cfg	pointer to the configuration structure (allocated via ne10_fft_alloc_c2c_int16)
[in]	inverse_fft	whether this is an FFT or IFFT (0: FFT, 1: IFFT)
[in]	scaled_flag	scale flag (0: unscaled, 1: scaled)

Implements a mixed radix-2/4 complex FFT/IFFT, supporting input lengths of the form 2^N (N > 0). Points to ne10_fft_c2c_1d_int16_c or ne10_fft_c2c_1d_int16_neon. This is an out-of-place algorithm. For usage information, please check test/test_suite_fft_int16.c.

Definition at line 147 of file NE10_init_dsp.c.

void(* ne10_fft_c2c_1d_int32) (ne10_fft_cpx_int32_t *fout, ne10_fft_cpx_int32_t *fin, ne10_fft_cfg_int32_t cfg, ne10_int32_t inverse_fft, ne10_int32_t scaled_flag)

Mixed radix-2/4 complex FFT/IFFT of 32-bit fixed point Q31 data.

Parameters

[out]	*fout	pointer to the output buffer
[in]	*fin	pointer to the input buffer
[in]	cfg	pointer to the configuration structure (allocated via a variant of ne10_fft_alloc_c2c_int32)
[in]	inverse_fft	whether this is an FFT or IFFT (0: FFT, 1: IFFT)
[in]	scaled_flag	scale flag (0: unscaled, 1: scaled)

Implements a mixed radix-2/4 complex FFT/IFFT, supporting input lengths of the form 2^N (N > 0). Points to ne10_fft_c2c_1d_int32_c or ne10_fft_c2c_1d_int32_neon. This is an out-of-place algorithm. For usage information, please check test/test_suite_fft_int32.c.

Definition at line 130 of file NE10_init_dsp.c.