Sub-optimal importance sampling for fast simulation of linear block codes over BSC channels

Estimation of very low word-error probability of hard-decoded linear block codes can be performed through Monte-Carlo simulation. The computational complexity of the standard method however increases as the probability of error to be estimated decreases. In this paper we propose a general algorithm for fast estimation of probability of error of linear block codes on BSC channels based on the importance sampling and the cross-entropy method for rare-events that can be employed for any hard-decision decoder. When optimal decoding is used the algorithm reduces to a single simulation run that can estimate, with a given accuracy, performances for a whole range of sufficiently high signal-to-noise ratios.