Intereting Posts

Does there exist an unbounded function that is uniformly continuous?
Why are the continued fractions of non-square-root numbers ($\sqrt{x}$ where $a>2$) not periodic?
Evaluate $\lim_{x \to 1} \frac{\sqrt{x} -1}{\sqrt{x} -1}$
Product of two compact topological spaces is compact.
Conjectured compositeness tests for $N=b^n \pm b \pm 1$
Classification of Proper Maps between domains in $\mathbb{R}^n$
Proving definition of norms induced by vector norms
Jacobian matrix
General Cholesky-like decomposition
Solve $f(x) = \lambda \int\limits_{0}^1(\max(x,t)+xt)f(t)dt$
How can you show there are only 2 nonabelian groups of order 8?
Component of a vector perpendicular to another vector.
Evaluating the sum $1\cdot 10^1 + 2\cdot 10^2 + 3\cdot 10^3 + \dots + n\cdot 10^n$
Functions determine geometry … Riemannian / metric geometry?
1 to the power of infinity, why is it indeterminate?

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 ?

- Understanding Reed-Solomon as it applies to Shamir secret sharing
- The sum of a polynomial over a boolean affine subcube
- Calculating CRC by long division: How to decide the top number of long division?
- Can all linear code be adapted so that the first bits of the encoded message are the bits from the original message?
- What is the difference between the sphere and projective space?
- Cryptography and Coding Theory

- The sum of a polynomial over a boolean affine subcube
- How is this possible to convert a long string to a number with less characters?
- Reed Solomon Polynomial Generator
- How to find all the coset leaders? (follow-up to a previous question)
- What requirements should a CRC polynomial satisfy?
- What is necessary to exchange messages between aliens?
- Good textbooks for lattice and coding theory
- An easy reference for genetic algorithm
- Using Extended Euclidean Algorithm to find multiplicative inverse
- Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?

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:

- The sum of subspaces $I_i(C)+F_i(C)$ is direct, i.e. they intersect trivially.
- 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.

- Proving $\sum\limits_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$
- Hamel basis for $\mathbb{R}$ over $\mathbb{Q}$ cannot be closed under scalar multiplication by $a \ne 0,1$
- Integration method for $\int_0^\infty\frac{x}{(e^x-1)(x^2+(2\pi)^2)^2}dx=\frac{1}{96} – \frac{3}{32\pi^2}.$
- Why is a raised to the power of Zero is 1?
- Finding the remainder of $11^{2013}$ divided by $61$
- If $f(x)\to 0$ as $x\to\infty$ and $f''$ is bounded, show that $f'(x)\to0$ as $x\to\infty$
- Is Pythagoras the only relation to hold between $\cos$ and $\sin$?
- Let $p=(5,0,-4)$ and $v \in T_{(5,0,-4)}M$. Compute $(F^{*}\omega)_p(v)$.
- Can any integer can be written as the sum of 8 integer cubes?
- Intuition behind $dx \wedge dy=-dy \wedge dx$
- Does the little-oh relation remain if $f(x)$ and $g(x)$ both integrate or differentiate?
- Why bother with Mathematics, if Gödel's Incompleteness Theorem is true?
- Why is a strictly monotonic mapping between intervals continuous?
- Why is $10\frac{\exp(\pi)-\log 3}{\log 2}$ almost an integer?
- endomorphism as sum of two endomorphisms (nilpotent and diagonalizable)