Forums

Levinson algo. wtih complex coef. required

Started by herbert arthur December 30, 2003
Hi,

I am desperatly looking for a generalized Levinson algorithm that can 
cope with complex autocorrelation values and giving complex filter 
coefficients...

I would like to implement it in C, and i have only found the classical 
LPC analysis but it can not deal with complex coefficients...

Anyone can help ?

Thanks in  advance

herbert arthur wrote:
> > Hi, > > I am desperatly looking for a generalized Levinson algorithm that can > cope with complex autocorrelation values and giving complex filter > coefficients... > > I would like to implement it in C, and i have only found the classical > LPC analysis but it can not deal with complex coefficients...
Off the top of my head, I can't think of any reason why the algorithm wouldn't work as-is for complex autocorrelation values. Classical LPC analysis may make assumptions about the sequence types, but the Levinson algorithm itself is just an iterative one for computing the inverse of a Toeplitz matrix that relies on the persymmetry of the matrix and its inverse. This holds whether or not the matrix is real. Even if the autocorrelation values are complex, the autocorrelation matrix will still be Toeplitz, no? Then the algorithm should work just fine with the usual adjustments for complex arithmetic. Glenn Zelniker
Hi,
You're right.. almost :)
If the autocorrelation coefficients are complex, the matrix becomes an 
Hermitian one, which is an 'upper class' or Toplietz matrix, i e, all 
Toplietz matrices are Hermitians, bute the opposite is not true.
Furthermore, you're right when speaking about the conservation of the 
Toplietz properties, but looking at the usual levinson algorithm, i 
found that some complex conjugations are to be introduced if one wants 
the algorithm to work...
Which calculation terms should be changed ? there, is the question...

H. Arthur


Glenn Zelniker wrote:
> herbert arthur wrote: > >>Hi, >> >>I am desperatly looking for a generalized Levinson algorithm that can >>cope with complex autocorrelation values and giving complex filter >>coefficients... >> >>I would like to implement it in C, and i have only found the classical >>LPC analysis but it can not deal with complex coefficients... > > > Off the top of my head, I can't think of any reason why the > algorithm wouldn't work as-is for complex autocorrelation values. > Classical LPC analysis may make assumptions about the sequence > types, but the Levinson algorithm itself is just an iterative one > for computing the inverse of a Toeplitz matrix that relies on the > persymmetry of the matrix and its inverse. This holds whether or > not the matrix is real. Even if the autocorrelation values are > complex, the autocorrelation matrix will still be Toeplitz, no? > Then the algorithm should work just fine with the usual > adjustments for complex arithmetic. > > Glenn Zelniker

herbert arthur wrote:
> > Hi, > You're right.. almost :) > If the autocorrelation coefficients are complex, the matrix becomes an > Hermitian one, which is an 'upper class' or Toplietz matrix, i e, all > Toplietz matrices are Hermitians, bute the opposite is not true. > Furthermore, you're right when speaking about the conservation of the > Toplietz properties, but looking at the usual levinson algorithm, i > found that some complex conjugations are to be introduced if one wants > the algorithm to work... > Which calculation terms should be changed ? there, is the question...
On page 865-868 of the third edition of Digital Signal Processing there is a derivation of Levinson-Durban that, while I've never studied it in depth, does state at one point in the derivation that conjugation is required; so that derivation seems to be generalized to complex matrices. Bob -- "Things should be described as simply as possible, but no simpler." A. Einstein
Glenn Zelniker <glennz@z-sys.com> wrote in message news:<3FF1A37F.CB0355F3@z-sys.com>...
> herbert arthur wrote: > > > > Hi, > > > > I am desperatly looking for a generalized Levinson algorithm that can > > cope with complex autocorrelation values and giving complex filter > > coefficients... > > > > I would like to implement it in C, and i have only found the classical > > LPC analysis but it can not deal with complex coefficients... > > Off the top of my head, I can't think of any reason why the > algorithm wouldn't work as-is for complex autocorrelation values. > Classical LPC analysis may make assumptions about the sequence > types, but the Levinson algorithm itself is just an iterative one > for computing the inverse of a Toeplitz matrix that relies on the > persymmetry of the matrix and its inverse. This holds whether or > not the matrix is real. Even if the autocorrelation values are > complex, the autocorrelation matrix will still be Toeplitz, no? > Then the algorithm should work just fine with the usual > adjustments for complex arithmetic. > > Glenn Zelniker
There is a nice recipe in Therrien: Discrete Random Signals and Statistical Signal Processing, Prentice-Hall, 1992. Table 8.2 if my memory serves me correctly. Rune

Bob Cain wrote:
> > On page 865-868 of the third edition of Digital Signal > Processing
By Proakis and Manolokis. Sorry.
> there is a derivation of Levinson-Durban that, > while I've never studied it in depth, does state at one > point in the derivation that conjugation is required; so > that derivation seems to be generalized to complex matrices. >
-- "Things should be described as simply as possible, but no simpler." A. Einstein
Bob Cain <arcane@arcanemethods.com> wrote in message news:<3FF257EF.DA197513@arcanemethods.com>...
> Bob Cain wrote: > > > > On page 865-868 of the third edition of Digital Signal > > Processing > > By Proakis and Manolokis. Sorry. > > > there is a derivation of Levinson-Durban that, > > while I've never studied it in depth, does state at one > > point in the derivation that conjugation is required; so > > that derivation seems to be generalized to complex matrices. > >
It appears to be the same as the algorithm Therrien gives. The predictor coefficents associated with the backwards prediction are complex conjugated. Rune
Haykin also has the complex-valued derivation in his "Adaptive Filter Theory" book,

Maurice Givens


allnor@tele.ntnu.no (Rune Allnor) wrote in message news:<f56893ae.0312310513.71b0bcf5@posting.google.com>...
> Bob Cain <arcane@arcanemethods.com> wrote in message news:<3FF257EF.DA197513@arcanemethods.com>... > > Bob Cain wrote: > > > > > > On page 865-868 of the third edition of Digital Signal > > > Processing > > > > By Proakis and Manolokis. Sorry. > > > > > there is a derivation of Levinson-Durban that, > > > while I've never studied it in depth, does state at one > > > point in the derivation that conjugation is required; so > > > that derivation seems to be generalized to complex matrices. > > > > > It appears to be the same as the algorithm Therrien gives. > The predictor coefficents associated with the backwards prediction > are complex conjugated. > > Rune