An efficient adaptive circular Viterbi algorithm for decoding generalized tailbiting convolutional codes

Viterbi decoding algorithms for convolutional codes are being considered for a number of applications in cellular mobile radio systems. There are three classes of Viterbi decoders depending on the nature of the formatting of the data: continuous decoding with a finite path memory, blockwise decoding with a terminating tail (known to the decoder), and blockwise decoding without a known tail. The latter class is also known as decoding of tailbiting convolutional codes. In this case, a coded message begins and ends in the same state which is unknown to the receiver. The authors present a class of Viterbi algorithms for tailbiting convolutional codes. These algorithms are used in blockwise transmission to save the overhead of a known tail. They call the new algorithm the circular Viterbi algorithm (CVA). The basic ideas are: (1) continue conventional seamless continuous Viterbi decoding beyond the block boundary by recording and repeating the received block of (soft) symbols; (2) start the decoding process in all states; and (3) end the decoding process either adaptively or with a fixed length. Three robust adaptive stopping rules are constructed and evaluated. Simulation results and comparison to previously known algorithms as well as the optimum algorithm are presented. The amount of computation required for previously reported iterative algorithms tends to increase dramatically as the channel bit error rate (BER) increases. In one reported instance, computation increased by over 900% while decoded BER increased from 8×10^-6 to 8×10^-3. For the same example, the CVA increase in computation was 11.4% and the worst case decoded BER was 4×10^-3. The authors conclude that for noisy channels the CVA decodes in a much shorter time with better performance than previously published iterative algorithms