Biased Monte Carlo methods for efficient simulation of communication systems

This thesis investigates biased Monte Carlo (MC) methods for efficient simulation of orthogonal frequency division multiplexing (OFDM), multiple-input multiple-output (MIMO) and coded communication systems. Analytical complexity of exact performance evaluation of modern communication systems demands MC simulations, which estimate the performance metrics by statistical sample averaging. Even though MC is generally applicable for arbitrarily complex systems, it requires large sample sizes and extensive computational time to estimate low probabilities with a high degree of accuracy. This motivates the development of efficient simulation techniques. Statistical efficiency of simulations can be improved by properly biasing the MC simulations to encourage the occurrence of important events. This thesis investigates such biasing strategies for communication system simulation. First, optimal importance sampling (IS) methods are proposed for efficient simulation of OFDM and MIMO-OFDM systems operating over frequency selective fading channels. Optimum IS parameters that minimise the statistical variance of the estimator are derived. The proposed methods provide increased sample size reductions with decreasing probability. Next, flat histogram Monte Carlo (FHMC) techniques, developed for statistical physics systems, are investigated in a communication engineering context. The potential of FHMC techniques to accelerate communication system simulations is explored. Simulation results show that sample size reductions in the order of 105 can be achieved in estimating probabilities in the order of 10-10 with a relative error of ±10%. Moreover, improved MC estimators are derived and these estimators are used to enhance the efficiency of FHMC algorithms. The improved FHMC algorithms are successfully applied to capacity estimation of MIMO systems whose analytical solutions are intractable. Of these derived estimators, the improved combination of Wang-Landau (WL) and transition matrix Monte Carlo (TMMC) methods shows the best performance while all of them can be generally applied to probability density function (pdf) estimation problems. Finally, IS and FHMC techniques are applied to efficient simulation of coded systems with Viterbi and maximum a posteriori probability (MAP) decoders. A novel algorithm, consisting of two phases that use FHMC concepts, is proposed for e_cient simulation of Viterbi and MAP decoders. The proposed algorithm demonstrates substantial sample size reductions in estimating low probabilities with a relative error of ±10%. This thesis has laid the foundation for further studies on using FHMC methods for performance evaluation of complex decoders and multiuser communication systems