partitioned convolution

Hi

Could anyone outline the basic steps for partitioned convolution
of audio, im fairly new to dsp, i have realtime FFT convolution in c++
working using overlap and add, but im limited at the moment to an IR[512],
with blocks of input[512] ide like to store the FFT of a larger ir split it
into blocks and loop through them in the frequency domain multiplication
step if possible.

thanks for any help

Gary wrote:
> Hi
>
> Could anyone outline the basic steps for partitioned convolution
> of audio, im fairly new to dsp, i have realtime FFT convolution in c++
> working using overlap and add, but im limited at the moment to an IR[512],
> with blocks of input[512] ide like to store the FFT of a larger ir split it
> into blocks and loop through them in the frequency domain multiplication
> step if possible.

Convolution is just a sum, you can break it up anywhere you like. If h
is the impulse response of length N and x the input signal, then the
convolution y is computed as

y(n) = h(n) * x(n) = sum_{k=0}^{N-1} h(k) x(n-k).

You can break this up at index 0 < N1 < N into

y(n) = sum_{k=0}^{N1-1} h(k) x(n-k) + sum_{k=N1}^{N-1} h(k) x(n-k)
= sum_{k=0}^{N1-1} h1(k) x(n-k) + sum_{k=0}^{N-N1-1} h2(k) x(n-k-N1)
= h1(n) * x(n) +  h2(n) * x(n-N1)

The last line shows that this is again two convolutions, where the
second convolution is with the input signal delayed by the length of
the first convolution. h(n) is partitioned into h1(n) = h(n) and h2(n)
=h(n+N1), and length(h1) = N1 and length(h2) = N-N1. 

Regards,
Andor

Thanks for your reply Andor

I think i get what your saying, but im kinda stumbling around 
with the implementation, 

heres what im doing at the moment:

- Capture 512 samples of input audio
- Zero pad to 1024
- FFT
- Multiply input with the FFT of the IR
- IFFT
- Add 512 overlap to the filtered signal
- Store 511 of the filtered signal in the overlap array
- Output filtered signal
- repeat

Ide like to do the following if correct, but im not sure
what should happen in this loop over the IR blocks, particularly
the overlaps

- Capture 512 samples of input audio
- Zero pad to 1024
- FFT

  <-- loop here over x of the IR instead of just one
- Multiply input with the FFT of the IR
  <-- repeat for x

- IFFT
- Add 512 overlap to the filtered signal
- Store 511 of the filtered signal in the overlap array
- Output filtered signal
- repeat

thanks
Gary

Gary wrote:
> Thanks for your reply Andor
>
> I think i get what your saying, but im kinda stumbling around
> with the implementation,

The point is that once you have implemented the software for frequency
domain filtering using an impulse response of length, say 512, then
implementing frequency domain filtering using an impulse response of
length 1024 is essentially just two calls to the frequency domain
filtering function, except that for the second call the input has to be
delayed. Afterwards, just add the two outputs together.

You might also be interested in what others have to say about this [1].

Regards,
Andor

[1] Gardner, W. G.: "Efficient Convolution without Input/Output
Delay", 97th AES Convention San Francisco, November 1994, AES
Preprint 3897

Hi Andor

thanks for bearing with me!

think i get it now, i need to buffer the input and delay each input block
by, 512 for each pass, i think the problem i had was accepting that the
result would be the same as convolving the whole input with the the whole
IR in one go as you would with direct convolution, i believe the Gardner
algorithm is patented and uses varying block sizes together with direct
convolution but i havent managed to track down a copy of the paper yet.

Gary

>Andor wrote:
>The point is that once you have implemented the software for frequency
>domain filtering using an impulse response of length, say 512, then
>implementing frequency domain filtering using an impulse response of
>length 1024 is essentially just two calls to the frequency domain
>filtering function, except that for the second call the input has to be
>delayed. Afterwards, just add the two outputs together.