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 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] 3rd CfP to SMC2011 - submissions and special issues
[Apologies for cross-postings] [Please distribute] 8th Sound and Music Computing Conference 06-09 July 2011, Padova, Italy Department of Information Engineering, University of Padova Conservatorio Cesare Pollini, Padova http://smc2011.smcnetwork.org/ The SMC Conference is the forum for international exchanges around the core interdisciplinary topics of Sound and Music Computing. SMC2011 will feature lectures, posters/demos, musical/sonic works, and other satellite events. The Call for Papers and the Call for Music have already been launched. We are now able to announce that revised versions of a selected number of papers (approx. 6 to 10) on the conference theme will be published in a Special Issue of the Journal of New Music Research (tentatively scheduled for the second half of 2012, to be confirmed). Please check http://smc2011.smcnetwork.org/call_for_participation.htm The online submission system is now open, and templates for paper and music contributions are available. Please check http://smc2011.smcnetwork.org/information_for_authors.htm You have 2 months left to prepare your submission! Important dates= Deadline for submissions of papers and music: Friday 25 March, 2011 Deadline for applications to Summer School: Friday 25 March, 2011 Notification of acceptance to Summer School: Monday 18 April, 2011 Notification of paper and music acceptances: Friday 6 May, 2011 Deadline for submission of camera-ready papers: Friday 20 May, 2011 Deadline for submission of final music materials: Friday 20 May 2011 SMC 2011 Summer School: Saturday 2 - Tuesday 5 July, 2011 Rencon Workshop and Satellite Events: Wednesday 6 July, 2011 SMC 2011 Conference: Thursday 07 - Saturday 09 July, 2011 === Want to help us promote SMC2011? Insert a SMC2011 banner in your blog or web page (available at http://smc2011.smcnetwork.org/img/banner/), and link it to http://smc2011.smcnetwork.org/ Want to follow and share SMC2011 related news? Join and invite your friends to the SMC2011 facebook fanpage (linked from http://smc2011.smcnetwork.org/news.htm) -- Federico Avanzini, PhD Sound and Music Computing Group Dep. of Information Engineering University of Padova Via Ognissanti 72 I-35129 Padova - ITALY Skype: federico.avanzini Tel: +39 049 827 7856 Fax: +39 049 827 7826 http://smc2011.smcnetwork.org http://smc.dei.unipd.it http://www.dei.unipd.it/~avanzini -- 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 : > 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 > 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 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 : >> 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 >> 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 : > 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 > 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 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 : >> 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 >> 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: > su
Re: [music-dsp] "Factorization" of filter kernels
I see, most people want *more* parallelisation in their algorithms, not less ;) Perhaps you could make a 'guess' at the first filter and then solve the problem of finding a second filter which gives you the desired result. Since: f1*f2=result ...we know f1 & f2 and so can find 'result', and... f1*fa*fb=result so by guessing at fa (for example, just taking the first n coefficients) the problem is simplified to finding an fb for which the above equation is true. Since we know that convolution is multiplication in the frequency domain, and assuming we were using fast fourier transforms, the coefficients would be calculated by: IFFT( FFT('result') / FFT( f1*fa) ) I.e. what would we multiply f1*fa by in the frequency domain (aka convolve with it) in order to achieve 'result'. Feel free to point out any big holes in my logic :I Tom -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 16:30 To: A discussion list for music-related DSP Subject: 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 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 : >> 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 >> 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
Re: [music-dsp] "Factorization" of filter kernels
Convolution is equivalent to polynomial multiplication. Presumably we all know how to factorize a polynomial? Xue -Original Message- From: music-dsp-boun...@music.columbia.edu [mailto:music-dsp-boun...@music.columbia.edu] On Behalf Of Thomas Young Sent: 19 January 2011 17:13 To: A discussion list for music-related DSP Subject: Re: [music-dsp] "Factorization" of filter kernels I see, most people want *more* parallelisation in their algorithms, not less ;) Perhaps you could make a 'guess' at the first filter and then solve the problem of finding a second filter which gives you the desired result. Since: f1*f2=result ...we know f1 & f2 and so can find 'result', and... f1*fa*fb=result so by guessing at fa (for example, just taking the first n coefficients) the problem is simplified to finding an fb for which the above equation is true. Since we know that convolution is multiplication in the frequency domain, and assuming we were using fast fourier transforms, the coefficients would be calculated by: IFFT( FFT('result') / FFT( f1*fa) ) I.e. what would we multiply f1*fa by in the frequency domain (aka convolve with it) in order to achieve 'result'. Feel free to point out any big holes in my logic :I Tom -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 16:30 To: A discussion list for music-related DSP Subject: 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 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 : >> 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 Brueggem