We suggest a decoding algorithm of q-ary linear codes, which we call supercode decoding. It ensures the error probability that approaches the error probability of minimum-distance decoding as the length of the code grows. For n/spl rarr//spl infin/ the algorithm has the maximum-likelihood performance. The asymptotic complexity of supercode decoding is exponentially smaller than the complexity of all other methods known. The algorithm develops the ideas of covering-set decoding and split syndrome decoding.

By means of local search techniques, five quasi-cyclic codes have been found that have a higher minimum distance than known binary linear codes. The new codes have parameters [102,17,37], [60,20,17], [84,21,27], [105,21,36], and [100,25,30]. Also, 39 other quasi-cyclic codes have been found that improve the parameter sets of previously known quasi-cyclic codes. Twenty-four of them give a new and easier description of binary linear codes with best known parameters.

New multilevel constructions of the Golay code and the Leech lattice are presented. These are derived from the Turyn construction and the "holy construction" with the octacode as the glue code. Further, we show that the "holy construction" of the Leech lattice with the octacode as the glue code is essentially different from the permuted Turyn construction, although both constructions rely on the octacode. The Turyn construction is based on an "odd" type of the octacode, whereas any type of the octacode can be used in the "holy construction." Moreover, the multilevel representation of the "holy construction" leads to a novel lattice partition chain. Based on these structures, we derive new bounded-distance decoders for the Golay code and the Leech lattice whose effective error coefficient is smaller than that of any previously known bounded-distance decoder. We provide a general theorem for computing the effective error coefficient of coset decoding with bounded distance decoding for the subcode.>

Multilevel constructions of the binary Golay code and the Leech lattice are described. Both constructions are based upon the projection of the Golay code and the Leech lattice onto the (6,3,4) hexacode over GF(4). However, unlike the previously reported constructions, the new multilevel constructions make the three levels independent by way of using a different set of coset representatives for one of the quaternary coordinates. Based upon the multilevel structure of the Golay code and the Leech lattice, efficient bounded-distance decoding algorithms are devised. The bounded-distance decoder for the binary Golay code requires at most 431 operations. As compared to 651 operations for the best known maximum-likelihood decoder. Efficient bounded-distance decoding of the Leech lattice is achieved by means of partitioning it into four cosets of Q/sub 24/, beyond the conventional partition into two H/sub 24/ cosets. The complexity of the resulting decoder is only 953 real operations on the average and 1007 operations in the worst case, as compared to about 3600 operations for the best known in maximum-likelihood decoder. It is shown that the proposed algorithms decode correctly at least up to the guaranteed error-correction radius of the maximum-likelihood decoder. Thus, the loss in coding-gain is due primarily to an increase in the effective error-coefficient, which is calculated exactly for both algorithms. Furthermore, the performance of the Leech lattice decoder on the AWGN channel is evaluated experimentally by means of a comprehensive computer simulation. The results show a loss in coding-gain of less than 0.1 dB relative to the maximum-likelihood decoder for BER ranging from 10/sup -1/ to 10/sup -7/.>

A new approach for encoding any string of information bits into a sequence having bounded running digital sum is presented. The results improve previously known values of the running digital sum for the same rate. Also discussed are ways of incorporating an error-correcting capability into these codes. Some general constructions are given and tables are constructed for specific cases.>

Two new implementations of a maximum-likelihood soft-decision decoding algorithm for binary linear codes are derived. Instead of checking only error patterns yielding a codeword when added to the rounded-off version of the received vector, these implementations principally consider all possible column patterns. Compared to known implementations, this allows a more efficient use of branching and bounding techniques.>

For the additive white Gaussian noise channel, there is a gap between the channel capacity and the highest achievable rate of equiprobable uniformly spaced one-dimensional signaling. It is commonly believed that approaching channel capacity requires the constituent one-dimensional signal points to have a Gaussian probability distribution. It is shown that the channel capacity can be achieved by equiprobable signaling with geometrical, Gaussian-like signal sets. Construction of these signal constellations is explicitly given. This result implicates that it is possible to approach channel capacity without using any kind of shaping codes.>

Several methods of constructing systematic t-error correcting/all unidirectional error-detecting codes are described. These codes can be constructed by adding a tail to a linear t-error correcting code, but other constructions presented are more of an ad hoc nature. These codes will often be found as suitably chosen subsets of nonsystematic tEC/AUED codes. Further bounds on the word length of systematic tEC/AUED codes are derived, and extensive tables are given.>

For a number of binary cyclic codes with e>e/sub BCH/, algebraic algorithms are given to find the error locator polynomial. Thus, for these codes more errors can be corrected algebraically than by the Berlekamp-Massey algorithm. In some cases, all error patterns of weight up to e can be decoded; in other cases, only error patterns of weight up to e' with e/sub BCH/>

The authors present families of binary systematics codes that can correct t random errors and detect more than t unidirectional errors. The first step of the construction is encoding the k information symbols into a codeword of an (n', k, 2t+1) error-correcting code. The second step involves adding more bits to this linear error-correcting code in order to obtain the detection capability of all unidirectional errors. Asymmetric error-correcting codes turn out to be a powerful tool in the proposed construction. The resulting codes significantly improve previous results. Asymptotic estimates and decoding algorithms are presented.>

Results are presented on families of balanced binary error-correcting codes that extend those in the literature. The idea is to consider balanced blocks as symbols over an alphabet and to construct error-correcting codes over that alphabet. Encoding and decoding procedures are presented. Several improvements to the general construction are discussed.>

A new class of codes, called burst identification codes, is defined and studied. These codes can be used to determine the patterns of burst errors. Two-dimensional burst correcting codes can be easily constructed from burst identification codes. The resulting class of codes is simple to implement and has lower redundancy than other comparable codes. The results are pertinent to the study of radiation effects on VLSI RAM chips, which can cause two-dimensional bursts of errors.>

Two families of binary linear multiple-burst-correcting array codes are presented. The codes consist of all possible n/sub 1/*n/sub 2/ arrays over GF(2), where the columns have even parity and the rows belong to any given code of length n/sub 2/ and minimum distance 2t. It is shown that if the bits are read out diagonally instead of horizontally, each diagonal followed by the preceding one (viewed cyclically), then the code can correct up to t bursts of lengthor=tn/sub 1/+1. If each diagonal is followed by the next one, the code can correct up to t bursts of lengthor=2t(n-2)+1. For t=1 some of these results are already known. Decoding algorithms are presented, and the case t=1 is discussed in more detail.>

It is shown that for each integerb \geq 1infinitely many optimum cyclicb-burst-correcting codes exist, i.e., codes whose lengthn, redundancyr, and burst-correcting capabilityb, satisfyn = 2^{r-b+1} - 1. Some optimum codes forb = 3, 4, and5are also studied in detail.

The usual(k_{2} + 1) \times (k_{1} + 1)array code, in which the last row and the last column contain redundant bits, can correct any single error. However, if the bits are read diagonally instead of horizontally, the code can correct bursts of errors. It is shown that the(_{k}2 + 1) \times (k_{1} + 1)array code with diagonal readout can correct any burst of length up tok_{1}if and only ifk_{2} \geq 2(k_{1} - 1).

Using earlier methods a combinatorial upper bound is derived for|C|. \cdot |D|, where(C,D)is a\delta-decodable code pair for the noisy two-access binary adder channel. Asymptotically, this bound reduces toR_{1}=R_{2} \leq \frac{3}{2} + e\log_{2} e - (\frac{1}{2} + e) \log_{2} (1 + 2e)= \frac{1}{2} - e + H(\frac{1}{2} - e) - \frac{1}{2}H(2e),wheree = \lfloor (\delta - 1)/2 \rfloor /n, n \rightarrow \inftyandR_{1}resp.R_{2}is the rate of the codeCresp.D.

An explicit construction is presented of uniquely decodable code pairs for the two-access binary erasure channel. Through a computer search we found many code pairs coming from this construction with a rate pair above the nonconstructive lower bound known in the literature. Also presented is a simple uniquely decodable code pair, with a high rate pair, found by a different method.

Letg(k, d) = \sum_{i=0}^{k-1} \lceil d / 2^{i} \rceil. By the Griesmer bound,n \geq g(k, d)for any binary, linear[n, k, d]code. Lets = \lceil d / 2^{k-1} \rceil. Then,scan be interpreted as the maximum number of occurrences of a column in the generator matrix of any code with parameters[g(k, d), k, d]. Let\rhobe the covering radius of a [g(k, d), k, d] code. It will be shown that\rho \leq d - \lceil s / 2 \rceil. Moreover, the existence of a[g(k, d), k, d]code with\rho = d - \lceil s / 2 \rceilis equivalent to the existence of a[g(k + 1, d), k + 1, d]code. Fors \leq 2, all[g(k,d),k,d]codes with\rho = d - \lceil s / 2 \rceilare described, while fors > 2a sufficient condition for their existence is formulated.

An algebraic and a combinatorial upper bound are derived on|C_{2}|given the codeC_{1}, where(C_{l}, C_{2})is a uniquely decodable code pair(C_{1}, C_{2})for a two-access binary adder channel. A uniquely decodable code with rate pair(0.5170, 0.7814)is also described.

An infinite sequence ofk-dimensional binary linear block codes is constructed with parametersn=2^{k}+2^{k-2}-15,d=2^{k-1}+2^{k-3}-8,k \geq 7. Fork \geq 8these codes are unique, while there are five nonisomorphic codes fork=7. By shortening these codes in an appropriate way, one finds codes meeting the Griesmer bound for2^{k-1}+2^{k-3}-15 \leq d \leq 2^{k-1}+2^{k-3}-8; k \geq 7.

Alternate symbol inversion is sometimes applied to the output of convolutional encoders to guarantee sufficient richness of symbol transition for the receiver symbol synchronizer. A bound is given for the length of the transition-free symbol stream in such systems, and those convolutional codes are characterized in which arbitrarily long transition free runs occur.

The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown. This strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.

A method for determining an upper bound for the size of a code for a two-access binary erasure channel is presented. For uniquely decodable codes, this bound gives a combinatorial proof of a result by Liao. Examples of the bound are given for codes with minimum distance 4.

An integer linear programming problem and an additional divisibility condition are described such that they have a common solution if and only if there is a quasi-cyclic code with rate1/m. A table of binary quasi-cyclic codes with dimensions seven and eight and rate1/mfor smallmis included. In particular, there are binary linear codes with (length, dimension, minimum distance)=(35, 7,16), (42, 7,19), (80, 8, 37), (96, 8, 46), and(112,8,54).