A SEMI-SYSTOLIC DECODER FOR THE PDSC-73 ERROR-CORRECTING CODE

This paper presents a semi-systolic architecture for decoding cyclic linear error-correcting codes at high speed. The architecture implements a variant of Tanner's Algorithm B, modified for simpler and faster implementation. The main features of the architecture are low computational complexity, a simple, regular arrangement of cells for easy layout, short critical paths, and a high clock rate. A prototype chip has been designed to decode a 73-bit perfect difference set code. This 4600-mu-m x 6800-mu-m chip should achieve 25MHz decoding in 2-mu-m n-well cMOS. The success of the implementation illustrates the value of using technology dependent constraints and cost measures to guide the design of algorithms and architectures.