Immitance-domain Levinson algorithms

Several computationally extra-efficient versions of the Levinson algorithm are presented. The new versions require half the number of multiplications and the same number of additions as the conventional form of the Levinson algorithm. The saving is achieved by using three- (rather than two) term recursions and propagating them in an Impedance/Admittance domain rather than the conventional scattering domain. Our result apply both to Toeplitz and to close to Toeplitz systems. Moreover they provide a general method for reducing computational requirements in various recursive algorithm, e.g. adaptive least-square lattice algorithms.