Optimising (for interleaved / padded input) FFT in progress. Basically you can select reading interleaved samples, or the first set of samples to the first/last set of frequencies as well as seeing gains in rendering IFFT from the first / last set of frequencies to interleaved or the first set of samples. Unnecessary computational paths will be eliminated.
This is all useful for up/down sampling as well as overlap-add.
ORIGINAL QUESTION (edited for clarity) ---
Example code: kfft.c
I wanted to know whether there is a similar FFT algorithm to mine.
I basically perform FFT by factorising calculations by recursively subtracting the second half of a signal from the first, meaning x[n] only needs to be multiplied by the complex sinusoid for only half of the duration, resulting in N/2 log N real multiplies (shown below). The summed signal is for multiplying with complex sinusoids that are multiples of the sampling period. For example groups {2, 6} are multiples of 2, and therefore have a periodicity of 4 samples.
Code: Select all
// For bins { 1, 3, 5 and 7 }
x1[0] = x0[0] - x0[4]
x1[1] = x0[1] - x0[5]
x1[2] = x0[2] - x0[6]
x1[3] = x0[3] - x0[7]
// Calculate sum (required for the next level of bins)
x0[0] = x0[0] + x0[4]
x0[1] = x0[1] + x0[5]
x0[2] = x0[2] + x0[6]
x0[3] = x0[3] + x0[7]
// For bins { 2 and 6 }
x2[0] = x0[0] - x0[2]
x2[1] = x0[1] - x0[3]
// Calculate sum (required for the next level of bins)
x0[2] = x0[0] + x0[2]
x0[3] = x0[1] + x0[3]
// For bin { 4 }
x3[0] = x0[0] - x0[1]
x3[1] = x0[0] + x0[1] // <-- This is the 0hz bin (sum)
