Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

I am in trouble with Viterbi decoder for a while. I have some questions.

I need to decode messages from a continuous stream which is encoded without resetting the state metrics. Each message starts with a preamble, but since these preambles are also encoded as part of the stream, there is actually no message concept before decoding.

1) Encoding without resetting the metrics means that the data is encoded as one big message, doesn't it?

2) The decoder I am using works frame by frame, without storing and re-using the state metrics. So, I am adding a prefix and a postfix from the previous and next messages.

(last n bits of the previous encoded message + message to be decoded + first m bits of the next encoded message)

I hopefully expect that the prefix works as a training data, and the state metrics after the prefix are ready to decode the actual message. In order to decode the last bits of the message correctly, the postfix is used. I suppose using the data from the next message as the postfix is better than adding zeros or random bits, because adding zeros or random numbers may cause a wrong path affecting not only the decoding of the postfix but also of the actual message.

Is this procedure reasonable? Is it common and does it have a name such as sliding windows?

3) How many bits should I use as the prefix and postfix? (I cannot set the traceback length and see if it is pre-set somewhere. The code rate is 1/2 and constraint length is 7.)

Thanks in advance.

share|improve this question
1  
What do you mean by "adding a prefex and a postfix from the previous and next messages"? Are you doing that at the transmitter? What exactly do you mean by "prefix" and "postfix"? –  Jim Clay Jan 18 '13 at 14:49
    
@Jim Clay I am not doing anything at the transmitter. What I mean is this: In order to decode a portion of k bits all correctly, I add the last n bits of the previous message as prefix and the first m bits of the next message as postfix. So I give (n + k + m) bits to the decoder as input. The decoder outputs (n/2 + k/2 + m/2) bits, and I take the middle k/2 portion as my decoded message. First n/2 and last m/2 bits are not trustworthy. –  groove Jan 18 '13 at 15:05

1 Answer 1

Since the decoder that you are working with is a black box, yes, adding prefixes and postfixes to the stream to "window-ize" it is appropriate. The pre and postfixes need to be the actual data from the previous and post windows, and they need to be at least as long as the traceback depth. If you do this and get rid of the result bits that correspond to the prefixes and postfixes, then you should do fine.

In a normal situation you would not need to add any postfixes or prefixes. There are only two things you need to do to handle continuous streams of Viterbi-encoded data.

1) occasionally check the state metrics and lower them when all of them get "high". This works because the only thing that matters is the difference between the state metrics, not their absolute value. An easy way to do this is to check if all of them are equal to or above half the maximum state metric value. If they are, subtract half the maximum value from all of them.

2) You have to do tracebacks while you are decoding. This is do-able in both FPGA's and microprocessors (it's actually quite easy in microprocessors). Every $N$ transitions (pick an $N$ that works for your architecture) you do a traceback and output $N$ bits. You have to go back through $M$ bits ($M$ being equal to the traceback depth) before you get to the $N$ bits that you will output.

share|improve this answer
    
Thanks for your answer. I am using a DSP (TI C6474) and I cannot see/modify the state metrics. Also I cannot see what the traceback length is and modify it. Probably it is possible to perform these operations on this DSP, but I have not been able to do during the last a few weeks. So I am trying to utilize what I have with a reasonable approach. If I give only the actual bits to the decoder as input, first a few and last a few bits are not decoded correctly. So I add a prefix to learn the state metrics until the actual message. –  groove Jan 18 '13 at 16:04
    
And I add a postfix to decode the last portion of the message that cannot be decoded because of the shift in the beginning. Similar to the prefix, adding the postfix data from the stream will not lead to a wrong decision path since all these bits are encoded together. I suppose the length of the prefix and postfix should be equal to the traceback length. –  groove Jan 18 '13 at 16:08
1  
I see. As long as your prefix and postfix are at least as long as a reasonable traceback depth (can be longer) you should be able to get away with doing this. You will also have to get rid of the result bits that correspond to the prefix and postfix of course. –  Jim Clay Jan 18 '13 at 17:24
    
I have read somewhere that the traceback length should be at least 4 or 5 times (k-1), so if I choose 5*(k-1), I should add a total of 5*6*2*2=120 redundant bits to the encoded message. Still I am not sure if it is enough or not. –  groove Jan 18 '13 at 17:34
1  
It should be enough. If it's not, you can always increase it. –  Jim Clay Jan 18 '13 at 19:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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