Error recovery of variable length codes over BSC with arbitrary crossover probability
The error recovery capability of variable length code (VLC) has been considered as an important performance and design criterion in addition to its coding efficiency. However, almost all of the existing methods for evaluating the error recovery capability of VLC assume that the transmission fault is a random single bit inversion. In this paper, we consider a more generalized problem of precisely evaluating the error recovery capability of VLC in the case that the encoded bit stream is transmitted over a BSC with arbitrary crossover probability. By making use of the Perron-Frobenius Theorem, we derive a very simple expression for the exact mean symbol error rate (MSER) in Levenshtein distance sense. We also prove that in the very low crossover probability region, the mean error propagation length (MEPL) derived for single inversion error case approaches a scaled value of MSER. In addition, we briefly discuss the error recovery of VLC over Gilbert-Elliott channel, which is one of the simplest and practical models for a channel with memory.