How to Resample Audio Using FFT or DFT

Question

I'm down sampling voice audio by first performing an FFT, then only taking the parts of the result that I need, and then performing an inverse FFT. However, it's only working properly when I'm using frequencies that are both power of two, say down-sampling from 32768 to 8192. I perform an FFT on the 32k data, discard the top 3/4 of the data and then perform an inverse FFT on the remaining 1/4.

However, whenever I try to do this with data that doesn't line up properly one of two things happen: The math library I'm (Aforge.Math) using throws a fit, because my samples are not a power of two. If I try to zero-pad the samples so they become power of twos, it get gibberish out on the other end. I also tried to use a DFT instead, but it ends up being insanely slow (this needs to be done in real time).

How would I go about to zero pad the FFT data properly, both on the initial FFT and the inverse FFT at the end? Assuming I have a sample at 44.1khz that needs to get to 16khz, I currently try something like this, the sample being 1000 in size.

1. Pad input data to 1024 at the end
2. Perform FFT
3. Read the first 512 items into an array (I only need the first 362, but need ^2)
4. Perform inverse FFT
5. Read the first 362 items into the audio play buffer

From this, i get garbage out at the end. Doing the same thing but without having to pad at step 1 and 3 due to the samples already being ^2, gives a correct result.

Answer 1

The first step is to verify that both your starting sample rate and your target sample rate are rational numbers. Since they are integers they are automatically rational numbers. If one of them wasn't a rational number it would still be possible to make the sample rate change, but it is a much different process and more difficult.

The next step is to factor the two sample rates. The starting sample rate, in this case, is 44100, which factors to $2^2*3^2*5^2*7^2$. The target sample rate, 16000, factors to $2^7*5^3$. Thus, to convert from the starting sample rate to the target rate we must decimate by $3^2*7^2$ and interpolate by $2^5*5$.

The previous steps have to be done no matter how you want to resample the data. Now let's talk about how to do it with FFT's. The trick to resampling with FFT's is to pick FFT lengths that make everything work out nicely. That means picking an FFT length that is a multiple of the decimation rate (441, in this case). For the sake of the example, let's pick an FFT length of 441, though we could have picked 882, or 1323, or any other positive multiple of 441.

To understand how this works it helps to visualize it. You start out with an audio signal that looks, in the frequency domain, something like the figure below.

When you're done with your processing you want to decrease the sample rate to 16 kHz, but you want as little distortion as possible. In other words, you simply want to keep everything from the picture above from -8 kHz to +8 kHz and drop everything else. That results in the picture below.

Please note that the sample rates are not to scale, they are just there to illustrate the concepts.

The beauty of picking an FFT length that is a multiple of the decimation factor is that you can resample simply by dropping portions of the FFT result, and then inverse FFT what is left. In the case of our example you FFT 441 samples of data, which gets you 441 complex samples in the frequency domain. We want to decimate by 441 and interpolate by 160 ($2^5*5$), so we keep the 160 samples that represent the frequencies from -8 kHz to +8 kHz. We then inverse FFT those samples and presto! You have 160 time domain samples that are sampled at 16 kHz.

As you might suspect, there are a couple of potential problems. I will go through each one and explain how you can overcome them.

1. What do you do if your data is not a nice multiple of the decimation factor? You can easily overcome this by padding the end of your data with enough zeros to make it a multiple of the decimation factor. The data is padded BEFORE it is FFT'ed.

2. Even though the method I explained is very simple, it is also non-ideal in that it can introduce ringing and other nasty artifacts in the time domain. You can avoid that by filtering the frequency domain data before dropping the high frequency data. You do this by FFT'ing your filter of length $l$, padding your data (before FFT'ing it) with at least $l-1$ zeros (please note that the number of data samples and the number of padding samples must BOTH be a positive multiple of the decimation factor- you can increase the padding length to meet this constraint), FFT'ing the padded data, multiplying the frequency domain data and filter, and then aliasing the high frequency (> 8 kHz) results down into the low frequency (< 8 kHz) results before dropping the high frequency results. Unfortunately, since filtering in the frequency domain is a big topic in its own right, I won't be able to go into more detail in this answer. I will say, though, that if you filter and are processing the data in more than one chunk, you will need to implement Overlap-and-Add or Overlap-and-Save to make the filtering continuous.

I hope this helps.

EDIT: The difference between the starting number of frequency domain samples and the target number of frequency domain samples needs to be even so that you can remove the same number of samples from the positive side of the results as the negative side of the results. In the case of our example, the starting number of samples was the decimation rate, or 441, and the target number of samples was the interpolation rate, or 160. The difference is 279, which is not even. The solution is to double the FFT length to 882, which causes the target number of samples to also double to 320. Now the difference is even, and you can drop the appropriate frequency domain samples with no problems.

Answer 2

While the above answer is really complete:

Here is the gist of it:

1. to downsample a signal it needs to be a whole number. Before the down sampling of a signal, you need to FILTER the signal.
2. you can acheive rational number downsampling by Up-sampling/interpolating the signal first.
3. Upsampling is simply inserting zeros and then FILTERING the signal.
4. so to achieve 3/4 sample rate. upsample the signal by inserting 4 zeros between every signal sample. Apply a filter. Then FILTER the signal and delete every 3 out of every 4 signal samples.

Details on this:

http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE523_files/Ch_14_1%20Subband%20Intro%20&%20Multirate%20(PPT).pdf

Also: unless it is absolutely necessary DO NOT computer the FFT to then compute the IFFT. Its an incredibly slow process and its considered inappropriate for most signal processing tasks. the FFT is usually used for analyzing a problem or applying signal processing only in the frequency domain.

Answer 3

As Bjorn Roche was saying, using FFT for this would be terribly inneficient. But here it goes in a very very simple fashion using the method of upsample filter and downsample in the frequency domain.

1 - Take desired vector signal of length N.

2 - Perform N point FFT.

3 - Zero padd the FFT with 160*N zeros at the middle of the FFT vector.

4 - Perform IFFT

5 - Select one out of 441 samples discarding the other 440.

You will be left with a vector of length N*160/441, that will be your resampled signal.

As you can see you are doing a lot of pointless computations, because most of the results will be then thrown away. But if you have access to the code performing the FFT, you could actually tweak it a little bit so it only calculates the IFFT results that you will end up with and not the ones you will throw away.

Hope it helps.