Even-weighted codes for error detection

For a binary symmetric channel, a code V with only evenweighted words performs better than a corresponding code V? with both odd- and even-weighted words, from the point of the probability of undetected errors. We derive an estimate of the improvement in the performance.     

Poor error correction codes are poor error detection codes (Corresp.)

We show that binary group codes that do not satisfy the asymptotic Varshamov-Gilbert bound have an undesirable characteristic when used as error detection codes for transmission over the binary symmetric channel.     

Optimal codes for minimax criterion on error detection

Nonlinear quadratic codes that are optimal for the minimax error detection are presented. Characteristic functions for these codes are asymptotically bent. For a given block size n and the number of codewords |C|, these codes minimize max Q(e), e≠0, where Q(e) is the conditional error-masking probability, given the error pattern e. The codewords are blocks of n symbols from GF(q). Encoding and decoding procedures for the codes are described     

Fast software implementation of error detection codes

Software implementations of error detection codes are considered to be slow compared to other parts of the communication system. This is especially true for powerful error detection codes such as CRC. However, we have found that powerful error detection codes can run surprisingly fast in software. We discuss techniques for, and measure the performance of, fast software implementation of the cyclic redundancy check (CRC), weighted sum codes (WSC), one's-complement checksum, Fletcher (1982) checksum, CXOR checksum, and block parity code. Instruction count alone does not determine the fastest error detection code. Our results show the computer memory hierarchy also affects performance. Although our experiments were performed on a Sun SPARCstation LX, many of the techniques and conclusions will apply to other processors and error detection codes. Given the performance of various error detection codes, a protocol designer can choose a code with the desired speed and error detection power that is appropriate for his network and application     

On error detection and error synchronization of reversible variable-length codes

Reversible variable-length codes (RVLCs) are not only prefix-free but also suffix-free codes. Due to the additional suffix-free condition, RVLCs are usually nonexhaustive codes. When a bit error occurs in a sentence from a nonexhaustive RVLC, it is possible that the corrupted sentence is not decodable. The error is said to be detected in this case. We present a model for analyzing the error detection and error synchronization characteristics of nonexhaustive VLCs. Six indices, the error detection probability, the mean and the variance of forward error detection delay length, the error synchronization probability, the mean and the variance of forward error synchronization delay length are formulated based on this model. When applying the proposed model to the case of nonexhaustive RVLCs, these formulations can be further simplified. Since RVLCs can be decoded in backward direction, the mean and the variance of backward error detection delay length, the mean and the variance of backward error synchronization delay length are also introduced as measures to examine the error detection and error synchronization characteristics of RVLCs. In addition, we found that error synchronization probabilities of RVLCs with minimum block distance greater than 1 are 0.     

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

The author investigates the (n, k, d⩾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^n-k-n]^-1 when used on a binary symmetric channel with transition probability less than 2/n     

Calculation of error probabilities for distance-invariant nonlinear error control codes

Expressions are given for the distance distribution of some nonlinear codes which enable error probabilities to be calculated using methods commonly associated with linear error control codes.<>     

Turbo-codes: the ultimate error control codes?

Turbo-codes have attracted a great deal of interest since their discovery in 1993. This paper reviews the reasons for this, in particular their attainment of the ultimate limits of the capacity of a communication channel. The paper describes the two fundamental concepts on which they are based: concatenated coding and iterative decoding. This latter is the real `turbo-principle', which is the real secret of their remarkable performance. The paper also reviews the direction of research in this area since 1993, and shows that, far from bringing coding research to an end, turbo-codes have led to a renaissance. In particular, other applications of the `turbo-principle' have emerged, and these are discussed, along with the practical applications of turbo-codes that have appeared, from mobile radio to deep-space exploration     

On testing for improper error detection codes

A family of tests for improper codes is given. These tests can be used in cases where the complete weight distribution of the code is unknown. It was found that knowledge of the number of minimum weight codewords can be used to greatly increase the effectiveness of the asymptotic Varshamov-Gilbert test. Further improvement is possible as more is known about the number of other weight codewords     

Weighted sum codes for error detection and their comparison withexisting codes

Describes a new family of error detection codes called weighted sum codes. These codes are preferred over four existing codes (CRC, Fletcher checksum, Internet checksum, and XTP CXOR), because they combine powerful error detection properties (as good as the CRC) with attractive implementation properties. One variant, WSC-1, has efficient software and hardware implementations; while a second variant, WSC-2, is almost as efficient in software (still significantly better than CRC) and offers commutative processing (that enables efficient out-of-order, parallel, and incremental update processing)     

Maximum runlength-limited codes with error control capabilities

New methods are presented to protect maximum runlength-limited sequences against random and burst errors and to avoid error propagation. The methods employ parallel conversion techniques and enumerative coding algorithms that transform binary user information into constrained codewords. The new schemes have a low complexity and are very efficient. The approach can be used for modulation coding in recording systems and for synchronization and line coding in communication systems. The schemes enable the usage of high-rate constrained codes, as error control can be provided with similar capabilities as for unconstrained sequences     

Efficient codes for single error detection and partial single error correction

Coding schemes are proposed for error control in systems where individual blocks of information are organised as two sub-blocks each requiring a different degree of error control. The codes described guarantee single error correction in one sub-block and provide single error detection and partial single error correction in the other. The main advantages are savings in redundancy and ability to use standard encoding/decoding procedures.     

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.     

Automatic generation of error control codes for computerapplications

This paper proposes a methodology, implemented in a tool, to automatically generate the main classes of error control codes (ECC's) widely applied in computer memory systems to increase reliability and data integrity. New code construction techniques extending the features of previous single error correcting (SEC)-double error detecting (DED)-single byte error detecting (SBD) codes have been integrated in the tool. The proposed techniques construct systematic odd-weight-column SEC-DED-SBD codes with odd-bit-per-byte error correcting (OBC) capabilities to enhance reliability in high speed memory systems organized as multiple-bit-per-chip or card     

Runlength-limited codes for single error detection in the magneticrecording channel

An arithmetic function that assigns the value 0, 1, or 2 to each binary sequence is introduced. The authors call this function the error-check value. Two sequences that differ by a single symmetric error or a single shift error are shown to have different error-check values. Runlength-limited codes for detecting single-errors are designed by taking a set of the constrained sequences such that each code sequence has the same error-check value. Systematic runlength-limited codes that detect single errors are constructed, based on the error-check value. It is shown that these systematic runlength-limited codes have the shortest parity length possible for a single error-detecting code     

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     

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.     

New class of codes suitable for computer error control

A new concept of generalised orthogonality is proposed and a class of generalised orthogonal codes based on SBIBD theory is developed     

The duals of MMD codes are proper for error detection

A linear code, when used for error detection on a symmetric channel, is said to be proper if the corresponding undetected error probability increases monotonically in /spl epsiv/, the symbol error probability of the channel. Such codes are generally considered to perform well in error detection. A number of well-known classes of linear codes are proper, e.g., the perfect codes, MDS codes, MacDonald's codes, MMD codes, and some Near-MDS codes. The aim of this work is to show that also the duals of MMD codes are proper.