Xu, Lihao and Bohossian, Vasken and Bruck, Jehoshua and Wagner, David G. (1998) Low density MDS codes and factors of complete graphs. In: IEEE International Symposium on Information Theory, 1998. IEEE , Piscataway, NJ, p. 20. ISBN 0-7803-5000-6. https://resolver.caltech.edu/CaltechAUTHORS:XULisit98
![]()
|
PDF
See Usage Policy. 115kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:XULisit98
Abstract
We reveal an equivalence relation between the construction of a new class of low density MDS array codes, that we call B-Code, and a combinatorial problem known as perfect one-factorization of complete graphs. We use known perfect one-factors of complete graphs to create constructions and decoding algorithms for both B-Code and its dual code. B-Code and its dual are optimal in the sense that (i) they are 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. 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: | Book Section | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
Additional Information: | © 1998 IEEE. Reprinted with Permission. Publication Date: 16-21 Aug. 1998. 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. | ||||||
Subject Keywords: | decoding; dual codes; graph theory; B-code; combinatorial problem; complete graphs; decoding algorithms; equivalence relation; information bit; low density MDS array codes; nodes; odd length code; optimal encoding property; optimal length code; parity bits; perfect one-factorization; perfect one-factorizations; perfect one-factors | ||||||
DOI: | 10.1109/ISIT.1998.708599 | ||||||
Record Number: | CaltechAUTHORS:XULisit98 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:XULisit98 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 10031 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | INVALID USER | ||||||
Deposited On: | 06 May 2008 | ||||||
Last Modified: | 08 Nov 2021 21:04 |
Repository Staff Only: item control page