An area efficient surviving paths unit for the Viterbi algorithm

A new surviving paths unit (SPU) is described wherein the decision bits produced in the add-compare-select unit (ACSU) of a parallel architecture for the Viterbi algorithm are prepared for efficient storage in a single compact random access memory (RAM). A significant reduction in the size of the RAM is achieved by pre-processing the data in an especially designed unit. The new SPU never requires a memory bandwidth more than the least possible bandwidth imposed by the throughput of the ACSU. A novel interface unit, hereafter referred to as the ACS interface unit (ACSIU), resolves surviving paths down to a pre-determined depth on the trellis diagram of a finite state Markov chain, and breaks the decision bits into a sequence of successive vectors, each of the same size as the word-size of the RAM. At any trace-back step, a subset of the previous content of the trace-back register is used to generate the address for the current output of the RAM. A disjoint subset of the current content of the trace-back register is used to select a pre-determined number of bits from the output of the RAM. The selected bits are used to update the content of the trace-back register. The trace-back register after a sufficient number of trace-back steps, contains the estimated bits