The undetected error probability for Reed-Solomon codes

Abstract

This paper is an extension of a recent paper by McEliece and Swanson dealing with the decoder error probability for Reed-Solomon codes {more generally, linear MDS codes). McEliece and Swanson offered an upper bound on P_E(u), the decoder error probability given u symbol errors occur. In this paper, by using combinatoric technique like the principle of inclusion and exclusion, an exact formula for P_E(u) is derived. The P_E(u) of an MDS code is observed to approach Q rapidly as u gets large, where Q is the probability that a compltely random error pattern will cause decoder error. An upper bound for the expression │P_E(u)/Q-1│ is derived, and is shown to decrease nearly exponentially as u increases. This proves analytically that P_E(u) indeed approaches Q as u becomes large, and some laws of large number come info play somehow.