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.

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.

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.

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.

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.

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.

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.

When decoding a cyclic code, an alternative to computing the syndrome by dividing the received n -tuple W(x) by the generator polynomial G(x) is to compute the product H(x)W(x) , mod x^n - 1 , with the check polynomial H(x) . It is shown in this paper that the form of the product can be predicted in terms of general code parameters and corresponds closely to the burst error from which it is derived. By using the properties of the product sequence, a burst-error decoder is derived in such a way that a family of potentially fast burst-error decoders can be constructed. Another important application of the proposed technique concerns decoder implementation for the correction of a synchronization error (slip) when the coset code technique is used. It is shown that slip correction can be implemented so that both the magnitude and direction of slip are determined by examining only one received n -tuple.

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.

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.

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.

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.

This paper shows that, although systematic cyclic codes have equal error protection for all information digits, there exist non-systematic cyclic codes that can provide unequal error protection for the information digits; that is, at least one information digit is protected for a number of errors that is larger than the number guaranteed by the minimum distance of the code.