Belief propagation

Implementing the Belief Propagation Algorithm in MATLAB
Bj¨rn S. R¨ffer∗ o u Christopher M. Kellett∗ Technical Report Version as of November 13, 2008

We provide some example Matlab code as a supplement to the paper [6]. This technical report is not intended as a standalone introduction to the belief propagation algorithm, but instead only aims to provide some technical material, which didn’tfit into the paper.

1 Introduction
For an excellent introduction and mathematical treatise of modern iterative decoding theory, we refer to [4]. Worth mentioning is also the survey paper [2] on factor graphs and the sum-product algorithm, the superclass that contains belief propagation. This current technical note provides Matlab code to implement the dynamical system formulation of the beliefpropagation algorithm and a few related concepts, as detailed in [6]. More conventional implementations —that is, from a coding perspective— exist and some are publicly available [3]. The Matlab code examples detailed in this report can be found, along with the most up-to-date version of this report itself, at [5]. Our presentation differs also in another aspect from the standard ones: Unlike theinformation theory convention, where messages and codewords are represented by row vectors, we throughout use column vectors as this is standard in dynamical systems. Of course this does not lead to differences other than representational ones. This report is organized as follows: In Section 2 we give a simple example on how one can generate a very basic random parity-check matrix and compute acorresponding generator matrix. Section 3 details the channel transmission and Section 4 provides code to implement the belief propagation algorithm as a dynamical system. The output trajectories obtained using this Matlab code can then be plotted using the routine in
∗

School of Electrical Engineering and Computer Science, The University of Newcastle, Australia, Bjoern.Rueffer@Newcastle.edu.au,Chris.Kellett@newcastle.edu.au

1

Section 5. In Section 6 we provide a more advanced method for generating parity-check matrices with prescribed degree distribution.

2 Parity-Check and generator matrices
A parity-check matrix is any matrix H ∈ Fm×n . Throughout we assume that n = m + k, 2 n, m, k > 0 and that H has full rank, i.e., rank m. If H does not have full rank, then rows can beremoved until it does, thereby increasing k and decreasing m accordingly. To generate a parity-check matrix for a repeat-n code in canonical form, one could use the following Matlab statement:
n=10; m=n−1; H=spalloc(n−1,n,2∗(n−1)); for i=1:n−1, H(i,i)=1; H(i,i+1)=1; end

A simple random parity-check matrix can be generated using the code in Listing 1, and code for generating more involvedparity-check matrices is given in Section 6. Using only Gauss elimination and possibly by swapping columns, H can be brought into the form QHP = Im A , (1) where the invertible matrix Q ∈ Fm×m encodes the steps of the Gauss elimination 2 (swapping and adding rows of H), P ∈ Fn×n is a permutation matrix to encode the 2 swapping of columns in H, A ∈ Fm×k , and Im is the m × m identity matrix. 2 A generatormatrix for H is a matrix G ∈ Fn×k such that HG = 0. According to (1) 2 we can take G to be A G=P , (2) Ik since QHG = Im A P −1 · P A = 2A = 0 Ik (in Fm ) . 2

Now G maps message vectors m ∈ Fk to codewords c = Gm ∈ Fn , i.e., to elements 2 2 of the null-space C = CH = {x ∈ Fn : Hx = 0} of H, which is also termed the set of 2 codewords or just the code. The MATLAB code examples in Listings 1 and 2can be used to generate a very basic parity-check matrix and to obtain a generator matrix from a given parity-check matrix. Listing 1: A crude way to obtain a simple parity-check matrix, by just specifying the dimensions m and n and a density of non-zero elements in H of at least d ∈ (0, 1).
1 2 3 4 5 6 7 8

function H = g e n e r a t e H (m, n , d )
% H = GENERATE H ( m , n , d ) % %...