[Libre-soc-dev] [RFC] REMAP, SHAPE, complex (full) FFT

[Luke Kenneth Casson Leighton]

---
crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68

On Tue, Jul 20, 2021 at 4:51 PM Jacob Lifshay <programmerjake at gmail.com> wrote:
>
> On Tue, Jul 20, 2021, 08:01 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
> wrote:
>
> > currently i have a reordering phase in the middle of the butterflies,
> > however i *believe* it will be possible to *pre-load* the data in just the
> > right inversed-order, and also set the "swapping" indices up in an
> > inversed-order...

success!
https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=src/openpower/decoder/isa/fastdctlee.py;h=4aef62e1d229878a2f26d15df7ea80ac416ae690;hb=af71f17e7d71af986d17808161fa812d33fe1d22

this involved inverting the order in which high-half-swapping was done,
such that *after* the inner butterfly was run, the data ended up in
sequential order.


> Do note that DCT isn't just a single thing, there are at least 8 different
> kinds of 1D DCT (named DCT I through DCT VIII), and more combinations of 2D
> and 3D DCT:
>
> https://en.wikipedia.org/wiki/Discrete_cosine_transform#Formal_definition

yes, i saw those.  one at a time :)

2D will be particularly obtuse and fun.  in theeooryy it should be possible to
do by arranging different kinds of schedules, or, simply, to perform multiple
1D DCTs in loops.

l.