An efficient adaptive circular Viterbi algorithm for decodinggeneralized tailbiting convolutional codes

摘要

Viterbi decoding algorithms for convolutional codes are beingnconsidered for a number of applications in cellular mobile radionsystems. There are three classes of Viterbi decoders depending on thennature of the formatting of the data: continuous decoding with a finitenpath memory, blockwise decoding with a terminating tail (known to thendecoder), and blockwise decoding without a known tail. The latter classnis also known as decoding of tailbiting convolutional codes. In thisncase, a coded message begins and ends in the same state which is unknownnto the receiver. The authors present a class of Viterbi algorithms forntailbiting convolutional codes. These algorithms are used in blockwisentransmission to save the overhead of a known tail. They call the newnalgorithm the circular Viterbi algorithm (CVA). The basic ideas are: (1)ncontinue conventional seamless continuous Viterbi decoding beyond thenblock boundary by recording and repeating the received block of (soft)nsymbols; (2) start the decoding process in all states; and (3) end thendecoding process either adaptively or with a fixed length. Three robustnadaptive stopping rules are constructed and evaluated. Simulationnresults and comparison to previously known algorithms as well as thenoptimum algorithm are presented. The amount of computation required fornpreviously reported iterative algorithms tends to increase dramaticallynas the channel bit error rate (BER) increases. In one reported instance,ncomputation increased by over 900% while decoded BER increased fromn8×10-6 to 8×10-3. For the samenexample, the CVA increase in computation was 11.4% and the worst casendecoded BER was 4×10-3. The authors conclude that fornnoisy channels the CVA decodes in a much shorter time with betternperformance than previously published iterative algorithms