Spectrum of incorrectly decoded bursts for cyclic burst error codes

The enumeration of the incorrectly decoded bursts for cyclic burst error-correcting codes is reported here. The enumeration yields closed formulas for long bursts, whereas an efficient algorithm for the enumeration is given for the short bursts. The enumeration is carried out for two different decoding rules. Under the first rule, the cyclic code is a full length code, and split decodable patterns are decoded by the decoder in spite of the fact that a split decodable pattern can be a burst that exceeds the decoding capability of the decoder. The analysis for the second rule assumes split patterns are not decoded. This analysis is valid for the class of shortened cyclic codes.     

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 burst error correcting power of m-sequence codes

Linear maximum length sequence codes are shown to be asymptotically efficient burst error correcting codes. These codes are essentially single burst correctors and for binary alphabets have the following parameters : block length, n = 2^m ? 1 ; number of information digits, k = m; and burst error correcting capability, b≥2^m?1 ? m, m ≥ 2 ; where m is an integer. A generalization to multilevel alphabets is also presented.     

Permutation-decodable binary cyclic codes

The letter develops bounds on the information rates of certain binary cyclic codes so that they are s-step permutation decodable (s=2, 3, 4).     

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     

Self-synchronizing codes derived from binary cyclic codes

The sensitivity of a binary block code to loss of synchronism (misplacement of the "commas" separating codewords) can be characterized by a pair of numbers[s, delta]such that any synchronization slip of s bits or less produces an overlap sequence differing from a legitimate codeword in at leastdeltaplaces. This definition is broader than that of comma freedom of indexdelta, which is included as the special case of s equal to the integer part of half the code block length. For codes having the slip-detecting characteristic[s, delta]there exists the possibility of implementation to restore synchronism during an interval relatively free from bit errors. It is shown that certain error-correcting binary cyclic block codes can be altered to obtain the characteristic[s, delta]by the addition of a fixed binary vector to each codeword prior to transmission. These altered cyclic codes retain the full error-correcting power of the original cyclic codes. An error-detecting/correcting data format providing protection against the acceptance of misframed data is thus obtained without the insertion of special synchronizing sequences into the bit stream.     

Easily decodable binary cyclic codes

This paper presents a class of binary cyclic codes with block length n = 2^m? 1, having n?k = 2^m? parity checks and a minimum distance d=m +1, where m is an integer. These codes are shown to be majority logic decodable in one step by making use of the concept of a quasi-perfect finite difference set.     

Reduced-redundancy product codes for burst error correction

In a typical burst error correction application of a product code of n_v×n_h arrays, one uses an [n_h, n_h-r_h] code C_h that detects corrupted rows, and an [n_v, n_v-r_v] code C_v that is applied to the columns while regarding the detected corrupted rows as erasures. Although this conventional product code scheme offers very good error protection, it contains excessive redundancy, due to the fact that the code C_h provides the code C_v with information on many error patterns that exceed the correction capability of C_v. A coding scheme is proposed in which this excess redundancy is eliminated, resulting in significant savings in the overall redundancy compared to the conventional case, while offering the same error protection. The redundancy of the proposed scheme is n_hr_v+r_h(lnr_v+O(1))+r_v , where the parameters r_h and r_v are close in value to their counterparts in the conventional case, which has redundancy n_hr_v+n_vr_h-r_h r_v. In particular, when the codes C_h and C _v have the same rate and r_h≪n_h, the redundancy of the proposed scheme is close to one-half of that of the conventional product code counterpart. Variants of the scheme are presented for channels that are mostly bursty, and for channels with a combination of random errors and burst errors     

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     

New binary codes from a chain of cyclic codes

Starting with a chain of cyclic linear binary codes of length 127, linear binary codes of lengths 129-167, and dimensions 30-50 are constructed. Some of these codes have a minimum distance exceeding the lower bound given in Brouwer's table     

The simplex codes and other even-weight binary linear codes for error correction

The probability of correct decoding on the binary-symmetric channel is studied. In particular, a class of codes with the same lengths and dimensions as the linear simplex codes, but with larger probability of correct decoding for all parameters p, 0 < p < 1/2, is given.     

A class of binary burst error-correcting quasi-cyclic codes

A class of binary quasi-cyclic burst error-correcting codes based upon product codes is studied. An expression for the maximum burst error-correcting capability for each code in the class is given. In certain cases, the codes exist in the class which have the same block length and number of check bits as the Gilbert codes, but correct longer bursts of errors than Gilbert codes. By shortening the codes, it is possible to design codes which achieve the Reiger bound     

Random error and burst correction by iterated codes

We give a decoding algorithm for iterated codes that can correct up to the number of errors guaranteed by the product minimum distance, rather than about half that number when the iterated codes are decoded independently. This result is achieved by adapting Forney's generalized minimum distance decoding for use with iterated codes. We derive results on the simultaneous burst- and random-error-correction capability of iterated codes that improve considerably on known results.     

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.     

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 undetected error probability for binary codes

In this paper, the undetected error probability for binary codes is studied. First complementary codes are studied. Next, a new proof of Abdel-Ghaffar's (1997) lower bound on the undetected error probability is presented and some generalizations are given. Further, upper and lower bounds on the undetected error probability for binary constant weight codes are given, and asymptotic versions are studied.     

Runlength limited codes for random and burst error correction

A product code approach to the design of multiple error correcting runlength limited codes is presented. In contrast to recent coding schemes of this type they are based entirely on binary coding operations and are therefore relatively simple to realise in hardware. A table of some illustrative codes is presented.<>     

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.     

The minimum distance of the duals of binary irreducible cyclic codes

Irreducible cyclic codes have been an interesting subject of study for many years. The weight distribution of some of them have been determined. We determine the minimum distance and certain weights of the duals of binary irreducible cyclic codes. We show that the weight distribution of these codes is determined by the cyclotomic numbers of certain order. As a byproduct, we describe a class of double-error correcting codes.