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