Houjun Liu

SU-ENGR76 MAY232024

Convolutional Code

A Convolutional Code, at each time \(j\), takes bit \(b_{j}\) and output two bits \(p_{2j-1}\), \(p_{2j}\), by using \(b_{j}\) and the previous two its \(b_{j-1}\) and \(b_{j-2}\).

Working Example

Consider that if you have \(k\) bits to communicate to the receiver:

\begin{equation} b_1, b_2, \dots, b_{k} \end{equation}

Codewords/Output sequence:

\begin{equation} p_1, p_{2}, \dots \end{equation}

Let we have some sequence of \(k\) input bits

\begin{equation} j = 1, \dots, k \end{equation}

then, for every input bit, we generate two output bits:

\begin{equation} p_{2j-1} = b_{j} \oplus b_{j-1} \oplus b_{j-2} \end{equation}

\begin{equation} p_{2j} = b_{j} \oplus b_{j-2} \end{equation}

if we are at \(j=1\), then we assume that \(b_{j-1} = b_{j-2} = 0\).

Shift Register

So you can encode this in a streaming fashion, and shift them off as you go


The Convolutional Code, then, is essentially a finite state machine: whereby the last two bits are essentially the “state” of the machine used for the output. \((b_{j-1}, b_{j-2})\). The input would be \(b_{j}\), and the output is \(p_{2j-1}, p_{2j}\).

During each action \(b_{j}\), we essentially perform the “shift” operation.

Therefore, you can draw it in terms of a finite state diagram.


Now, consider rolling out finite state machine over time: make a grid of \(j\) on the x axis, and state on y axis. Then, you can trace possible lines connecting everything.

We can encode any encoding process as a PATH is the rollout trellis.

This could also help us perform decoding, because we can spot which edge our scheme traveled down.

Viterbi Decoding

bottom-up DP

  1. go through your edges, calculating Hamming Distance of each edge of your trellis’ decoding and the one you recieved; replace each edge with that distance
  2. edit distance minimize lol through the path to solve (i.e. run dijikstra on these edges)