Overview

These are the intrinsics functions used for implementing FFT functionality.

For intrinsics used for addressing related to FFT please see FFT addressing.

The FFT algorithm works by executing these functions a number of times in different stages.

The number of stages is the log of the number of points in the FFT with the radix as the base of the log. For instance for a 256 point radix 2 FFT the process is split into 8 stages. The first 6 stages are the same and consist of calling the butterfly function on every input value that is supplied to it, these input values depend on the radix. In this instance (radix 2) means that every second block is processed. The input pointer is determined by by an incrementation function fft_data_incr. The twiddle values are determined by the use of two functions fft_permute_incr which determines which values within the register to use and fft_twiddle_incr which increments the pointer to the twiddle factors, thereby providing a fresh set of twiddle values.

The output of each stage becomes the input of the next stage.

The last two stages differ from the initial 6 stages in the way that the inputs are twiddles are mapped from the registers and how often the twiddles are updated from the registers.

In the case of radix 2, 256 point FFT with 32bit data, a stage will consist of 32 butterfly calls, each consuming 8 samples, 64 store operations and 64 AIE cycles total.

FFT scalar functions
unsigned	fft_zoffs (umod_t cntwrap, int step, bool wide_twiddle, bool wide_data)
	Change twiddle factor selectors.

umod_t	fft_mod_delay (umod_t cntwrap)
	Delay the count/wrap parameter.

Function Documentation

◆ fft_mod_delay()

umod_t fft_mod_delay ( umod_t cntwrap )

Delay the count/wrap parameter.

Parameters

cntwrap Counts the number of FFT wraps. The MSB is the wrap bit itself.

Returns: Same value as input but delayed by some cycles.

This function is needed in the radix-4 FFT implementations where the cntwrap parameter is generated many cycles before its consumption and hence needs to be delayed.

◆ fft_zoffs()

unsigned fft_zoffs	(	umod_t	cntwrap,
		int	step,
		bool	wide_twiddle,
		bool	wide_data )

Change twiddle factor selectors.

Parameters

cntwrap	Counts the number of FFT wraps. The MSB is the wrap bit itself.
step	Range {0..3}. Binary logarithm of the count wrap around (number of wraps per twiddle vector). This must be a compile time constant.
wide_twiddle	True if a wide 8 lane twiddle vector is used. This must be a compile time constant.
wide_data	True if a wide 8 lane data vector is used This must be a compile time constant.

Returns: Coefficient (twiddle) selector value for the butterfly() intrinsic.

Note: Parameters 'step', 'wide_twiddle' and 'wide_data' must be compile time constants.

The butterfly function chooses which twiddle values from the register to use with which input values, based on the returned zoffs value.

For instance if zoffs = 0x1100 then the first twiddle value is used with in[3] and in[2] and the second twiddle value is used with in[1] and in[0]. Which values in the input register correspond to in[3]-in[0] is determined by a similar mapping process in the butterfly function.

For more information on the intrinsic's behaviour you can check the following pseudocode:

unsigned fft_zoffs_test(int cntwrap, int step, bool wide_twiddle, bool wide_data) {
    int out;
    switch (step) {
    case 0:
        if (wide_data == 1)
            out = 0x76543210;
        break;
    case 1:
        cntwrap &= 1;
        if (wide_data == 0)
            out = 4*cntwrap * 0x1111     + 0x3210;
        else
            out = 4*cntwrap * 0x11111111 + 0x33221100;
        break;
    case 2:
        cntwrap &= 3;
        if (wide_data == 0)
            out = 2*cntwrap * 0x1111     + 0x1100;
        else
            out = 2*cntwrap * 0x11111111 + 0x11110000;
        break;
    case 3:
        cntwrap &= 7;
        if (wide_data == 0)
            out =   cntwrap * 0x1111;
        else
            out =   cntwrap * 0x11111111;
        break;
    }
 
    if (wide_twiddle == 0) {
        out &= 0x33333333;
    } else {
        out &= 0x77777777;
    }
    return out;
}

The following tables shows the resulting offset's the intrinsic would return when:

wide_twiddle = wide_data = 0

cntwrap	Stage=3	Stage=2	Stage=1
0	{0,0,0,0}	{0,0,1,1}	{0,1,2,3}
1	{1,1,1,1}	{2,2,3,3}	{0,1,2,3}
2	{2,2,2,2}	{0,0,1,1}	{0,1,2,3}
3	{3,3,3,3}	{2,2,3,3}	{0,1,2,3}
4	{0,0,0,0}	{0,0,1,1}	{0,1,2,3}
5	{1,1,1,1}	{2,2,3,3}	{0,1,2,3}
6	{2,2,2,2}	{0,0,1,1}	{0,1,2,3}
7	{3,3,3,3}	{2,2,3,3}	{0,1,2,3}

wide_twiddle = 1, wide_data = 0

cntwrap	Stage = 3	Stage = 2	Stage = 1
0	{0,0,0,0}	{0,0,1,1}	{0,1,2,3}
1	{1,1,1,1}	{2,2,3,3}	{4,5,6,7}
2	{2,2,2,2}	{4,4,5,5}	{0,1,2,3}
3	{3,3,3,3}	{6,6,7,7}	{4,5,6,7}
4	{4,4,4,4}	{0,0,1,1}	{0,1,2,3}
5	{5,5,5,5}	{2,2,3,3}	{4,5,6,7}
6	{6,6,6,6}	{4,4,5,5}	{0,1,2,3}
7	{7,7,7,7}	{6,6,7,7}	{4,5,6,7}

wide_twiddle = 0, wide_data = 1

cntwrap	Stage = 3	Stage = 2	Stage = 1
0	{0,0,0,0,0,0,0,0}	{0,0,0,0,1,1,1,1}	{0,0,1,1,2,2,2,3}
1	{1,1,1,1,1,1,1,1}	{2,2,2,2,3,3,3,3}	{0,0,1,1,2,2,2,3}
2	{2,2,2,2,1,1,1,1}	{0,0,0,0,1,1,1,1}	{0,0,1,1,2,2,2,3}
3	{3,3,3,3,3,3,3,3}	{2,2,2,2,3,3,3,3}	{0,0,1,1,2,2,2,3}
4	{0,0,0,0,0,0,0,0}	{0,0,0,0,1,1,1,1}	{0,0,1,1,2,2,2,3}
5	{1,1,1,1,1,1,1,1}	{2,2,2,2,3,3,3,3}	{0,0,1,1,2,2,2,3}
6	{2,2,2,2,1,1,1,1}	{0,0,0,0,1,1,1,1}	{0,0,1,1,2,2,2,3}
7	{3,3,3,3,3,3,3,3}	{2,2,2,2,3,3,3,3}	{0,0,1,1,2,2,2,3}

wide_twiddle = 1, wide_data = 1

cntwrap	Stage = 3	Stage = 2	Stage = 1	Stage = 0
0	{0,0,0,0,0,0,0,0}	{0,0,0,0,1,1,1,1}	{0,0,1,1,2,2,2,3}	{0,1,2,3,4,5,6,7}
1	{1,1,1,1,1,1,1,1}	{2,2,2,2,3,3,3,3}	{4,4,5,5,6,7,7,7}	{0,1,2,3,4,5,6,7}
2	{2,2,2,2,1,1,1,1}	{4,4,4,4,5,5,5,5}	{0,0,1,1,2,2,2,3}	{0,1,2,3,4,5,6,7}
3	{3,3,3,3,3,3,3,3}	{6,6,6,6,7,7,7,7}	{4,4,5,5,6,6,7,7}	{0,1,2,3,4,5,6,7}
4	{4,4,4,4,4,4,4,4}	{0,0,0,0,1,1,1,1}	{0,0,1,1,2,2,2,3}	{0,1,2,3,4,5,6,7}
5	{5,5,5,5,5,5,5,5}	{2,2,2,2,3,3,3,3}	{4,4,5,5,6,7,7,7}	{0,1,2,3,4,5,6,7}
6	{6,6,6,6,6,6,6,6}	{4,4,4,4,5,5,5,5}	{0,0,1,1,2,2,2,3}	{0,1,2,3,4,5,6,7}
7	{7,7,7,7,7,7,7,7}	{6,6,6,6,7,7,7,7}	{4,4,5,5,6,6,7,7}	{0,1,2,3,4,5,6,7}