Partial permutation decoding for codes from designs and finite geometries.

摘要

An algorithm for decoding linear codes having large automorphism groups was introduced in the 1960s and was applied primarily to cyclic codes and to the Golay codes. This algorithm, called the permutation decoding algorithm, involves choosing appropriate information sets for the code and finding a set of automorphisms, called a PD-set, that satisfies certain conditions.; In this dissertation we determine to what extent permutation decoding can be used for codes obtained from some combinatorial structures. In particular, we consider codes from a class of graphs, codes from ovals in finite projective planes, and codes from finite projective planes. Examining the structures of these codes, we observed that after a certain length, codes from Paley graphs and finite projective planes do not have PD-sets for full error correction. We considered partial permutation decoding, using a set of automorphisms, called an s-PD-set, that can correct up to s errors where s is less than the full error-correcting capability of the code.; For Paley graphs of prime order, we construct 2-PD-sets of small size and 3-PD-sets of a size depending on the length of the code using any information set. In the case of Paley graphs of prime-square order, we show that 2-PD-sets for binary codes can be found using specific information sets.; In the finite desarguesian projective plane of prime power order q, we consider an MDS code obtained from an oval and generate a new code for the purpose of permutation decoding. We show that this new code has s-PD-sets for s ≤ q - 1.; For the finite desarguesian projective planes of even order, we study geometric configurations of points of the planes satisfying certain properties. These configurations can be the support of the vectors of small weight in the dual codes of the planes. In the case of prime-square order, we construct a set of points in a manner similar to that of a Moorhouse basis and conjecture that this set will form a basis for the code. We also show that using that set as an information set, a 2-PD-set can be found for the code.