In this paper an optimal importance sampling (IS) method is derived for a transient Markov system. Several propositions are presented. It is shown that the optimal IS method is unique, and it must converge to the standard Monte Carlo (MC) simulation method when the sample path length approaches infinity. Therefore, it is not the size of the state space of the Markov system, but the sample path length, that limits the efficiency of the IS method. Numerical results are presented to support the argument.

We derive an upper bound on the bit-error probability (BEP) in limited-search detection over a finite interference channel. A unified channel model is presented; this includes finite-length intersymbol interference channels and multiuser CDMA channels as two special cases. We show that the BEP of the M-algorithm (MA) is bounded from above by the sum of three terms: an upper bound on the error probability of the Viterbi (1967) algorithm (VA) detection given by Forney Jr. (1972), and upper bounds on the error probabilities of two types of erroneous decision caused by the correct path loss event. We prove that error propagation (in terms of the mean recovery step number) is finite for all finite interference channels. The convergence and asymptotic behavior of the upper bounds are studied. The results show that, if a channel satisfies certain mild conditions, all series in the bounds are convergent. One of the key results is that, for any finite interference channel satisfying certain mild conditions. the asymptotic BEP of the MA is bounded by the same upper and lower bounds (which have the same asymptotical behavior) as those for the VA if the correct path loss probability is smaller than that of the VA. Furthermore, we extend the above results to near optimally decode long convolutional codes in a short packet format (about 200-300 bits). We present a nonsorting combined M/T algorithm and showed that the M/T algorithm with M>2(/sup d/free//sup n/) and T>(d/sub free/E/sub b/)/n can near-optimally decode the code. We also propose a hierarchical decoding algorithm (HDA) to further cut down the average decoding complexity. Numerical results show that the bounds are reasonably tight. The HDA can achieve a performance within about 0.8 dB of the sphere-packing lower bound for a packet error rate of 10/sup -4/ and a packet length below 200 bits, which is the best reported decoding performance so far for block sizes from 100 to 200 bits.

In this correspondence, we first correct a mistake in Best et al. (1995) and then present a method to compute the exact probability of information bit error as a function of truncation length K for a rate 1/2, 2 state code, Finally, we generalize the method to compute the exact bit-error probability of the above convolutional code when the information bits are transmitted in blocks. The simulation results are compared with the analytical results and good agreement is observed.

A Markov analysis method for packet reservation multiple access (PRMA) performance study is presented. A Markov model is formulated, the stationary state probability distribution and hence the system performance, such as packet dropping probability, system throughput, are calculated accurately. We also consider a stability measure of the system in terms of average first exit time (FET) of the channel into an unsafe operating region starting from an initially empty channel. It is shown that the Markov analysis method establishes a powerful tool for the performance analysis and design of PRMA systems.>