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 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.<>     

Hybrid burst erasure correction of LDPC codes

In this letter, burst erasure correction of low density parity check codes based on a hybrid approach is presented. The proposed method preserves as much as possible the original low density representation and augments it by specific check sums judiciously selected.     

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.     

Sparse-graph codes for quantum error correction

Sparse-graph codes appropriate for use in quantum error-correction are presented. Quantum error-correcting codes based on sparse graphs are of interest for three reasons. First, the best codes currently known for classical channels are based on sparse graphs. Second, sparse-graph codes keep the number of quantum interactions associated with the quantum error-correction process small: a constant number per quantum bit, independent of the block length. Third, sparse-graph codes often offer great flexibility with respect to block length and rate. We believe some of the codes we present are unsurpassed by previously published quantum error-correcting codes.     

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.     

New array codes for multiple phased burst correction

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors     

Random codes: minimum distances and error exponents

Minimum distances, distance distributions, and error exponents on a binary-symmetric channel (BSC) are given for typical codes from Shannon's random code ensemble and for typical codes from a random linear code ensemble. A typical random code of length N and rate R is shown to have minimum distance N/spl delta//sub GV/(2R), where /spl delta//sub GV/(R) is the Gilbert-Varshamov (GV) relative distance at rate R, whereas a typical linear code (TLC) has minimum distance N/spl delta//sub GV/(R). Consequently, a TLC has a better error exponent on a BSC at low rates, namely, the expurgated error exponent.     

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 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.     

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.     

The single burst error detection performance of binary cyclic codes

Using a new statistical model for burst errors, the authors calculate the conditional probability of undetected error for CRC codes with generator polynomials of the form g(x)=(1+x)p(x), p(x) a primitive polynomial. They show that the choice of p(x) affects the performance of these codes     

Some classes of burst asymmetric or undirectional error correcting codes

Classes of systematic codes correcting burst asymmetric or unidirectional errors are proposed. These codes have less check bits than ordinary burst error correcting codes. Decoding algorithms for the proposed codes are also presented. Encoding and decoding of the codes is very easy.<>     

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     

Using codes for error correction and detection (Corresp.)

A linear codeCover GF(q)is good fort-error-correction and error detection ifP(C,t;epsilon) leq P(C,t;(q - 1)/q)for allepsilon, 0 leq epsilon leq (q - 1)/q, whereP(C, t; epsilon)is the probability of an undetected error after a codeword inCis transmitted over aq-ary symmetric channel with error probabilityepsilonand correction is performed for all error patterns withtor fewer errors. A sufficient condition for a code to be good is derived. This sufficient condition is easy to check, and examples to illustrate the method are given.     

Efficient implementation of error correction codes in hash tables

Hash tables are one of the most commonly used data structures in computing applications. They are used for example to organize a data set such that searches can be performed efficiently. The data stored in a hash table is commonly stored in memory and can suffer errors. To ensure that data stored in a memory is not corrupted when it suffers errors, Error Correction Codes (ECCs) are commonly used. In this research note a scheme to efficiently implement ECCs for the entries stored in hash tables is presented. The main idea is to use an ECC as the hash function that is used to construct the table. This eliminates the need to store the parity bits for the entries in the memory as they are implicit in the hash table construction thus reducing the implementation cost.     

On decoding iterated codes

Algorithms to decode iterated codes when at least one of the "component codes" is majority decodable are given. The decoding algorithms allow the use of the decoders of the component codes and still make it possible to correct all error patterns guaranteed to be correctable by the minimum distance of the iterated code.     

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     

Subspace-based error and erasure correction with DFT codes for wireless channels

This paper deals with the decoding of lowpass discrete Fourier transform (DFT) codes in the presence of both errors and erasures. We propose a subspace-based approach for the error localization that is similar to the subspace approaches followed in the array signal processing for direction-of-arrival (DOA) estimation. The basic idea is to divide a vector space into two orthogonal subspaces of which one is spanned by the error locator vectors. The locations of the errors are estimated from the spanning eigenvectors of the complement subspace. However, unlike the subspace approach in DOA estimation, which is similar to estimating the subspaces from the syndrome covariance matrix after a projection, in the proposed approach, the subspaces are estimated from the modified syndrome covariance matrix after a whitening transform. Simulation results with a Gauss-Markov source reveal that the proposed algorithm is more efficient than the coding theoretic approach on impulsive channels as well as the subspace approach with projection on lossy channels.