Decoding of circulant codes (Corresp.)

Abstract

Many of the best random error-correcting group codes known (cyclic or not) can be reduced to echelon canonical form, in which the parity matrix is mainly or entirely composed of one or several circulants. This correspondence deals with simple and efficients methods for coding and decoding such codes, called quasi-cyclic in recent literature. The main result is that when the parity matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</tex> , or its complement <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(C + J)</tex> are nonsingular, simplified and fast decoding methods based on the quasi-cyclic structure, and alternately using syndromes based respectively on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</tex> and on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C^{-1}</tex> , permit correction to full error-correcting capacity. This is also extended to the (simplest) case of several parity circulants in a row.