Single chip implementation of the Levinson algorithm

The design, implementation, and testing procedure are presented for a single chip implementation of the Levinson algorithm. This algorithm provides an iterative procedure for the solution of certain systems of linear equations and is used in many basic problems in communications and signal processing. This chip consists of a 1200-bit RAM memory, a divider based on the nonrestoring division algorithm, a recorder-based multiplier suitable for pipelined operations, and a controller that consists of two PLAs and six address registers. Modifications of the algorithm permit the parallel use of both the multiplier and the divider. The design is done in 4-μm NMOS technology, and 12-bit-long operants in two´s complement are used. By using a 5-MHz two-phase clock, the chip can compute 20 iterations of the algorithm in approximately 675 μs. Application to lattice filtering in linear data channel equilization is considered. Off-line testing of the chip can be done effectively with minimum additional hardware through separate data and control buses.