Support

If you have a problem or need to report a bug please email : support@dsprobotics.com

There are 3 sections to this support area:

DOWNLOADS: access to product manuals, support files and drivers

HELP & INFORMATION: tutorials and example files for learning or finding pre-made modules for your projects

USER FORUMS: meet with other users and exchange ideas, you can also get help and assistance here

Stream FFT and iFFT

DSP related issues, mathematics, processing and techniques

Re: Stream FFT and iFFT

Postby MyCo » Thu Jun 27, 2013 8:50 pm

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.
Attachments
Stream FFT v8 (trogluddite, MyCo).fsm
(278.88 KiB) Downloaded 684 times
User avatar
MyCo
 
Posts: 761
Joined: Tue Jul 13, 2010 12:33 pm
Location: Germany

Re: Stream FFT and iFFT

Postby martinvicanek » Sat Jun 29, 2013 4:21 pm

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. :D
User avatar
martinvicanek
 
Posts: 1028
Joined: Sat Jun 22, 2013 8:28 pm

Re: Stream FFT and iFFT

Postby MyCo » Mon Jul 01, 2013 6:15 pm

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?
Attachments
Stream FFT v9 (trogluddite, MyCo).fsm
(324.22 KiB) Downloaded 634 times
User avatar
MyCo
 
Posts: 761
Joined: Tue Jul 13, 2010 12:33 pm
Location: Germany

Re: Stream FFT and iFFT

Postby martinvicanek » Tue Jul 02, 2013 5:47 pm

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.
Attachments
FFT_convolution.png
FFT_convolution.png (102.14 KiB) Viewed 21331 times
User avatar
martinvicanek
 
Posts: 1028
Joined: Sat Jun 22, 2013 8:28 pm

Re: Stream FFT and iFFT

Postby MyCo » Tue Jul 02, 2013 6:37 pm

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).
User avatar
MyCo
 
Posts: 761
Joined: Tue Jul 13, 2010 12:33 pm
Location: Germany

Re: Stream FFT and iFFT

Postby martinvicanek » Wed Jul 03, 2013 10:03 pm

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! :)
Attachments
Stream FFT v10 (trogluddite, MyCo, MV).fsm
Basic Filter Implementation with FFT
(241.5 KiB) Downloaded 646 times
User avatar
martinvicanek
 
Posts: 1028
Joined: Sat Jun 22, 2013 8:28 pm

Re: Stream FFT and iFFT

Postby MyCo » Thu Jul 04, 2013 6:44 am

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 :mrgreen:

EDIT2: Why are all modules in your schematic unsynchronized?
User avatar
MyCo
 
Posts: 761
Joined: Tue Jul 13, 2010 12:33 pm
Location: Germany

Re: Stream FFT and iFFT

Postby martinvicanek » Thu Jul 04, 2013 7:28 am

MyCo wrote: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)


MyCo wrote:EDIT: forget that with the twiddle factor, it's indeed wrong. Damn... but how do I fix that in the full blown ASM Code :mrgreen:
Not necessarily wrong, only inconsistent with green. Easy remedy: exchange FFT for IFFT and vice versa (apart from normalization maybe).
MyCo wrote:EDIT2: Why are all modules in your schematic unsynchronized?
Dunno, maybe because I'm still on the free version? :oops:
User avatar
martinvicanek
 
Posts: 1028
Joined: Sat Jun 22, 2013 8:28 pm

Re: Stream FFT and iFFT

Postby MyCo » Thu Jul 04, 2013 8:42 am

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.
Attachments
Stream FFT v11 (trogluddite, MyCo, MV).fsm
(328.43 KiB) Downloaded 675 times
User avatar
MyCo
 
Posts: 761
Joined: Tue Jul 13, 2010 12:33 pm
Location: Germany

Re: Stream FFT and iFFT

Postby digitalwhitebyte » Thu Jul 04, 2013 4:06 pm

I guess now I finally begin to understand a little of FFT world.
I am happy about this, thanks gentlemen.
User avatar
digitalwhitebyte
 
Posts: 108
Joined: Sat Jul 31, 2010 10:20 am

PreviousNext

Return to DSP

Who is online

Users browsing this forum: steph_tsf and 3 guests