Error-correcting code on a cactus:A solvable model

Article, Preprint English OPEN
Vicente, Renato ; Saad, David ; Kabashima, Yoshiyuki (2000)

An exact solution to a family of parity check error-correcting codes is provided by mapping the problem onto a Husimi cactus. The solution obtained in the thermodynamic limit recovers the replica symmetric theory results and provides a very good approximation to finite systems of moderate size. The probability propagation decoding algorithm emerges naturally from the analysis. A phase transition between decoding success and failure phases is found to coincide with an information-theoretic upper bound. The method is employed to compare Gallager and MN codes.
  • References (25)
    25 references, page 1 of 3

    [1] Shannon C., Bell Syst. Tech. J., 27 (1948) 379.

    [2] Viterbi A. J. and Omura J. K., Principles of Digital Communication and Coding, (McGraw-Hill Book Co., Singapore) 1979.

    [3] MacKay D. J. C. and Neal R. M., Electr. Lett., 32 (1996) 1645; MacKay D. J. C., IEEE Trans. Info. Theory, 45(1999) 399.

    [4] Gallager R. G., IRE Trans. Info. Theory, 8 (1962) 21.

    [5] Berrou G. et al., Proc. of the IEEE Int. Conf. on Comm., (Geneva) 1993 p. 1064.

    [6] Davey M. C., Record-braking error-correction using low-density parity-check codes, (Hamilton prize essay, University of Cambridge) 1998.

    [7] Kanter I.and Saad D., Phys. Rev. Lett., 83(1999) 2660; J. Phys A, 33 (2000) 1675.

    [8] Sourlas N., Nature, 339 (1989) 693; Europhys. Lett., 25(1994) 159.

    [9] Derrida B., Phys. Rev. B, 24 (1981) 2613.

    [10] Saakian D.B., Pis'ma Zh. EĀ“ksp. Teor. Fiz.[JETP Lett.], 67 (1998) 440.

  • Metrics
    No metrics available
Share - Bookmark