Mapping of Trellises Associated with General Encoders onto High-Performance VLSI Architectures

A rate 1/n binary generic convolutional encoder is a shift-register circuit where the inputs are information bits and the outputs are blocks of n bits generated as linear combinations on the appropriate shift register contents. The decoding of the outputs of a convolutional encoder can be carried out by the well-known Viterbi algorithm. The communication pattern of the Viterbi Algorithm is given as a graph, called trellis, associated to the state diagram of the corresponding encoder. In this paper we present a methodology that permits the efficient mapping of the Viterbi algorithm onto a column of an arbitrary number of processors. This is done through the representation of the data flow by using mathematical operators which present an inmediate hardware 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 employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated opimizing the use of the processors and the communications. As a result, we obtain a highly regular and modular architecture suitable for VLSI implementation.