Thread: FFT and convolution

I am posting this here because it is more algorithmically related than C++ related (especially since I am not writing this program in C++ anyways). I am working on this project right now in which I am using fast fourier transforms and convolving two audio files together into one.

For example, I have an audio file of a person speaking, and then I have a filter audio file from a parking garage, and I convolve them together to make it sound like the person is speaking inside of a parking garage.

I am inputting the audio signals and then using the FFT on both the signal and the filter. From there I need to convolve them, and then do an inverse-FFT to get back to an audio signal, and then write that to a file.

The part that I am getting held up on is the actual convolving (the multiplying of the two signals together).

Basically it is like polynomial multiplication:

Here is some pseudo code:

Code:

Array audio_file = loadMusicSignalFile(file one);
Array filter_file = loadMusicSignalFile(file two);

A = FFT(audio_file);
B = FFT(filter_file);

Array C;

for each element of A:
	C[x] = A[x] * B[x];

final_audio = inverse_FFT ( C );

Now...here is my question: how does this work if A and B are different sizes? Obviously A (the audio file) could be something like 10 seconds long...but the filter file only 2 or 3 seconds...and therefore the arrays of data will be of different length.

Should I just pad the filter array with zeros, or is there a better way to do it, such as repeating the filter until it is the same length as the audio file? There is also the issue of the fact that in order to properly do an FFT, the array passed to the FFT needs to have a length of a power of 2...but that isn't difficult. In order to do that, I know that I can just pad with zeros. I just wasn't sure how I should properly make A and B of equal length.

Any suggestions?

You need to pad the filter array with zeros, as you suggested. If the filter is much shorter than the audio file, you shouldn't use FFT. Regular convolution will be faster. I hope this helps.

Originally Posted by DavidP

INow...here is my question: how does this work if A and B are different sizes? Obviously A (the audio file) could be something like 10 seconds long...but the filter file only 2 or 3 seconds...and therefore the arrays of data will be of different length.

Make the arrays the same length by padding the filter signal with zeros before taking the FFT. Do NOT repeat the filter, since this will introduce frequencies which don't actually exist. In addition, you should apply a window of some kind (look up "Blackman window" on Google) to the filter to avoid the edge effect which occurs when the end of the padding zeros wraps around to the beginning of the filter again -- that introduces spurious frequencies as well.

EDIT EDIT: You also need to take into account the time lag caused by the filter itself. This means that if signal A is of length N1, and signal B is of length N2, then BOTH signals should be zero-padded to a length of N1+N2-1. You have to do this to avoid circular convolution which would cause the trailing edge of the result signal to overlap the leading edge, which is a defect. For a deeper explanation see the DSP Book (http://www.dspguide.com) (this is an artifact of the FFT convolution method -- in regular convolution, if your output array is not large enough the result simply gets truncated instead of wrapping over the front of the result signal)

Depending on the size of your filter, it may be less expensive to do a "normal" convolution instead of an FFT convolution. It also might be cheaper to use a windowed approach with a smaller FFT, combining the intermediate results using a method such as overlap-add. I've done all this before so if you want more info just ask.

EDIT: Sorry Sang-drax, I don't usually read threads and it turns out I just echoed you

It's also near two years old before "me too" bumped it.

Originally Posted by Salem

It's also near two years old before "me too" bumped it.

This bugs me. If we're going to be hostile toward thread bumping why not just close the threads after a certain period of time? I'm not going to carefully scan the date and time on each thread I see just because 0.5% of the time it's a zombie thread.

> So? What difference does it make?
Well it separates those who've read the rules, from those who haven't
C Board - Announcements in Forum : General Discussions

2. Please follow the forum structure when posting. Post threads on the board best suited for the topic. Please do not cross post (i.e. post the same question on multiple boards). Do not bump threads. (Bumping: Posting messages on threads to move them up the list or to post on a thread that has been inactive for two weeks or longer).

Or it separates those that can tell the difference between weeks and years.