AN EFFICIENT ADAPTIVE CIRCULAR VITERBI ALGORITHM FOR DECODING GENERALIZED TAILBITING CONVOLUTIONAL-CODES

Viterbi decoding algorithms for convolutional codes are being consider ed for a number of applications in cellular mobile radio systems. Ther e 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), a nd blockwise decoding without a known tail. The latter class is also k nown as decoding of tailbiting convolutional codes. In this case, a co ded message begins and ends in the same state which is unknown to the receiver. In this paper, we 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. We call the new al gorithm 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; 3) end the dec oding process either adaptively or with a fixed length. Three robust a daptive stopping rules are constructed and evaluated. Simulation resul ts and comparison to previously known algorithms as well as the optimu m algorithm are presented. The amount of computation required for prev iously 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 x 10(-6) to 8 x 10(-3). For the same example, the CVA increase in com putation was 11.4% and the worst case decoded BER was 4 x 10(-3). We c onclude that for noisy channels the CVA decodes in a much shorter time with better performance than previously published iterative algorithm s.