Low-density MDS codes and factors of complete graphs

We present a class of array code of size n x I, where I = 2n or 2n + 1, cal led B-Code. The distances of the B-Code and its dual are 3 and I - 1, respe ctively. The B-Code and its dual are optimal in the sense that i) they are maximum-distance separable (MDS), ii) they have an optimal encoding propert y, i.e., the number of the parity bits that are affected by change of a sin gle information bit is minimal, and iii) they have optimal length. Using a new graph description of the codes, we prove an equivalence relation betwee n the construction of the B-Code (or its dual) and a combinatorial problem known as perfect one-factorization of complete graphs, thus obtaining const ructions of two families of the B-Code and its dual, one of which is new. E fficient decoding algorithms are also given, both for erasure correcting an d for error correcting. The existence of perfect one-factorizations for eve ry complete graph with an even number of nodes is a 35 Sears long conjectur e in graph theory. The construction of B-Codes of arbitrary odd length will provide an affirmative answer to the conjecture.