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?

  • $\begingroup$ Are you tracing back from the zero state when you do the traceback? $\endgroup$ – Jim Clay Apr 27 '16 at 21:00
  • $\begingroup$ 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. $\endgroup$ – Brian Armstrong Apr 27 '16 at 21:27

You do not need any additional bits to help the decoder converge. There should be no need for convergence at the boundaries, because the start and end states are completely known (the all zeros state) so there is no guessing involved.

If you are getting more errors at the end it is likely due to a bug in the decoder.

  • $\begingroup$ I see. I'll keep debugging, then. I've also checked libfec's behavior, and it seems libfec also exhibits some weakness to errors in the final byte, although to a lesser extent. I'd say it's far more likely for libfec to have errors there than anywhere else, though. $\endgroup$ – Brian Armstrong Apr 29 '16 at 19:37
  • $\begingroup$ Hmm. Strange. I honestly don't know why that would be. $\endgroup$ – Jim Clay Apr 30 '16 at 5:26
  • $\begingroup$ Ok, you were correct. Embarrassingly, I was leaving a final trailing 0 off from my encoder. It seemed to me that I was fully flushing the shift register but I was apparently missing a final state. And since libfec doesn't have an encoder, I had to use mine to test it, which explains the behavior appearing in both decoders. $\endgroup$ – Brian Armstrong May 2 '16 at 23:35
  • $\begingroup$ I'm glad you found it. $\endgroup$ – Jim Clay May 3 '16 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.