MAPPING OF TRELLISES ASSOCIATED WITH GENERAL ENCODERS ONTO HIGH-PERFORMANCE VLSI ARCHITECTURES

A rate lin binary generic convolutional encoder is a shift-register ci rcuit where the inputs uk are information bits and the outputs y(k) ar e blocks of n bits generated as linear combinations on the appropriate shift register contents. The decoding of the outputs of a convolution al encoder can be carried out by the well-known Viterbi algorithm. The communication pattern of the Viterbi Algorithm is given as a graph, c alled trellis, associated to the state diagram of the corresponding en coder. In this paper we present a methodology that permits the efficie nt mapping of the Viterbi algorithm onto a column of an arbitrary numb er of processors. This is done through the representation of the data flow by using mathematical operators which present an inmediate hardwa re projection. A single operator string has been obtained to represent a generic encoder through the study of the data flow of free-forward encoders and feed-back encoders. The formal model developed is employe d for the partitioning of the computations among an arbitrary number o f processors in such a way that the data are recirculated opimizing th e use of the processors and the communications. As a result, we obtain a highly regular and modular architecture suitable for VLSI implement ation.