# What is the trellis diagram for a linear block code?

For the convolutional codes there is so-called trellis diagram,
for which the definition is rather clear for me, however in mathematical sense is not.

I have heard that it can be defined for linear block codes also.
Linear codes have very simple mathematical meaning – just the linear subspaces
in $(F_q)^n$.
So I guess the “trellis” should also be something simple.

So what is the trellis for a linear block code ?

#### Solutions Collecting From Web of "What is the trellis diagram for a linear block code?"

This question is studied very extensively in Alex Vardy’s chapter in Handbook of Coding Theory. I describe the idea below.

To get a trellis for a linear block code $C$, we need to define something like a time axis for the positions of the individual symbols of all the codewords. So basically an ordering of the symbols that is already there: this is the first symbol, this is the second,…, this is the last. Later on we may want to change the ordering, but let’s fix one for now.

The trellis collects information about which beginnings of codewords can be matched with which endings in such a way that the end result will be a valid codeword. In the case of a liner code this translates into an algebraic formulation as follows.

Fix a point $i,0<i<n,$ on the time axis. Consider the so called initially trivial subspace $I_i(C)$ and finally trivial subspace $F_i(C)$ of $C$ defined by
$$I_i(C)=\{\vec{c}=(c_1,c_2,\ldots,c_n)\in C\mid c_j=0\ \text{for all}\ j\le i\}.$$
and
$$F_i(C)=\{\vec{c}=(c_1,c_2,\ldots,c_n)\in C\mid c_j=0\ \text{for all}\ j> i\}.$$
Let’s extend these definitions by declaring that $F_0(C)=I_n(C)=\{0\}$ and
$F_n(C)=I_0(C)=C$.
The key observations are that:

1. The sum of subspaces $I_i(C)+F_i(C)$ is direct, i.e. they intersect trivially.
2. If $\vec{c}\in C$, $\vec{c}_I\in I_i(C)$, $\vec{c}_F\in F_i(C)$ are arbitrary,
then the vector $\vec{c}+\vec{c}_I$ is a legal codeword that agrees with $\vec{c}$ up to and including the component $c_i$, and $\vec{c}+\vec{c}_F$ is a legal codeword that agrees with $\vec{c}$ from that point on, i.e. at positions $>i$. Furthermore, all the codewords with these properties are gotten in this way, because if two codewords agree up to and including (resp. from this point on), then their difference is in the initially trivial (resp. finally trivial) subcode.

So we can partition the code $C$ into cosets of the subspace $I_i(C)+F_i(C)$. Let us select a sequence of split points $0=i_0<i_1<i_2<\cdots<i_k=n$. Note that we may not use all the points as split points. With this data at hand we build a trellis for $C$ as follows. At split point $i_t$ we have the state-space
$$V_t(C)=C/(I_{i_t}(C)\oplus F_{i_t}(C).$$ We observe $V_0(C)$ and $V_k(C)$ are both trivial 0-dimensional spaces. These will give us a unique initial and final state respectively.

The trellis diagram is a directed graph. It has a vertex for each order pair $(t,a)$, with
$0\le t\le k$ and $a\in V_t(C).$
For each interval $t,t+1$, we define the subspace $T_t=I_{i_{t+1}}(C)\oplus F_{i_t}(C)$.
We then define a set of edges connecting the vertex $(t,a)$ and the vertex $(t+1,a’)$. These are in a bijective correspondence with cosets $\vec{c}+T_t$ such that
$\vec{c}\in a\cap a’$. The number of such edges is thus $|a\cap a’|/|T_t|.$
The edges of the graph are labelled, and the above edge is labelled with the
sequence of symbols $c_{i_t+1},c_{i_t+2},\ldots,c_{i_{t+1}}$. Observe that 1) if $a\cap a’=\emptyset$ there will be no edges from $(t,a)$ to $(t+1,a’)$, 2) all the codewords
in the coset $\vec{c}+T_t$ give the same sequence as labels.

What this amounts to is that for each codeword $\vec{c}\in C$ there is a unique path
from $(0,V_0(C))$ to $(k,V_k(C))$ such that at each split point $i_t$ the path passes thru
the vertex $(t,\vec{c}+I_{i_t}(C)\oplus F_{i_t}(C))$, and that it follows the edge
associated with $\vec{c}+T_t$ between those two vertices.
We can read the components of the codeword $\vec{c}$ by concatenating the labels of the edges along the path. Furthermore, it is not to hard to show that all the paths through the trellis represent valid codewords.

We can then decode using the Viterbi algorithm taking advantage of partial codewords shared by many words – exactly as in the case of convolutional codes.

The catch is that the number of either states or edges may easily be prohibitively large. For example, if systematic encoding is used with a $k$-dimensional code, then there are no shared sequences of $k$ first symbols among any codewords (because all those symbols are payload, and can be freely chosen by the user). This means that it this split point the initially trivial subspaces are all trivial, and consequently the state space may be very large (up to $k$-dimensional, possibly smaller). We can try and play the game of permuting the symbol positions. This is kind of a “black art”, and it is not guaranteed to reduce the size of the trellis significantly. Therefore this is not a magic tool allowing us to efficiently decode any linear code with the Viterbi algorithm.

Sorry about the residual garbage on the background. The figure shows a trellis of the extended binary linear Hamming code of length 16, rank 11 and minimum distance 4. The split points are at $i_0=0,i_1=4,i_2=8,i_3=12$ and $i_4=16$. The code is defined by the parity check matrix
$$H=\pmatrix{1111&1111&1111&1111\cr 1111&1111&0000&0000\cr 1111&0000&1111&0000\cr 1100&1100&1100&1100\cr 1010&1010&1010&1010\cr}.$$
As in all trellis the time axis runs from left to right. The vertices associated with a given split point are stacked on top of each other. Here all the edges are actually double edges, i.e. two parallel edges going from one vertex to another, the labels of the two parallel edges are always bitwise complements of each other. The finally trivial subcodes are spanned by
$$F_4=\langle 1111 0000 0000 0000\rangle,$$
$$F_8=F_4\oplus \langle 0000 1111 0000 0000, 0011 0011 0000 0000, 0101 0101 0000 0000\rangle,$$
$$F_{12}=F_8\oplus\langle 0000 0000 1111 0000, 1100 1010 0110 0000, 1010 0110 1100 0000\rangle,$$
and have respective dimensions 1,4,7. The initially trivial subcodes are
$$I_{12}=\langle 0000 0000 0000 1111\rangle,$$
$$I_8=I_{12}\oplus\langle 0000 0000 1111 0000, 0000 0000 1100 1100, 0000 0000 1010 1010\rangle,$$
$$I_4=I_8\oplus\langle 0000 1111 0000 0000, 0000 0110 0101 0011, 0000 0011 0110 0101\rangle,$$
with complementary dimension such that $\dim I_i\oplus F_i=8$ for all $i\in\{4,8,12\}$.
The words of this code are of the form $(a|b|c|d|)$, where each letter stands for a vector in $\mathbb{F}_2^4$, i.e. a group of 4 bits. The constraints are: $a+b+c+d$ must be either $0000$ or $1111$. The parities of the weights of the groups are either all odd or all even.

I’m a little rusty on this but let me give it a shot.

Block codes and convolutional codes are fundamentally different. Block codes generally do not have any “memory”, that is, the encoding of future words does not depend on the encoding of previous words.

This “memory” feature is one of the things that makes convolutional codes different. The second thing is that convolutional encoding takes place basically “one bit at a time” but block codes need an entire block to carry out the encoding step.

A trellis diagram is meant to capture the process of bitwise encoding by recording transitions between states, and the output produced as a function of that state and the input.

Since block linear codes do not have “states” and are not encoded bitwise, I don’t see (or don’t remember) how you can formulate a trellis diagram for a block linear code.

A Hasse diagram of the lattice of subspaces of $F_q^n$ is fine, but I don’t see any real connection to trellis diagrams.