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 ?

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.

• Great answer ! I have not yet got it all, let me think... May I ask for some comments to the picture: what Hamming code ? (7,4) ? Time axes is "X" or "Y", well I guess "X", but why then only 5 time moments ? – Alexander Chervov Jun 15 '12 at 14:02
• @Alexander: We get lower dimensional state-spaces by using a coarser time axis with ticks only at points $0,4,8,12,16$. And, yeah, $x$-axis is the time direction. (I deleted an earlier version of this comment, because I think it had an error in the numbers). – Jyrki Lahtonen Jun 15 '12 at 14:21
• For example at split point $6$ with the example code we have a $2$-dimensional $F_6$ and a $5$-dimensional $I_6$ leaving us with a 4-dimensional state-space and thus 16 states. A larger state space adds to the complexity of Viterbi decoding, but edge complexity also matters, so it is not clear cut. I selected this example partly for simplicity and regularity of the trellis. – Jyrki Lahtonen Jun 15 '12 at 14:24
• Sorry about not having the labels of the edges in the trellis. Couldn't squeeze them in :-( – Jyrki Lahtonen Jun 15 '12 at 14:25
• One way of better understanding the graph in my answer is the following. You see that the graph is divided into an upper half and a lower half. This reflects the constraint that all the four 4 bit segments of all the codewords have either odd or even weight. That the two halves won't cross over to the other side is a manifestation of this. One half has all even weight edge labels the other odd weight labels. – Jyrki Lahtonen Jun 15 '12 at 15:52

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.

• When encoding a block code using a generator matrix, you can also say that you are encoding "one bit at a time", because you won't be needing the value of an information carrying bit before you reach the first "1" on that row of the generator matrix. With elementary row operations you can always arrange things in such a way that those first "1" come at distinct column (but that may not be best!). The last "1" OTOH turns its row "off". This is what trellises of block codes do: you want as few rows to be simultaneously "active" as possible. The black art is to find the best column permutation. – Jyrki Lahtonen Jun 15 '12 at 16:13
• @JyrkiLahtonen If you are saying there is a trellis diagram for an ordinary block code, then can you explain, please? – rschwieb Jun 15 '12 at 16:30
• For linear block codes there is. See my answer. It differs markedly from those of the convolutional codes in that the appearance of the directed graph is "time-dependent." The trellis works with fractional parts of a block. The simplest example is the $(n,n-1,2)$ parity check code. There we can equate "state" with "the running sum of information bits". IOW after each information bit there are two possible states. The value of the last bit (=the parity check bit) depends on the state at that point. The common feature is: legal codewords = paths thru the trellis. – Jyrki Lahtonen Jun 15 '12 at 16:42
• @JyrkiLahtonen I see... that is quite different, but has that common thread. – rschwieb Jun 15 '12 at 17:53