Evaluation of a Reduced Complexity ML Decoding Algorithm for Tailbiting Codes on Wireless Systems

Tailbiting convolutional codes will be used for several applications in new cellular mobile radio systems. This encoding method does not reset the encoder memory at the end of each data block, avoiding the overhead of the zero tail and improving the efficiency. Nevertheless, the absence of a known tail highly increases the complexity of the decoding process. Recently, the use of the A* algorithm has highly decreased the computational complexity of Maximum Likelihood (ML) decoding of tailbiting convolutional codes. The decoding process in this case requires two steps. In the first step, a typical Viterbi decoding is employed to collect information regarding the trellis. The A* algorithm is then applied in the second step, using the information obtained in the first step to calculate the heuristic function. The improvements proposed in this work decrease the computational complexity of the A* algorithm using further information from the first step of the algorithm. This information is used for finding early terminating conditions for the A* algorithm. Simulation results show that the proposed modification decreases the complexity of ML decoding with the A* algorithm in terms of the performed number of operations.