Weight distribution and decoding of codes on hypergraphs

Alexander Barg; Arya Mazumdar; Gilles Zémor

doi:10.3934/amc.2008.2.433

Article Contents

2008, Volume 2, Issue 4: 433-450. Doi: 10.3934/amc.2008.2.433

This issue Previous Article On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables Next Article Geometric constructions of optimal optical orthogonal codes

Weight distribution and decoding of codes on hypergraphs

1.
Dept. of ECE and Institute for Systems Research, University of Maryland, College Park, MD 20742
2.
Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742
3.
Institut de Mathématiques de Bordeaux, Université de Bordeaux 1, 351 cours de la Libération, 33405 Talence

Received: June 30, 2008

Revised: September 30, 2008

Published: October 2008

Abstract Related Papers Cited by

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 improves earlier estimates of the distance of bipartite-graph codes. They also suggested a decoding algorithm for such codes and estimated its error-correcting capability.
In this paper we study two aspects of hypergraph codes. First, we compute 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.

Keywords:

Mathematics Subject Classification: Primary: 94B25; Secondary: 94B35, 05C65.

Citation:

Article Metrics

HTML views() PDF downloads(139) Cited by(0)

Weight distribution and decoding of codes on hypergraphs

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

Weight distribution and decoding of codes on hypergraphs

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content