Low density MDS codes and factors of complete graphs

被引：1

作者：

Xu, LH ^{[1
]}

Bohossian, V ^{[1
]}

Bruck, J ^{[1
]}

Wagner, DG ^{[1
]}

机构：

[1] CALTECH, Pasadena, CA 91125 USA

来源：

1998 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS | 1998年

关键词：

D O I：

10.1109/ISIT.1998.708599

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

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.

引用

页码：20 / 20

页数：1