Optimal codes for correcting single errors and detecting adjacenterrors

Optimal codes that correct single errors and detect double errors within nibbles of power of two length are presented. For each n, a code of length n with the largest possible dimension which corrects single errors and detects double adjacent errors is presented. The problem of constructing optimal codes which correct single errors and detect double adjacent errors within nibbles of length l is discussed     

Bounds and constructions for codes correcting unidirectional errors

A brief introduction is given on the theory of codes correcting unidirectional errors, in the context of symmetric and asymmetric error-correcting codes. Upper bounds on the size of a code of length n correcting t or fewer unidirectional errors are then derived. Methods in which codes correcting up to t unidirectional errors are constructed by expurgating t-fold asymmetric error-correcting codes or by expurgating and puncturing t -fold symmetric error-correcting codes are also presented. Finally, tables summarizing some results on the size of optimal unidirectional error-correcting codes which follow from these bounds and constructions are given     

Weight distribution of translates, covering radius, and perfect codes correcting errors of given weights

LetVbed binary linear(n,k)code defined by a check matrixHand leth(x)be the characteristic function for the set of columns ofH. Connections between the Walsh transform ofh(x)and the weight distributions of all translates of the code are obtained. Explicit formulas for the weight distributions of translates are given for small weightsi(i<8). The computation of the weight distribution of all translates (including the code itself) fori<8requires at most7(n-k)2^{n-k}additions and subtractions,6 cdot 2^{n-k}multiplications and2^{n-k+l}memory cells. This method may be very effective if there is an analytic expression forh(x). A simple method for computing the covering radius of the code by the Walsh transform ofh(x)is described. The implementation of this method requires for largenat most2^{n-k}(n-k) log_{2}(n-k)arithmetical operations and2^{n-k+1}memory cells. We define the conceptL-perfect for codes, whereLis a set of weights. After describing several linear and nonlinearL-perfect codes, necessary and sufficient conditions for a code to beL-perfect in terms of the Walsh transform ofh(x)are established. An analog of the Lloyd theorem for such codes is proved.     

Bounds on constant weight codes correcting localized errors

We derive upper and lower bounds for constant weight codes on a channel with localized errors. Coding for channels with localized errors is a new branch of coding theory. From a practical point of view it is important to find good, easily decodable codes. From an information theory point of view it is important to investigate how good these codes can be, that is finding the theoretical limits. For conventional error correcting codes a great deal of interest has been directed towards constant weight codes. They have properties which make them interesting in various situations. This fact has motivated us to look at constant weight codes for localized errors     

New lower bounds and constructions for binary codes correcting asymmetric errors

In this correspondence, we study binary asymmetric error-correcting codes. A general construction for binary asymmetric error-correcting codes is presented. We show that some previously known lower bounds for binary asymmetric error-correcting codes can be obtained from this general construction. Furthermore, some new lower bounds for binary asymmetric error-correcting codes are obtained from this general construction. These new lower bounds improve the existing ones.     

Some new binary codes correcting asymmetric/unidirectional errors

The authors give a tabulation of the numbers of codewords in new binary codes with the asymmetric/unidirectional error-correcting capabilities of 3, 4, 5, 6 for lengths 14, 15, . . . , 23. The new codes have greater sizes than the known codes for 14⩽n⩽23 and 3⩽t⩽6     

Block codes capable of correcting both additive and timing errors

Binary block codes are constructed that are capable of correcting successive timing errors such as the deletion or insertion ofsbits(sleq D)within a single additive burst of errors of lengthbor less(b=f+g+2D), wherefandDare the design parameters that specify the length of correctable successive timing errors andgis the length of the correctable additive burst. A decoding algorithm is given and the efficiency of these codes is discussed.     

Upper bounds on codes correcting asymmetric errors (Corresp.)

A Survey is given of known upper bounds on codes correcting asymmetric errors. The bounds are improved by introducing new Ideas. By solving a linear programming problem an upper bound is given that is easy to compute for all codelengths and all minimum asymmetric distances.     

A new decoding algorithm for correcting both erasures and errors of Reed-Solomon codes

In this paper, a high efficient decoding algorithm is developed here in order to correct both erasures and errors for Reed-Solomon (RS) codes based on the Euclidean algorithm together with the Berlekamp-Massey (BM) algorithm. The new decoding algorithm computes the errata locator polynomial and the errata evaluator polynomial simultaneously without performing polynomial divisions, and there is no need for the computation of the discrepancies and the field element inversions. Also, the separate computation of the Forney syndrome needed in the decoder is completely avoided. As a consequence, the complexity of this new decoding algorithm is dramatically reduced. Finally, the new algorithm has been verified through a software simulation using C/sup ++/ language. An illustrative example of (255,239) RS code using this program shows that the speed of the decoding process is approximately three times faster than that of the inverse-free Berlekamp-Massey algorithm.     

Multiple-word correcting convolutional codes

Two classes of multiple-word correcting convolutional encoders are defined and analyzed. We obtain some conditions for these encoders to be noncatastrophic, and we describe ways to check the (word) minimum distance of the generated codes. The first class can easily be analyzed by algebraic means, but the redundancy of the corresponding codes is not arbitrarily iow. The codes generated by the second class of encoders may have a lower redundancy, but their analysis requires the use of a computer program.     

Parallel error correcting codes

We introduce the concept of "parallel error correcting" codes, the error correcting codes for parallel channels. Here, a parallel channel is a set of channels such that the additive error over a finite field occurs in one of its members at time T if the same error occurs in all members at the same time. The set of codewords of a parallel error correcting code has to be a product set, if the messages transmitted are from independent information sources. We present a simple construction of optimal parallel error correcting codes based on ordinary optimal error correcting codes and a construction of optimal linear parallel codes for independent sources based on optimal ordinary linear error correcting codes. The decoding algorithms for these codes are provided as well     

Efficient erasure correcting codes

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number ϵ a family of linear codes of rate R which can be encoded in time proportional to ln(1/ϵ) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+ϵ)Rn or more. The recovery algorithm also runs in time proportional to n ln(1/ϵ). Our algorithms have been implemented and work well in practice; various implementation issues are discussed     

New lower bounds for covering codes

Some new lower bounds on |C| for a binary linear [n, k]R code C with n+1=t(R +1)-r(0⩽r<R+1, t>2 odd) or with n+1=t(R+1)-1(t>2 even) are obtained. These bounds improve the sphere covering bound considerably and give several new values and lower bounds for the function t[n, k], the smallest covering radius of any [n, k] code     

Lower bounds for binary covering codes

G.D. Chen et al. (ibid., vol.IT-32, p.680-94, 1986) presented two new lower bounds for K(n,R), where K(n,R) denotes the minimum cardinality of a binary code of length n and covering radius R. The author shows that a slight modification gives further improvements and some examples are given to confirm the argument. Codes that have a certain partitioning property are considered     

Reed-Solomon codes for correcting phased error bursts

A code structure is introduced that represents a Reed-Solomon (RS) code in two-dimensional format. Based on this structure, a novel approach to multiple error burst correction using RS codes is proposed. For a model of phased error bursts, where each burst can affect one of the columns in a two-dimensional transmitted word, it is shown that the bursts can be corrected using a known multisequence shift-register synthesis algorithm. It is further shown that the resulting codes posses nearly optimal burst correction capability, under certain probability of decoding failure. Finally, low-complexity systematic encoding and syndrome computation algorithms for these codes are discussed. The proposed scheme may also find use in decoding of different coding schemes based on RS codes, such as product or concatenated codes.     

New upper bounds on the size of codes correcting asymmetric errors (Corresp.)

New upper bounds on the size of codes correcting asymmetric errors are derived by sharpening some of the constraints in the integer programming problem of Delsarte and Piret. It is shown that their code for length9and asymmetric distance2is optimal.     

Linear codes with covering radius 2, 3 and saturating sets in projective geometry

Infinite families of linear codes with covering radius R=2, 3 and codimension tR+1 are constructed on the base of starting codes with codimension 3 and 4. Parity-check matrices of the starting codes are treated as saturating sets in projective geometry that are obtained by computer search using projective properties of objects. Upper bounds on the length function and on the smallest sizes of saturating sets are given.     

On the structure of linear codes with covering radius two and three

We obtain new bounds on l(m,r), the minimum length of a linear code with codimension m and covering radius r. All bounds are derived in a uniform way. We employ results from coding theory, some earlier results on covering codes, and combinatorial arguments. We prove the following bounds: l(6, 2)=13, l(7,2)=19, l(8,2)⩾25, l(9,2)⩾34, l(2m-l,2)⩾2^m+1 for m⩾3, l(14,2)⩾182, l(16,2)⩾363, l(18,2)⩾725, l(20,2)⩾1449, l(22,2)⩾2897, l(24,2)⩾5794, l(9,3)⩾17, l(10,3)⩾21, l(12,3)⩾31, l(13,3)⩾38     

Long packing and covering codes

We study geometrically the domain of linear binary codes and of unrestricted binary codes in the plane (normalized covering radius, normalized minimal distance)