The sum-product algorithm on small graphs. (English) Zbl 1155.68091
Shaska, T. (ed.) et al., Advances in coding theory and cryptography. Selected papers based on the presentations at the Vlora conference in coding theory and cryptography, Vlora, Albania, May 26–27, 2007 and a special session on coding theory as part of the applications of computer algebra conference, Rochester, MI, USA, July 19–22, 2007. Hackensack, NJ: World Scientific (ISBN 978-981-270-701-7/hbk). Series on Coding Theory and Cryptology 3, 160-180 (2007).
The sum-product algorithm is a general form of the forward-backward algorithm. In this paper an algebraic analysis of the sum-product algorithm is given for a set of connected bipartite graphs, on which all check nodes are of degree 2. The code defined by such a graph is a repetition code. In particular cases some formulas for the convergence of the sum-product algorithm are also derived. The examples investigated in this paper are mainly of theoretical interest.
For the entire collection see [Zbl 1120.94004].
For the entire collection see [Zbl 1120.94004].
Reviewer: Piroska Lakatos (Debrecen)
MSC:
| 68W40 | Analysis of algorithms |
| 94B60 | Other types of codes |
| 94B25 | Combinatorial codes |
| 94A45 | Prefix, length-variable, comma-free codes |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
