[linux-audio-dev] Realtime convolution - a threading problem?

[Steve Harris]

On Thu, Apr 07, 2005 at 01:33:01AM +0200, Florian Schmidt wrote:
> > 2: Another approach is to split the FIR in blocks of different sizes, as can 
> > be seen in the bottom figure of this page:
> > http://www.music.miami.edu/programs/mue/Research/jvandekieft/jvchapter2.htm
> > This approach has an obvious advantage in that it allows "zero" latency, 
> > while still retaining some of the computational efficiency of the 
> > high-latency FFT based method. As far as I can see, the complexity of this 
> > algorithm scales as (ln_2(N))^2 for zero-latency. This is not as good as the 
> > high latency efficiency of ln_2(N) - but still far better than using method 
> > 1. with low latency.
> > 
> > As far as I know, the programs I've come across so far (most notably 
> > BruteFIR and Jack_convolve) uses method 1. to get low latency. This leads to 
> > my first question:
> > Has anybody implemented method 2. in a jack application, or, more generally, 
> > under GPL?. If not, are there any reasons that I'm not aware of, why one 
> > should not choose algorithm 2 instead of 1?
> 
> I _heard_ that in the US the algorithm 2 is patented. I haven't really
> looked into it, since my time is limited ATM. If it is not, i might have
> a shot at it at some unspecified time in the future.

Its a while since I looked at it, but I think that the patented algorithm
has a bit more too it. Just splitting the ER and FFT should be fine.

Its known as the "Lake DSP Patent" FWIW.

- Steve