The use of information sets in decoding cyclic codes

A class of decoding algorithms using encoding-and-comparison is considered for error-correcting code spaces. Code words, each of which agrees on some information set for the code with the word r to be decoded, are constructed and compared with r. An operationally simple algorithm of this type is studied for cyclic code spaces A. Let A have length n, dimension k over some finite field, and minimal Hamming distance m. The construction of fewer than n²/2 code words is required in decoding a word r. The procedure seems to be most efficient for small minimal distance m, but somewhat paradoxically it is suggested on operational grounds that it may prove most useful in those cases where m is relatively large with respect to the code length n.