[Libre-soc-dev] FFT, DCT, REMAP

Luke Kenneth Casson Leighton lkcl at lkcl.net
Mon Jun 21 18:54:36 BST 2021

On 6/21/21, Jacob Lifshay <programmerjake at gmail.com> wrote:

> we'd need to correctly handle loading from the middle of a bigger array

from reading that fft.py source which is some algorithm B-somebody... bluestein!

a non-power-2 FFT can be done with a pair of smaller FFTs one of which
is power-2 the other recursively drilled down, and a convolution.

also, looking at ffmpeg, again, the larger FFTs can be done with
"pairs of smaller FFTs plus an extra layer"

in other words, the small FFT can be entirely local (local bitreversed
indices) where no offset is required.

joining two half FFTs together then applying an extra layer to make a
longer one? no idea, have to investigate that one.

but, it would not surprise me at all if it could be done with local
bitreverse combined with an immediate offset that doubles for each

have to check.  good call jacob.


More information about the Libre-soc-dev mailing list