🧵 Transpose FFT

Anonymous at Mon, 15 Jul 2024 09:15:31 UTC No. 16282176

I have recently explored the possibility of doing a FFT entirely with addition, subtraction, and transpose.
Turns out this is indeed possible, however, you're approximating the phase, so you need to project to a lattice and then at the end perform a phase adjustment from a much larger range of phase to a smaller range(project from thousands to billions of radians to just -pi, pi).
Your lattice can be entirely hypothetical, you dont need extra memory.

However, you need to explore and work out the math for each transpose sequence along with the final positioning in the imaginary sparse lattice, so you can get the individual phase adjustments needed. This work only needs to be done once for any FFT size, and then the phase adjustments and transposes can be used as a lookup table. We're talking doing an FFT in only 15% of the work!

Phase Lattice Mapping: Phase angles are mapped onto a lattice using a function φ(k) = 2πk * (L/N), where L is a chosen lattice size larger than N (FFT size). This spreads phase values over a range of 2πL/N.

Pre-Processing: Input signals are multiplied by exp(i * φ(n)), embedding phase information into the lattice positions.

FFT Operation: Instead of computing complex rotations, FFT operations involve simple integer shifts on the lattice. Each butterfly operation becomes an integer arithmetic operation.

Post-Processing: Results are reconstructed by sampling the lattice to retrieve magnitude and phase information, then converting back to standard phase ranges using modulo operations.


What do you think?

for a small FFT this doesnt need a lot of memory but for a 4 million point FFT. you need 700mb of ram

also, since our operations are cumulative, some will cancel out meaning the algorithm can be optimized further.

>>https://colab.research.google.com/drive/1ET3R_JkckEJ-LxJpd05PjbfGK-TyiPNF#scrollTo=B_ulN6Vv4e0X
I did some python to explore this concept