Hello,

I had quite a few questions I was hoping someone could answer regarding the use of FFT's when convolving a digital signal:

1. When convolving some digital signal A by some impulse response B, do we get the same convolved digital signal, whether we use an FFT or not?

In other words, if we performed a binary comparison of the convovled digital signal produced when using an FFT to convolve A by B, would it match the convolved digital signal produced when convolving A by B without the use of an FFT?

2. Though I'm fairly new to FFT's, an FFT was described to me as a digital signal transformation which converts a digital signal into the frequencies that make it up. By doing this, it allows us to perform digital signal operations on the frequencies that make up a digital signal, opposed to each individual sample of a digital signal operation.

Assuming the digital signal is made up of fewer frequencies than samples, using an FFT to perform some DSP operation will be far more efficient than when not using an FFT.

Is my understanding of an FFT correct?

3. Regarding parallelization, once a digital signal has been converted into an FFT, is it safe to assume that some DSP operation performed on each frequency (for example, convolution) can be performed in parallel?

In other words, if a digital signal consisting of the C4 major chord was transformed into an FFT, consisting of the following 3 frequencies:

C4 @ 261.63 Hz
E4 @ 329.63 Hz
G4 @ 392.00 Hz

Is it safe to assume that if I wished to convolve the C major chord by my impulse response B, that I could split my computational workload among the following 3 threads:

Thread 1 convolves C4 by impulse response B
Thread 2 convolves E4 by impulse response B
Thread 3 convolves G4 by impulse response B

Or is it instead the case that operations performed on an FFT can only be performed serially (e.g. not in parallel)?

4. Are there situations when using an FFT is not beneficial?

For instance, if some digital signal consists of only 10 samples, but 10 or more frequencies, would:

1. Converting the digital signal to an FFT
2. Performing some DSP operation (e.g. convolution) on each frequency.
3. Converting the FFT back to a digital signal

...be slower than simply performing convolution on each sample?

If so, does this sort of situation tend to happen a lot (with random digital signals), or is it rare?

5. Are certain DSP operations actually more computationally intensive when performed on frequency data, opposed to sample data?

For example, is performing an operation such as convolution more computationally difficult / intensive when performed on frequency data opposed to sample data?

6. Is there some average / general-case efficiency speedup of using an FFT as opposed to not in the DSP literature?

In other words, are using FFT's to perform some DSP operation considered to be (on average) 50% more efficient than when not using an FFT (or is this primarily dependent on the makeup of the digital signal - e.g. number of samples vs frequencies which make up a particular digital signal)?

7. Would it be possible to create a compression algorithm to compress digital signals into an FFT (which would then be converted back to a digital signal during the decoding phase)?

8. If it's possible to compress / represent a digital signal as an FFT, is the compression / representation lossy or lossless (or is this something that is primarily implementation dependent)?

If this is implementation dependent, is it safe to assume that there will always be some compression advantage to converting a digital signal into an FFT (over using something like variable bit-rate audio compression)?

Or is the compression advantage only worth it, if during the FFT transformation, we omit or drop certain frequency data (for example, dropping frequencies that can't be heard or picked up by most consumer speakers / headphones)?

9. Assuming a digital signal can be converted into an FFT, will the compression ratio (e.g. the amount of compression) of a digital signal via an FFT depend simply on the amount of different frequencies that makeup a digital signal, or will the number of times that frequency is present in the digital signal also be taken into account?

In other words, will the FFT for the following digital signal (consisting of the following 3 frequencies: A, B and C):

Figure 1

...be the same size as the following digital signal (consisting for the same 3 frequencies: A, B and C)?

Figure 2

10. If the answer to question is 9 is no, assuming the extra signal data from Figure 1 consists of 1,000 samples of data, will the the FFT from Figure 1 be (some constant * 1000) greater in size than the FFT for Figure 2, or will the FFT for Figure 1 be much smaller in size?

Thank you,
Nelson

Wow - that's a lot of questions.

I'm not going to try to answer them all - I would suggest you read any of the good DSP text books for that. But I'll try to point you in the right direction.

A "digital signal" can be represented in the time domain or in the frequency domain - this is similar to a vector in three dimensions being represented using different triples of orthogonal basis vectors. The interesting thing is that some operations are more efficient to carry out in the time domain and some in the frequency domain. That is why we need an efficient method of going back and forth between the domains - which is what the FFT gives us.

Filtering entails a convolution in the time domain (which is N multiplies and adds for each sample output, N^2 for N samples) but simple multiplications in the frequency domain (N multiplies for N outputs). In theory if you do an FFT + M multiplications + iFFT you will get the same answer - but don't expect bit-exactness unless you are very careful.

When you say that C4 is 261 Hz you are talking about the fundamental frequency. On any real instrument there will be harmonics (and possibly overtones that are not harmonic - as in string instruments). So there will be many non-zero bins. That is not why you save in computation! There are methods for saving in computation when it is known that there are only a few frequencies (Goertsel, Pisarenko, ...) but FFT is not one of them.

Indeed there are plenty of situations when converting to the frequency domain is not a good idea. For example - a simple gain is N multiplies for N samples in either domain - so there is no reason for 2 N log N conversions if you have the signal in the time domain. Similarly, a N^2 convolution in the frequency domain (which can be useful!) is N multiplications in the time domain! 

There are indeed cases where specification in the frequency domain involves fewer bits than in the time domain, and vice versa. And there are other transforms that may be even better for specific signals. The minimum involves something called the KLT.

As I said - you asked a lot and it would require a large part of a textbook or a basic course on signals and systems to answer all of your questions.

Y(J)S

as an example of fft based convolution targeting equivalent sample values(bit-true) here is what I will do. There is some rounding issue but you can remove it.

n = 100;

m = 200;

a = randn(1,n);

b = randn(1,m);

y1 = conv(a,b);

y2 = ifft(fft(a,n+m-1).* fft(b,n+m-1));

plot(y1); hold

plot(real(y2),'r--')

Hello Y(J)S,

You are correct that I did ask a lot of question, but I was hoping I could use an FFT as an optimization to an algorithm I was working on.

Unfortunately the following quotes:

"In theory if you do an FFT + M multiplications + iFFT you will get the same answer - but don't expect bit-exactness unless you are very careful."

...and:

"There are methods for saving in computation when it is known that there are only a few frequencies (Goertsel, Pisarenko, ...) but FFT is not one of them."

...lead me to believe that an FFT won't be of any real help to my algorithm.

Thank you very much for the detailed response, as it helped steer me away from going down a development path which would be of little benefit.

Regards,
Nelson