M.Sc Thesis
M.Sc Student Louidor Erez Lowest-Density MDS Codes over Super-Alphabets Department of Computer Science Professor Ronny Roth

Abstract

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).