Search

Cyclically permutable codes have error-correcting properties which are invariant under arbitrary cyclic permutation of any of their code words. This paper summarizes the results of an empirical investigation of certain of these codes, which have parameters not covered by a previous paper of E. N. Gilbert. ^{1} These codes are thought to be nearly optimal. Estimates of the obtainable number of code words are given. The codes may be suitable for use in certain asynchronous multiplex communication systems.

In this paper a new decoding scheme for random convolutional codes is described. This scheme is different from other effective decoding schemes, such as sequential decoding [1] and low-density parity check codes [2]. The new scheme yields (for a certain region of information rates) an upper bound on the average number of computations which is {\em independent} of the coding constraint length. Furthermore, unlike sequential decoding, a bound on the total number of computations (rather than just on the "incorrect subset") is derived in this paper.

Recurrent codes for burst-error correction are defined to be a type B1 code. A type B1 code is capable of correcting all the single burst errors of length l or less. A type B2 code is a subclass of a type B1 code with the restriction that the single burst error of length l or less occurs within r consecutive blocks (it is assumed that l is divisible by b and l = rb ). In this paper, the author will present a class of q -nary recurrent codes--both type B1 and B2 codes--for burst-error correction. The construction procedures for this class of codes are simple and systematic. An interesting relation exists between a type B1 and a type B2 code. If a code is type B2 (with block length b , burst-error-correction capability l = rb ), then by reducing the block length by one symbol, the type B2 code becomes a type B1 code, while the burst-error-correction capability remains the same. Both types of codes can be used for the correction of binary burst errors. The correction of binary burst errors will be briefly discussed in this paper.

This paper is concerned with the construction of the most efficient shortened cyclic (pseudo-cyclic) codes that can correct every burst-error of length b or less. These codes have the maximum number of information digits k among all shortened cyclic burst- b codes with a given number of check digits r . The search procedure described is readily programmable for computer execution and efficient particularly for the case where r is close to the theoretical minimum of 2b check digits. For 2 \leq b \leq 10 , several optimum shortened cyclic codes in the above-mentioned sense have been found. Their code-lengths and generators are tabulated in this paper.

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.

To improve the reliability of two-dimensional information, codes that can correct two-dimensional bursts (or spots) may be useful. In this paper a class of two-dimensional burst-correcting codes, called two-dimensional Fire codes, is proposed. The definition of these codes is a natural extension of that of the conventional Fire codes. The two-dimensional Fire code is a two-dimensional cyclic code designed for single two-dimensional burst correction. Several important properties such as the burst-correcting capability and the positions of the check symbols are presented. Also, encoding and decoding methods are presented. It is shown that the encoding and decoding are easily implemented by using two-dimensional feedback shift registers.

A code of integers into binary sequences is called a difference-preserving code (DP code) if it has the following two properties: 1) if the absolute value of the difference between two integers is less than or equal to a certain threshold, the Hamming distance between their codewords is equal to this value and 2) if the absolute value of the difference between two integers exceeds the threshold, then the Hamming distance between their codewords also exceeds this threshold. Such codes (or slight modifications thereof) have also been called path codes, circuit codes, or snake-in-the-box codes. This paper discusses the application of DP codes to pattern recognition and classification problems and presents a construction of efficient DP codes whose information content is asymptotically (in the length of codewords) of the order of theoretical upper bounds.

In many communication channels noise disturbances occur in the form of low-density bursts. Codes capable of correcting multiple bursts of low density are efficient tools of error control for such channels. One such class of codes is presented ia this paper. This Class of codes can be decoded by simple majority logic. The approach is to use codes which are the duals of product codes whose component codes are majority-logic-decodable cyclic codes.

This paper presents majority-decoding algorithms for four classes of binary cyclic codes. The classes are those for which the parity-check polynomial is: 1) the product of two primitive polynomials with relatively prime exponents and 2) the product of (x^r + 1)/(x + 1) and a primitive polynomial, where r \geq 3 is odd and the exponents are relatively prime, together with the corresponding nonexpurgated codes.

This paper describes the application of selected block and convolutional coding techniques to digital transmission over an HF radio channel. Performance results are presented for interleaved binary Bose-Chaudhuri-Hocquenghem (BCH) codes, interleaved two-stage concatenated codes, and diffuse convolutional codes. The performance results are based upon raw error data recorded in transmission over a 640-km HF path, with various data runs representing the typical effects of frequency-selective and non-selective fading, atmospheric impulse noise, and interference from other users of the HF band. The performance of binary BCH codes with bit interleaving is presented and the selection of a code to meet a specified performance criterion is described. The sensitivity of specific codes to changing channel conditions is presented, along with the cost, in terms of interleaving, of designing for one set of channel conditions rather than others. Concatenated codes are discussed as a means of effective error control on channels with clustered errors. Performance data are presented for selected two-stage codes used with inner-stage word interleaving and the effects of varying certain of the code parameters are shown. Emphasis is placed on code designs that use the inner-stage code only for error detection and the outer-stage code mainly for erasure filling with only a small amount of symbol error correction. The impact of error clustering on the performance of concatenated codes is discussed. Two diffuse convolutional codes are evaluated with the use of recorded error data in computer simulations of their threshold-decoding algorithms. Performance of various configurations of these convolutional codes is given and a comparison is made with that of a simple block coding scheme having the same decoder storage requirements. The various coding techniques studied are compared on the basis of achievable performance as well as certain factors affecting the feasibility of implementation.

This paper presents a table of upper and lower bounds on d_{max} (n,k) , the maximum minimum distance over all binary, linear (n,k) error-correcting codes. The table is obtained by combining the best of the existing bounds on d_{max} (n,k) with the minimum distances of known codes and a variety of code-construction techniques.

Bose and Ray-Chaudhuri have recently described a class of binary codes which for arbitrary m and t are t -error correcting and have length 2^m - 1 of which no more than mt digits are redundancy. This paper describes a simple error-correction procedure for these codes. Their cyclic structure is demonstrated and methods of exploiting it to implement the coding and correction procedure using shift registers are outlined. Closer bounds on the number of redundancy digits are derived.

A binary superimposed code consists of a set of code words whose digit-by-digit Boolean sums (1 + 1 = 1) enjoy a prescribed level of distinguishability. These codes find their main application in the representation of document attributes within an information retrieval system, but might also be used as a basis for channel assignments to relieve congestion in crowded communications bands. In this paper some basic properties of nonrandom codes of this family are presented, and formulas and bounds relating the principal code parameters are derived. Finally, there are described several such code families based upon (1) q -nary conventional error-correcting codes, (2) combinatorial arrangements, such as block designs and Latin squares, (3) a graphical construction, and (4) the parity-check matrices of standard binary error-correcting codes.

In this paper, some properties of maximum-distance separable linear codes are presented. Based on these properties, a decoding algorithm for correcting random errors is established. A simpler decoding algorithm for correcting burst errors is also given. Applying these decoding algorithms to known classes of maximum-distance separable linear codes, the amount of hardware required for implementation is only a small fraction of those required by the existing decoding algorithms.

This paper shows the existence (by construction) of rate \frac{1}{2} convolutional codes that correct bursts of length B or t random errors. The codes have memory length and guard space requirements that are asymptotically 4B and minimal effective length. Kohlenberg introduced the term "diffuse code" for his two random-error or single-burst error-correcting codes with minimal effective length and both a memory and guard-space requirement of 3B + 1 . To this point, there does not seem to be any procedure for finding codes with minimal effective length and guard space requirements asymptotically 3B .

The purpose of this paper is to develop more general techniques for the synthesis of error-correcting codes that dispense with the requirement that coding elements and operations must be associated with finite fields. This approach permits an extension of the class of coded messages and coding operations and leads in certain cases to a reduction of implementation complexity.

In this paper we define a subclass of comma-free codes which has a property called path invariance. The main advantage of codes in this subclass lies in the ease of establishing the positions of the divisions between words. Certain path-invariant comma-free dictionaries using K symbols to form n-symbol words are developed and their properties are studied. The number of words in these dictionaries is determined to be L(K-L)^{[n/2]}K^{[(n-1)/2]} where L is a parameter which equals one when n \geq 4K/3 , and [x] denotes the integral part of x . That this is the maximum obtainable dictionary size is proved for a special case. The ability of these codes to correct registration (synchronization) errors when n consecutive symbols are available (as opposed to the 2n consecutive symbols required by general fixed-word-length comma-free codes) is demonstrated. A comparison of dictionary sizes is made for path-invariant comma-free codes, general fixed-word-length comma-free codes, and codes using one symbol as a comma. In the range K \leq 6 and n \leq 9 the path-invariant dictionaries are about \frac{1}{2} to \frac{3}{4} the size of the corresponding general comma-free dictionaries. Asymptotic dictionary sizes are obtained for K \rightarrow \infty and for n \rightarrow \infty .

A linear code of block length n possessing minimum weight d has one code word of weight zero, and no other code words of weight less than d . The weight distribution of the code is given by the set of all W(j), d \leq j \leq n , describing the number of code words having a weight of exactly j . Exact weight distributions are known for only a handful of linear codes. This paper presents an explicit upper bound upon W(j) as a function of n, d , and j . The bound has general applicability to all linear codes.

Linear residue codes are useful for error control in both arithmetic operations and data transmission. When used in data transmission, they do not require special coding equipment, as encoding and decoding operations may be easily carried out in digital computers. In this paper, number-theoretic concepts are used to construct linear residue codes for the correction of burst errors. A general theory is developed for the class of codes derived from the multiplicative group G(A) modulo A , an odd integer, which consists of all the integers smaller than and relatively prime to A . Construction schemes for various classes of burst-error-correcting binary linear residue codes are determined and discussed.

In this paper we show that for memoryless time-discrete sources with a bounded fidelity criterion, the limiting average distortion achievable by tree codes of rate R is D , the solution of the equation R = R(D) , where R( ) denotes the usual rate distortion function. Thus the performance of tree codes is as good as that of block codes. Some theoretical and experimental results are also discussed indicating that tree codes and corresponding encoding algorithms exist having for given values of R and D an implementation complexity that is far smaller than the one obtainable from block codes.

This paper presents a systematic procedure for finding optimum error-correcting group codes for the binary symmetric channel with m check digits and a minimum distance not less than do, where m and do are given integers. Some new schemes for reducing the computing time are used. The search procedure is readily programmable for computer execution and several programs were carried out on an IBM 7044. The newly found seven optimum triple-error-correcting group codes and six optimum double-error-correcting group codes including five quasi-perfect double-error-correcting codes are tabulated. Also, a list of optimum shortened cyclic codes found by a similar procedure is presented. The efficiency of the search procedure is demonstrated by the fact that the program yielded the new codes in a fairly short time.

This paper presents a class of majority-logic decodable codes whose structure is based on the structural properties of Euclidean geometries (EG) and codes that are invariant under the affine group of permutations. This new class of codes contains the ordinary EG codes and some generalized EG codes as subclasses. One subclass of new codes is particularly interesting: they are the most efficient majority-logic decodable codes that have been constructed.

Two n -digit sequences, called "points," of binary digits are said to be at distance d if exactly d corresponding digits are unlike in the two sequences. The construction of sets of points, called codes, in which some specified minimum distance is maintained between pairs of points is of interest in the design of self-checking systems for computing with or transmitting binary digits, the minimum distance being the minimum number of digital errors required to produce an undetected error in the system output. Previous work in the field had established general upper bounds for the number of n -digit points in codes of minimum distance d with certain properties. This paper gives new results in the field in the form of theorems which permit systematic construction of codes for given n, d ; for some n, d , the codes contain the greatest possible numbers of points.

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.

The class of codes discussed in this paper has the property that its error-correction capability is described in terms of correcting errors in specific digits of a code word even though other digits in the code may be decoded incorrectly. To each digit of the code words is assigned an error protection level f_{i} . Then, if f errors occur in the reception of a code word, all digits which have protection f_{i} greater than or equal to f will be decoded correctly even though the entire code word may not be decoded correctly. Methods for synthesizing these codes are described and illustrated by examples. One method of synthesis involves combining the parity check matrices of two or more ordinary random error-correcting codes to form the parity check matrix of the new code. A decoding algorithm based upon the decoding algorithms of the component codes is presented. A second method of code generation is described which follows from the observation that for a linear code, the columns of the parity check matrix corresponding to the check positions must span the column space of the matrix. Upper and lower bounds are derived for the number of check digits required for such codes. The lower bound is based upon counting the number of unique syndromes required for a specified error-correction capability. The upper bound is the result of a constructive procedure for forming the parity check matrices of these codes. Tables of numerical values for the upper and lower bounds are presented.

A group code is a set of vectors, generated by a group of orthogonal matrices transforming a starting vector. Ingemarsson [5] has shown that, if the group is commutative, the code is equivalent to a set of phase-modulated signals. Codes generated by noncommutative groups have been described by Slepian [9]. In this paper another class of codes generated by noncommutative groups is described. This class is called group codes for PHAMP signals and can be described as a combination of phase- and amplitude-modulated signals. The performance of these codes, when communicating over the Gaussian channel, is analyzed, and it is shown that some of them have a performance close to the bounds given by Slepian [8].

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 that e -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 with d/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 we present a new error-control technique intended for use in 2^l -level data-transmission systems that employ Gray coding to transform a binary source sequence into the 2^l -ary transmitted sequence. The codes, which we call i -compressed codes, make use of the structure of binary codes and have the property that for some integer i , 1 \leq i \leq l , transmission errors can be corrected if the erroneously received signals lie less than 2^{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 the i -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 an i -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 decodable i -compressed codes. Finally, for the case i = 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.

Upper bounds for error detecting and error correcting codes are obtained in this paper. One upper bound is found by exploiting the geometrical model of coding introduced by Hamming. The volume of an appropriate geometrical body is compared with the volume of the unit cube, in getting the first upper bound. An improvement on this upper bound can be found by introducing a mass density function, and comparing the mass of the body with the mass of the unit cube. A comparison is made with known upper bounds, and with best codes found thus far. The improved upper bound given here is frequently somewhat smaller than previously known upper bounds.

Many data-transmission and data-storage systems are corrupted by disturbances of both the burst type and the random type. In this paper two classes of error-correcting codes for use with these systems have been constructed analytically and with the aid of a computer. Although not optimal, these codes do have the advantage of ease of implementation

This paper presents several results involving Fano's sequential decoding algorithm for convolutional codes. An upper bound to the a th moment of decoder computation is obtained for arbitrary decoder bias B and a \leq 1 . An upper bound on error probability with sequential decoding is derived for both systematic and nonsystematic convolutional codes. This error bound involves the exact value of the decoder bias B . It is shown that there is a trade-off between sequential decoder computation and error probability as the bias B is varied. It is also shown that for many values of B , sequential decoding of systematic convolutional codes gives an exponentially larger error probability than sequential decoding of nonsystematic convolutional codes when both codes are designed with exponentially equal optimum decoder error probabilities.

In this paper improved upper bounds are obtained for A(n,d) , the maximum number of binary code vectors in a code of block length n and minimum distance d . Known bounds are presented in a unified way and then refined, giving improvement over best previously published results in almost all cases. Finally, tabulations of the improved results are given. Asymptotically, the new bounds agree with those given by Elias.

This paper concerns the analysis of recurrent-type, parity-check, error-correcting codes for memoryless, binary symmetric channels. These codes are defined to consist of message sequences augmented by insertions of r successive parity digits every b successive message digits. An analysis framework is established for the codes which consists mainly of a parity check matrix [M] and a message difference vector [N] . Within this framework, a decoding scheme is developed which renders the codes capable of correcting any set of \eqslantless e errors in m/b successive (b + r)- digit blocks of coded message sequence, where e is maximized over all parity-check codes having the same redundancy ratios and maximal lengths of dependence among their digits. An example is given of a linear-recurrent code which has a lower probability of error than the best comparable block code, and several outstanding problems are discussed.

Information theory obtains efficient codes by encoding messages in large blocks. The code design requires block probabilities that are often hard to measure accurately. This paper studies the effect of inaccuracies in the block probabilities and gives coding procedures that anticipate some of the worst errors. For an efficient code, the mean number d of digits per letter must be kept small. In some cases the expected value of d can be related to the size of the sample on which probability estimates are based. To underestimate badly the probability of a common letter or block is usually a serious error. To ensure against this possibility, some coding procedures are given that avoid extremely long codewords. These codes provide a worthwhile insurance but are still very efficient if the probability estimates happen to be correct.

In this paper a class of nonprimitive cyclic codes quite similar in structure to the original Reed-Muller codes is presented. These codes, referred to herein as nonprimitive Reed-Muller codes, are shown to possess many of the properties of the primitive codes. Specifically, two major results are presented. First the code length, number of information symbols, and minimum distance are shown to be related by means of a parameter known as the order of the code. These relationships show that for given values of code length and rate the codes have relatively large minimum distances. It is also shown that the codes are subcodes of the BCH codes of the same length and guaranteed minimum distance; thus in general the codes are not as powerful as the BCH codes. However, for most interesting values of code length and rate the difference between the two types of codes is slight. The second result is the observation that the codes can be decoded with a variation of the original algorithm proposed by Reed for the Reed-Muller codes. In other words, they are L -step orthogonalizable. Because of their large minimum distances and the simplicity of their decoders, nonprimitive Reed-Muller codes seem attractive for use in error-control systems requiring multiple random-error correction.

The problem posed in this paper is to give a relation connecting the noise stability of a communication system in which error-correcting codes are used to the parameters of these codes. The amount x of code combinations is found, which differ from each other by not less than a given number of elements for a given arrangement of all the possible combinations. It is proved that the quantity x depends on the arrangement of the primary combinations. Inequalities are obtained for the greatest amount of combinations x_m , for which any two differ by not less than d elements for small and large values n of the common number of elements in each code combination. It is established that the probability of distortion, p_n , of a code group in a system with correcting codes satisfies the inequality p_n , where p is the probability of distortion of one element. The shape of the f(p, n, d) function is found for large values of n . Graphs of this function are constructed.

This paper presents new general error-correction procedures for fhe class of codes known as Bose-Chaudhuri-Hocquenghem codes. It is shown that these procedures are efficient in time required for error-correction, and that they can be implemented with relatively simple electronic circuits. A comparison is also made with existing procedures.

This paper gives a method for constructing minimum-redundancy prefix codes for the general discrete noiseless channel without constraints. The costs of code letters need not be equal, and the symbols encoded are not assumed to be equally probable. A solution had previously been given by Huffman [10] in 1952 for the special case in which all code letters are of equal cost. The present development is algebraic. First, structure functions are defined, in terms of which necessary and sufficient conditions for the existence of prefix codes may be stated. From these conditions, linear inequalities are derived which may be used to characterize prefix codes. Gomory's integer programming algorithm is then used to construct optimum codes subject to these inequalities; computational experience is presented to demonstrate the practicability of the method. Finally, some additional coding problems are discussed and a problem of classification is treated.

Efficient use of block codes to communicate over a telemetry channel is dependent upon the knowledge of the instants, in time, that one code waveform, or code word, ends and the succeeding waveform begins. This word synchronization is the subject of concern in this paper. Two basically different single-channel synchronization techniques are discussed. The first relies upon the identification of periodically transmitted prefixes, which unavoidably increase the redundancy of the code without increasing its synchronous reliability. The second method eliminates the need for prefixes entirely and relies instead upon certain properties of the code itself. Both these techniques are investigated more closely as applied to binary orthogonal codes. Asymptotic results are obtained which show that the number of received words necessary to obtain synchronization with a fixed prefix length increases in proportion to the size of the code when the prefix method is used. In contrast, the number of words which need to be observed for the prefix-free codes remains constant independent of the code length. Finally, some results of the search for prefix-free codes of moderate size are reported.

A coding scheme based on the properties of rank vectors is presented. The new codes are based on the theory of permutation groups by introducing a new notation for the group operation that simplifies the generation and decoding of desirable rank codes. The use of group theory is made possible by the introduction of the Kendall correlation coefficient as a measure of the distance between code words. This technique provides a method for the choice of rank vector code words superior to those that have been proposed in the past. Much of the terminology used in block coding can also be used to describe rank vector codes, but the actual quantities involved are quite different. The rank vector codes discussed in the paper offer the advantage of low sensitivity of the probability of error to the noise distribution because of the nonparametric character of rank vector detection schemes. Bounds that have been verified by extensive computer simulation have been derived for the probability of error.

This paper explores the relationship between variable word-length synchronizable codes and comma-free codes. A simple construction procedure for comma-free codes of maximum dictionary size is presented. The concept of comma freedom is then reformulated to include the possibility of variable word length and two construction procedures for variable word-length comma-free codes are given. The resultant codes allow transmission of information at a higher rate than fixed word-length comma-free codes, for the same maximum synchronization delay.

Polynomial codes and their dual codes as introduced by Kasami, Lin, and Peterson have considerable algebraic and geometric structure. It has been shown that these codes contain many well-known classes of cyclic codes as subclasses, such as BCH codes, projective geometry codes (PG codes), Euclidean geometry codes (EG codes), and generalized Reed-Muller codes (GRM codes). In this paper, combinatorial expressions for the number of information symbols and parity-check symbols in polynomial codes are derived. The results are applied to two important subclasses of codes, the PG codes and EG codes.

This paper presents a number of interesting results relating to the determination of actual minimum distance of cyclic codes. Codes with multiple sets of consecutive roots are constructed. A bound on the minimum weight of odd-weight codewords is determined. Relations on the distribution of roots of the generator polynomial are investigated. Location polynomials of reversible codes are examined. These results are used to obtain better estimates of the minimum distance of many new cyclic codes.

Properties of integers, related to the generation of the arithmetic AN codes, are investigated in this paper. A programmable algorithm for the computation of the binary norm of an arbitrary integer is developed. A table of norms of the natural numbers is generated and from this the distribution of integers of a given norm is found. These results are used to compute bounds on the size of an e -fold or less error-correcting AN code and to derive some further properties of single- and double-error-correcting AN codes.

The problem of detecting and correcting loss of synchronization for binary cyclic codes is examined. The method used is to form a coset code from tho given (n, k) cyclic code by adding a suitable n vector to each cyclic code word before transmission. Unlike some other techniques, the length of the code word n is not altered. A code word may be represented in at least two ways: 1) as a vector and 2) as a polynomial. Depending on the problem at hand, one approach may offer more insight or supply a shorter proof for a theorem than the other. Throughout this paper, we use the binary n -vector representation. Using this approach, we give new proofs to some known results, and derive some now theorems dealing with the simultaneous occurrence of loss of synchronization and additive errors. Specifically, it is shown that there exist coset codes that can correct both additive error and synchronization error even when they occur simultaneously.

This paper discusses the use of two types of convolutional codes, diffuse threshold-decoded codes and Gallager codes, on channels with memory (burst channels). The operation of these codes is explained and test results are given for a variety of equipments operated over phone line, HF radio, and troposcatter channels. Error propagation in the threshold-decoded codes is discussed and, in the Appendix, we prove that, for one important diffuse code, propagation is finite and small.

The class of polynomial codes introduced by Kasami et al. has considerable inherent algebraic and geometric structure. It has been shown that this class of codes and their dual codes contain many important classes of cyclic codes as subclasses, such as BCH codes, Reed-Solomon codes, generalized Reed-Muller codes, projective geometry codes, and Euclidean geometry codes. The purpose of this paper is to investigate further properties of polynomial codes and their duals. First, majority-logic decoding for the duals of certain primitive polynomial codes is considered. Two methods of forming nonorthogonal parity-check sums are presented. Second, the maximality of Euclidean geometry codes is proved. The roots of the generator polynomial of an Euclidean geometry code are specified.

In the past, criteria for predicting the performance of individual codes with sequential decoding have been intuitive. In this paper, simple tests are derived that allow easy determination of the performance on the BSC (binary symmetric channel) of a given binary convolutional code decoded with a modified version of the Fano algorithm. A "distance-guaranteed computational cutoff rate," R_{dgcomp} , is defined in terms of the BSC crossover probability and the "uniform minimum distance" of the code. The latter is a measure of the minimum distance between codewords of all lengths up to and including the constraint length of the code. A bound is derived on the average number of decoding computations and is shown to be small and insensitive to constraint length if the code rate, R , satisfies the test R . Also, the probability of a decoding error is overbounded and the bound decreases exponentially with constraint length with exponent (R_{dgcomp} - R) . Consequently, the probability of error is small if (R_{dgcom} - R) is large. The existence of binary convolutional codes with a uniform minimum distance which meets the Gilbert bound is demonstrated. This result is combined with the condition R to show the existence of codes of rate less than a rate R_{D} for which the average number of decoding computations is small. The rate R_{D} is approximately one half of the true computational cutoff rate R_{comp} on the BSC with crossover probability of 10^{-4} .

The paper considers group codes whose function is split between error correction and error detection with retransmission. For a given code, the minimum error probability is obtained when retransmission occurs whenever an error is detected. An estimate of the redundancy added by retransmission is given and the behavior of retransmission channels as the length of the code words increases is studied. Most of the analysis is for the binary symmetric channel, although some of the results apply to more general channels.

A detailed study has been made of a certain class of systematic binary error-correcting codes that will correct the error bursts typical of some digital channels. These codes--generalizations of codes discovered by Abramson and Melas--are cyclic codes designed to correct any single burst of errors per n -digit word provided that the width of the burst (regarded cyclically) does not exceed a certain number of digits, b . Moreover, these codes are optimum in the sense that they employ the minimum number of redundant digits theoretically possible for a cyclic code with given values of n and b . A cyclic code is completely characterized by its generator polynomial g(x) , hence, the properties of the code can be determined by analysis of the corresponding g(x) . Necessary and sufficient conditions on g(x) have been formulated for the corresponding cyclic code to be an optimum burst- b correcting code. These conditions have been formulated into a series of tests that can be carried out (in principle) on any g(x) . All optimum burst- b cyclic codes with n and b have been found in this way and their generators are tabulated in the paper. In all, 98 codes are listed (not counting reciprocals) for b = 3 and b = 4 ; it was shown that no optimum codes exist for b = 5 within the limits stated. Practical codes for b \geq 6 will probably be nonoptimum codes because of the extreme word lengths required for optimum ones.