Viterbi algorithm explained using Trellis diagram

INTRODUCTION

The Viterbi algorithm is an iterative method used to find the most likely sequence of states according to a pre-defined decision rule related to the assignment of a probability value (or a value proportional to it).

In the current post, an example of the Viterbi algorithm is shown using the Trellis diagram. The Trellis diagram is a directed tree in which the edges represent transitions from different states into others of the next timestep. The idea is very similar to the state-transition table.

Both concepts are used in the telecommunication field, e.g. in the context of sequence detection.

An empty Trellis diagram with 4 possible states (00, 10, 01, 11) may look like the following, with the assumption of the initial state being 00.

Partial results are written under “MIN”. Such values are propagated through the path and summed up along it. “MIN” values are given (in our examples) as minimum of all incoming propagated values. In this case, each state receives not more than 1 value, but in general, if more values reach the same state, the minimum is chosen.

The above shown transitions could also be represented (without timesteps) by the following state diagram:

EXAMPLE #1

In this example we are going to use the above shown Trellis diagram to apply a Viterbi Algorithmus with the following decision rule:

The vector [2 3 1] is the impulse response vector of the telecommunication channel, describing its transmission behaviour. This rule is typical for a Maximum-Likelihood detector, which selects the most likely bit according to the nearest expected value (given by the scalar product of our data vector with the impulse response vector) to the received value (namely the i-th element of the received vector r).

The received data vector is the following:

As first sample value, we may compute the red highlighted state (10) input value contribution from the state 00. To do this, we sum up the old value (in this case 0) to the new value computed with the mentioned decision rule, using the green highlighted information.

Since this result is the only value for the state 10 at i=2, the “MIN” value is the same. Under “PATH” we write the corresponding transition value, in this case, 1.

Same logic for another transition, for example from 10 to 01 at final timestep i=3.

At the very end of this process, the received vector r will be mapped to the sequence corresponding to the state with the minimum propagated value, in this case [0,  0], hence to the most likely according to our decision rule.

EXAMPLE #2

Using the same vectors but with a slightly different state transition we get a new Trellis diagram. In this case we consider a general 2 bit state Z which is not related to the context of the data transmission (otherwise the connection between state 10 at i=2 and itself at i=3 would not make sense by using 0 as current data bit, which should lead to the new state 01 instead). Also in this case, the vector [2.49, -0.5] will be mapped to [0, 0].