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*
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

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_{}).