VLSI Structures for Viterbi Receivers: Part I--General Theory and Applications

A taxonomy of VLSI grid model layouts is presented for the implementation of certain types of digital communication receivers based on the Viterbi algorithm. We deal principally with networks of many simple processors connected to perform the Viterbi algorithm in a highly parallel way. Two interconnection patterns of interest are the "shuffleexchange" and the "cube-connected cycles." The results are generally applicable to the development of area-efficient VLSI circuits for decoding: convolutional codes, coded modulation with multilevel/phase signals, punctured convolutional codes, correlatively encoded MSK signals and for maximum likelihood sequence estimation of -ary signals on intersymbol interference channels. In a companion paper, we elaborate on how the concepts presented here can be applied to the problem of building encoded MSK Viterbi receivers. Lower bounds are established on the product (chip area) * (baud rate)^-2and on the energy consumption that any VLSI implementation of the Viterbi algorithm must obey, regardless of the architecture employed or the intended application.