Stream FFT and iFFT

[MyCo]

TheAudiophileDutchman, pointed out, that the error rate could be so low because of the accuracy of internal sine table. And he was right with that. I've changed the "From mag/phase" module to interpolate the sine table now, and the error rate is much better (max. error = -125dB).
I've done several other changes, too. Can't remember all of them. For testing purpose I've added a really basic Frequency domain filter.

Due to the sine table accuracy, maybe I've to change the sine table inside the FFT code again. The one from trog could probably deliver better results.

[martinvicanek]

Impressive work, MyCo!
One note regarding the filter (I know it is for testing only at this stage): the straight intuitive implementation introduces time aliasing. This is because a multiplication in the frequency domain amounts to a convolution or (FIR filtering) in the time domain. Now the convolution of a signal block of length N with a FIR of length M results in a block of length N + M - 1. Since the FFT/IFFT processing is circular, the extra length will alias unless we use sufficiently long blocks with some appropriate zero padding before and overlap-adding after processing. Here is a full explanation. Let me see if I can implement that (might take some time though). Oh, btw for linear filtering we can bypass the phase/magnitude conversion and process the real and imaginary parts directly.
Once again, thanks Trog, MyCo and DWB for pushing this. Reason for me to join this forum.

[MyCo]

Small update:
I've changed everything into quad packs, although the FFT itself is still mono. Some of the modules benefit from that, because they don't need to calculate anything twice (eg. Window, Scale, Phase/Mag,...).
I've ported DWBs ArcTan to Assembler, there is a small performance boost from that, too.

@Martin: When you have to zero pad does this mean, that your FFT has smaller Frame size as the iFFT? Or do you have to pad before you do the FFT?

[martinvicanek]

MyCo, FFT and IFFT are the same size. Before you do the FFT, you fill only half the frame with stream values and zero pad the rest. After convolution and IFFT you get a full frame back. Then you have to overlap add with the adjacent frames with 50% overlap. The figure below from the DAFX book illustrates the process quite well.

[MyCo]

OK, when I understand that right, we just need 2 parallel running FFTs in our system. The second is 1/2 Buffer delayed. That's like the current setup does it already. I'm just wondering what happens with the window. When I apply the window to 1/2 of the Frame, the other half is zero, then I'll probably need another set of 2 FFT/iFFTs that compensate for the window borders (1/4 and 3/4 of the Framesize delayed).

[martinvicanek]

As long as you stick to rectangular windows, 2 parallel FFT/IFFT will suffice for the filtering exercise. Demo attached. I have added a "half square" window function for the signal zero padding. The thing is you have to zero pad the FIR filter coefficients as well, so that involves some back and forth IFFT/FFT etc. which, however, can all be done in green. Look inside the schematic for documentation. By the way, I noticed that the green and the stream FFTs apparently have different exponent signs of the twiddle factors, you might want to check and make it consistent if necessary. Anyway, I think we have a first application of the stream FFT!

[MyCo]

Well it realy sounds right, but I don't think that this is right. When you don't filter at all (all bars in the graph are 100%), then the output of the filter part doesn't match the original. You can see it in the "Differential Error" box on the right bottom. I haven't checked it fully, but it looks like your green part allways removes the first FFT Bin, and therefor the DC offset. Also when the filter is completely down (all bars at 0%) you shouldn't hear anything, but I can still hear the bass.
So maybe the twiddle factor is right, but there is an offset in the filter output, so everything is shifted.

EDIT: forget that with the twiddle factor, it's indeed wrong. Damn... but how do I fix that in the full blown ASM Code

EDIT2: Why are all modules in your schematic unsynchronized?

[martinvicanek]

Well it realy sounds right, but I don't think that this is right. When you don't filter at all (all bars in the graph are 100%), then the output of the filter part doesn't match the original. You can see it in the "Differential Error" box on the right bottom. I haven't checked it fully, but it looks like your green part allways removes the first FFT Bin, and therefor the DC offset. Also when the filter is completely down (all bars at 0%) you shouldn't hear anything, but I can still hear the bass.
So maybe the twiddle factor is right, but there is an offset in the filter output, so everything is shifted.

Thanks for that, will have a closer look this evening. Note that the filter is linear phase with an additional group delay of 1/4 frame size, even if all bars are up. So that has to be accounted for in the differential error display.

EDIT: I don't quite understand the details of this in the Spectrum Draw module:

Code: Select all

output([1]+@in[0..len-1] + @in[0..len-2].reverse)

That does not strictly ensure hermitian symmetry. Also, if you force the first bin to 1, then DC always goes through no matter what the bar settings. Could that explain why you hear the bass when all bars are down?
Why not simply

Code: Select all

output(@in[0..len-1] + @in[0..len-1].reverse)

EDIT: forget that with the twiddle factor, it's indeed wrong. Damn... but how do I fix that in the full blown ASM Code

Not necessarily wrong, only inconsistent with green. Easy remedy: exchange FFT for IFFT and vice versa (apart from normalization maybe).

EDIT2: Why are all modules in your schematic unsynchronized?

Dunno, maybe because I'm still on the free version?

[MyCo]

Update:
- fixed, the synchronization in Martins version. Weird that the free version removes that.
- changed the window functions, so they automatically zero fill, when the Window-size is smaller than the FFT Size
- flipped the twiddle factor in FFT code
- converted Martins complex multiplication to assembler
- changed the Graph Symetry Ruby code to real symetry
- fixed delay compensation

The Ruby code for the symetrie was a quick fix for my previous tests. I had to keep the DC offset for every window, that doesn't remove it completely. So the first bin had to be one, no matter what the others were set to. In Martins filter code this isn't necessary, because it removes DC anyway.
Changing the twiddle factor was not a big deal. I just had to change a jump instruction.
The windows are now calculated from 0 to window size minus one. If the window size is smaller, the remaining samples are set to zero. This is now a universal solution, so we don't need new windows for different sizes.

@Martin:
Thanks for your help, it works perfectly now. I've changed the delay compensation and the error is gone. The filter drawing is just a little bit washed at the moment. No matter how big your FFT Size is, it always stretches the filter bins. That needs some little tweaks, so that we can do very exact filtering.

[digitalwhitebyte]

I guess now I finally begin to understand a little of FFT world.
I am happy about this, thanks gentlemen.