Weight distribution and decoding of codes on hypergraphs

Alexander Barg, Arya Mazumdar, Gilles Zémor

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

Codes on hypergraphs are an extension of the well-studied family of codes on bipartite graphs. Bilu and Hoory (2004) constructed an explicit family of codes on regular t-partite hypergraphs whose minimum distance im- proves earlier estimates of the distance of bipartite-graph codes. They also sug- gested a decoding algorithm for such codes and estimated its error-correcting capability. In this paper we study two aspects of hypergraph codes. First, we com- pute the weight enumerators of several ensembles of such codes, establishing conditions under which they attain the Gilbert-Varshamov bound and deriving estimates of their distance. In particular, we show that this bound is attained by codes constructed on a fixed bipartite graph with a large spectral gap. We also suggest a new decoding algorithm of hypergraph codes that corrects a constant fraction of errors, improving upon the algorithm of Bilu and Hoory.

Original languageEnglish (US)
Pages (from-to)433-450
Number of pages18
JournalAdvances in Mathematics of Communications
Volume2
Issue number4
DOIs
StatePublished - Nov 2008

Keywords

  • Codes on graphs
  • Decoding
  • Hypergraphs
  • Weight distribution

Fingerprint Dive into the research topics of 'Weight distribution and decoding of codes on hypergraphs'. Together they form a unique fingerprint.

  • Cite this