Exact thresholds and optimal codes for the binary-symmetric channel and Gallager´s decoding algorithm A

We show that for the case of the binary-symmetric channel and Gallager´s decoding algorithm A the threshold can, in many cases, be determined analytically. More precisely, we show that the threshold is always upper-bounded by the minimum of (1-λ₂ρ´(1))/(λ´(1)ρ´(1)-λ₂ρ´(1)) and the smallest positive real root τ of a specific polynomial p(x) and we observe that for most cases this bound is tight, i.e., it determines the threshold exactly. We also present optimal degree distributions for a large range of rates. In the case of rate one-half codes, for example, the threshold x₀^* of the optimal degree distribution is given by x^*₀∼0.0513663. Finally, we outline how thresholds of more complicated decoders might be determined analytically.