IEEE Transactions on Information Theory

The undetected error probability threshold of m-out-of-n codes

Fang‐Wei Fu, Torleiv Kløve, Shu‐Tao Xia

Published Jul 1, 2000• 5 citations

Abstract

The well-known m-out-of-n code /spl Omega//sub n//sup m/ consists of all binary vectors of length n and weight m. It is known that it is good for error detection (in the technical sense, that is, the probability of undetected error P/sub ud/(/spl Omega//sub n//sup m/,p)/spl les/P/sub ud/(/spl Omega//sub n//sup m/,1/2) for all p, 0/spl les/p/spl les/1/2) only for a few small values of m and n. It is therefore of interest to determine (bounds for) the threshold in general, that is, find the range of bit-error probabilities p for which P/sub ud/ (/spl Omega//sub n//sup m/,p)/spl les/P/sub ud/ (/spl Omega//sub n//sup m/,1/2). In this article such bounds are given.

DOI: 10.1109/18.850701

Related papers

Bounds on the undetected error probabilities of linear codes for both error correction and detection

Mao‐Chao Lin

The author investigates the (n, k, d>or=2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) (2/sup n-k/-n)/sup -1/ when used on a binary symmetric channel with transition probability less than 2/n.>

IEEE Transactions on Information TheoryJan 1, 19900 citations

Necessary conditions for good error detection

P.N. Perry

The problem of determining the error detection capabilities of linear codes where the channel is a binary symmetric channel is addressed. Necessary conditions are given on the number of codewords in an (n,k) linear code and its dual for the probability of an undetected error to be upper bounded by 2/sup -(n-k)/.>

IEEE Transactions on Information TheoryMar 1, 199117 citations

Undetected error probability of hamming code for any number of symbols

Manish K. Gupta, Jaskaran Singh Bhullar, Bharat Naresh Bansal

In past papers, it has been shown that probability of undetected error Pu(ε) for binary (n = 2m- 1, k = n - m, 3) Hamming code (q = 2) used for error detection on binary symmetric channel satisfies the 2-pbound, where p is the parity check bits equal to n - k, hence binary Hamming codes are proper. In this correspondence this result is generalized and it has been shown that not only binary but Hamming Codes (for any value of q) satisfy this bound, so generalized Hamming codes are proper.

IEEE International Conference on Information Theory and Information SecurityDec 1, 20104 citations

Concerning a bound on undetected error probability

Kamal Gupta

In the past, it has generally been assumed that the probability of undetected error for an (n,k) block code, used solely for error detection on a binary symmetric channel, is upper bounded by 2-(n-k). In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.

International Journal of Statistics and Applied MathematicsJan 1, 20171 citation

Concerning a bound on undetected error probability (Corresp.)

S. Leung-Yan-Cheong, Martin E. Hellman

In the past, it has generally been assumed that the probability of undetected error for an(n,k)block code, used solely for error detection on a binary symmetric channel, is upperbounded by2^{-(n-k)}. In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.

IEEE Transactions on Information TheoryMar 1, 197649 citations

On the Probability of Undetected Error for Linear Block Codes

Jack K. Wolf, Arnold M. Michelson, Allen H. Levesque

The problem of computing the probability of undetected error is considered for linear block codes used for error detection. The recent literature is first reviewed and several results are extended. It is pointed out that an exact calculation can be based on either the weight distribution of a code or its dual. Using the dual code formulation, the probability of undetected error for the ensemble of all nonbinary linear block codes is derived as well as a theorem that shows why the probability of undetected error may not be a monotonic function of channel error rate for some poor codes. Several bounds on the undetected error probability are then presented. We conclude with detailed examples of binary and nonbinary codes for which exact results can be obtained. An efficient technique for measuring an unknown weight distribution is suggested and exact results are compared with experimental results.

IRE Transactions on Communications SystemsFeb 1, 1982137 citations