The maximum-likelihood decoding threshold for graphic codes

الأصل · EN

For a class C of binary linear codes, we write θC (0,1) → [0,1/2] for the maximum-likelihood decoding threshold function of C, the function whose value at R ∈ (0,1) is the largest bit-error rate p that codes in C can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if C is the class of cycle codes of graphs, then θC(R) ≤ (1-√R)²2(1+R) for each R, and show that equality holds only when R is asymptotically achieved by cycle codes of regular graphs.