CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:XULieeetit99a

[img]
Preview
PDF
See Usage Policy.

197Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:XULieeetit99a

Abstract

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
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
Record Number:CaltechAUTHORS:XULieeetit99a
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:XULieeetit99a
Alternative URL:http://dx.doi.org/10.1109/18.782102
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5193
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:04 Oct 2006
Last Modified:26 Dec 2012 09:04

Repository Staff Only: item control page