Re: [music-dsp] Factorization of filter kernels

2011-01-25 Thread Massimiliano Tonelli

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

2011-01-21 Thread Sampo Syreeni

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

2011-01-19 Thread 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
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

2011-01-19 Thread Uli Brueggemann
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

2011-01-19 Thread Olli Niemitalo
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

2011-01-19 Thread Thomas Young
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

2011-01-19 Thread Uli Brueggemann
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

2011-01-19 Thread Thomas Young
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
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

Re: [music-dsp] Factorization of filter kernels

2011-01-18 Thread Brad Smith
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