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 http://resolver.caltech.edu/CaltechAUTHORS:XULieeetit99a
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:XULieeetit99a
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.
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||04 Oct 2006|
|Last Modified:||26 Dec 2012 09:04|
Repository Staff Only: item control page