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

[Luke Kenneth Casson Leighton]

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.

l.