Forums

Levinson-Durbin Recursion revisited

Started by panu November 19, 2008
I know this subject has been discussed in the past on this site in relation
to inverse filter design, and this is also the subject of this post. My
specific application is acoustics. If you have experience with the
Levinson-Durbin algorithm in C/C++ I could use your help.

I have been using the code found at
http://kbs.cs.tu-berlin.de/~jutta/gsm/lpc.html
to try to implement the algorithm in C to replicate results given in
matlab for the simple command:

levinson(autocorM,lpclength);

levinson() in matlab produces a set of filter coefficients that is the
same length as the autocorrelation function, and this filter deconvolves
the impulse response in matlab.

However, the few C implementations that I have seen have as a a parameter
an autocorrelation buffer (autocorC) which is one sample longer (N+1) than
the lpc coefficients.

I am not able to reproduce my matlab result, the closest I can get in my
C++ project is when 
length(autocorC) = length(autocorM)+1, 
and the result is identical, except one less sample in the beginning and
one more at the end. Thus a shift of one will give me a perfect match
except for a zero in the first bin, which is crucial!

Any advice would be appreciated,
Panu


On 19 Nov, 21:06, "panu" <pan...@gmail.com> wrote:
> I know this subject has been discussed in the past on this site in relation > to inverse filter design, and this is also the subject of this post. My > specific application is acoustics. If you have experience with the > Levinson-Durbin algorithm in C/C++ I could use your help. > > I have been using the code found athttp://kbs.cs.tu-berlin.de/~jutta/gsm/lpc.html > to try to implement the algorithm in C to replicate results given in > matlab for the simple command: > > levinson(autocorM,lpclength); > > levinson() in matlab produces a set of filter coefficients that is the > same length as the autocorrelation function, and this filter deconvolves > the impulse response in matlab. > > However, the few C implementations that I have seen have as a a parameter > an autocorrelation buffer (autocorC) which is one sample longer (N+1) than > the lpc coefficients. > > I am not able to reproduce my matlab result, the closest I can get in my > C++ project is when > length(autocorC) = length(autocorM)+1, > and the result is identical, except one less sample in the beginning and > one more at the end. Thus a shift of one will give me a perfect match > except for a zero in the first bin, which is crucial!
So why not read up on the algorithm itself instead of relying on 3rd and 4th hand information? The Levinson recursion is standard material and has been for decades. You will find material if you look for it. Rune
On Nov 19, 3:06&#2013266080;pm, "panu" <pan...@gmail.com> wrote:
> I know this subject has been discussed in the past on this site in relation > to inverse filter design, and this is also the subject of this post. My > specific application is acoustics. If you have experience with the > Levinson-Durbin algorithm in C/C++ I could use your help. > > I have been using the code found athttp://kbs.cs.tu-berlin.de/~jutta/gsm/lpc.html > to try to implement the algorithm in C to replicate results given in > matlab for the simple command: > > levinson(autocorM,lpclength); > > levinson() in matlab produces a set of filter coefficients that is the > same length as the autocorrelation function, and this filter deconvolves > the impulse response in matlab. > > However, the few C implementations that I have seen have as a a parameter > an autocorrelation buffer (autocorC) which is one sample longer (N+1) than > the lpc coefficients. > > I am not able to reproduce my matlab result, the closest I can get in my > C++ project is when > length(autocorC) = length(autocorM)+1, > and the result is identical, except one less sample in the beginning and > one more at the end. Thus a shift of one will give me a perfect match > except for a zero in the first bin, which is crucial! > > Any advice would be appreciated, > Panu
Hello Panu, Try looking up Panos Papamichalis' book "Practical Approaches to Speech Coding." In here you will find good code not only on the LPC analysis but also finding the PARCORs (if you are using those). You do know that MATLAB uses indices starting at 1 and not at 0. Could that be your problem? In C when you define your array, just use a pointer to it offset by one or just waste the extra ram (a small amount). At lot of DSP code (especially old stuff from the Fortran days) is designed to use origin 1 instead of origin 0. Clay
On 19 Nov, 21:57, c...@claysturner.com wrote:
> On Nov 19, 3:06&#2013266080;pm, "panu" <pan...@gmail.com> wrote: > > > > > > > I know this subject has been discussed in the past on this site in relation > > to inverse filter design, and this is also the subject of this post. My > > specific application is acoustics. If you have experience with the > > Levinson-Durbin algorithm in C/C++ I could use your help. > > > I have been using the code found athttp://kbs.cs.tu-berlin.de/~jutta/gsm/lpc.html > > to try to implement the algorithm in C to replicate results given in > > matlab for the simple command: > > > levinson(autocorM,lpclength); > > > levinson() in matlab produces a set of filter coefficients that is the > > same length as the autocorrelation function, and this filter deconvolves > > the impulse response in matlab. > > > However, the few C implementations that I have seen have as a a parameter > > an autocorrelation buffer (autocorC) which is one sample longer (N+1) than > > the lpc coefficients. > > > I am not able to reproduce my matlab result, the closest I can get in my > > C++ project is when > > length(autocorC) = length(autocorM)+1, > > and the result is identical, except one less sample in the beginning and > > one more at the end. Thus a shift of one will give me a perfect match > > except for a zero in the first bin, which is crucial! > > > Any advice would be appreciated, > > Panu > > Hello Panu, > > Try looking up Panos Papamichalis' book "Practical Approaches to > Speech Coding." In here you will find good code not only on the LPC > analysis but also finding the PARCORs (if you are using those). > > You do know that MATLAB uses indices starting at 1 and not at 0. Could > that be your problem? In C when you define your array, just use a > pointer to it offset by one or just waste the extra ram (a small > amount). At lot of DSP code (especially old stuff from the Fortran > days) is designed to use origin 1 instead of origin 0.
This might be one explanation. But there is the possibility that some of the codes need space for the a(0) coefficient which always equals 1. Which is the reason why I asked the OP to check the algorithm, not just the codes. Rune
On Nov 19, 4:44&#2013266080;pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 19 Nov, 21:57, c...@claysturner.com wrote: > > > > > > > On Nov 19, 3:06&#2013266080;pm, "panu" <pan...@gmail.com> wrote: > > > > I know this subject has been discussed in the past on this site in relation > > > to inverse filter design, and this is also the subject of this post. My > > > specific application is acoustics. If you have experience with the > > > Levinson-Durbin algorithm in C/C++ I could use your help. > > > > I have been using the code found athttp://kbs.cs.tu-berlin.de/~jutta/gsm/lpc.html > > > to try to implement the algorithm in C to replicate results given in > > > matlab for the simple command: > > > > levinson(autocorM,lpclength); > > > > levinson() in matlab produces a set of filter coefficients that is the > > > same length as the autocorrelation function, and this filter deconvolves > > > the impulse response in matlab. > > > > However, the few C implementations that I have seen have as a a parameter > > > an autocorrelation buffer (autocorC) which is one sample longer (N+1) than > > > the lpc coefficients. > > > > I am not able to reproduce my matlab result, the closest I can get in my > > > C++ project is when > > > length(autocorC) = length(autocorM)+1, > > > and the result is identical, except one less sample in the beginning and > > > one more at the end. Thus a shift of one will give me a perfect match > > > except for a zero in the first bin, which is crucial! > > > > Any advice would be appreciated, > > > Panu > > > Hello Panu, > > > Try looking up Panos Papamichalis' book "Practical Approaches to > > Speech Coding." In here you will find good code not only on the LPC > > analysis but also finding the PARCORs (if you are using those). > > > You do know that MATLAB uses indices starting at 1 and not at 0. Could > > that be your problem? In C when you define your array, just use a > > pointer to it offset by one or just waste the extra ram (a small > > amount). At lot of DSP code (especially old stuff from the Fortran > > days) is designed to use origin 1 instead of origin 0. > > This might be one explanation. But there is the possibility > that some of the codes need space for the a(0) coefficient > which always equals 1. Which is the reason why I asked the > OP to check the algorithm, not just the codes. > > Rune- Hide quoted text - > > - Show quoted text -
Another case may be if one has unnormalized autocorrelation params. I've seen several different ways of getting there. But certainly one needs to mate the code with the theory. Code from one book and theory from another may lead to a nasty suprise. Clay