Convolution Reverb

[KG_is_back]

I'm starting a new project and it'll be a quite big one. A zero latency convolution reverb using combination of time-based FIR filter and a cascade of FFT based FIR filters. Here's the idea.

impulse itself will be cut into a number of 64sample long bins. First bin will be convolved using time domain FIR filter, which has zero latency (to leave one bin time to load buffer for FFT).
Rest of the bins will be FFTied offline.
As the t-d FIR filter is working buffer off stream FFT is filling. At 64th sample the FFT of signal is calculated and multiplied with (already precomputed) FT of 2nd impulse bin. Also the FFT of the signal is stored in memory (and at 128th sample multiplied with 3rd impulse bin and so on).
Multiplications of all stored signal FFTs and impulse FTs are ten summed and iFFT of double size is preformed (to prevent circular convolution). First half of the computed iFFT is then send to output and summed with second half of previous iFFT and with the output of time-domain FIR filter.

This algorithm should be extremely efficient because there are only one 64sample ong FIR filter + 64sample FFT + 128sample iFFT + (impulse length -64) multiplications and summations.

I will need a lot of help with this, cos' except for the time domain FIR filter, which will run in parallel everything else must be in one Assembly block. It will also need some adjustments to the FFT procedure. It there anyone interested in collaboration on this project?

[tester]

I would ask MyCo and steph_tsf, and Trog. They seem to go beyond any boundaries...

[MyCo]

FIR: viewtopic.php?f=3&t=1487&p=6393
FFT/iFFT: viewtopic.php?f=4&t=1510

The all in one block idea is not so good... have a look at the final FFT code in the project above. It's massive! And you'll have this twice, and the FIR as well... there is no chance to get this managed. After some days you'll lose the overview completely. The FFT code in the final version took weeks!!!

[KG_is_back]

would the FFT code simplify if it is made fixed size?
while making benefit of FFT and iFFT i don't really have to care what's inside them. Sure, the code will get very very large, but as long as we don't have the memin/memout working, there's no way to split the parts.

[trogluddite]

as long as we don't have the memin/memout working, there's no way to split the parts.

As long as the incoming array isn't changing too fast, there may be a way...

You can transform an array of floats into a Ruby Frame object - normally made by sampling a stream, but just as easily done within the Ruby code. You can also use the "Frame.data" method to obtain the Frame's memory address - for example when passing it as a pointer to a DLL.
So, I thought, can we pass this address into an assembly block, and thus gain access to the float data?

And it looks as if it really could work...

Array to mem experiment.fsm

(2.34 KiB) Downloaded 1597 times

This is just my first experiment, and I haven't crashed FS with it yet - though I haven't tried writing to the Frame from asm yet (which would presumably be more 'dangerous').
The Ruby code is written so that the Frame object is only constructed once and then re-used, which should mean that its address will not change for the lifetime of the schematic - so could probably be re-built in the asm once at startup (you'll see what I mean by 're-building' the address when you see the schematic).

Lots of stability testing required yet, I think - I've not put anything together that's useful enough to try exporting thus far. But it looks promising as a way to pass large amounts of data into assembly without a ridiculously large number of discrete inputs, or 'serialising' the data.

[KG_is_back]

I've just found out one little error... the FFT has to be double size too- the input second half padded with zeros.

However maybe the data serialization is not a bad thing. Without the serialization following calculations must be preformed at every 64th sample:
128sample FFT
multiplication and summation of complex numbers (the output of stream FFT and the FFTs of the impulse) of [imuplse length] times
128sample iFFT.

If we serialize the output of FFT the multiplications and summations can be preformed sample by sample rather than calculated all every 64th sample. that would smooth out the CPU response at cost of higher overall CPU (because that would add another 64bit latency to the FFT convolution - the time domain FIR will have to be 128sample)

Trog, could you adjust the FFT so it will load 64samples, then preforms 128sample long FFT (with second half of the input buffer empty as only 64samples are loaded) and outputs the spectrum as serialized data? It will need 2real and 2imaginary outputs cos it will have to put out 128complex numbers per 64samples...
And adjust iFFT that it loads the input in similar way as the FFT outputs them. In this case the output of iFFT has to be serialized so the one output will be data of the first half of output buffer and second will be data of the second half of output buffer (they will be later delayed by 64samples and added to output).

If this is done then the precomputation of the loaded impulse and the multiplication of the spectra is relatively simple...

[MyCo]

If we serialize the output of FFT the multiplications and summations can be preformed sample by sample rather than calculated all every 64th sample. that would smooth out the CPU response at cost of higher overall CPU (because that would add another 64bit latency to the FFT convolution - the time domain FIR will have to be 128sample)

That's not possible, FFT calculates over complete buffer, not only adjacent samples. Also it's a recusive task, so when it has a result, it calculates the next set from that. On CPU it doesn't matter at all, the calculation / second stays the same. Also it looks like FS processes each sample when its time comes, in reality a block comes into FS, it runs through each sample, and then idles. That's how all audio software works.

Trog, could you adjust the FFT so it will load 64samples, then preforms 128sample long FFT (with second half of the input buffer empty as only 64samples are loaded) and outputs the spectrum as serialized data?

That's actually what the final stream FFT version does. There are 2 FFTs/iFFTs running in parallel. The second pair is shifted by 1/2 Buffer size. The window function is only applied to the first half of each buffer, the other half is zeroed. Can't remember why we've done that. I think it's because of the FIR that's in there.

FIY put your Impulse Response in the "Spectrum Draw (v2)" part of the final stream-FFT version (the one from martin), and you're done.

[Katheflowstone]

Hi everybody!!...please i need help....how can i make a convolution of two signals? ...flowstone not have convolution how i make it!!

[martinvicanek]

Wow, KG_is_back, that's quite a big project indeed! As MyCo points out, an STFFT implementation alone has been a considerable effort in FS. I believe the original idea of a latency free FFT based convolver goes back to Gardner. He is discussing uniform vs. non-uniform partitioning. An excellent paper, have a look.

[KG_is_back]

It seems, the Trog's array to memory is not working.
Here is the first version - not working...
http://www.mediafire.com/?eou8vcmlzfude7w