Bounds on the minimum code distance for nonbinary codes based on bipartite graphs

A. A. Frolov, V. V. Zyablov

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

The minimum distance of codes on bipartite graphs (BG codes) over GF(q) is studied. A new upper bound on the minimum distance of BG codes is derived. The bound is shown to lie below the Gilbert-Varshamov bound when q > 32. Since the codes based on bipartite expander graphs (BEG codes) are a special case of BG codes and the resulting bound is valid for any BG code, it is also valid for BEG codes. Thus, nonbinary (q > 32) BG codes are worse than the best known linear codes. This is the key result of the work. We also obtain a lower bound on the minimum distance of BG codes with a Reed-Solomon constituent code and a lower bound on the minimum distance of low-density parity-check (LDPC) codes with a Reed-Solomon constituent code. The bound for LDPC codes is very close to the Gilbert-Varshamov bound and lies above the upper bound for BG codes.

Original languageEnglish
Pages (from-to)327-341
Number of pages15
JournalProblems of information transmission
Volume47
Issue number4
DOIs
Publication statusPublished - Dec 2011
Externally publishedYes

Fingerprint

Dive into the research topics of 'Bounds on the minimum code distance for nonbinary codes based on bipartite graphs'. Together they form a unique fingerprint.

Cite this