The MMD codes are proper for error detection

The undetected error probability of a linear code used to detect errors on a symmetric channel is a function of the symbol error probability /spl epsi/ of the channel and involves the weight distribution of the code. The code is proper, if the undetected error probability increases monotonously in /spl epsi/. Proper codes are generally considered to perform well in error detection. We show in this correspondence that maximum minimum distance (MMD) codes are proper.     

On the Probability of Undetected Error for Linear Block Codes

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.     

Undetected error probabilities of binary primitive BCH codes forboth error correction and detection

We investigate the undetected error probabilities for bounded-distance decoding of binary primitive BCH codes when they are used for both error correction and detection on a binary symmetric channel. We show that the undetected error probability of binary linear codes can be simplified and quantified if the weight distribution of the code is binomial-like. We obtain bounds on the undetected error probability of binary primitive BCH codes by applying the result to the code and show that the bounds are quantified by the deviation factor of the true weight distribution from the binomial-like weight distribution     

Necessary conditions for good error detection

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^-(n-k)     

Concerning a bound on undetected error probability (Corresp.)

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.     

Word error rate for group codes detected by correlation and other means

General expressions for the probability of word error for several encoding/detection schemes using group codes are derived. Correlation detection, digital decoding, straight Wagner codes, "Wagnerized" codes, and direct transmission are covered. Specific results are given for each in the case where the additive channel noise is white and Gaussian. A good indication of the relative amounts of power required by two schemes operating at the same error rate is available from an asymptotic relationship as the signal-to-noise ratio approaches infinity. Numerical results are presented for three easily implemented codes.     

Linear block codes for error detection (Corresp.)

The probability of undetected error of linear block codes for use on a binary symmetric channel is investigated. Upper hounds are derived. Several classes of linear block codes are proved to have good error-detecting capability.     

Quantum error detection .II. Bounds

For pt.I see ibid., vol.46, no.3, p.778-88 (2000). In Part I of this paper we formulated the problem of error detection with quantum codes on the depolarizing channel and gave an expression for the probability of undetected error via the weight enumerators of the code. In this part we show that there exist quantum codes whose probability of undetected error falls exponentially with the length of the code and derive bounds on this exponent. The lower (existence) bound is proved for stabilizer codes by a counting argument for classical self-orthogonal quaternary codes. Upper bounds are proved by linear programming. First we formulate two linear programming problems that are convenient for the analysis of specific short codes. Next we give a relaxed formulation of the problem in terms of optimization on the cone of polynomials in the Krawtchouk basis. We present two general solutions of the problem. Together they give an upper bound on the exponent of undetected error. The upper and lower asymptotic bounds coincide for a certain interval of code rates close to 1     

A lower bound on the undetected error probability and strictlyoptimal codes

Error detection is a simple technique used in various communication and memory systems to enhance reliability. We study the probability that a q-ary (linear or nonlinear) block code of length n and size M fails to detect an error. A lower bound on this undetected error probability is derived in terms of q, n, and M. The new bound improves upon other bounds mentioned in the literature, even those that hold only for linear codes. Block codes whose undetected error probability equals the new lower bound are investigated. We call these codes strictly optimal codes and give a combinatorial characterization of them. We also present necessary and sufficient conditions for their existence. In particular, we find all values of n and M for which strictly optimal binary codes exist, and determine the structure of all of them. For example, we construct strictly optimal binary-coded decimal codes of length four and five, and we show that these are the only possible lengths of such codes     

Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes

The performance of maximum-likelihood (ML) decoded binary linear block codes is addressed via the derivation of tightened upper bounds on their decoding error probability. The upper bounds on the block and bit error probabilities are valid for any memoryless, binary-input and output-symmetric communication channel, and their effectiveness is exemplified for various ensembles of turbo-like codes over the additive white Gaussian noise (AWGN) channel. An expurgation of the distance spectrum of binary linear block codes further tightens the resulting upper bounds     

Commutative group codes for the Gaussian channel

A class of codes for the Gaussian channel is analyzed. The code class is a subclass of the group codes for the Gaussian channel described by Slepian. Using the vector model for the Gaussian channel, the code vectors are obtained by transformations of an initial vector. The class of codes in which the transformations form a commutative group is called the class of commutative group codes. The performance of the codes is evaluated using the union bound on the error probability as a performance measure. The union bound is shown to be closely related to the moments of the scalar product between the code vectors. Commutative group codes are described. It is shown that linear algebraic codes may be represented as commutative group codes. The code class is also shown to include simplex and biorthogonal codes in all dimensions.     

Decoding of Expander Codes at Rates Close to Capacity

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding error probability. Specifically, it is assumed that there exists a family of codes of length N and rate R=(1-epsiv)C (C is a capacity of a binary-symmetric channel), whose decoding probability decreases inverse polynomially in N. It is shown that if the decoding probability decreases sufficiently fast, but still only inverse polynomially fast in N, then there exists another such family of codes whose decoding error probability decreases exponentially fast in N. Moreover, if the decoding time complexity of the assumed family of codes is polynomial in N and 1/epsiv, then the decoding time complexity of the presented family is linear in N and polynomial in 1/epsiv. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes", IEEE Transactions on Information Theory, 2002, and "Concatenated Codes: Serial and Parallel", IEEE Transactions on Information Theory, 2005. It is shown that the latter families cannot be tuned to have exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/epsiv     

Soft-decision differential phase detection of turbo-coded M-ary CPFSK signals over Ricean channels

The performance of turbo codes is examined over the Ricean fading channel with soft-decision differential phase detection (DPD). M-ary continuous phase frequency-shift keying (CPFSK) signaling and puncturing of the coded sequence are considered to achieve bandwidth efficient communication. The effects of the number of phase decision regions, fading conditions, number of states of the constituent codes, and code rate are examined. A bit error rate upper bound is developed, which is useful at low values of bit error probability where computer simulations are lengthy. Significant gains using soft-decision DPD over hard-decision DPD and conventional noncoherent detection are reported.     

On the undetected error probability of nonlinear binary constantweight codes

The undetected error probability (UEP) of binary (n, 2δ, m) nonlinear constant weight codes over the binary symmetric channel (BSC) is investigated, where n is the blocklength, m is the weight of codeword and 2δ is the minimum distance of the codes. The distance distribution of the (n, 2, m) nonlinear constant weight codes is evaluated. It is proven in this paper that the (5, 2, 2) code, (5, 2, 3) code, (6, 2, 3) code, (7, 2, 4) code, (7, 2, 3) code and (8, 2, 4) code are the only proper error-detecting codes in the (n, 2, m) nonlinear constant weight codes for n⩾5, in the sense that their UEP is increased monotonically with the channel error rate p, of course all these proper codes are m-out-of-n codes. Furthermore, it is conjectured that except for the cases of n⩽4δ, there are no proper error-detecting binary (n, 2δ, m) nonlinear constant weight codes, for n>8 and δ⩾1     

Binomial moments of the distance distribution: bounds andapplications

We study a combinatorial invariant of codes which counts the number of ordered pairs of codewords in all subcodes of restricted support in a code. This invariant can be expressed as a linear form of the components of the distance distribution of the code with binomial numbers as coefficients. For this reason we call it a binomial moment of the distance distribution. Binomial moments appear in the proof of the MacWilliams (1963) identities and in many other problems of combinatorial coding theory. We introduce a linear programming problem for bounding these linear forms from below. It turns out that some known codes (1-error-correcting perfect codes, Golay codes, Nordstrom-Robinson code, etc.) yield optimal solutions of this problem, i.e., have minimal possible binomial moments of the distance distribution. We derive several general feasible solutions of this problem, which give lower bounds on the binomial moments of codes with given parameters, and derive the corresponding asymptotic bounds. Applications of these bounds include new lower bounds on the probability of undetected error for binary codes used over the binary-symmetric channel with crossover probability p and optimality of many codes for error detection. Asymptotic analysis of the bounds enables us to extend the range of code rates in which the upper bound on the undetected error exponent is tight     

关于线性分组码的不可检错误概率

本文给出了检错好码的定义,证明了GF(2)上的(n,k)线性分组码为检错好码的充要条件是其对偶码也为检错好码。文中还得到了关于检错好码的一系列新的结果。对二元(n,k)线性分组码,我们给出了不可检错误概率新的下限。这些限只与n和k有关,而与码的重量结构无关。     

Improving the generalized likelihood ratio test for unknown linear Gaussian channels

In this work, we consider the decoding problem for unknown Gaussian linear channels. Important examples of linear channels are the intersymbol interference (ISI) channel and the diversity channel with multiple transmit and receive antennas employing space-time codes (STC). An important class of decoders is based on the generalized likelihood ratio test (GLRT). Our work deals primarily with a decoding algorithm that uniformly improves the error probability of the GLRT decoder for these unknown linear channels. The improvement is attained by increasing the minimal distance associated with the decoder. This improvement is uniform, i.e., for all the possible channel parameters, the error probability is either smaller by a factor (that is exponential in the improved distance), or for some, may remain the same. We also present an algorithm that improves the average (over the channel parameters) error probability of the GLRT decoder. We provide simulation results for both decoders.     

On the computation of the performance probabilities for block codeswith a bounded-distance decoding rule

When a block code is used on a discrete memoryless channel with an incomplete decoding rule that is based on a generalized distance, the probability of decoding failure, the probability of erroneous decoding, and the expected number of symbol decoding errors can be expressed in terms of the generalized weight enumerator polynomials of the code. For the symmetric erasure channel, numerically stable methods to compute these probabilities or expectations are proposed for binary codes whose distance distributions are known, and for linear maximum distance separable (MDS) codes. The method for linear MDS codes saves the computation of the weight distribution and yields upper bounds for the probability of erroneous decoding and for the symbol error rate by the cumulative binomial distribution. Numerical examples include a triple-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) code of length 63 and a Reed-Solomon code of length 1023 and minimum distance 31     

A New Upper Bound on the Block Error Probability After Decoding Over the Erasure Channel

Motivated by cryptographic applications, we derive a new upper bound on the block error probability after decoding over the erasure channel. The bound works for all linear codes and is in terms of the generalized Hamming weights. It turns out to be quite useful for Reed-Muller codes for which all the generalized Hamming weights are known whereas the full weight distribution is only partially known. For these codes, the error probability is related to the cryptographic notion of algebraic immunity. We use our bound to show that the algebraic immunity of a random balanced m-variable Boolean function is of order ^m/₂(1-o(1)) with probability tending to 1 as m goes to infinity     

The threshold probability of a code

We define and estimate the threshold probability &thetas; of a linear code, using a theorem of Margulis (1974) originally conceived for the study of the probability of disconnecting a graph. We then apply this concept to the study of the erasure and Z-channels, for which we propose linear coding schemes that admit simple decoding. We show that &thetas; is particularly relevant to the erasure channel since linear codes achieve a vanishing error probability as long as p⩽&thetas;, where p is the probability of erasure. In effect, &thetas; can be thought of as a capacity notion designed for codes rather than for channels. Binomial codes haven the highest possible &thetas; (and achieve capacity). As for the Z-channel, a subcapacity is derived with respect to the linear coding scheme. For a transition probability in the range ]log (3/2); 1[, we show how to achieve this subcapacity. As a by-product we obtain improved constructions and existential results for intersecting codes (linear Sperner families) which are used in our coding schemes