On codes decoding a constant fraction of errors on the BSC

Using techniques and results from [8] we strengthen the bounds of [10] on the weight distribution of linear codes achieving capacity on the BEC. In particular, we show that for any doubly transitive binary linear code C ⊆ 0, 1 n of rate 0 < R < 1 with weight distribution (a

For doubly transitive codes with minimal distance at least Ω (n c ), 0 < c ≤ 1, the error factor of 2 o(n) in this bound can be removed at the cost of replacing 1 -R with a smaller constant a = a(R, c) < 1 -R. Moreover, in the special case of Reed-Muller codes, due to the additional symmetries of these codes, this error factor can be removed at essentially no cost.

This implies that for any doubly transitive code C of rate R with minimal distance at least Ω (n c ), there exists a positive constant p = p(R, c) such that C decodes errors on BSC(p) with high probability if p < p(R, c). For doubly transitive codes of a sufficiently low rate (smaller than some absolute constant) the requirement on the minimal distance can be omitted, and hence this critical probability p(R) depends only on R. Furthermore, p(R) → 1 2 as R → 0. In particular, a Reed-Muller code C of rate R decodes errors on BSC(p) with high probability if R < 1 -4p(1 -p) 1 4 ln 2 , answering a question posed in [1].