- DSP log - http://www.dsplog.com -
Viterbi with finite survivor state memory
Posted By Krishna Sankar On July 27, 2009 @ 5:26 am In Coding | 10 Comments
In the post on Viterbi decoder [1] and soft input Viterbi decoder [2], we discussed a convolutional encoding scheme with rate 1/2, constraint length and having generator polynomial
and having generator polynomial
. If the number of uncoded bits is
, then the number of coded bits at the output of the convolutional encoder is
. 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 states, compute the path metric knowing the following.
3. Store the survivor predecessor state for each state.
4. Once we have processed 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
input bits can be decoded.
However, when the number of input uncoded bits is large, the memory requirements for a survivor state matrix of dimension
becomes impossible to manage.
To be able to decode with finite survivor memory, lets say we need to start the traceback at some time instant , where
is the decoding depth and
is the traceback depth.
The sequence of events are as follows:
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 .
Note: The literature of different architectures for survivor state management is vast and is not explored in this post.
At time instant , there are multiple ways to select the state to
From simulations, can identify the minimum value of traceback depth (), which results in performance comparable to infinite survivor path memory case. From simulations shown in the post on hard decision Viterbi decoder [1], we know that at
, results in a bit error rate of
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 corresponds to around 5 times the constraint length of
.
Additionally, as expected starting traceback with from the state with minimum pathmetric shows better performance than always starting at state 00.
Click here to download Matlab/Octave script for simulating bit error rate vs traceback for Eb/N0 = 4dB. [3]
Click here to download Matlab/Octave script for simulating BER for BPSK with convolotional coding with hard/soft decision Viterbi decoding and with finite survivor state memory [4]
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
Digital Communication: Third Edition, by John R. Barry, Edward A. Lee, David G. Messerschmitt [5]
Article printed from DSP log: http://www.dsplog.com
URL to article: http://www.dsplog.com/2009/07/27/viterbi-with-finite-survivor-state-memory/
URLs in this post:
[1] Viterbi decoder: http://www.dsplog.com/2009/01/04/viterbi/
[2] soft input Viterbi decoder: http://www.dsplog.com/2009/01/14/soft-viterbi/
[3] Matlab/Octave script for simulating bit error rate vs traceback for Eb/N0 = 4dB.: http://www.dsplog.com/db-install/wp-content/uploads/2009/07/script_bpsk_ber_vs_traceback_viterbi_decode.m
[4] Matlab/Octave script for simulating BER for BPSK with convolotional coding with hard/soft decision Viterbi decoding and with finite survivor state memory: http://www.dsplog.com/db-install/wp-content/uploads/2009/07/script_bpsk_ber_awgn_convolutional_code_soft_viterbi_decode_with_traceback.m
[5] Digital Communication: Third Edition, by John R. Barry, Edward A. Lee, David G. Messerschmitt: http://www.amazon.com/gp/redirect.html?ie=UTF8&location=http%3A%2F%2Fwww.amazon.com%2FDigital-Communication-John-R-Barry%2Fdp%2F0792375483&tag=dl04-20&linkCode=ur2&camp=1789&creative=9325
[6] Digital Communications by John Proakis: http://www.amazon.com/gp/redirect.html?ie=UTF8&location=http%3A%2F%2Fwww.amazon.com%2FDigital-Communications-John-Proakis%2Fdp%2F0072321113&tag=dl04-20&linkCode=ur2&camp=1789&creative=9325
[7] click here to SUBSCRIBE : http://www.feedburner.com/fb/a/emailverifySubmit?feedId=1348583&loc=en_US
Click here to print.
Copyright © 2007-2012 dspLog.com. All rights reserved. This article may not be reused in any fashion without written permission from http://www.dspLog.com.