A parallel Viterbi algorithm for decoding convolutional codes on SIMD machines

The parallel implementation aspects of the Viterbi algorithm, which gives the maximum likelihood solution to decoding conventional codes, are studied. The interconnection of the trellis diagram of a binary convolutional code is similar to the shuffle exchange. This similarity is exploited to present a parallel version of the Viterbi algorithm. The proposed algorithm avoids tasks such as appending and exchanging the survivor lists that are considered pragmatic issues to be accommodated in implementing the Viterbi algorithm. This is done by introducing an additional back-tracking procedure which is almost identical to the forward path where branch and path metrics are computed. The parallel Viterbi algorithm is implemented on the connection machine which is a SIMD (single instruction stream and multiple data stream) parallel machine