Part of Advances in Neural Information Processing Systems 12 (NIPS 1999)
Yoshiyuki Kabashima, Tatsuto Murayama, David Saad, Renato Vicente
The performance of regular and irregular Gallager-type error(cid:173) correcting code is investigated via methods of statistical physics. The transmitted codeword comprises products of the original mes(cid:173) sage bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are con(cid:173) sidered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties.