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\ge32$. 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\ge32$) 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.
Fulltext:
PDF file (417 kB)
