(3 votes, average: 5.00 out of 5)

# Viterbi with finite survivor state memory

by on July 27, 2009

In the post on Viterbi decoder and soft input Viterbi decoder, we discussed a convolutional encoding scheme with rate 1/2, constraint length $K=3$ and having generator polynomial $K=3$ and having generator polynomial $\left[ 7, 5\right]_8$. If the number of uncoded bits is $N$, then the number of coded bits at the output of the convolutional encoder is $2(N+K-1)$ . Decoding the convolutionaly encoded bits by Viterbi algorithm consisted of the following steps.

1. For group of two bits, compute Hamming distance or Euclidean distance (for hard decision or soft decision respectively)

2. For each of the $2^{K-1}=4$ states, compute the path metric knowing the following.

• Each state can be reached from only two previous states (out of the 4 possible states).
• For each possible transition, compute the branch metric by adding the path metric of the previous state to the Hamming/Euclidean distance of the transition
• Select the branch metric which is minimum among the two values and store it as the path metric for the current state

3. Store the survivor predecessor state for each state.

4. Once we have processed $2(N+K-1)$ received bits, we know that the convolution encoder has reached state 00. We start traceback from state 00, and given that we know the current and previous state, the $N$ input bits can be decoded.

However, when the number of input uncoded bits $N$is large, the memory requirements for a survivor state matrix of dimension $(2^{K-1})\mbox{ x } (N+K-1)$ becomes impossible to manage.

## Traceback with finite survivor memory

To be able to decode with finite survivor memory, lets say we need to start the traceback at some time instant $D+TB$ , where

$D$ is the decoding depth and

$TB$ is the traceback depth.

The sequence of events are as follows:

• At time instant $D+TB$, we start the traceback and continue tracing back through the survivor path $TB$ times. Once we are done with the traceback, we start estimating the $D$ decoded bits knowing the current state and previous state.
• Similarly, we again start the traceback at time $2D+TB$, do traceback $TB$ times and then decode bits from $2D$ to $D$.
• Once we reach the end of the input sequence at time instance $N+K-1$, we know that trellis has converged to state00 and then we do demodulation with traceback.

Figure: Viterbi traceback with finite survivor memory

Given that traceback speed is equal to storing the speed incoming coded bits, we can implement the above algorithm with a memory of $D+2TB$.

Note: The literature of different architectures for survivor state management is vast and is not explored in this post.

### Selecting start state for traceback

At time instant $D+TB$, there are multiple ways to select the state to

• Always start from a defined state (for example state 00)
• Start from the state which has the minimum path metric

From simulations, can identify the minimum value of traceback depth ($TB$), which results in performance comparable to infinite survivor path memory case. From simulations shown in the post on hard decision Viterbi decoder, we know that at $\frac{E_b}{N_0}=4\mbox{dB}$, results in a bit error rate of $10^{-2}$

Figure: BER vs traceback depth at Eb/N0 = 4dB

From simulations it has been observed that doing traceback depth of around 15 ensures that the obtained BER with finite survivor state memory is close to the BER with infinite survivor state memory. Note that $TB=15$ corresponds to around 5 times the constraint length of $K=3$.

Additionally, as expected starting traceback with from the state with minimum pathmetric shows better performance than always starting at state 00.

## Simulation results

Warning: This simulation took around 10hrs to complete. Am thinking that I will move to C code for simulations involving lots of for-loops.

Figure: BER for BPSK with convolutional coding with finite survivor state memory

## Reference

Digital Communication: Third Edition, by John R. Barry, Edward A. Lee, David G. Messerschmitt

D id you like this article? Make sure that you do not miss a new article by subscribing to RSS feed OR subscribing to e-mail newsletter. Note: Subscribing via e-mail entitles you to download the free e-Book on BER of BPSK/QPSK/16QAM/16PSK in AWGN.

malathi.p August 20, 2012 at 12:58 am

in this communication very interest,,,,,,,,

Wig December 7, 2009 at 7:00 pm

Mr. Krishna:

Because I’m trying to understand these math equations and describe in this
article, so I confused why some equations can’t display.

thanks~

Krishna Sankar December 8, 2009 at 5:31 am

@Wig: I checked the post. From a quick look, I see that all the equations are displayed. Am I missing something?

Bill Cassidy February 27, 2010 at 6:23 am

@Wig, @Krishna, some of the math type images are from URIs such as http://www.dsplog.com/2009/07/cgi-bin/mimetex.cgi?D+2TB which should link to http://www.dsplog.com/cgi-bin/mimetex.cgi?D+2TB.

Krishna Sankar March 30, 2010 at 5:28 am

@Bill Cassidy: Yes, thanks. I have fixed the errors.

Wig November 24, 2009 at 8:32 am

Hello Mr. Krishna

Why some equations can’t display??

etc.

best regard! Wig

Krishna Sankar December 7, 2009 at 4:21 am

@Wig: Well, remove ’2009/07′ from the urls. But, why are you trying this?

rajesh August 24, 2009 at 8:16 am

hi
i have tried this viterbi decoding with finite survivor state memory.but it is giving error at function conv() at the starting of program it self.