You are here

Low Density MDS Codes and Factors of Complete Graphs

TitleLow Density MDS Codes and Factors of Complete Graphs
Publication TypeJournal Article
Year of Publication1998
AuthorsXu, L, Bohossian, V, Bruck, J, Wagner, D
JournalIEEE Trans. on Information Theory
Volume45
Pagination1817–1826
Keywordsarray codes, low density, MDS Codes, update complexity
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 onefactorization 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

URLhttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.8899
AttachmentSize
PDF icon 10.1.1.42.8899.pdf278.6 KB