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.

# Regarding Viterbi decoder of continuous transmission?

Started by ●February 19, 2007

Reply by ●February 19, 20072007-02-19

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

Reply by ●February 20, 20072007-02-20

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 >

Reply by ●February 20, 20072007-02-20

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. > > > JohnIt'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

Reply by ●February 20, 20072007-02-20

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

Reply by ●February 20, 20072007-02-20

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.comIn 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

Reply by ●July 19, 20072007-07-19

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