# Decoding final bits with viterbi

I'm writing a viterbi decoder and I'm rather confused about the correct process of decoding the final k bits for a kth order convolutional filter.

For the bulk of the message, my process considers the 0-successor and 1-successor of every state, that is, the resulting shift register state found by shifting a 0 in or a 1 in, respectively. Both of these successors share a least-error ancestor found by the dynamic programming step in the Viterbi algorithm.

For the last k bits, we know that the encoder shifted in 0s in order to flush out the payload and reset to the 0 state. I can confirm this is the case because I've also written the encoder. So, when I get to this part of the message, my decoder only considers 0-successors. I think this is all I can do with this information, but I feel like I'm possibly missing some extra info that would help recover the message.

What I'm discovering in reality is that unrecoverable errors are far, far more likely to occur in the final k bits of the message leading up to these 0 flush bits. For example, if my decoded message is 256 bytes long, and I inject errors at a rate of 3%, I find that 15% of the unrecovered errors occur in the last byte.

To some extent, I might expect this to be the case as there aren't additional bits left to help the Viterbi best path converge. I'm using a convergence length of 5k, or 35 decoded bits for a 7th order filter. Should I just expect that without a padding of 35 bits, the end of my message is more likely to receive errors? Or should I keep looking for a bug in my decoder implementation? In practice, is it common to add additional payload bits to help viterbi converge?

• Are you tracing back from the zero state when you do the traceback? – Jim Clay Apr 27 '16 at 21:00
• Jim, that's correct. I am actually explicitly setting the 0 state as the best state at the end of the process. Also, I've done a fair amount of printing/debugging to confirm that on the final iteration, all that's left is the 0 state. On the iteration before that, all that are left are 0 and the state with just the highest order bit (e.g. the oldest bit) set. Given how much state is produced by Viterbi it's hard for me to confirm absolutely that this is working but to my knowledge that is how my implementation is working. – Brian Armstrong Apr 27 '16 at 21:27