On the Probability of Undetected Error for the Maximum Distance Separable Codes

Tadao Kasami, Shu Lin

IRE Transactions on Communications Systems · 1984 · 98 citations · 10 references

Concepts

Abstract

In this paper we investigate the performance of maximum-distance-separable codes with symbols from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">GF(q)</tex> when they are used for pure error detection or for simultaneous error correction and detection over a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> -input and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> -output discret memoryless channel with symbol error probability ε. First we show that the probability of undetected error for an MDS code used for pure error detection is upper bounded by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q^{-r}</tex> and decreases monotonically as εdecreases from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(q - 1)/q</tex> to 0, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</tex> is the number of parity-check symbols of the code. Then we show that the probability of undetected error for an MDS code used for correcting <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</tex> or fewer symbol errors is upper bounded by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q^{-r} \Sum\min{i=0}\max{t}(\min{i} \max{n})(q - 1)^{i}</tex> and decreases monotonically as ε decreases from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(q - 1)/q</tex> to 0. These results show that the MDS codes are effective for both pure error detection and simultaneous error correction and detection.

References

10