Parallel Viterbi Decoding Algorithms Design And Implementation On GPU

Viterbi algorithm, with a maxmium likelihood decoding solution, has been widely applied in convolutional codes’ decoding. In many wireless communication systems such as software defined radio, because the computing complexity of Viterbi algorithm increases rapidly at exponential rate with the growth of constraint length, implementation based on CPU and DSP can not achieve a higher decoding rate. However, Viterbi algorithm has potential for parallel implementation due to its parallelized trellis structure. In this thesis, the main work is on how to design and improve Viterbi parallel decoding algorithms, and implement them on GPU.Based on existing Viterbi parallel decoding algorithms, two improved parallel Viterbi algorithms are presented in the thesis for overcoming the shortcomings. Through three computation steps:the tiling parallel Viterbi forward iteration, the surival paths modification between chunks and the global parallel tracing back, both the alogrithms can efficiently reduce the decoding latency while keeping an elegant error-bits perfomance.In addition, a parallel decoding algorithm for the tail-bitng convolutional codes widely used on LTE standards is designed based on the maximum likelihood criterion. And a parallel soft-in decoding algorithm is implemented on GPU. All the parallel decoding algorithms are implemented by using CUDA programming language and are tested on GPU in the thesis.The experimental results given in the thesis show that the proposed algorithms outperform the existing serial or parallel Viterbi algorithms in terms of decoding latency and error-bits rate.