1

With a 1/2-rate convolutional encoder, $n$ bits are encoded into $2n$ symbols.

Assume we have a long encoded stream such as $[... s_0, s_1, s_2, s_3, s_4, s_5, s_6, s_7, s_8, s_9, ..., s_{100}, ...]$. I want to extract a small portion from the middle of it, and decode it.

Starting from the symbol $s_1$, the data is decoded as follows:

$[s_1, s_2, s_3, s_4, s_5, s_6, s_7, s_8, ..., s_{100}]$ ---Viterbi Decoder---> $[b_1, b_2, b_3, b_4, ..., b_{50}]$

What happens if we start from $s_2$?

$[s_2, s_3, s_4, s_5, s_6, s_7, s_8, s_9, ..., s_{100}]$ ---Viterbi Decoder---> $[b_1', b_2', b_3', b_4', ..., b_{49}']$

Using Matlab's vitdec, starting from $s_1$ or $s_3$ produces the same result where the only difference is that $s_3$ starts from the second bit. But starting from $s_2$ produces a totally different vector, there is no small pattern in common between this and the results obtained when starting from $s_1$ or $s_3$.

Is this the expected result? Do we have to do symbol alignment to get correct results? Since the preamble in the data is encoded too, I do not know where to start decoding.

groove
  • 185
  • 7
  • 1
    Why is the preamble encoded? – Jim Clay Mar 05 '13 at 16:53
  • @Jim Clay In 'satellite based augmentation systems' data the preamble is encoded, I do not know why. Moreover, I do not know how to decode the stream properly since it is not clearly stated in the standards document. In a paper I have seen that all messages are encoded together as if there is only one big message. After decoding, I look for a preamble by correlation or simple pattern matching. – groove Mar 05 '13 at 18:34
  • 1
    " After decoding, I look for a preamble by correlation or simple pattern matching" Unfortunately, if the input is mis-framed, the output is completely garbled, as you have discovered already, and so looking for a preamble usually fails to work. – Dilip Sarwate Mar 05 '13 at 18:53
  • @DilipSarwate So I re-run with a one-symbol-shifted stream, decode, and look for the preamble, again. Checking the path metrics seems to be a better solution, but in my implementation, the embedded design does not allow seeing the metrics (at least I cannot see). Lack of documentation available, the rest of the design which I have to fit and my incompetencies force me to look for workarounds for nearly everything. – groove Mar 06 '13 at 07:51
  • 2
    @groove Since the path metrics are not available, I think that running the decoder again with input stream shifted by one bit is the way to go whenever the sync word is not found in the initial decoding. If it is a $(n,k)$ code with $n > 2$, then additional shifts might be need to be tried. But one of your other comments seems to indicate that you have a $(2,1)$ code, and so two decodings will, hopefully, result in the sync word being found in one of them. – Dilip Sarwate Mar 06 '13 at 16:58

2 Answers2

2

I find it surprising that it didn't matter where you started. Normally incorrect symbol alignment will completely change your results. The usual method for determining the correct alignment (assuming you don't have other information like a Frame Alignment Word to help you figure it out) is to try both possible phases and see which produces a lower path metric.

You can, by the way, do the same when the code is punctured, you just have more phases to try.

Jim Clay
  • 12,101
  • 31
  • 55
  • It matters actually. Starting from $s_1$ produces an output starting from $b_1$ while starting from $s_3$ produces the output starting from $b_2$. The latter only lacks the first bit. In the other case, starting from $s_2$ results a different output and $s_2$ and $s_4$ have a similar relation as $s_1$ and $s_3$. – groove Mar 05 '13 at 18:43
  • I suppose I should start from a random symbol and look for a preamble and do CRC. If I cannot find any, I should turn back and start from the next symbol. This procedure doubles the computational work, but I understand that there is no easier way. – groove Mar 05 '13 at 18:48
  • 1
    Yes, that sounds like the right way to go and will definitely work. There may be an even easier way, though. If the encoder is reset at the beginning of the preamble and the preamble bits don't change, then the encoded preamble will always be the same. You could then search for the encoded preamble and symbol align that way. – Jim Clay Mar 06 '13 at 13:45
1

I do not have any information about MATLAB's vitdec program and questions about vitdec are off-topic here anyway, but in general, if the SNR is good, a Viterbi decoder can be used to detect a mis-framing of the incoming signal reasonably reliably. If the SNR is not very good, the method described below can lead to lots of false alarms that the incoming signal is mis-framed.

Given a received sequence (of bits or soft decisions) the Viterbi decoder for a $(n,k)$ convolutional code of constraint length $\nu$ finds the maximum-likelihood path (which corresponds to the maximum-likelihood codeword) through the code trellis by computing iteratively the maximum-likelihood path to each of the $2^{\nu}$ nodes in the trellis at depth $j$. Now, assuming that the SNR is good, and there has not, in the immediate past, been an unusually long (or unusually strong) burst of noise (none in progress right now, either!) one of the paths typically has much larger log-likelihood than most of the other paths. Furthermore, when the add-compare-select process is choosing the best path to a node at the next level, in most cases, one path is a clear winner over the others. On the other hand, if the sequence is mis-framed, then all the log-likelihoods of paths at depth $j$ are not only comparable, but also very negative. Also, in the add-select-compare process at the nodes at the next depth, hardly any of the paths look particularly appealing, and the system chooses the best of a bad lot. Thus, repeated absence of good choices and universally low path metrics can be taken as an indication that mis-framing has occurred. Recovery depends on the rest of the system implemenation. Perhaps there is enough time to re-run the incoming signal with a different framing. Or the mis-framing can be corrected by some bit-stuffing or bit-deletion of the signal as it continues to come in, and it is left to the next higher level to request a re-transmission of the mis-framed portion, etc.

Dilip Sarwate
  • 20,349
  • 4
  • 48
  • 94