2000/08/24 by David Saad, Yoshiyuki Kabashima, Tatsuto Murayama · 1 citation
Computer Science · Engineering · Physics and Astronomy · #Coding theory and cryptography #Error Correcting Code Techniques #cond-mat.dis-nn #graph theory and CDMA systems
paper · pdf · doi:10.1063/1.1358168
6 pages
arxiv created 2000/08/24 · openalex publication_date 2001/01/01 · arxiv updated 2009/11/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/29
We employ the methods of statistical physics to study the performance of Gallager type error-correcting codes. In this approach, the transmitted codeword comprises Boolean sums of the original message bits selected by two randomly-constructed sparse matrices. We show that a broad range of these codes potentially saturate Shannon’s bound but are limited due to the decoding dynamics used. Other codes show sub-optimal performance but are not restricted by the decoding dynamics. We show how these codes may also be employed as a practical public-key cryptosystem and are of competitive performance to modern cyptographical methods.