Weight distribution and decoding of codes on hypergraphs
| hal.structure.identifier | Dept. of ECE and Institute for Systems Research, university of Maryland | |
| dc.contributor.author | BARG, Alexander | |
| hal.structure.identifier | Dept. of ECE and Institute for Systems Research, university of Maryland | |
| dc.contributor.author | MAZUMDAR, Arya | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | ZÉMOR, Gilles | |
| dc.date.accessioned | 2024-04-04T02:43:34Z | |
| dc.date.available | 2024-04-04T02:43:34Z | |
| dc.date.created | 2008-11 | |
| dc.date.issued | 2008-11 | |
| dc.identifier.issn | 1930-5346 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191343 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | AIMS | |
| dc.title.en | Weight distribution and decoding of codes on hypergraphs | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.3934/amc.2008.2.433 | |
| dc.subject.hal | Informatique [cs]/Théorie de l'information [cs.IT] | |
| dc.identifier.arxiv | 0808.3453 | |
| bordeaux.journal | Advances in Mathematics of Communications | |
| bordeaux.page | 433 - 450 | |
| bordeaux.volume | 2 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 4 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00346971 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00346971v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Advances%20in%20Mathematics%20of%20Communications&rft.date=2008-11&rft.volume=2&rft.issue=4&rft.spage=433%20-%20450&rft.epage=433%20-%20450&rft.eissn=1930-5346&rft.issn=1930-5346&rft.au=BARG,%20Alexander&MAZUMDAR,%20Arya&Z%C3%89MOR,%20Gilles&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||