Parallel Viterbi Decoding Implementation by Multi-Microprocessors

Hui ZHAO  Xiaokang YUAN  Toru SATO  Iwane KIMURA  

IEICE TRANSACTIONS on Communications   Vol.E76-B   No.6   pp.658-666
Publication Date: 1993/06/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Communication Theory
coding,  error correction code,  convolutional code,  Viterbi decoding,  parallel algorithm,  parallel Viterbi decoding,  coding by microprocessor,  

Full Text: PDF(824.5KB)>>
Buy this Article

The Viterbi algorithm is a well-established technique for channel and source decoding in high performance digital communication systems. However, excessive time consumption makes it difficult to design an efficient high-speed decoder for practical application. This paper describes the implementation of parallel Viterbi algorithm by multi-microprocessors. Internal computations are performed in a parallel fashion. The use of microprocessors allows low-cost implementation with moderate complexity. The software and hardware implementations of the Viterbi algorithm on parallel multi-microprocessors for real-time decoding are presented. The implemented method is based on a combination of forming a set of tables and calculations. For efficient operation under fully parallel Viterbi decoding by microprocessors, we considered: (1) branch metrics processing, path metrics updating, path memory updating and decoding output for microprocessor, (2) efficient decomposition of the sequential Viterbi algorithm into parallel algorithms, (3) minimization of the communication among the microprocessors. The practical solutions for the problems of synchronization among the miroprocessors, interconnection network for communication among the microprocessors and memory management are discussed. Furthermore the performance and the speed of the parallel Viterbi decoding are given. For a fixed processing speed of given hardwares, parallel Viterbi decoding allows a linear speed up in the throughput rate with a linear increase in hardware complexity.