A method of constructing binary linear codes that have a minimum Hamming distance of five is presented. The author proposes a general formulation of the parity check matrix for the desired code and then derives necessary conditions for the code to have a minimum distance of five. Some new codes that satisfy the necessary conditions are described. Some efficient new codes are obtained. In particular, a (47,36,5) code is obtained that has six more information bits than the best previously known code with 11 check bits.>

Techniques are presented for the construction of error-correcting codes for semiconductor memory subsystems that are organized in a multibit-per-chip manner. These codes are capable of correcting all single-byte errors and detecting all double-byte errors, where a byte represents the number of bits that are fed from the same chip to the same codeword.

The construction of a class of binary linear codes for masking computer memory defects is presented. These codes are capable of masking three or fewer defects and correcting multiple random errors.

Logic testing of today's integrated circuits is a task of increasing difficulty as the number of circuits or transistors packed onto a single chip grows higher and higher. Exhaustive pattern testing, with adequate partitioning of logic, has been explored regarding its potential in solving the problems in test pattern generation and fault coverage. In this paper, we propose a new method of simultaneously generating exhaustive test patterns for all possible input subsets (each corresponding to an output) up tq a specified size. The method is based on the structure of linear polynomial codes and can be easily implemented by modifying existing shift-registers in an LSSD or scan path design to embody additional feedback connections. This is particularly attractive since the implementation is compatible with the approach of self-testing using pseudorandom patterns. Thus, a very reasonable strategy is to combine limited exhaustive pattern testing with pseudorandom pattern testing ini cases where complete exhaustive testing is not practical.

Single error-correcting and double error-detecting codes capable of detecting all single byte errors are important for practical applications. They can be used to enhance the reliability and the data integrity of computer memory systems. Here we present the construction of these codes. The construction techniques are developed from the theory of orthogonal flats in finite Euclidean geometry.

There are several known approaches to solving quadratic equations over GF(2^{m}). Here the approach to solving the equations is different from the known approaches in that the solutions are presented in terms of the parameters of the equations. The formulas for solving the quadratic equations are also used to solve the equations of degrees three and four. The results can be combined with other known techniques to solve equations of higher degrees.

A general algorithm is derived for the calculation of the error location polynomial in decoding a Bose-Chaudhuri-Hocquenguem (BCH) code. A shorter decoding time is required by the algorithm for low-weight errors because only a subset of the syndrome equations are to be satisfied. The application of the general algorithm to Berlekamp's algorithm is also presented.

Error correcting codes have been successfully employed to correct errors associated with failures in computer memories. A typical code which has found wide application is the binary Hamming code. This code corrects single bit errors. With the advent of large-scale integration (LSI) storage array technology, the likelihood of errors which exceed the correction and detection capability of such a code is significant. A serious and heretofore unanswered question is the error detection capability of a given code which is implemented and decoded for single error correction, particularly when a storage array chip or card carrying multiple bits from the codeword has failed. In order to identify this capability, a new reliability parameter called package detectability is defined. This paper also presents a method for computing package detectability. The analysis has been performed on a number of codes in order to optimize the packaging for maximum detectability. In addition, a class of distance 3 codes with maximal b-bit package detectability is given.

Irreducible Goppa codes extended with an overall parity check are shown to be cyclic or shortened cyclic codes. The location points of a codeword of the extended irreducible codes can be designated as the points of a finite projective geometry. Bounds on the number of equivalence classes of both irreducible and extended irreducible Goppa codes are derived.

A new bound on the error-correcting capability of majority decoding using nonorthogonal parity checks is derived. The new bound is then applied to a class of Euclidean geometry codes.

For the single error correcting convolutional codes introduced by Wyner and Ash, it is shown that if sufficiently few errors occur in an appropriate neighborhood of a block, the probability of correctly decoding that block is independent of errors outside that neighborhood. This fact is used to derive bounds on the bit error probability and the mean time to first error.

A particular shortening technique is applied to majority logic decodable codes of length2^{t}. The shortening technique yields new efficient codes of lengthsn = 2^{p}, wherepis a prime, e.g., a (128,70) code withd_{maj} = 16. For moderately long code lengths (e.g.,n = 2^{11} or 2^{13}), a 20-25 percent increase in efficiency can be achieved over the best previously known majority logic decodable codes. The new technique also yields some efficient codes for lengthsn = 2^{m}wheremis a composite number, for example, a (512,316) code withd_{maj} = 32code which has 42 more information bits than the previously most efficient majority logic decodable code.

An asymptotic bound on the minimum distance is derived to show the existence of good high-rate multiple-error-correcting arithmetic codes.

A new class of cyclic multiple-error-correcting arithmetic codes is described, and the minimum distance of these codes is determined analytically. A two-step majority-logic decoding scheme is developed for these arithmetic codes. The new class of codes is extended to a new class of arithmetic codes having a primitive cyclotomic factor as the generator and anL-step majority-logic decoding scheme is developed for the extended class of codes.

Construction of shortened geometric codes as Shown here results in 1-step majority-logic deeodable codes. The shortened codes retain the error-correction ability of the parent codes and the decoders for the shortened codes are much simpler than for the parent code. A table of shortened codes is given.

In a recent paper [1], techniques for reducing the number of majority-logic decoding steps for finite geometry codes have been proposed. However, the lower bound of [1, lemma 4] is incorrect; finite geometry codes, in general, cannot be decoded in less than or equal to three steps of orthogonalization, as was claimed. This correspondence presents a decoding procedure for finite geometry codes that requires as few decoding steps as possible. It is shown that the minimum number of steps is a logarithmic function of the dimension of the associated geometry.

In this paper constructions are given for combining two, three, or four codes to obtain new codes. The Andryanov-Saskovets construction is generalized. It is shown that the Preparata double-error-correcting codes may be extended by about (block length)^{1/2}symbols, of which only one is a check symbol, and thate-error-correcting BCH codes may sometimes be extended by (block !ength)^{1/e}symbols, of which only one is a check symbol. Several new families of linear and nonlinear double-error-correcting codes are obtained. Finally, an infinite family of linear codes is given withd/n = \frac{1}{3}, the first three being the(24,2^12, 8)Golay code, a(48,2^15, 16)code, and a(96,2^18, 32)code. Most of the codes given have more codewords than any comparable code previously known to us.

In this paper, an improved decoding algorithm for codes that are constructed from finite geometries is introduced. The application of this decoding algorithm to Euclidean geometry (EG) and projective geometry (PG) codes is further discussed. It is shown that these codes can be orthogonalized in less than or equal to three steps. Thus, these codes are majority-logic decodable in no more than three steps. Our results greatly reduce the decoding complexity of EG and PG codes in most cases. They should make these codes very attractive for practical use in error-control systems.