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 matrixC, or its complement(C + J)are nonsingular, simplified and fast decoding methods based on the quasi-cyclic structure, and alternately using syndromes based respectively onCand onC^{-1}, permit correction to full error-correcting capacity. This is also extended to the (simplest) case of several parity circulants in a row.

The Introduction contains a new circulant echelon canonical form for the perfect(23,12)Golay code and some tentative conclusions are suggested. Section I gives an account of the properties of circulant matricesA, and a number of lemmas that make it possible to determine the minimum weight of codes generated by the rows of a matrix of the form|E|A|. In Section II, it is shown that many quadratic residue codes are almost of this form. The following new minimum weight results are obtained: For the(79, 40)code,w = 15; (103, 52), w = 19; (151, 76), w = 19; (89, 45), w = 17and for(113, 57), w = 15. In Section III, high-quality (noncyclic) group codes are constructed by means of circulants. In some cases a definite improvement is obtained on the best previously known Bose-Chaudhuri-Hocquenghem cyclic codes (including the(31, 16)code). Methods of coding and decoding circulant codes are not discussed.