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

# Levinson algo. wtih complex coef. required

Started by ●December 30, 2003

Reply by ●December 30, 20032003-12-30

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

Reply by ●December 30, 20032003-12-30

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

Reply by ●December 30, 20032003-12-30

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

Reply by ●December 30, 20032003-12-30

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 ZelnikerThere 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

Reply by ●December 31, 20032003-12-31

Bob Cain wrote:> > On page 865-868 of the third edition of Digital Signal > ProcessingBy 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

Reply by ●December 31, 20032003-12-31

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

Reply by ●December 31, 20032003-12-31

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