Thomas, I suppose that a decomposition of a n-taps kernel into n zero-padded kernels would directly lead to the basics of the convolution algorithm :-) But your proposal also introduces a parallel computation, where the results have to be offset and added (incl. overlap treatment). My question is aiming a serial computation, like f1*f2 = f1*fa*fb with f2=fa*fb. Again: f1 is given and fa, fb are searched.
Greetings, Uli On Wed, Jan 19, 2011 at 5:07 PM, Thomas Young <thomas.yo...@rebellion.co.uk> wrote: > Hi Uli > > I don't know if this will be useful for your situation, but a simple method > for decomposing your kernel is to simply chop it in two. So for a kernel: > > 1 2 3 4 5 6 7 8 > > You can decompose it into two zero padded kernels: > > 1 2 3 4 0 0 0 0 > > 0 0 0 0 5 6 7 8 > > And sum the results of convolving both of these kernels with your signal to > achieve the same effect as convolving with the original kernel. You can do > this because convolution is distributive over addition, i.e. > > f1*(f2+f3) = f1*f2 + f1*f3 > > For signals f1,f2 & f3 (* meaning convolve rather than multiply). > > Obviously all those zero's do not need to be evaluated, meaning the problem > is changed to one of offsetting your convolution algorithm (which may or may > not be practical in your situation), but does allow you to use half the > number of coefficients. > > Thomas Young > > Core Technology Programmer > Rebellion Developments LTD > > -----Original Message----- > From: music-dsp-boun...@music.columbia.edu > [mailto:music-dsp-boun...@music.columbia.edu] On Behalf Of Uli Brueggemann > Sent: 19 January 2011 14:56 > To: A discussion list for music-related DSP > Subject: Re: [music-dsp] "Factorization" of filter kernels > > Hi, > > thanks for the answer so far. > A polyphase filter is a nice idea but it does not answer the problem. > The signal has to be demultiplexed (decimated), the different streams > have to be filtered, the results must be added to get the final output > signal. > > My question has a different target. > Imagine you have two system (e.g. some convolution boards with DSP). > Each system can just run a 512 tap filter. Now I like to connect the > two systems in series to mimic a desired 1024 tap filter. The 1024 > kernel is known and shall be generated by the two 512 tap filters. > So what's a best way to decompose the known kernel into two parts ? Is > there any method described somewhere? > > Uli > > > 2011/1/19 João Felipe Santos <joao....@gmail.com>: >> Hello, >> >> a technique that allows something similar to what you are suggesting >> is to use polyphase filters. The difference is that you will not >> process contiguous vectors, but (for a 2-phase decomposition example) >> process the even samples with one stage of the filter and the odd >> samples with another stage. It is generally used for multirate filter >> design, but it makes sense to use this kind of decomposition if you >> can process the stages in parallel... or at least it is what I think >> makes sense. >> >> You can search for references to this technique here  and here . >> A full section on how to perform the decomposition is presented on >> "Digital Signal Processing: a Computer-based approach" by Sanjit K. >> Mitra. >> >>  >> http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE521_files/IV-05%20Polyphase%20FIlters%20Revised.pdf >>  https://ccrma.stanford.edu/~jos/sasp/Multirate_Filter_Banks.html >> >> -- >> João Felipe Santos >> >> >> >> On Tue, Jan 18, 2011 at 5:46 AM, Uli Brueggemann >> <uli.brueggem...@gmail.com> wrote: >>> Hi, >>> >>> a convolution of two vectors with length size n and m gives a result >>> of length n+m-1. >>> So e.g. two vectors of length 512 with result in a vector of length 1023. >>> >>> Now let's assume we have a vector (or signal or filter kernel) of size >>> 1024, the last taps is 0. >>> How to decompose it to two vectors of half length? The smaller vectors >>> can be of any arbitrary contents but their convolution must result >>> must be equal to the original vector. >>> >>> It would be even interesting to "factorize" given kernel into n >>> smaller kernels. Again the smaller kernels may have any arbitrary but >>> senseful contents, they can be identical but this is not a must. >>> >>> Is there a good method to carry out the kernel decomposition? (e.g. >>> like calculating n identical factors x of a number y by x = >>> Exp(Log(y)/n) with x^n = x*x*...*x = y) >>> >>> Uli >>> -- >>> dupswapdrop -- the music-dsp mailing list and website: >>> subscription info, FAQ, source code archive, list archive, book reviews, >>> dsp links >>> http://music.columbia.edu/cmc/music-dsp >>> http://music.columbia.edu/mailman/listinfo/music-dsp >>> >> -- >> dupswapdrop -- the music-dsp mailing list and website: >> subscription info, FAQ, source code archive, list archive, book reviews, dsp >> links >> http://music.columbia.edu/cmc/music-dsp >> http://music.columbia.edu/mailman/listinfo/music-dsp >> > -- > dupswapdrop -- the music-dsp mailing list and website: > subscription info, FAQ, source code archive, list archive, book reviews, dsp > links > http://music.columbia.edu/cmc/music-dsp > http://music.columbia.edu/mailman/listinfo/music-dsp > -- > dupswapdrop -- the music-dsp mailing list and website: > subscription info, FAQ, source code archive, list archive, book reviews, dsp > links > http://music.columbia.edu/cmc/music-dsp > http://music.columbia.edu/mailman/listinfo/music-dsp > -- dupswapdrop -- the music-dsp mailing list and website: subscription info, FAQ, source code archive, list archive, book reviews, dsp links http://music.columbia.edu/cmc/music-dsp http://music.columbia.edu/mailman/listinfo/music-dsp