ON MDS codes and Bruen-Silverman codes.

摘要

An (n,k,r)-MDS code C is defined as follows. Let n, k, and r be positive integers with 2 r k. Then C is a set of nr k-tuples—called codewords or words—over an alphabet $A$ of size n satisfying the following condition.; Condition: No two codewords of C agree in as many as r positions.; It follows that the Hamming distance between any two words of C will be at least k − r + 1. Thus, if d′ is the minimum distance between any two words of C, then d′ > (k − r + 1). For any linear code, the Singleton bound gives d′ (k − r + 1). As such, MDS codes are optimal for error detection and correction. For fixed r, examples of MDS codes exist with arbitrarily large k. Furthermore, in the linear case these codes are easily decoded. For these reasons, MDS codes have been intensively studied in both theory and practice. The main practical applications are in error detection and correction for satellite transmissions and cryptography. On the purely mathematical level, it is a difficult unsolved problem—even in the linear case—to find the maximum value of k given both r and n. For example, if r = 2 then a solution would resolve the existence problem for finite planes.; Related to the issue of longest possible codes are the questions of structure and of the embedding of C in a longer code. In this thesis we skirmish with the embedding problem in the general (not necessarily linear) case. In some situations we can show embeddability. Given n and r, we obtain an upper bound on k. Moreover, we are able to give examples of inextendable MDS codes of length close to the provided bound. Some results of a purely geometrical nature are derived from our work. In an interesting special case we are able to obtain the unique structure of the MDS code.