A NEW METHOD FOR VITERBI DECODER SIMULATION USING IMPORTANCE SAMPLING

Importance sampling is a technique for speeding up Monte-Carlo simulation. The basic idea is to bias the simulation distribution to increase the relative frequency of “important” events, and then weight the observed simulation data in order to obtain decision error probability estimates for the true input distribution. When the proper weighting is employed, the result is an unbiased Monte-Carlo estimator which often requires orders of magnitude fewer simulation runs than ordinary Monte-Carlo to obtain the same specified precision. In this paper, a new technique is presented for Viterbi decoder simulation. Each simulation run simulates a single error event, that is, a subsequence of incorrect trellis branching decisions, and importance sampling is used to emphasize the “important” nontrivial error events. The result is dramatically improved efficiency. In addition to presenting the basic principles of the new error event simulation method, several numerical examples demonstrate the power and accuracy of this new simulation method. © 1990 IEEE