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. https://resolver.caltech.edu/CaltechAUTHORS:XULieeetit99a
![]()
|
PDF
See Usage Policy. 202kB |
Use this Persistent URL to link to this item: https://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 | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
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 | ||||||
DOI: | 10.1109/18.782102 | ||||||
Record Number: | CaltechAUTHORS:XULieeetit99a | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:XULieeetit99a | ||||||
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: | 08 Nov 2021 20:23 |
Repository Staff Only: item control page