BSC Thresholds for Code Ensembles Based on “Typical Pairs” Decoding

Abstract

In this paper, we develop a method for closely estimating noise threshold values for ensembles of binary linear codes on the binary symmetric channel. Our method, based on the “typical pairs” decoding algorithm pioneered by Shannon, completely decouples the channel from the code ensemble. In this, it resembles the classical union bound, but unlike the union bound, our method is powerful enough to prove Shannon’s theorem for the ensemble of random linear codes. We apply our method to find numerical thresholds for the ensembles of low-density parity-check codes, and “repeat-accumulate” codes.