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

[Jacob Lifshay]

On Tue, Jun 22, 2021, 06:09 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
wrote:

> 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
> > using bit-reversed indices,
>
> deep breath, look again at the Cooley butterfly:
>
> https://en.wikipedia.org/wiki/File:DIT-FFT-butterfly.png
>
> so imagine that the initial width is 1024, that is split 512 .... down
> to e.g. 8 where we can do the REMAP.
>
> i *think*... that you have to select data at the *low* level to suit
> the *high* level.
>
> i.e. rather than the bitreverse being simply based on log2(8) i.e. 3
> LSBs you have to select like this:
>
> for batches in range(0, 1024, 1024/8):
>     idxes = bitreverse(range(8))
>     idexes <<= log2(1024/8)
>     indexes += batches
>
> in other words, the bitreversing happens in the *TOP* bits, but the
> LSBs are left alone, i.e. are sequential.
>
> eurrgh :)
>
> i am going to have to do a demo on this.
>
> bottom line is, that the bitreversal indices might not need an SPR,
> Jacob: a simple shift-amount should be sufficient.
>

but that shift amount needs to live somewhere -- no space in the argument
list -- and if you want the code to be able to handle variable-sized FFT
then sticking the shift amount in an immediate won't work, hence the SPR.
We wouldn't necessarily need a new SPR, we can re-use CTR or LR or
something fast and accessible from userland.

Jacob