In this paper we present a new error-control technique intended for use in2^l-level data-transmission systems that employ Gray coding to transform a binary source sequence into the2^l-ary transmitted sequence. The codes, which we calli-compressed codes, make use of the structure of binary codes and have the property that for some integeri,1 \leq i \leq l, transmission errors can be corrected if the erroneously received signals lie less than2^{i-1}levels from the corresponding correct, or nominal signal levels. The number of such errors that can be corrected is related to the error-correcting capability of the underlying binary code used in the construction. In return for this restriction on the magnitude of correctable errors in the received signal, these codes have higher rates than binary codes of comparable length (in bits) and number of correctable errors. Hence in applications where it can be assumed that the fraction of errors exceeding a certain magnitude is negligible (or at least tolerable), this technique is more efficient than the conventional practice of placing a binary encoder between the data source and modulator and a binary decoder between the demodulator and data sink. Furthermore, although thei-compressed codes are nonbinary, the decoding algorithm is that of the underlying binary code plus a small amount of additional processing; hence it is generally simpler to implement than other nonbinary decoding algorithms. It is also observed that the rate of ani-compressed code is always greater than that of the underlying binary code. Thus certain classes of low-rate binary codes that have simple decoding algorithms can be used as underlying codes in the construction of high-rate easily decodablei-compressed codes. Finally, for the casei = 1, encoding and decoding becomes exceptionally simple and for this case it is possible to make use of "soft decisions" at the receiver to improve the performance.

At each step in Berlekamp's iterative algorithm for BCH codes, the decoder follows one of two possible branches. This correspondence presents a slight rephrasing of the algorithm for binary codes, which results in a very simple circuit for controlling the branching process. This circuit also performs all necessary tests on the validity of the resulting error-locator polynomial.

The burst-trapping error control technique developed by Tong [1] corrects both random and burst errors adaptively. A generalization of this scheme, called generalized burst trapping (GBT), is presented here. Generalized burst-trapping codes (GBTC) also correct both random and burst errors adaptively but, in addition, are capable of correcting random errors in the guard space following a correctable burst. This added capability is obtained at the expense of a longer guard space or a lower rate and a modest increase in complexity of implementation. Nevertheless, these codes are simple to encode and decode and, in particular, the storage-saving technique used with the original burst-trapping codes is directly applicable to the generalized codes. Also it is shown that at most one block of error propagation can occur if a simple and reasonable condition is met. Thus the generalized codes have better propagation properties than the original burst-trapping codes. This new error control technique is well suited to error correction on channels where it cannot be assumed that bursts are isolated events separated by error-free intervals. Thus, for example, this technique appears well suited to error correction on telephone facilities that incorporate multiple-level signaling.

One of the simplest, yet most effective schemes thus far devised for the correction of errors on compound channels is the adaptive decoding scheme invented by Gallager. In this paper we present a generalization of this scheme which, at a modest sacrifice in rate, enables the decoder to correct a burst even when the guard space following the burst contains random errors. This is accomplished with the use of two convolutional codes,CandC^ {\ast}, whereC^ {\ast}containsC. At the encoder, the information sequence is first encoded withCand then, after a fixed delay, is encoded with a "shortened" version ofC^ {\ast}, which is added to the parity sequences ofC. At the decoder there are two modes of operation, a random mode and a burst mode. In the random mode errors are corrected withCin a manner similar to that of the Gallager scheme. In the burst mode, the information bits in the bursty blocks are recovered from the later blocks where they have been superimposed on the parity bits. In this mode a decoder forC^ {\ast}, which precedes the decoder forC, removes random errors from these later blocks, thereby greatly increasing the probability of recovery from the burst.

The problem of error propagation in uniform codes is investigated using the concept of parity-parallelogram submatrices and the threshold-decoding algorithm. A set of optimum orthogonalization rules is presented and it is shown that if these rules are incorporated into the decoder, then sufficient conditions can be found for the return of the decoder to correct operation following a decoding error. These conditions are considerably less stringent than the requirement that the channel be completely free of errors following a decoding error. However, this is not the case if the prescribed orthogonalization rules are not followed, as is demonstrated with a simple example. It is also shown that the syndrome memory required with Massey's orthogonalization procedure for definite decoding of uniform codes is the lowest possible. The results of simulation of the rate\frac{1}{4}and\frac{1}{8}uniform codes are presented, and these codes are seen to make fewer decoding errors with feedback decoding than with definite decoding. Comparison of the performance of an ordinary feedback decoder with a genie-aided feedback decoder, which never propagates errors, indicates that error propagation with uniform codes is a minor problem if the optimum orthogonalization rules are used, but that the situation is somewhat worse with nonoptimum orthogonalization.

The probability of a set of binaryn-tuples is defined to be the sum of the probabilities of the individualn-tuples when each digit is chosen independently with the same probabilitypof being a "one." It is shown that, under such a definition, the ratio between the probability of a subgroup of order2^{k}and any of its proper cosets is always greater than or equal to a functionF_{k}(p), whereF_{k}(p) \geq 1forp \leq \frac{1}{2}with equality when and only whenp = \frac{1}{2}. It is further shown thatF_{k}(p)is the greatest lower bound on this ratio, since a subgroup and proper coset of order2^{k}can always be found such that the ratio between their probabilities is exactlyF_{k}(p). It is then demonstrated that for a linear code on a binary symmetric channel the "tall-zero" syndrome is more probable than any other syndrome. This result is applied to the problem of error propagation in convolutional codes.