Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

South African Symposium on Communications and Signal Processing (COMSIG)

On the undetected error probability of linear block codes on channels with memory

A. Kuznetsov, F. Swarts, Hendrik Christoffel Ferreira

Published Dec 30, 2002• 1 citation
Publisher

Abstract

We give an upper band on the undetected error probability of binary (n,k)-codes used on channels with memory described by Markov distributions. This bound is a generalization of the bound presented by Kasami (1983) for the binary symmetric channel (BSC). An extended bound is given for the Gilbert-Elliott channel (1960, 1963) and Markov channels with deterministic errors. We also develop a recursive technique for the exact calculation of the undetected error probability of an arbitrary linear block code used on a Markov type channel. This technique is based on the trellis representation of block codes described by Wolf (1978). Results of the computations are presented.>

DOI
10.1109/comsig.1993.365871

Related papers

On the undetected error probability of linear block codes on channels with memory

A. Kuznetsov, F. Swarts, A. J. Han Vinck +1 more

We derive an upper bound on the undetected error probability of binary (n, k) block codes used on channels with memory described by Markov distributions. This bound is a generalization of the bound presented by Kasami et al. (1984) for the binary symmetric channel, and is given as an average value of some function of the composition of the state sequence of the channel. It can be extended in particular cases of Markov-type channels. As an example, such an extended bound is given for the Gilbert-Elliott (1960, 1963) channel and Markov channels with deterministic errors determined by the state. We develop a recursive technique for the exact calculation of the undetected error probability of an arbitrary linear block code used on a Markov-type channel. This technique is based on the trellis representation of block codes described by Wolf (1978). Results of some computations are presented.

IEEE Transactions on Information Theory•Jan 1, 1996•11 citations

On the computation of the probability of undetected error for linear block codes on the Gilbert channel

B. Wong

An important measure of the performance of error detecting codes is the probability of undetected error. Extensive study on the subject has yielded results which allow for the computation of the probability of undetected error for many codes on the binary symmetric channel (BSC). However, little is known about code performance in more complicated channel models. The Gilbert channel is a two-state, three-parameter model with memory which simulates the effects of burst noise. In this thesis, we investigate methods to compute the probability of undetected error of binary linear block codes on this channel. We examine an approach to approximate code performance based on the P(m,n) distribution which is the probability of m errors in a block of n bits and the weight distribution of the code. For the Gilbert channel, P(m,n) can in principle be calculated from the channel parameters. In practice however, existing methodologies suffer from rather excessive computational requirements, particularly when n is larger than one thousand or so. We have developed an efficient method to calculate P(m,n) for reasonable channel parameters. This allows the probability of undetected error for many codes to be readily estimated. For certain channel and code parameters, the approximation method described above may not be sufficiently accurate. Exact analytical results are difficult to obtain, however; because unlike the BSC, the probability of a particular error pattern on the Gilbert channel depends not just on the number of 1's in the pattern. Nevertheless, by appropriately exploiting certain symmetries present on the Gilbert channel, we can acquire some useful results. We have derived the probability of undetected error for the single parity check code. We have also obtained a formula for summing over a cyclic class of vectors and shown that reciprocal generator polynomials generate cyclic codes which have the same probability of undetected error on the Gilbert channel. The Monte Carlo simulation technique is often used when exact analysis is difficult. In a simulation study of CRC codes, we are able to observe several interesting qualitative results with just a reasonable amount of computational effort. We find that as on the BSC, on the Gilbert channel the probability of undetected error does not always increase with worsening channel conditions. Also, the CRC-CCITT code appears to maintain its superiority in terms of error detection performance over the CRC-ANSI code on the Gilbert channel, and perhaps most significantly, for some ranges of channel parameters, the probability of undetected error estimated using BSC results with the effective bit error rate can be quite inaccurate.

•Jan 1, 2010•2 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 Systems•Feb 1, 1982•137 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 Mathematics•Jan 1, 2017•1 citation

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 Theory•Jan 1, 1990•0 citations

An upper bound on the average probability of undetected error for the ensemble of all iterated codes

T. Nishijima

An upper bound on the average probability of undetected error for the ensemble of all iterated codes is given. It is assumed that the codes are binary linear block codes, and the channel is the binary symmetric channel.

IEEE Information Theory Workshop (ITW)•Jan 20, 2003•1 citation
We give an upper band on the undetected error probability of binary (n,k)-codes used on channels with memory described by Markov distributions. This bound is a generalization of the bound presented by Kasami (1983) for the binary symmetric channel (BSC). An extended bound is given for the Gilbert-Elliott channel (1960, 1963) and Markov channels with deterministic errors. We also develop a recursive technique for the exact calculation of the undetected error probability of an arbitrary linear block code used on a Markov type channel. This technique is based on the trellis representation of block codes described by Wolf (1978). Results of the computations are presented.>
We derive an upper bound on the undetected error probability of binary (n, k) block codes used on channels with memory described by Markov distributions. This bound is a generalization of the bound presented by Kasami et al. (1984) for the binary symmetric channel, and is given as an average value of some function of the composition of the state sequence of the channel. It can be extended in particular cases of Markov-type channels. As an example, such an extended bound is given for the Gilbert-Elliott (1960, 1963) channel and Markov channels with deterministic errors determined by the state. We develop a recursive technique for the exact calculation of the undetected error probability of an arbitrary linear block code used on a Markov-type channel. This technique is based on the trellis representation of block codes described by Wolf (1978). Results of some computations are presented.
An important measure of the performance of error detecting codes is the probability of undetected error. Extensive study on the subject has yielded results which allow for the computation of the probability of undetected error for many codes on the binary symmetric channel (BSC). However, little is known about code performance in more complicated channel models. The Gilbert channel is a two-state, three-parameter model with memory which simulates the effects of burst noise. In this thesis, we investigate methods to compute the probability of undetected error of binary linear block codes on this channel. We examine an approach to approximate code performance based on the P(m,n) distribution which is the probability of m errors in a block of n bits and the weight distribution of the code. For the Gilbert channel, P(m,n) can in principle be calculated from the channel parameters. In practice however, existing methodologies suffer from rather excessive computational requirements, particularly when n is larger than one thousand or so. We have developed an efficient method to calculate P(m,n) for reasonable channel parameters. This allows the probability of undetected error for many codes to be readily estimated. For certain channel and code parameters, the approximation method described above may not be sufficiently accurate. Exact analytical results are difficult to obtain, however; because unlike the BSC, the probability of a particular error pattern on the Gilbert channel depends not just on the number of 1's in the pattern. Nevertheless, by appropriately exploiting certain symmetries present on the Gilbert channel, we can acquire some useful results. We have derived the probability of undetected error for the single parity check code. We have also obtained a formula for summing over a cyclic class of vectors and shown that reciprocal generator polynomials generate cyclic codes which have the same probability of undetected error on the Gilbert channel. The Monte Carlo simulation technique is often used when exact analysis is difficult. In a simulation study of CRC codes, we are able to observe several interesting qualitative results with just a reasonable amount of computational effort. We find that as on the BSC, on the Gilbert channel the probability of undetected error does not always increase with worsening channel conditions. Also, the CRC-CCITT code appears to maintain its superiority in terms of error detection performance over the CRC-ANSI code on the Gilbert channel, and perhaps most significantly, for some ranges of channel parameters, the probability of undetected error estimated using BSC results with the effective bit error rate can be quite inaccurate.
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.