Fast Fourier Transform (FFT)

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);
}

Similarly, a 512 point FFT can be implemented, using a mix of radix-2 and radix-4 stages, as follows:

void fft_512pt(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<256>(x,   tw1,                     512, shift_tw, shift, inv, y);
    aie::fft_dit_r4_stage<64> (y,   tw2,   tw4,   tw2_4,     512, shift_tw, shift, inv, tmp);
    aie::fft_dit_r4_stage<16> (tmp, tw8,   tw16,  tw8_16,    512, shift_tw, shift, inv, y);
    aie::fft_dit_r4_stage<4>  (y,   tw32,  tw64,  tw32_64,   512, shift_tw, shift, inv, tmp);
    aie::fft_dit_r4_stage<1>  (tmp, tw128, tw256, tw128_256, 512, shift_tw, shift, inv, y);
}

Note

For an odd number of stages the input buffer may be used in place of the tmp, which could be of benefit for large FFTs.

The order of the twiddle arguments are outlined in the description of each FFT stage function: aie::fft_dit_r2_stage, aie::fft_dit_r3_stage, aie::fft_dit_r4_stage, aie::fft_dit_r5_stage

An R-Radix, N-point FFT requires R-1 twiddle tables per stage.

Each of the tables are of length (n_stage / R), where n_stage is the local number of samples of the current radix stage. The local number of samples is given as the total point size, N, divided by the Vectorization, which is the template parameter of the fft_dit_r*_stage function calls. This is due to the fact that earlier stages of an N-point FFT are smaller, batched FFTs.

For each stage, the twiddle tables can be computed, in floating point, as:

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

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

template <typename TR, typename T>
TR convert_twiddle_to_fixed_point(T val, unsigned shift_tw) {
    return aie::to_fixed<TR>(val * (1 << shift_tw));
}
 
// Required to prevent overflow on conversions
aie::set_rounding(aie::rounding_mode::positive_inf);
aie::set_saturation(aie::saturation_mode::saturate);
 
unsigned shift_tw = 15;
cfloat tw = cfloat(1.0f, 0.0f);
cint16 tw_fixed = convert_twiddle_to_fixed_point<cint16>(tw, shift_tw);
// tw_fixed = 32767 + 0j

The following python code may be used to generate the twiddle tables:

import numpy as np
 
def tw(n, radix, vec):
    n_stage = n / vec
    points = n_stage / radix
    return np.exp(-2j * np.pi * np.arange(1, radix).reshape(-1,1) * np.arange(0, points) / n_stage)

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 > requires (arch::is(arch::AIE, arch::AIE_ML))
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) && detail::is_floating_point_v<Input>)
void	aie::fft_dit_r3_stage (const Input *__restrict x, const Twiddle *__restrict tw0, const Twiddle *__restrict tw1, unsigned n, bool inv, Output *__restrict out)
	A function to perform a single floating point radix 3 FFT stage.
template<unsigned Vectorization, typename Input , typename Output , typename Twiddle > requires (arch::is(arch::AIE, arch::AIE_ML))
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 > requires (arch::is(arch::AIE, arch::AIE_ML))
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) && detail::is_floating_point_v<Input>)
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, bool inv, Output *__restrict out)
	A function to perform a single floating point radix 5 FFT stage.
template<unsigned Vectorization, typename Input , typename Output , typename Twiddle > requires (arch::is(arch::AIE, arch::AIE_ML))
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, 3, 4, 5
c32b	c16b	c16b	2, 4,	2, 4
c32b	c32b	c16b	2, 3, 4, 5	2, 3, 4, 5
c32b	c16b	c32b	2
c32b	c32b	c32b	2, 3, 4, 5
cfloat	cfloat	cfloat	2, 3, 5

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 >
requires (arch::is(arch::AIE, arch::AIE_ML))

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() [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_r3_stage	(	const Input *__restrict	x,
		const Twiddle *__restrict	tw0,
		const Twiddle *__restrict	tw1,
		unsigned	n,
		bool	inv,
		Output *__restrict	out
	)

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

Defining the rotation rate of a given twiddle to be w(tw), the relationship between the twiddle groups are

w(tw0) < w(tw1)

Parameters

x	Input data pointer
tw0	First twiddle group pointer
tw1	Second 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_r3_stage() [2/2]

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

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.

Defining the rotation rate of a given twiddle to be w(tw), the relationship between the twiddle groups are

w(tw0) < w(tw1)

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 >
requires (arch::is(arch::AIE, arch::AIE_ML))

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.

Defining the rotation rate of a given twiddle to be w(tw), the relationship between the twiddle groups are

w(tw1) < w(tw0) < w(tw2)

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() [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_r5_stage	(	const Input *__restrict	x,
		const Twiddle *__restrict	tw0,
		const Twiddle *__restrict	tw1,
		const Twiddle *__restrict	tw2,
		const Twiddle *__restrict	tw3,
		unsigned	n,
		bool	inv,
		Output *__restrict	out
	)

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

Defining the rotation rate of a given twiddle to be w(tw), the relationship between the twiddle groups are

w(tw0) < w(tw1) < w(tw2) < w(tw3)

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
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() [2/2]

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

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.

Defining the rotation rate of a given twiddle to be w(tw), the relationship between the twiddle groups are

w(tw0) < w(tw1) < w(tw2) < w(tw3)

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.