The maximum-likelihood decoding threshold for graphic codes

Abstract

For a class $\mathcal{C}$ of binary linear codes, we write ${\theta }_{\mathcal{C}}:(0,1)\to [0,\frac{1}{2}]$ for the maximum-likelihood decoding threshold function of $\mathcal{C}$, the function whose value at $R\in (0,1)$ is the largest bit-error rate $p$ that codes in $\mathcal{C}$ can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if $\mathcal{C}$ is the class of cycle codes of graphs, then ${\theta }_{\mathcal{C}}(R)\le \frac{(1-\sqrt{R}{)}^2}{2(1+R)}$ for each $R$, and show that equality holds only when $R$ is asymptotically achieved by cycle codes of regular graphs.

References in corpus (1)

• A Decomposition Theory for Binary Linear Codes