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. (1998) Low Density MDS Codes and Factors of Complete Graphs. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:1998.ETR025

[img]
Preview
PDF (Adobe PDF (1.8MB))
See Usage Policy.

1834Kb
[img]
Preview
Postscript
See Usage Policy.

387Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:1998.ETR025

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:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr025.psPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1998.ETR025
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:1998.ETR025
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26048
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:03 Sep 2002
Last Modified:26 Dec 2012 13:52

Repository Staff Only: item control page