Algebraic and Stochastic Coding Theory

15

LDPC Codes

15.1  Tanner Graphs

A Tanner graph is a pictorial representation for the parity-check constraints of an ECC (Tanner [1981]). In Tanner graphs each square represents a parity-check bit and each circle connected to a square represents a bit that participates in that parity check. Thus, the nodes of the graph are separated into two distinct sets: c-nodes (top nodes, circles) and p-nodes (bottom nodes, squares). For an (n, k) code, the c-nodes c_i, i = 1, …, n, and the p-nodes p_j, j = 1,…, m, m = n − k, represent the message bits (symbols) and the parity bits, respectively, for a transmitted word c_i (or received word denoted by w_i). These nodes are connected to each other by the following formula:

$\{\begin{array}{c}\text{p-node }{p}_j\text{ is connected to c-node ...}\end{array}$