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 premade 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
Re: Stream FFT and iFFT
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.
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

MyCo  Posts: 761
 Joined: Tue Jul 13, 2010 12:33 pm
 Location: Germany
Re: Stream FFT and iFFT
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 overlapadding 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.
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 overlapadding 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.

martinvicanek  Posts: 1028
 Joined: Sat Jun 22, 2013 8:28 pm
Re: Stream FFT and iFFT
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?
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

MyCo  Posts: 761
 Joined: Tue Jul 13, 2010 12:33 pm
 Location: Germany
Re: Stream FFT and iFFT
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 (102.14 KiB) Viewed 21331 times

martinvicanek  Posts: 1028
 Joined: Sat Jun 22, 2013 8:28 pm
Re: Stream FFT and iFFT
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).

MyCo  Posts: 761
 Joined: Tue Jul 13, 2010 12:33 pm
 Location: Germany
Re: Stream FFT and iFFT
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

martinvicanek  Posts: 1028
 Joined: Sat Jun 22, 2013 8:28 pm
Re: Stream FFT and iFFT
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?
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?

MyCo  Posts: 761
 Joined: Tue Jul 13, 2010 12:33 pm
 Location: Germany
Re: Stream FFT and iFFT
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.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.
EDIT: I don't quite understand the details of this in the Spectrum Draw module:
 Code: Select all
output([1]+@in[0..len1] + @in[0..len2].reverse)
Why not simply
 Code: Select all
output(@in[0..len1] + @in[0..len1].reverse)
Not necessarily wrong, only inconsistent with green. Easy remedy: exchange FFT for IFFT and vice versa (apart from normalization maybe).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
Dunno, maybe because I'm still on the free version?MyCo wrote:EDIT2: Why are all modules in your schematic unsynchronized?

martinvicanek  Posts: 1028
 Joined: Sat Jun 22, 2013 8:28 pm
Re: Stream FFT and iFFT
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 Windowsize 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.
 fixed, the synchronization in Martins version. Weird that the free version removes that.
 changed the window functions, so they automatically zero fill, when the Windowsize 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

MyCo  Posts: 761
 Joined: Tue Jul 13, 2010 12:33 pm
 Location: Germany
Re: Stream FFT and iFFT
I guess now I finally begin to understand a little of FFT world.
I am happy about this, thanks gentlemen.
I am happy about this, thanks gentlemen.

digitalwhitebyte  Posts: 108
 Joined: Sat Jul 31, 2010 10:20 am
Who is online
Users browsing this forum: steph_tsf and 3 guests