Multiframe FFT using single larger FFT

Started by kgrze 2 years ago4 replieslatest reply 2 years ago222 views


I have an algorithm that slices wav file into blocks (frames) of size 64 and does 64 point FFT on them. Recently I was give a hardware acceleration library with supported FFT sized of 512, 1024, 2048, 4096 and 8192.

My question is: could we take a multiple blocks say 8 blocks and do 512 point FFT on them and then split them somehow into 8 x FFT(64) form?

All signals are sampled with the same frequency. The reason I need to use 64-bin representation is that I have another DSP nodes requiring such format.

Looking forward on suggestions.




[ - ]
Reply by fharrisFebruary 10, 2022


yes you can do that!

suppose you have two 64 point transforms you want to do but only have a 128 point FFT.

imagine doing this: take the first time sequence of length 64 and put it into the 128 point input array by repeating the same sequence [h1(n) h1(n)]. if you FFT this repeated sequence the transfrom you get will be 128 points but every other sample will be zero... zero packing a sequence causes its transfrom to repeat. What you can do is put the second sequence in the same input array in a way that places its transform in the zero valued transform points of the same 128 point fft. You do this by repeating the second array with a sign change. [h2(n) -h2(n)]... if we add these two repeated sequences 

[h1+h2 h1-h2] the 128 point transform will have interleaved the 64 point transfoms of the original two input sequeces.. The pre processing is the equivalent of a butterfly operation of the two input sequences, a two point transform of the same sequences. 

We can accomplish the same thing with 4 shorter sequences, doing 1-to-4 repeats of the 4 shorter sequences using a 4-point butterfly structure (called a dragonfly)... or a 4-point FFT with the twiddle factors being successive powers of j. the resulting transform will contain 4-interleaved shorter transforms..  I used a similar trick in the attached paper.  


best regards

fred h

[ - ]
Reply by dudelsoundFebruary 10, 2022

Awesome! Wish I had grasped that earlier!

[ - ]
Reply by fharrisFebruary 10, 2022

It is a pretty neat trick that i developed for the same reason you have.

fred h

[ - ]
Reply by kgrzeFebruary 10, 2022

Wow, thanks for such a detailed reply. I will try to implement this fancy trick and then get back with some update. Thanks again!