FFT and convolution


#1

I am attempting to make a plugin that applies an impulse response to an incoming signal. A few questions have arisen.

  1. I initialize all of the FFTs outside of the processBlock method. Is the FFT module fast enough to perform a realOnlyForwardTransformation inside of the processBlock method?

  2. Once I have obtained the two transformations, can I just loop through them and multiply all the elements? Or do I have to do a conversion to Complex and then work with those?

  3. Must I perform an inverse transformation on the result of the multiplication?

Thanks!


#2

[quote=“mUmbler, post:1, topic:21220”]

  1. I initialize all of the FFTs outside of the processBlock method. Is the FFT module fast enough to perform a realOnlyForwardTransformation inside of the processBlock method?
    [/quote]Yes, depending on the length of your impulse, of course.

[quote=“mUmbler, post:1, topic:21220”]
2) Once I have obtained the two transformations, can I just loop through them and multiply all the elements? Or do I have to do a conversion to Complex and then work with those?
[/quote]They are complex numbers, you need to perform complex multiplication

[quote=“mUmbler, post:1, topic:21220”]
3) Must I perform an inverse transformation on the result of the multiplication?
[/quote]Yes, and remember your transform size will be impulse length + block length. So you need to zero pad your transforms to that size.


#3

I am currently looking into doing the same.

I can recommend the following PHD thesis, which seems to give quite a good overview of the possible algorithms:

Also note that forum member “HiFi-LoFi” has made an OpenSource Convolution plugin. See this thread:


It is GPL though, unfortunately. Therefore I cannot use it.


#4

Because you’re using the real-transorm, might be worth to mention that JUCE’s implementation is at least two times slower than other FFT libraries’ implementations of it, as it simply converts the reals to complex numbers and performs the full complex-fft.


#5

I want to add:

I just fond out there is an open source convolution engine, which is not GPL. In other words, you can use it freely even in commercial plugins. Its part of WDL from Cockos:
http://www.cockos.com/wdl/

Other Jucers seeem to be using it successfully. See also the following thread:


#6

@Mayae
Thank you very much! I am in the process of applying your suggestions.

@Alatar
Thank you for the paper. I don’t think Klang will help, this is for my senior project so I wish to figure this out for myself. I might have to check that out if I cannot figure out how to efficiently use the built in FFT module.

@yairadix
I was thinking of maybe using FFTW, which I may have to resort to using.


#7

@Mayae

Quick question: When you say I must zero pad the transformations, do you mean that I must zero pad the results of the transformations before I do the complex multiplication and inverse transformation, or that I must zero pad the arrays that I pass into the transformations?


#8

Say your impulse response is 1000 samples long (K), and your block size is 1000 (M). The result of the convolution is an array of size N=K+M-1 = 1999 samples, ie. your must zero-pad your input signals to size N, otherwise you will have circular convolution.

In this case, you would probably round N to the next power of two for FFT effeciency (N = 2048).


#9

Would I have to zero pad the impulse response to N as well?

Also, I thought the sample buffer must be double the length for the FFT. So should it be 2*N?

One final question: should the individual FFTs be initialized to log2(N), or log2 of their respective sizes?


#10

[quote=“mUmbler, post:9, topic:21220”]
Would I have to zero pad the impulse response to N as well?
[/quote]Yes.

[quote=“mUmbler, post:9, topic:21220”]
Also, I thought the sample buffer must be double the length for the FFT. So should it be 2N?
[/quote]The sample buffer should be N complex numbers (which requires 2
N normal floats, but it is really easier to think of in terms of complex entities).

[quote=“mUmbler, post:9, topic:21220”]
One final question: should the individual FFTs be initialized to log2(N), or log2 of their respective sizes?
[/quote]All of your operations in the frequency domain require transforms of equal size (N). It doesn’t make sense to perform convolution on differently-sized transforms… The complex sinusoids don’t match up.


#11

Hi,

I just changed the license of FFTConvolver from GPL to MIT, so it should be working now for you as far as licensing is concerned.

Regards, Uli