Generalized trace-back techniques for survivor memory management in the Viterbi algorithm

The trace-back technique is an effective approach for survivor memory management in the Viterbi algorithm. It is especially attractive when the number of states in the trellis is large, in which case the register exchange approach is impractical due to the area required for wiring. Previous descriptions of the trace-back technique have assumed either one or two trace-back pointers and have made specific assumptions about the speeds of those pointers. In this paper we present a general framework for implementing the trace-back technique with any number of trace-back pointers and with relaxed assumptions about the speeds of the pointers. We also show that the use of additional trace-back pointers reduces the memory requirements. Two implementations of the generalized trace-back techniques based on standard RAMs and custom shift registers are presented. © 1993 Kluwer Academic Publishers.