Re: [music-dsp] Factorization of filter kernels
Hi, Maybe this can be of help. http://www.musicdsp.org/archive.php?classid=3#65 All the best Massimiliano Il 19/01/2011 15.56, Uli Brueggemann ha scritto: 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 Santosjoao@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 [1] and here [2]. A full section on how to perform the decomposition is presented on Digital Signal Processing: a Computer-based approach by Sanjit K. Mitra. [1] http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE521_files/IV-05%20Polyphase%20FIlters%20Revised.pdf [2] 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
Re: [music-dsp] Factorization of filter kernels
On 2011-01-19, Olli Niemitalo wrote: Find the roots, pair the complex conjugate roots and distribute the pairs and single real roots evenly (how exactly?) in the two filters. Matlab at least has facilities finding roots of large polynomials. Funny. I would have gone the transform-way. That is, take the impulse response, Fourier transform it into the frequency domain, and then try to figure out how to separate it complex-additively. Perhaps using some standard, l1-minimizing knapsack solver, or something. Did you notice, btw, that you can read off the polyphase intermediate rates right off the maxima of the baserate impulse response of a filter? -- Sampo Syreeni, aka decoy - de...@iki.fi, http://decoy.iki.fi/front +358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2 -- 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
Re: [music-dsp] Factorization of filter kernels
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 [1] and here [2]. A full section on how to perform the decomposition is presented on Digital Signal Processing: a Computer-based approach by Sanjit K. Mitra. [1] http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE521_files/IV-05%20Polyphase%20FIlters%20Revised.pdf [2] 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
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 [1] and here [2]. A full section on how to perform the decomposition is presented on Digital Signal Processing: a Computer-based approach by Sanjit K. Mitra. [1] http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE521_files/IV-05%20Polyphase%20FIlters%20Revised.pdf [2] 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
Re: [music-dsp] Factorization of filter kernels
Find the roots, pair the complex conjugate roots and distribute the pairs and single real roots evenly (how exactly?) in the two filters. Matlab at least has facilities finding roots of large polynomials. -olli On Wed, Jan 19, 2011 at 4:56 PM, Uli Brueggemann uli.brueggem...@gmail.com wrote: 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 [1] and here [2]. A full section on how to perform the decomposition is presented on Digital Signal Processing: a Computer-based approach by Sanjit K. Mitra. [1] http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE521_files/IV-05%20Polyphase%20FIlters%20Revised.pdf [2] 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
Re: [music-dsp] Factorization of filter kernels
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 [1] and here [2]. A full section on how to perform the decomposition is presented on Digital Signal Processing: a Computer-based approach by Sanjit K. Mitra. [1] http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE521_files/IV-05%20Polyphase%20FIlters%20Revised.pdf [2] 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
Re: [music-dsp] Factorization of filter kernels
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 [1] and here [2]. A full section on how to perform the decomposition is presented on Digital Signal Processing: a Computer-based approach by Sanjit K. Mitra. [1] http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE521_files/IV-05%20Polyphase%20FIlters%20Revised.pdf [2] 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
Re: [music-dsp] Factorization of filter kernels
I've only seen this kind of thing done on 2D signals (i.e. images), where it is much faster to use two 1D convolution passes (one in each dimension) than to use the much larger 2D kernel. The term I'm used to is a separable filter. It works fine as a technique, but you are very restricted in the kernels you can use. In 1D, are you really gaining anything? Won't two 512 sample kernels take the same time to process as one 1024 sample kernel? A different technique I've used to create very long convolutions with less processing time for images (but should work for sound as well) is to downsample, apply convolution, then upsample. Of course, you're going to lose the higher frequencies in the downsampling step, but it can be useful in situations where that is an acceptable trade. -- Brad Smith On Tue, Jan 18, 2011 at 2: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
[music-dsp] Factorization of filter kernels
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
