A Geometric Approach to Coding Theory with Application to Information Retrieval

摘要

Finding cyclic codes that can be decoded efficiently by threshold logic is important because the decoders are very easy to implement. Two related classes of codes derived from Euclidean geometries are presented. The code length, number of information symbols, and minimum distance are shown to be related by means of parameters of a code. These codes can be decoded with a variation of the original algorithm proposed by Reed for Reed-Muller codes. We show that these codes are comparable to Rudolph's projective geometry codes which are known to have the following important feature. For a given code length and rate, the projective geometry code has relatively large minimum distance and the decoder is usually very simple. We have derived a class of codes from projective geometries in terms of the roots of generator polynomials. These codes are shown to contain the corresponding non-primitive Reed-Muller codes discovered by Weldon as subcodes, in many cases, proper subcodes with the same error-correcting ability by L-step orthogonalization procedure. These codes are found to be identical to Rudolph's projective geometry codes for all useful parameters of the codes. Threshold decoding of BCH codes and the generality of L-step orthogonalization procedure to cyclic codes are discussed. Investigation on the application of coding theory to information retrieval is presented. (Author)