FFT - iFFT

[kheber]

Hi, I see a FFT functions in the Espressif DSP Library at :
https://docs.espressif.com/projects/esp ... s.html#fft

However, it is unclear which functions are forward or backward FFT / iFFT. The documentation is very unhelpful and there are no examples given.

Can anyone provide application examples of FFT / iFFT?

Thank you

[tommeyers]

Where have you looked? What did you find? (Google.com ?)

Tom

[bobolink]

For complex numbers you can use the FFT for the IFT:
ift = conjugate, fft, conjugate, scale
Check a math book for details.

[kheber]

That's an idea; thank you. It requires unanticipated work and it should be in ASM to be fully optimized. Most other DSP suppliers have already solved that problem and written a proper iFFT for their libraries.

[Vvvoid]

It's 2025 and there's still no ifft

[knutbrut]

Sorry for restarting an old thread. I am aware we can do:

IFFT(data) = 1/N * conj(FFT(conj(data)))

However for efficiency a dedicated IFFT function would be better. Looking at the math the difference other than the 1/N scaling factor is as "simple" as a sign flip for the exponent of "e" from (-jwt) into (+jwt). Now looking at the dsps_fft2r_fc32_aes3 assembly (as ESP32-S3 is my target). The core processing block:

Code: Select all

#include "dsps_fft2r_platform.h"
#if (dsps_fft2r_fc32_aes3_enabled == 1)

	.text
	.align  4
	.global dsps_fft2r_fc32_aes3_
	.type   dsps_fft2r_fc32_aes3_,@function

dsps_fft2r_fc32_aes3_: 
//esp_err_t dsps_fft2r_fc32_ansi(float *data, int N, float* dsps_fft_w_table_fc32)

	entry	a1, 16

// Array increment for floating point data should be 4
// data - a2
// N - a3
// dsps_fft_w_table_fc32 - a4

// a6 - k, main loop counter; N2 - for (int N2 = N/2; N2 > 0; N2 >>= 1)
// a7 - ie
// a8 - j
// a10 - (j*2)<<2,  or a10 - j<<3
// f0 - c or w[2 * j]
// f1 - s or w[2 * j + 1]
// a11 - ia
// a12 - m
// a13 - ia pointer
// a14 - m pointer
// f6  - re_temp
// f7  - im_temp

    srli a6, a3, 1 // a6 = N2 = N/2
    movi.n a7, 1   // a7 - ie

.fft2r_l1:
    movi.n a8, 0   // a8 - j
    movi.n a11,0   // a11 = ia = 0;

.fft2r_l2:         // loop for j, a8 - j
        addx8    a10, a8, a4 // a8 - shift for cos () -- c = w[2 * j]; -- pointer to cos
        ee.ldf.64.ip f1, f0, a10, 0
        add.n    a12, a11, a6   // a12 = m = ia + N2
        addx8    a14, a12, a2   // a14 - pointer for m*2

        loopnez a6, .fft2r_l3
            ee.ldf.64.ip f5, f4, a14, 0 // data[2 * m], data[2 * m + 1]
            mul.s    f6, f0, f4     // re_temp =  c * data[2 * m]
            mul.s    f7, f0, f5     // im_temp =  c * data[2 * m + 1]

            addx8    a13, a11, a2   // a13 - pointer for ia*2
            ee.ldf.64.ip f3, f2, a13, 0 // data[2 * ia], data[2 * ia + 1]

            madd.s   f6, f1, f5     // re_temp += s * data[2 * m + 1]; // <---------- add the w term
            msub.s   f7, f1, f4     // im_temp -= s * data[2 * m];  // <------------- subtracting the w term

            addi     a11, a11, 1    // ia++
            add.n    a12, a11, a6   // a12 = m = ia + N2

            sub.s    f8, f2, f6     // = data[2 * ia] - re_temp;
            sub.s    f9, f3, f7     // = data[2 * ia + 1] - im_temp;
            add.s    f10, f2, f6    // = data[2 * ia] + re_temp;
            add.s    f11, f3, f7    // = data[2 * ia + 1] + im_temp;

            ee.stf.64.ip f9, f8, a14, 0
            addx8    a14, a12, a2   // a14 - pointer for m*2
            ee.stf.64.ip f11, f10, a13, 0
.fft2r_l3:
        add.n   a11, a11, a6

        addi.n  a8, a8, 1 // j++
        bne     a8, a7, .fft2r_l2
    slli    a7, a7, 1  // ie = ie<<1
// main loop: for (int k = N/2; k > 0; k >>= 1)
    srli    a6, a6, 1     // a6 = a6>>1
    bnez    a6, .fft2r_l1 // Jump if > 0

	movi.n	a2, 0 // return status ESP_OK
	retw.n

#endif // dsps_fft2r_fc32_aes3_enabled

I'm pondering if it would be as simple as exchanging the msub.s and madd.s. The twiddle factors would be unchanged. Like this:

Code: Select all

msub.s   f6, f1, f5     // re_temp -= s * data[2 * m + 1]; 
madd.s   f7, f1, f4     // im_temp += s * data[2 * m];  

thoughts?

[MicroController]

You may want to check out esp-dl's FFT:
https://components.espressif.com/compon ... if/dl_fft/
https://github.com/espressif/esp-dl/tre ... ols/dl_fft

Seems to have iFFT functions too.