Fast Fourier Transform (FFT)

The AIE API offers a stage-based interface for carrying out decimation-in-time FFTs. More...

Overview

The AIE API offers a stage-based interface for carrying out decimation-in-time FFTs.

For example, assuming twiddle pointer visibility, a 1024 point FFT can be computed as follows:

void fft_1024pt(const cint16 * __restrict x,  // Input pointer
                unsigned shift_tw,            // Indicates the decimal point of the twiddles
                                              // e.g. The twiddle 1.0+0.0i can be represented with cint16(32767, 0) and a shift_tw of 15
                unsigned shift,               // Shift applied to apply to dit outputs
                bool inv,                     // Run inverse FFT
                cint16 * __restrict tmp,      // Scratch space for intermediate results
                cint16 * __restrict y         // Output pointer
               )
{
    aie::fft_dit_r2_stage<512>(x,   tw1,   1024, shift_tw, shift, inv, tmp);
    aie::fft_dit_r2_stage<256>(tmp, tw2,   1024, shift_tw, shift, inv, y);
    aie::fft_dit_r2_stage<128>(y,   tw4,   1024, shift_tw, shift, inv, tmp);
    aie::fft_dit_r2_stage<64> (tmp, tw8,   1024, shift_tw, shift, inv, y);
    aie::fft_dit_r2_stage<32> (y,   tw16,  1024, shift_tw, shift, inv, tmp);
    aie::fft_dit_r2_stage<16> (tmp, tw32,  1024, shift_tw, shift, inv, y);
    aie::fft_dit_r2_stage<8>  (y,   tw64,  1024, shift_tw, shift, inv, tmp);
    aie::fft_dit_r2_stage<4>  (tmp, tw128, 1024, shift_tw, shift, inv, y);
    aie::fft_dit_r2_stage<2>  (y,   tw256, 1024, shift_tw, shift, inv, tmp);
    aie::fft_dit_r2_stage<1>  (tmp, tw512, 1024, shift_tw, shift, inv, y);
}

An R-radix, N-point FFT typically requires R-1 twiddle tables, each with N / R entries. The entries, in floating point, are given by

for (unsigned r = 1; r < R; ++r) {
    for (unsigned i = 0; i < N / R; ++i) {
        tw[r-1][i] = exp(-2j * pi * r * i / n);
    }
}

For fixed point implementations, the twiddle value should be multiplied by (1 << shift_tw) before casting to the output type.

Given that earlier stages of an N-point FFT are smaller, batched FFTs, the same equation for the twiddle values hold. However, N is divided by the Vectorization to give N_stage = N / Vectorization.

Typedefs
template<unsigned Vectorization, unsigned Radix, typename Input , typename Output = Input, typename Twiddle = detail::default_twiddle_type_t<Input, Output>>
using	aie::fft_dit = detail::fft_dit< Vectorization, detail::fft_get_stage< Vectorization, Radix, Input, Output, Twiddle >(), Radix, Input, Output, Twiddle >
	Type that encapsulates the functionality for decimation-in-time FFTs.

Functions
template<unsigned Vectorization, typename Input , typename Output , typename Twiddle > requires (arch::is(arch::AIE) && detail::is_floating_point_v<Input>)
void	aie::fft_dit_r2_stage (const Input *__restrict x, const Twiddle *__restrict tw, unsigned n, bool inv, Output *__restrict out)
	A function to perform a single floating point radix 2 FFT stage.
template<unsigned Vectorization, typename Input , typename Output , typename Twiddle >
void	aie::fft_dit_r2_stage (const Input *__restrict x, const Twiddle *__restrict tw, unsigned n, unsigned shift_tw, unsigned shift, bool inv, Output *__restrict out)
	A function to perform a single radix 2 FFT stage.
template<unsigned Vectorization, typename Input , typename Output , typename Twiddle > requires (arch::is(arch::AIE))
void	aie::fft_dit_r3_stage (const Input *__restrict x, const Twiddle *__restrict tw0, const Twiddle *__restrict tw1, unsigned n, unsigned shift_tw, unsigned shift, bool inv, Output *__restrict out)
	A function to perform a single radix 3 FFT stage.
template<unsigned Vectorization, typename Input , typename Output , typename Twiddle >
void	aie::fft_dit_r4_stage (const Input *__restrict x, const Twiddle *__restrict tw0, const Twiddle *__restrict tw1, const Twiddle *__restrict tw2, unsigned n, unsigned shift_tw, unsigned shift, bool inv, Output *__restrict out)
	A function to perform a single radix 4 FFT stage.
template<unsigned Vectorization, typename Input , typename Output , typename Twiddle > requires (arch::is(arch::AIE))
void	aie::fft_dit_r5_stage (const Input *__restrict x, const Twiddle *__restrict tw0, const Twiddle *__restrict tw1, const Twiddle *__restrict tw2, const Twiddle *__restrict tw3, unsigned n, unsigned shift_tw, unsigned shift, bool inv, Output *out)
	A function to perform a single radix 5 FFT stage.

Supported Fast Fourier Transform Modes

Supported FFT/IFFT Modes

Input Type	Output Type	Twiddle Type	AIE Supported Radices	AIE-ML Supported Radices
c16b	c16b	c16b	2, 4	2, 4
c16b	c32b	c16b	2, 3, 4, 5	2, 4
c32b	c16b	c16b	2, 4,	2, 4
c32b	c32b	c16b	2, 3, 4, 5	2, 4
c32b	c16b	c32b	2
c32b	c32b	c32b	2, 3, 4, 5
cfloat	cfloat	cfloat	2

Typedef Documentation

fft_dit

template<unsigned Vectorization, unsigned Radix, typename Input , typename Output = Input, typename Twiddle = detail::default_twiddle_type_t<Input, Output>>

using aie::fft_dit = typedef detail::fft_dit<Vectorization, detail::fft_get_stage<Vectorization, Radix, Input, Output, Twiddle>(), Radix, Input, Output, Twiddle>

Type that encapsulates the functionality for decimation-in-time FFTs.

Deprecated:

The iterator interface is deprecated and the stage-based interface should be preferred.

Template Parameters

Vectorization	Vectorization of the FFT stage
Radix	Number which selects the FFT radix.
Input	Type of the input elements.
Output	Type of the output elements, defaults to input type.
Twiddle	Type of the twiddle elements, defaults to cint16 for integral types and cfloat for floating point.

See also

fft_dit_r2_stage, fft_dit_r3_stage, fft_dit_r4_stage, fft_dit_r5_stage

Function Documentation

fft_dit_r2_stage() [1/2]

template<unsigned Vectorization, typename Input , typename Output , typename Twiddle >
requires (arch::is(arch::AIE) && detail::is_floating_point_v<Input>)

void aie::fft_dit_r2_stage	(	const Input *__restrict	x,
		const Twiddle *__restrict	tw,
		unsigned	n,
		bool	inv,
		Output *__restrict	out
	)

A function to perform a single floating point radix 2 FFT stage.

Parameters

x	Input data pointer
tw	Twiddle group pointer
n	Number of samples
inv	Run inverse FFT stage
out	Output data pointer

Template Parameters

Vectorization	Vectorization of the FFT stage
Input	Type of the input elements.
Output	Type of the output elements, defaults to input type.
Twiddle	Type of the twiddle elements, defaults to cint16 for integral types and cfloat for floating point.

fft_dit_r2_stage() [2/2]

template<unsigned Vectorization, typename Input , typename Output , typename Twiddle >

void aie::fft_dit_r2_stage	(	const Input *__restrict	x,
		const Twiddle *__restrict	tw,
		unsigned	n,
		unsigned	shift_tw,
		unsigned	shift,
		bool	inv,
		Output *__restrict	out
	)

A function to perform a single radix 2 FFT stage.

Parameters

x	Input data pointer
tw	Twiddle group pointer
n	Number of samples
shift_tw	Indicates the decimal point of the twiddles
shift	Shift applied to apply to dit outputs
inv	Run inverse FFT stage
out	Output data pointer

Template Parameters

Vectorization	Vectorization of the FFT stage
Input	Type of the input elements.
Output	Type of the output elements, defaults to input type.
Twiddle	Type of the twiddle elements, defaults to cint16 for integral types and cfloat for floating point.

fft_dit_r3_stage()

template<unsigned Vectorization, typename Input , typename Output , typename Twiddle >
requires (arch::is(arch::AIE))

void aie::fft_dit_r3_stage	(	const Input *__restrict	x,
		const Twiddle *__restrict	tw0,
		const Twiddle *__restrict	tw1,
		unsigned	n,
		unsigned	shift_tw,
		unsigned	shift,
		bool	inv,
		Output *__restrict	out
	)

A function to perform a single radix 3 FFT stage.

Parameters

x	Input data pointer
tw0	First twiddle group pointer
tw1	Second twiddle group pointer
n	Number of samples
shift_tw	Indicates the decimal point of the twiddles
shift	Shift applied to apply to dit outputs
inv	Run inverse FFT stage
out	Output data pointer

Template Parameters

Vectorization	Vectorization of the FFT stage
Input	Type of the input elements.
Output	Type of the output elements, defaults to input type.
Twiddle	Type of the twiddle elements, defaults to cint16 for integral types and cfloat for floating point.

fft_dit_r4_stage()

template<unsigned Vectorization, typename Input , typename Output , typename Twiddle >

void aie::fft_dit_r4_stage	(	const Input *__restrict	x,
		const Twiddle *__restrict	tw0,
		const Twiddle *__restrict	tw1,
		const Twiddle *__restrict	tw2,
		unsigned	n,
		unsigned	shift_tw,
		unsigned	shift,
		bool	inv,
		Output *__restrict	out
	)

A function to perform a single radix 4 FFT stage.

Parameters

x	Input data pointer
tw0	First twiddle group pointer
tw1	Second twiddle group pointer
tw2	Third twiddle group pointer
n	Number of samples
shift_tw	Indicates the decimal point of the twiddles
shift	Shift applied to apply to dit outputs
inv	Run inverse FFT stage
out	Output data pointer

Template Parameters

Vectorization	Vectorization of the FFT stage
Input	Type of the input elements.
Output	Type of the output elements, defaults to input type.
Twiddle	Type of the twiddle elements, defaults to cint16 for integral types and cfloat for floating point.

fft_dit_r5_stage()

template<unsigned Vectorization, typename Input , typename Output , typename Twiddle >
requires (arch::is(arch::AIE))

void aie::fft_dit_r5_stage	(	const Input *__restrict	x,
		const Twiddle *__restrict	tw0,
		const Twiddle *__restrict	tw1,
		const Twiddle *__restrict	tw2,
		const Twiddle *__restrict	tw3,
		unsigned	n,
		unsigned	shift_tw,
		unsigned	shift,
		bool	inv,
		Output *	out
	)

A function to perform a single radix 5 FFT stage.

Parameters

x	Input data pointer
tw0	First twiddle group pointer
tw1	Second twiddle group pointer
tw2	Third twiddle group pointer
tw3	Fourth twiddle group pointer
n	Number of samples
shift_tw	Indicates the decimal point of the twiddles
shift	Shift applied to apply to dit outputs
inv	Run inverse FFT stage
out	Output data pointer

Template Parameters

Vectorization	Vectorization of the FFT stage
Input	Type of the input elements.
Output	Type of the output elements, defaults to input type.
Twiddle	Type of the twiddle elements, defaults to cint16 for integral types and cfloat for floating point.