Information-Geometrical Significance of Sparsity in Gallager Codes
Abstract
We report a result of perturbation analysis on decoding error of the belief propagation decoder for Gallager codes. The analysis is based on infor- mation geometry, and it shows that the principal term of decoding error at equilibrium comes from the m-embedding curvature of the log-linear submanifold spanned by the estimated pseudoposteriors, one for the full marginal, and K for partial posteriors, each of which takes a single check into account, where K is the number of checks in the Gallager code. It is then shown that the principal error term vanishes when the parity-check matrix of the code is so sparse that there are no two columns with overlap greater than 1.
Cite
Text
Tanaka et al. "Information-Geometrical Significance of Sparsity in Gallager Codes." Neural Information Processing Systems, 2001.Markdown
[Tanaka et al. "Information-Geometrical Significance of Sparsity in Gallager Codes." Neural Information Processing Systems, 2001.](https://mlanthology.org/neurips/2001/tanaka2001neurips-informationgeometrical/)BibTeX
@inproceedings{tanaka2001neurips-informationgeometrical,
title = {{Information-Geometrical Significance of Sparsity in Gallager Codes}},
author = {Tanaka, Toshiyuki and Ikeda, Shiro and Amari, Shun-ichi},
booktitle = {Neural Information Processing Systems},
year = {2001},
pages = {527-534},
url = {https://mlanthology.org/neurips/2001/tanaka2001neurips-informationgeometrical/}
}