Regarding Viterbi decoder of continuous transmission?

I am reading Viterbi decoding technique, and confused with
the trace back. Assume rate 1/2 K=3 convolutional encoding.

When the trace back depth is 5K. Is the trace back operation
performed in blocks of 5K bits and decode 5K bits at a time,

or trace back operation is performed on a 5K FIFO which stores
the state history, and decode the single bit in the beginning of the
state history FIFO?

Many thanks.

On Feb 19, 9:44 am, "news reader" <newsrea...@google.com> wrote:
> I am reading Viterbi decoding technique, and confused with
> the trace back. Assume rate 1/2 K=3 convolutional encoding.
>
> When the trace back depth is 5K. Is the trace back operation
> performed in blocks of 5K bits and decode 5K bits at a time,
>
> or trace back operation is performed on a 5K FIFO which stores
> the state history, and decode the single bit in the beginning of the
> state history FIFO?
>
> Many thanks.


The latter statement is correct.

John

Thank you John.

If the trace back depth is too much, for example R=1/2, K = 5 and the
traceback depth is 50 symbols. In order to save hardware, is it possible
to decode multiple bits in each traceback operation?

For example,
@T50, traceback -> T0, decode b0, b1, ...b9,
@T60, traceback -> T10, decode b10, b11, ...b19,
@T70, traceback -> T20, decode b20, b21, ...b29,
etc.

What impact will such technique have on the error correction capability?








<sampson164@gmail.com> wrote in message 
news:1171897266.560372.170130@p10g2000cwp.googlegroups.com...
> On Feb 19, 9:44 am, "news reader" <newsrea...@google.com> wrote:
>> I am reading Viterbi decoding technique, and confused with
>> the trace back. Assume rate 1/2 K=3 convolutional encoding.
>>
>> When the trace back depth is 5K. Is the trace back operation
>> performed in blocks of 5K bits and decode 5K bits at a time,
>>
>> or trace back operation is performed on a 5K FIFO which stores
>> the state history, and decode the single bit in the beginning of the
>> state history FIFO?
>>
>> Many thanks.
>
>
> The latter statement is correct.
>
> John
> 

On Feb 20, 6:21 am, "news reader" <newsrea...@google.com> wrote:
> Thank you John.
>
> If the trace back depth is too much, for example R=1/2, K = 5 and the
> traceback depth is 50 symbols. In order to save hardware, is it possible
> to decode multiple bits in each traceback operation?
>
> For example,
> @T50, traceback -> T0, decode b0, b1, ...b9,
> @T60, traceback -> T10, decode b10, b11, ...b19,
> @T70, traceback -> T20, decode b20, b21, ...b29,
> etc.
>
> What impact will such technique have on the error correction capability?
>
> <sampson...@gmail.com> wrote in message
>
> news:1171897266.560372.170130@p10g2000cwp.googlegroups.com...
>
> > On Feb 19, 9:44 am, "news reader" <newsrea...@google.com> wrote:
> >> I am reading Viterbi decoding technique, and confused with
> >> the trace back. Assume rate 1/2 K=3 convolutional encoding.
>
> >> When the trace back depth is 5K. Is the trace back operation
> >> performed in blocks of 5K bits and decode 5K bits at a time,
>
> >> or trace back operation is performed on a 5K FIFO which stores
> >> the state history, and decode the single bit in the beginning of the
> >> state history FIFO?
>
> >> Many thanks.
>
> > The latter statement is correct.
>
> > John


It's possible to decode multiple bits per traceback, but you have to
extend the traceback buffer so that all bits have at least 5*K
history. I don't think this will save hardware, but it can speed up a
software decoder.

John

sampson164@gmail.com wrote:


> It's possible to decode multiple bits per traceback, but you have to
> extend the traceback buffer so that all bits have at least 5*K
> history. I don't think this will save hardware, but it can speed up a
> software decoder.

Interesting. I have never thought of doing Viterbi decoder by a block at 
a time. Where does the speed gain come from in this case?

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

On Feb 20, 10:58 am, Vladimir Vassilevsky <antispam_bo...@hotmail.com>
wrote:
> sampson...@gmail.com wrote:
> > It's possible to decode multiple bits per traceback, but you have to
> > extend the traceback buffer so that all bits have at least 5*K
> > history. I don't think this will save hardware, but it can speed up a
> > software decoder.
>
> Interesting. I have never thought of doing Viterbi decoder by a block at
> a time. Where does the speed gain come from in this case?
>
> Vladimir Vassilevsky
>
> DSP and Mixed Signal Design Consultant
>
> http://www.abvolt.com


In the usual method, the traceback operation looks back 5*K symbols to
get a new output bit. So there is a loop with 5*K comparisons to get
one output bit. This loop executes once for every output bit.

If the traceback buffer is longer than 5*K, keep going after you get
the next output bit and get some more output bits. You don't have to
start over. In this case the traceback only executes once per block of
output bits. The savings comes from only having to loop through the
first 5*K symbols for each block of bits instead of for every bit.

John

Hello,

I got a similar question. I am trying to parallelize the whole Viterbi
decoder trellis. My question is:
If my trellis has N stages, 2^(K-1) states per stage, may I divide N into
M sub-trellis (each having (N/M + 5K) stages) for which I independently do
a traceback to decode the corresponding bits. The thing I am not sure of is
that I can process the M sub-trellis in parallel, meaning that e.g.,
sub-trellis 2 does not require to know the final path length information
from sub-trellis 1 to start. 
In other words, for each subtrellis, I would have path length 0 for all
states of the first stage of the sub-trellis. I would only consider the
path length from state transitions within this sub-trellis in order to
find the final state from which I would start the traceback for this
sub-trellis (the one with the longest path). Is this doable? Or do I need
to process these sub-trellis in sequence?

Thank you for help

Fran