Example Digital Convolution in the Time Domain is Computationally Expensive

Looking for a succinct example showing convolution processing (in the time
domain) is notoriously computationally intensive; e.g., the typical
reverberation time of a room is approximately 0.3 seconds which
corresponds to 2400 samples, i.e., taps (filter coefficients), for an 8
kHz sampled sound.  Because the sound is sampled at 8 kHz, the "delay
steps" are each of length 1/8000 (0.000125 seconds).  Assuming that the
sampled sound and the impulse response have a length of 0.3 seconds, the
number of samples is equal to 2400 (0.3 seconds/0.000125 seconds).
A more complete example (from an anonymous source at the University of
Miami) showing that time-domain convolution processing is notoriously
computationally intensive follows: "For typical audio signals, three
second impulse response sampled at 44.1 kHz requires around 2 * (3 *
44,100)^2 or 35 billion computations to convolve with the same length
input."
I can understand most of where the 35 billion number comes from. It comes
from this:  Delay steps for 44.1 kHz signal is equal to 2.675737 E-5
seconds.  3.0 seconds / 2.675737 E-5 seconds = 132300 increments. 
2*(132300^2) = 2 * (17,503,290,000) = 35,006,580,000. 
What I don't understand are the purposes of the “2” and the “^2”
expressions.  I suppose that the “^2” expression represents each
convolution operation (from convolving the impulse response with the
sound).  Trying to figure out the purpose of the “2” i.e., the “2”
multiplied with “(132300)”.  A Professor Emeritus at Penn State
recently suggested that the “2” might be needed to evaluate whether or
not each convolution was positive or negative; but he wasn’t sure. 



---------------------------------------
Posted through http://www.DSPRelated.com

On 07.01.16 18.06, johnnmonroe wrote:
> "For typical audio signals, three
> second impulse response sampled at 44.1 kHz requires around 2 * (3 *
> 44,100)^2 or 35 billion computations to convolve with the same length
> input."

> What I don't understand are the purposes of the “2” and the “^2”
> expressions.  I suppose that the “^2” expression represents each
> convolution operation (from convolving the impulse response with the
> sound).

You need to multiply 3 * 44100 samples of the FIR filter with the same 
number of input samples to get exactly one sample of output. For 3 
seconds of output you need 3 * 44100 times as much operations.

More useful in fact is the number of computations per second, i.e.
2 * 3 * 44100� (per channel) ~ 1.2 Gflops.

But no one who is not off one's head would implement a 130k FIR filter 
in the time domain. With FFT convolution even a raspberry pi 1 is able 
to do the job. If you already have several seconds latency the 
additional latency of the FFT convolution does not count.


Marcel

>On 07.01.16 18.06, johnnmonroe wrote:
>> "For typical audio signals, three
>> second impulse response sampled at 44.1 kHz requires around 2 * (3 *
>> 44,100)^2 or 35 billion computations to convolve with the same length
>> input."
>
>> What I don't understand are the purposes of the “2” and the
“^2”
>> expressions.  I suppose that the “^2” expression represents
each
>> convolution operation (from convolving the impulse response with the
>> sound).
>
>You need to multiply 3 * 44100 samples of the FIR filter with the same 
>number of input samples to get exactly one sample of output. For 3 
>seconds of output you need 3 * 44100 times as much operations.
>
>More useful in fact is the number of computations per second, i.e.
>2 * 3 * 44100² (per channel) ~ 1.2 Gflops.
>
>But no one who is not off one's head would implement a 130k FIR filter 
>in the time domain. With FFT convolution even a raspberry pi 1 is able 
>to do the job. If you already have several seconds latency the 
>additional latency of the FFT convolution does not count.
>
>
>Marcel

Marcel,

I really appreciate your reply.  Could you clarify 44100� (per
channel) please?  I think the andsign and the numbersign might obscure the
2013266098 and not sure where the 2013266098 is coming from.  Thanks
again. John
---------------------------------------
Posted through http://www.DSPRelated.com

On 07.01.16 19.18, johnnmonroe wrote:
> I really appreciate your reply.  Could you clarify 44100� (per
> channel) please?

Seems that one of us has some problems with the encoding. From my point 
of view my post seems to be clean with respect to special characters 
(ISO/IEC 8859-15).

> I think the andsign and the numbersign might obscure the
> 2013266098 and not sure where the 2013266098 is coming from.

No idea. It was a superscript 2. Probably your reader is not capable of 
ISO 8895-15 (Latin-9) encoding. Look here:
https://groups.google.com/d/msg/comp.dsp/0nZ9L7h99mw/NsnEHHiNDgAJ


Marcel

Marcel,  I can see the uncorrupted message using the link you provided. 
Thanks again.  John
---------------------------------------
Posted through http://www.DSPRelated.com