FFT and convolution

This is a discussion on FFT and convolution within the General Discussions forums, part of the Community Boards category; I am posting this here because it is more algorithmically related than C++ related (especially since I am not writing ...

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738

    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?
    My Website

    "Circular logic is good because it is."

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    bvr
    bvr is offline
    Registered User
    Join Date
    Jul 2009
    Posts
    2
    That's the exact same project i'm working on right now! And i'm stuck at the same problem!

    How did you do it? Please tell me that you finished it and can help me out.. PLEASE!

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by DavidP View Post
    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
    Last edited by brewbuck; 07-02-2009 at 09:54 AM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    It's also near two years old before "me too" bumped it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by Salem View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    bvr
    bvr is offline
    Registered User
    Join Date
    Jul 2009
    Posts
    2
    @brewbuck

    Thank you! That was actually very helpful..


    Quote Originally Posted by Salem View Post
    It's also near two years old before "me too" bumped it.
    So? What difference does it make?

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21