Statistical physics of regular low-density parity-check error-correcting codes

被引：60

作者：

Murayama, T ^{[1
]}

Kabashima, Y

Saad, D

Vicente, R

机构：

[1] Tokyo Inst Technol, Dept Computat Intelligence & Syst Sci, Yokohama, Kanagawa 2268502, Japan

[2] Aston Univ, Neural Comp Res Grp, Birmingham B4 7ET, W Midlands, England

来源：

PHYSICAL REVIEW E | 2000年 / 62卷 / 02期

关键词：

D O I：

10.1103/PhysRevE.62.1577

中图分类号：

O35 [流体力学]; O53 [等离子体物理学];

学科分类号：

070204 ; 080103 ; 080704 ;

摘要：

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

引用

页码：1577 / 1591

页数：15

共 23 条

[1]

Frey B. J., 1998, ADAP COMP MACH LEARN

[2] LOW-DENSITY PARITY-CHECK CODES [J].

GALLAGER, RG .

IRE TRANSACTIONS ON INFORMATION THEORY, 1962, 8 (01) :21-&

[3] The Nishimori line and Bayesian statistics [J].

Iba, Y .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1999, 32 (21) :3875-3888

[4]

Kabashima Y, 2000, ADV NEUR IN, V12, P272

[5] Statistical mechanics of error-correcting codes [J].

Kabashima, Y ;

Saad, D .

EUROPHYSICS LETTERS, 1999, 45 (01) :97-103

[6] Belief propagation vs. TAP for decoding corrupted messages [J].

Kabashima, Y ;

Saad, D .

EUROPHYSICS LETTERS, 1998, 44 (05) :668-674

[7] Typical performance of Gallager-type error-correcting codes [J].

Kabashima, Y ;

Murayama, T ;

Saad, D .

PHYSICAL REVIEW LETTERS, 2000, 84 (06) :1355-1358

[8] Finite-size effects and error-free communication in Gaussian channels [J].

Kanter, I ;

Saad, D .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2000, 33 (08) :1675-1681

[9] Error-correcting codes that nearly saturate Shannon's bound [J].

Kanter, I ;

Saad, D .

PHYSICAL REVIEW LETTERS, 1999, 83 (13) :2660-2663

[10] Improved low-density parity-check codes using irregular graphs and belief propagation [J].

Luby, MG ;

Mitzenmacher, M ;

Shokrollahi, MA ;

Spielman, DA .

1998 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS, 1998, :117-117

← 1 2 3 →