Trellis pipeline-interleaving: a novel method for efficient Viterbi decoder implementation

The authors derive the novel trellis-pipeline interleaving (TPI) technique for introducing pipeline-interleaving into the nonlinear data-dependent add-compare-select (ACS) recursion in Viterbi decoders. It is shown that the overall recursion can be split into loosely coupled parts which can be computed in an interleaved way. A formal method is given to introduce various degrees of interleaving into the recursion making use of the topological equivalence of various different trellis representations. Conventional high speed Viterbi decoder architectures are coarse-grain pipelined at the ACS level. Using TPI far more efficient solutions are obtained by using fewer processing elements than states. The additional concurrency available through TPI is exploited by fine-grain pipelined architectures. The results agree with the general concept of first introducing pipelining to the maximum possible extent before introducing parallelism to achieve the most efficient solutions. >