Method for carrying out a Viterbi algorithm with parallel processing structures

摘要

To implement the Viterbi algorithm (Viterbi decoder) for very high data decoding rates, the basic trellis diagram (original trellis diagram) of the Markov process is considered over a relatively long period. M transitions of the original trellis diagram are in each case combined to form a multi-step transition (multi-step trellis diagram; Figure 1). …??The number of transition branches, which increases exponentially with M during this process, is reduced to a lesser number by utilising fundamental characteristics of the original trellis diagram forming the basis of the multi-step transitions. Independently of multi-step transition to multi-step transition, non-optimal transition branches are eliminated by this means. This allows Viterbi decoders to be built for very high data rates because more time is available for executing the computing operations on several arithmetic units than the maximum time permitted for executing similar (identical) operations when the Viterbi algorithm is implemented on the basis of the one-step transition of the original trellis diagram. …IMAGE…