A Caltech Library Service

Low-density MDS codes and factors of complete graphs

Xu, Lihao and Bohossian, Vasken and Bruck, Jehoshua and Wagner, David G. (1999) Low-density MDS codes and factors of complete graphs. IEEE Transactions on Information Theory, 45 (6). pp. 1817-1826. ISSN 0018-9448. doi:10.1109/18.782102.

See Usage Policy.


Use this Persistent URL to link to this item:


We present a class of array code of size n×l, where l=2n or 2n+1, called B-Code. The distances of the B-Code and its dual are 3 and l-1, respectively. 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 property, i.e., the number of the parity bits that are affected by change of a single information bit is minimal, and iii) they have optimal length. Using a new graph description of the codes, we prove an equivalence relation between the construction of the B-Code (or its dual) and a combinatorial problem known as perfect one-factorization of complete graphs, thus obtaining constructions of two families of the B-Code and its dual, one of which is new. Efficient decoding algorithms are also given, both for erasure correcting and for error correcting. The existence of perfect one-factorizations for every complete graph with an even number of nodes is a 35 years long conjecture in graph theory. The construction of B-Codes of arbitrary odd length will provide an affirmative answer to the conjecture.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received August 25, 1998. This work was supported in part by the NSF Young Investigator Award CCR-9457811, by an IBM Partnership Award, by the Sloan Research Fellowship, and by DARPA through an agreement with NASA/OSAT. Communicated by A. M. Barg, Associate Editor for Coding Theory. We are grateful to Dr. M. Blaum of IBM Almaden Research Center for his helpful discussions with us.
Subject Keywords:Array codes, low density, MDS codes, update complexity, perfect one-factorization
Issue or Number:6
Record Number:CaltechAUTHORS:XULieeetit99a
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5193
Deposited By: Archive Administrator
Deposited On:04 Oct 2006
Last Modified:08 Nov 2021 20:23

Repository Staff Only: item control page