3.4 Syndrome-Former Trellis Representation of Binary Linear Block Codes

So far, we have used matrix theory to describe a block encoder. We can also describe an ( n, k) linear block code with the aid of a trellis diagram. A trellis is simply a collection of nodes or states interconnected by unidirectional edges. The nodes are grouped into sets and a node indexed by a particular value d' is said to be at depth d' for d' = 0, 1, . . ., n. Edges are drawn from a node at depth d' to a node at depth d' + 1. For an ( n, k) linear block code, the trellis has n stages and the trellis is used to represent all the codewords of the code. Each distinct codeword corresponds to a distinct path in the trellis. We describe how to construct the trellis for an ( n, k) binary linear block code.

Consider the transpose of the ( n ? k)-by- n parity-check matrix H of an ( n, k) binary linear block code. Suppose that a code vector V is transmitted. In the presence of errors, the n-component received vector R may not be the same as the vector V and the product of R and H ^T may not be the all-zero vector. The product of R and H