Complexity Reduction of the Viterbi Algorithm Based on Samples Reliability

Luís O. Mataveli, Celso de Almeida

DOI: 10.14209/sbrt.2013.180

Evento: XXXI Simpósio Brasileiro de Telecomunicações (SBrT2013)

Keywords: Viterbi algorithm complexity reduction relia- bility threshold.

Abstract

The Viterbi algorithm is a maximum likelihood algorithm that is used for decoding convolutional codes. In order to determine the survivor path in a trellis, it is necessary to calculate the metrics of each branch. In this paper, we propose a method that reduces the number of branches in the trellis and consequently its complexity, based on the reliability of the received signal samples. The complexity of the proposed algorithm is reduced with the number of reliable samples. The proposed algorithm achieves a performance close to the Viterbi algorithm, but with lesser complexity, depending on the reliability threshold. The performance is evaluated in terms of bit error probability and complexity, obtained by simulation, for different signal to noise ratio and reliability threshold values. The results are obtained for different convolutional encoders by considering a Rayleigh fading channel.

Download