CODEWITHSUNDEEP
javac++fftconvolution
TheWinterSnow
TheWinterSnow

Reputation: 175

Properly manipulating data with FFT based convolution

I have been reading the DSP Guide for what seems like a good 3 years now. Only until recently getting comfortable enough with programming did I decide to start experimenting around with FFT based convolution, 1D to be exact, one real in, a complex out.

I stumbled across some code for getting the FFT and IFFT and got it to work, I am getting a correct DFT in the complex frequency domain which after a little bit of bit manipulation (separating the complex array back into two separate real and imaginary arrays) and running it back through the IFFT followed by again more bit manipulation yeilds the original input like expected.

Now maybe I have the concept of Convolution all wrong but simply multiplying like elements of the complex arrays and then running the result back through the IFFT is giving bogus numbers. To test I am simply making a ramping kernel, and a dirac delta function as the input and plugging the result into the IFFT, the code is not giving the original kernel as expected.

public void convolution(double [] xReal, double [] xImag,
                        double [] hReal, double [] hImag){

    for (int i = 0; i < n; i++){
        xReal[i] *= hReal[i];
        xImag[i] *= hImag[i];
    }
}

My question is: is this code for multiplying the elements of the complex DFT correct.

I have been looking for simple convolution code or simply the math behind it but have had no such luck. Everything I have found has just been "multiplication in the frequency domain equals convolution in the time domain".

Upvotes: 2

Views: 575

Answers (1)

hotpaw2
hotpaw2

Reputation: 70673

Multiplication in the frequency domain does a circular convolution, not a straight linear convolution, unless you zero pad out the FFTs and IFFT to longer than the sum of the length of the time domain signal and the full time domain impulse response. (Zero-pad, because a circular wrap/around of all zeros is the same as no wrap around).

Also, for convolution, you need to multiply by the transform (FFT) of the zero-padded impulse response (its frequency response), not the impulse response itself.

Also, the multiplication has to be a complex multiply, not a multiply of just the 2 separated component vectors.

Upvotes: 1

Related Questions