Intro to Convolutional Coding — Part II
This post describes the decoding process of convolutional codes using the Viterbi algorithm. It continues my previous post on the subject, which presented these codes more generally and the encoding process.
The Decoding Problem
The decoding problem can be stated as finding the “best possible” sequence of transmitter states (or symbols), given a sequence of received bits. However, this definition is vague as there is no clear definition of what best means. The Viterbi algorithm finds the most likely sequence and is thus termed a maximum likelihood (ML) decoder.
Likelihood & Hamming Distance
The most likely transmitted sequence is related to hamming distance. The Hamming distance between two-bit sequences sums the XOR of the two sequences. For instance, the distance of C₁=1101001 and C₂=1100111 is: d(C₁, C₂)=3. However, for C₁ and C₃=1100001, d(C₁, C₃)=1. Therefore, if C₁ was received, C₃ is more likely the transmitted sequence as it implies less bit flips occurred. Conceptually, we inspect all possible codewords and decide according to the minimal weight to find the most likely transmitted sequence. That being said, this concept (which is utilized in syndrome decoding) is challenging as the length of a convolutional code is infinite.
Path Along A Trellis
The problem is resolved using the Viterbi algorithm, which uses the trellis representation of the code shown in the previous post. For instance, consider the following encoder:
The trellis representation of this code is shown below. A path along the trellis is shown in red, assuming an input sequence of 101100.
Viterbi decoder finds the most likely path along the trellis. Given a sequence of received bits, one can traverse the trellis. Each transition shown as a red arrow in the figure tells us another one of the original information-bearing bits (shown as a single bit along each arrow). The decoder maintains several possible paths and their accumulated errors in case errors occur. To avoid keeping all 2ᴺ possible paths for an N bits long sequence, only the more likely ones are maintained, while less likely ones are discarded along the way.
The Viterbi Decoder
The decoder uses two metrics, a branch metric, and a path metric. The branch metric measures the distance (Hamming distance is used for hard decoding) along each edge of the trellis between the received codeword and possibly transmitted codewords given a state and input. The figure below shows the branch metrics (in red), assuming the received codeword was 00. In black, you can see the inputs and corresponding new states.
The path metric is the sum of branch metrics along each path. If we look at the decoder at some time t+1, we note that it could have arrived there, only from two distinct states. Thus, if we don’t want to keep all states in mind, it would be best if we could discard one of them. Luckily we can. The decoder generally looks for the path with the smallest path metric. When discussing two paths leading into a particular state, we can discard the path that has the more significant path metric. Therefore, while decoding, we need to keep in mind only 2ᴸ paths, one leading into each state.
Eventually, we traverse the trellis (along with all received codewords) and choose the most likely path as the decoded path. If a pre-determined termination scheme is used, such as a zero-tailed termination, this can ease the choice of the final state. Algorithm iteration steps:
- Add the branch metric to the path metric for the old state.
- Compare the sum for paths entering the same new state.
- Select the path with the smallest metric, entering into each state as the survivor path.
In the end, choose the most likely path with the smallest path metric or by an apriori known termination scheme.
Sources
In writing this post, I used:
- MIT open courseware notes — encoding
- MIT open courseware notes — decoding
