Typical performance of gallager-type error-correcting codes

Yoshiyuki Kabashima, Tatsuto Murayama, David Saad

    Research output: Contribution to journalArticlepeer-review


    The performance of Gallager's error-correcting code is investigated via methods of statistical physics. In this method, the transmitted codeword comprises products of the original message 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 is saturated for many of the codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding.
    Original languageEnglish
    Pages (from-to)1355-1358
    Number of pages4
    JournalPhysical Review Letters
    Issue number6
    Publication statusPublished - 7 Feb 2000

    Bibliographical note

    Copyright of the American Physical Society


    • Gallager's error-correcting code
    • statistical physics
    • transmitted codeword
    • matrices
    • Shannon's channel capacity
    • decoding aspects
    • TAP approach


    Dive into the research topics of 'Typical performance of gallager-type error-correcting codes'. Together they form a unique fingerprint.

    Cite this