|M.Sc Student||Louidor Erez|
|Subject||Lowest-Density MDS Codes over Super-Alphabets|
|Department||Department of Computer Science||Supervisor||Professor Ronny Roth|
Let denote a field and b be a positive integer. A nonempty set is said to be an F-linear code of length n over (the extension alphabet) if C is a vector space over F. Each codeword of C can be transformed in a one-to-one manner into a word of simply by concatenating its n entries. The set of words thus obtained will be denoted by . Clearly, is a linear code (in the traditional sense) of length nb over F.
Let C be an F-linear code of length n overand let d denote its minimum Hamming distance (measured with respect to the alphabet ). Letting denote the dimension of C (or ) as a vector space over F, we denote by k the (rational) quantity and refer to C as an F-linear [n,k,d] code over . The redundancy of C is defined accordingly by .
A matrix is said to be a parity-check (resp. generator) matrix of C if it is a parity-check (resp. generator) matrix of . Such a matrix is called systematic, if it contains the (resp. identity matrix as a sub-matrix.
An F-linear [n,k,d] code that attains the Singleton bound with equality (namely, ) is called maximum-distance separable, or MDS. It is known that each row in a parity-check matrix of an F-linear MDS code C over must contain at least nonzero entries. We say that a parity-check matrix of C has lowest density if it meets this lower bound for every row. We call C a lowest-density MDS code if it has a systematic lowest-density parity-check matrix.
This work studies a certain class of F-linear codes over whose length is a prime p such that b divides and their redundancy equals . These codes, which we denote by, are not always MDS; yet, when they are, then they are also lowest-density MDS. We identify a range of parameters for which these codes are MDS and construct a decoding algorithm for that corrects one erroneous symbol (over).