Viterbi 'synchronization'?

   Hello,

this is almost a philosofical questions, but I couldn't find an answer on
the web, so I'm asking here.

I am trying to decode a stream of convolutionary coded symbols (R=1/2;
K=7) with Viterbi and everything runs fine. The encoded makes from one bit
two symbols, so the encoded stream contains these alternating symbols (1st,
2nd, 1st, 2nd, 1st, 2nd, etc.).

When I pass the stream to the viterbi starting with 1st symbol (1st, 2nd,
1st, 2nd, ...), the stream gets decoded well and the viterbi error is low.
But when I pass the stream to the viterbi starting with 2nd symbol (2nd,
1st, 2nd, ...) then the error is high and the decoded bits are useless.
This is logical. 

On the real stream of symbols I can't tell if I started on the first or on
the second symbol, so from outside it looks like it works in the 50% of the
times, and that it doesn't work in the other 50% of the times. 

So my question is: is there some way to tell if I've started on the right
symbol (on the 1st); or that I've started on the wrong symbol (on the 2nd)
and that I should skip one symbol to get back on the 1st symbol?

The way I'm doing it now is that I'm checking the viterbi error and if
it's too high, then I skip one symbol and try again... This works, but it
doesn't seem right to me.

Thank you for any replies ;)
   Jookie (M. Nohaj)

On Aug 7, 7:28 am, "jookie" <j...@kie.sk> wrote:
>    Hello,
>
> this is almost a philosofical questions, but I couldn't find an answer on
> the web, so I'm asking here.
>
> I am trying to decode a stream of convolutionary coded symbols (R=1/2;
> K=7) with Viterbi and everything runs fine. The encoded makes from one bit
> two symbols, so the encoded stream contains these alternating symbols (1st,
> 2nd, 1st, 2nd, 1st, 2nd, etc.).
>
> When I pass the stream to the viterbi starting with 1st symbol (1st, 2nd,
> 1st, 2nd, ...), the stream gets decoded well and the viterbi error is low.
> But when I pass the stream to the viterbi starting with 2nd symbol (2nd,
> 1st, 2nd, ...) then the error is high and the decoded bits are useless.
> This is logical.
>
> On the real stream of symbols I can't tell if I started on the first or on
> the second symbol, so from outside it looks like it works in the 50% of the
> times, and that it doesn't work in the other 50% of the times.
>
> So my question is: is there some way to tell if I've started on the right
> symbol (on the 1st); or that I've started on the wrong symbol (on the 2nd)
> and that I should skip one symbol to get back on the 1st symbol?
>
> The way I'm doing it now is that I'm checking the viterbi error and if
> it's too high, then I skip one symbol and try again... This works, but it
> doesn't seem right to me.
>
> Thank you for any replies ;)
>    Jookie (M. Nohaj)


Usually in a protocol, there is some means for word sync. I.e., there
is a header that you sync to. Are you working with an in use protocol,
or are you experimenting eith a protocol of your own design?

Clay

>On Aug 7, 7:28 am, "jookie" <j...@kie.sk> wrote:
>>    Hello,
>>
>> this is almost a philosofical questions, but I couldn't find an answer
on
>> the web, so I'm asking here.
>>
>> I am trying to decode a stream of convolutionary coded symbols (R=1/2;
>> K=7) with Viterbi and everything runs fine. The encoded makes from one
bit
>> two symbols, so the encoded stream contains these alternating symbols
(1st,
>> 2nd, 1st, 2nd, 1st, 2nd, etc.).
>>
>> When I pass the stream to the viterbi starting with 1st symbol (1st,
2nd,
>> 1st, 2nd, ...), the stream gets decoded well and the viterbi error is
low.
>> But when I pass the stream to the viterbi starting with 2nd symbol
(2nd,
>> 1st, 2nd, ...) then the error is high and the decoded bits are
useless.
>> This is logical.
>>
>> On the real stream of symbols I can't tell if I started on the first or
on
>> the second symbol, so from outside it looks like it works in the 50% of
the
>> times, and that it doesn't work in the other 50% of the times.
>>
>> So my question is: is there some way to tell if I've started on the
right
>> symbol (on the 1st); or that I've started on the wrong symbol (on the
2nd)
>> and that I should skip one symbol to get back on the 1st symbol?
>>
>> The way I'm doing it now is that I'm checking the viterbi error and if
>> it's too high, then I skip one symbol and try again... This works, but
it
>> doesn't seem right to me.
>>
>> Thank you for any replies ;)
>>    Jookie (M. Nohaj)
>
>
>Usually in a protocol, there is some means for word sync. I.e., there
>is a header that you sync to. Are you working with an in use protocol,
>or are you experimenting eith a protocol of your own design?
>
>Clay


I'm working with an in use protocol, which has a the Attached Sync Marker
(ASM) defined, but I thought that it couldn't be used, because even the
ASM was convolutionary coded - the original stream was sliced to packets,
then it had the ASM attached, then it was convolutionary coded, so the
conv. coded ASM can be always different (when it follows some other coded
bits, the conv. coder can be in a different state every time, so the conv.
coded ASM may become a different stream of symbols) - am I right or wrong?
AFAIK, the ASM is used for the synchronization after the the viterbi
decoding, before deramdomization...

This is just my theory, please correct me if I'm wrong....

Jookie

You take the Viterbi decoded output and you re-encode it with R=1/2 K=7 
(identical to the source encoder). In parallel, you take the input stream of 
the encoder and delay it by the transport delay of the decoder/encoder 
cascade. Then you compare both streams (input stream and decoded/re-encoded 
stream) with an XOR operation. When you are out of sync, the match is very 
poor. When you are in sync, the match is very good. In addition when in 
sync, this scheme gives you an estimate of the error rate on the channel 
prior the Viterbi decoding process.

LM

"jookie" <joo@kie.sk> wrote in message 
news:OJadnT_T7-vFyiXbnZ2dnUVZ_tijnZ2d@giganews.com...
>   Hello,
>
> this is almost a philosofical questions, but I couldn't find an answer on
> the web, so I'm asking here.
>
> I am trying to decode a stream of convolutionary coded symbols (R=1/2;
> K=7) with Viterbi and everything runs fine. The encoded makes from one bit
> two symbols, so the encoded stream contains these alternating symbols 
> (1st,
> 2nd, 1st, 2nd, 1st, 2nd, etc.).
>
> When I pass the stream to the viterbi starting with 1st symbol (1st, 2nd,
> 1st, 2nd, ...), the stream gets decoded well and the viterbi error is low.
> But when I pass the stream to the viterbi starting with 2nd symbol (2nd,
> 1st, 2nd, ...) then the error is high and the decoded bits are useless.
> This is logical.
>
> On the real stream of symbols I can't tell if I started on the first or on
> the second symbol, so from outside it looks like it works in the 50% of 
> the
> times, and that it doesn't work in the other 50% of the times.
>
> So my question is: is there some way to tell if I've started on the right
> symbol (on the 1st); or that I've started on the wrong symbol (on the 2nd)
> and that I should skip one symbol to get back on the 1st symbol?
>
> The way I'm doing it now is that I'm checking the viterbi error and if
> it's too high, then I skip one symbol and try again... This works, but it
> doesn't seem right to me.
>
> Thank you for any replies ;)
>   Jookie (M. Nohaj)
>
> 

>You take the Viterbi decoded output and you re-encode it with R=1/2 K=7 
>(identical to the source encoder). In parallel, you take the input stream
of 
>the encoder and delay it by the transport delay of the decoder/encoder 
>cascade. Then you compare both streams (input stream and
decoded/re-encoded 
>stream) with an XOR operation. When you are out of sync, the match is
very 
>poor. When you are in sync, the match is very good. In addition when in 
>sync, this scheme gives you an estimate of the error rate on the channel

>prior the Viterbi decoding process.
>
>LM


Hmm, seems like a good method! Is it used in some system? And what about
the Att. Sync. Marker?

Jookie

"jookie" <joo@kie.sk> wrote in message
news:OJadnT_T7-vFyiXbnZ2dnUVZ_tijnZ2d@giganews.com...
>    Hello,
>
> this is almost a philosofical questions, but I couldn't find an answer on
> the web, so I'm asking here.
>
> I am trying to decode a stream of convolutionary coded symbols (R=1/2;
> K=7) with Viterbi and everything runs fine. The encoded makes from one bit
> two symbols, so the encoded stream contains these alternating symbols
(1st,
> 2nd, 1st, 2nd, 1st, 2nd, etc.).
>
> When I pass the stream to the viterbi starting with 1st symbol (1st, 2nd,
> 1st, 2nd, ...), the stream gets decoded well and the viterbi error is low.
> But when I pass the stream to the viterbi starting with 2nd symbol (2nd,
> 1st, 2nd, ...) then the error is high and the decoded bits are useless.
> This is logical.
>
> On the real stream of symbols I can't tell if I started on the first or on
> the second symbol, so from outside it looks like it works in the 50% of
the
> times, and that it doesn't work in the other 50% of the times.
>
> So my question is: is there some way to tell if I've started on the right
> symbol (on the 1st); or that I've started on the wrong symbol (on the 2nd)
> and that I should skip one symbol to get back on the 1st symbol?

There are two possible approaches:

1. Using some sort of synchronization marker to start the decoder properly.

2. Running the decoder from the 1st and from the 2nd bits and picking the
result with better metrics.

> The way I'm doing it now is that I'm checking the viterbi error and if
> it's too high, then I skip one symbol and try again... This works, but it
> doesn't seem right to me.

Actually this is a good approach if you can afford running two decoders
instead of one. There is no overhead for transmitting markers, and you can
synchronize starting from the arbitrary moment without waiting for marker.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

jookie wrote:
>    Hello,
> 
> this is almost a philosofical questions, but I couldn't find an answer on
> the web, so I'm asking here.
> 
> I am trying to decode a stream of convolutionary coded symbols (R=1/2;
> K=7) with Viterbi and everything runs fine. The encoded makes from one bit
> two symbols, so the encoded stream contains these alternating symbols (1st,
> 2nd, 1st, 2nd, 1st, 2nd, etc.).
> 
> When I pass the stream to the viterbi starting with 1st symbol (1st, 2nd,
> 1st, 2nd, ...), the stream gets decoded well and the viterbi error is low.
> But when I pass the stream to the viterbi starting with 2nd symbol (2nd,
> 1st, 2nd, ...) then the error is high and the decoded bits are useless.
> This is logical. 
> 
> On the real stream of symbols I can't tell if I started on the first or on
> the second symbol, so from outside it looks like it works in the 50% of the
> times, and that it doesn't work in the other 50% of the times. 
> 
> So my question is: is there some way to tell if I've started on the right
> symbol (on the 1st); or that I've started on the wrong symbol (on the 2nd)
> and that I should skip one symbol to get back on the 1st symbol?
> 
> The way I'm doing it now is that I'm checking the viterbi error and if
> it's too high, then I skip one symbol and try again... This works, but it
> doesn't seem right to me.
> 
> Thank you for any replies ;)
>    Jookie (M. Nohaj)
> 
> 

This is called "Node Synchronization" in some of the literature. Here 
are a couple references:

http://tmo.jpl.nasa.gov/progress_report/42-128/128E.pdf

"Node Synchronization for the Viterbi Decoder", G. Lorden & R.J. 
McEliece, IEEE Trans Comm, May 1984

John



John

>There are two possible approaches:
>
>1. Using some sort of synchronization marker to start the decoder
properly.


Hmm, this sounds just like what I'm looking for. Is there something on the
web that I can read? 

>2. Running the decoder from the 1st and from the 2nd bits and picking
the
>result with better metrics.

Isn't this the same as running two decoders at once? I don't realy run two
at once (just one), but when the error seems to be very high, then I shift
the input to the decoder in the next buffer which will be decoded.

Thank you for help, mr. Vassilevsky!

 Regards,
  Jookie

>This is called "Node Synchronization" in some of the literature. Here 
>are a couple references:
>
>http://tmo.jpl.nasa.gov/progress_report/42-128/128E.pdf
>
>"Node Synchronization for the Viterbi Decoder", G. Lorden & R.J. 
>McEliece, IEEE Trans Comm, May 1984



Great link. Thank you, John! I'll have to go through the document...

 Jookie

>You take the Viterbi decoded output and you re-encode it with R=1/2 K=7 
>(identical to the source encoder). In parallel, you take the input stream
of 
>the encoder and delay it by the transport delay of the decoder/encoder 
>cascade. Then you compare both streams (input stream and
decoded/re-encoded 
>stream) with an XOR operation. When you are out of sync, the match is
very 
>poor. When you are in sync, the match is very good. In addition when in 
>sync, this scheme gives you an estimate of the error rate on the channel

>prior the Viterbi decoding process.
>
>LM
>
>"jookie" <joo@kie.sk> wrote in message 
>news:OJadnT_T7-vFyiXbnZ2dnUVZ_tijnZ2d@giganews.com...
>>   Hello,
>>
>> this is almost a philosofical questions, but I couldn't find an answer
on
>> the web, so I'm asking here.
>>
>> I am trying to decode a stream of convolutionary coded symbols (R=1/2;
>> K=7) with Viterbi and everything runs fine. The encoded makes from one
bit
>> two symbols, so the encoded stream contains these alternating symbols 
>> (1st,
>> 2nd, 1st, 2nd, 1st, 2nd, etc.).
>>
>> When I pass the stream to the viterbi starting with 1st symbol (1st,
2nd,
>> 1st, 2nd, ...), the stream gets decoded well and the viterbi error is
low.
>> But when I pass the stream to the viterbi starting with 2nd symbol
(2nd,
>> 1st, 2nd, ...) then the error is high and the decoded bits are
useless.
>> This is logical.
>>
>> On the real stream of symbols I can't tell if I started on the first or
on
>> the second symbol, so from outside it looks like it works in the 50% of

>> the
>> times, and that it doesn't work in the other 50% of the times.
>>
>> So my question is: is there some way to tell if I've started on the
right
>> symbol (on the 1st); or that I've started on the wrong symbol (on the
2nd)
>> and that I should skip one symbol to get back on the 1st symbol?
>>
>> The way I'm doing it now is that I'm checking the viterbi error and if
>> it's too high, then I skip one symbol and try again... This works, but
it
>> doesn't seem right to me.
>>
>> Thank you for any replies ;)
>>   Jookie (M. Nohaj)
>>
>> 
>


I am having the same problem using a Viterbi Decoder.  I am implementing
the design in an FGPA using an IP core that is provided by Altera. One of
the proposed solutions referred me to the following link:

http://tmo.jpl.nasa.gov/progress_report/42-128/128E.pdf

The paper discusses node synchronization and described the exact problem
that I am having, however after talking with Altera's Technical support
staff, they told me that I cannot use the BER or normalization rate, which
is generated by the their IP core, as a method to synchronize my data. 
Their core uses the common approach to decode the incoming data stream,
then re-encode it and compare it against a delayed version.  

The way I understand this concept is, when the Viterbi Decoder is
synchronized it should not have to normalize any of the branch metrics
therefore the normalization rate should be very low.  The same is true for
the BER.  So I figured that I can just determine an appropriate threshold
value and monitor when the BER and normalizations exceed the threshold and
auto adjust my incoming data accordingly to ensure that I'm always
synchronized.  Makes sense to me, but Altera says that these parameters
are only good for estimating channel quality and not synchronizing.

Xilinx has a comparable Viterbi IP core that claims I can use BER and
normalizations for my purpose. 

http://www.xilinx.com/ipcenter/catalog/logicore/docs/viterbi_synchronization.pdf

Am I missing something here?

Any input is greatly appreciated.
Jeff