On lowest density MDS codes

Abstract

Let F/sub q/ denote the finite field GF(q) and let h be a positive integer. MDS (maximum distance separable) codes over the symbol alphabet F/sub q//sup b/ are considered that are linear over F/sub q/ and have sparse ("low-density") parity-check and generator matrices over F/sub q/ that are systematic over F/sub q//sup b/. Lower bounds are presented on the number of nonzero elements in any systematic parity-check or generator matrix of an F/sub q/-linear MDS code over F/sub q//sup b/, along with upper bounds on the length of any MDS code that attains those lower bounds. A construction is presented that achieves those bounds for certain redundancy values. The building block of the construction is a set of sparse nonsingular matrices over F/sub q/ whose pairwise differences are also nonsingular. Bounds and constructions are presented also for the case where the systematic condition on the parity-check and generator matrices is relaxed to be over F/sub q/, rather than over F/sub q//sup b/.