Codes on hypergraphs - Computer Science > Information TheoryReport as inadecuate

Codes on hypergraphs - Computer Science > Information Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: Codes on hypergraphs are an extension of the well-studied family of codes onbipartite graphs.
Bilu and Hoory 2004 constructed an explicit family of codeson regular t-partite hypergraphs whose minimum distance improves earlierestimates of the distance of bipartite-graph codes.
They also suggested adecoding algorithm for such codes and estimated its error-correctingcapability.In this paper we study two aspects of hypergraph codes.
First, we compute theweight enumerators of several ensembles of such codes, establishing conditionsunder which they attain the Gilbert-Varshamov bound and deriving estimates oftheir distance.
In particular, we show that this bound is attained by codesconstructed on a fixed bipartite graph with a large spectral gap.We also suggest a new decoding algorithm of hypergraph codes that corrects aconstant fraction of errors, improving upon the algorithm of Bilu and Hoory.

Author: Alexander Barg, Arya Mazumdar, Gilles Zémor



Related documents