Search

This paper demonstrates two improvements in coding techniques that could be used for memory word coding. First, within the fixed structure of a Hamming single-error-correcting, double-error-detecting (SEC/DED) code, an improvement can be obtained in circuit cost and operational speed over more conventional code implementations. Second, the mechanics of error correction in a fault-tolerant computer may be carried out via conventional hardware means or by use of the existing system facilities, such as the combination of the microprogram unit, local store, and the arithmetic-logic unit. These improvements may be obtained by the use of Rotational Coding schemes in conjunction with a technique calied "lookaside correction." This paper first shows a generalized algorithm for specifying the parity check matrix of Rotational Codes. The structure implemented by the parity check matrix in this paper is not merely encoding and decoding circuitry, but translates between Rotational Code forms and byte-parity encoded forms. The unique feature of these translators is that use of the Rotational Code permits the error correction to be performed on only a subset of the data word bits, and only if a single-error condition has been detected. The correction mechanism may be either a hardware logic circuit or firmware. The paper concludes with a comparison of the circuit requirements and correctional speed of the Hamming (72, 64) single-error-correcting, double-error-detecting code, as it normally would be implemented, and a Rotational Code translator also operating on 64 data bits and 8 check bits.

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 a previous paper Hsu (1971) , it was pointed out that the shortened cyclic codes generated by g(x) = (xc + 1) g1(x) have the best rate of transmission when it is used as error correcting codes in a compound channel. The shortened cyclic codes are of length N + c where N and c are relatively prime and g1(x) generates a cyclic code of length N with dmin ⩾ 2t + 1. This paper studies the random error decoding algorithms for the shortened cyclic codes. Two random error decoding algorithms are presented. It is also found that if g1(x) generates a maximum length code, then N and c are not required to be relatively prime. The shortened cyclic codes generated can be easily decoded without using the two random error decoding algorithms presented. This result is also reported.

Introduction. Most encoding and decoding equipment operates in binary symbols, whereas it is often desirable to use a code consisting of symbols from GF(2S); each code symbol is really s binary symbols. This happens, for example, in multilevel transmission; it also happens when the chief function of the code is burst-error correction. The question discussed in this paper is when and how a binary cyclic code of block length s(2s 1) can be mapped in a natural way onto a cyclic code of block length 2s 1 over GF(2S). Such codes are attractive because they combine the advantages of multilevel efficiency with binary implementation; however the moral of this paper seems to be that we had better look for other ways to achieve this goal. Indeed the "natural" practical mapping between codes over GF(2) and codes over GF(2S) is mathematically rather unnatural. The image of a cyclic code over GF(2) may easily fail to be a linear space over GF(2S). Thus it is not surprising (although disappointing) that we appear to find only a rather small class of rather poor codes. The only previous published work on this subject known to the writer is due to M. Hanan and F. P. Palermo; these authors discuss a more general form of the same basic question, and arrive at the same basic conclusion. The plan of this paper is as follows: Section 1 describes the mapping p from the vector space over the binary field to the vector space over GF(2s), and gives an explicit form for the inverse mapping. Section 2 gives necessary and sufficient conditions for the image under (p of a binary cyclic code to be a cyclic code over GF(2S), and consequently for the image under p ` of a cyclic code over GF(2S) to be a binary cyclic code. These conditions are essentially the same as those given by Hanan and Palermo, and are definitely unhelpful from a practical point of view. Section 3 describes the class of "interlaced" codes, which can always be mapped back and forth, and shows that the union and intersection of an interlaced code with a mappable code is again mappable. Section 4 shows how to get new mappings from old-specifically, if a(x) is the polynomial of least degree in a mappable cyclic code (the generator polynomial), then the reciprocal polynomial of a(x) is also mappable, and so is the polynomial obtained by reversing the order of the coefficients of a(x). (The mapping function 5p is different in the three cases.) Section 5 describes the one choice of p which we know always works and shows how it works. Section 6 contains several theorems which are useful when looking for mappings; for example, we need consider only noninterlaced codes generated over GF(2s) by polynomials of degree ?s 1. The Appendix contains a series of examples, which hopefully will be useful as illustrations of the text.

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.

In an asymmetric binary channel, it may be sufficient to correct single O-errors and detect double 0-errors, for example, while correcting double 1-errors and detecting quadruple 1-errors. (A double 1-error is said to occur when two of the l's of an input code character are delivered as O's at the output of the channel.) Minimum distance requirements are given for pairs of code characters of a code which corrects k -tuple 1-errors, detects (k+a) -tuple 1-errors, corrects j -tuple 0-errors, and detects (j+b) -tuple O-errors (k,a,j , and b , are non-negative integers with k > j and a \geq b ). These requirements are weaker than those for a symmetrical k -tuple error correcting, (k+a) -tuple error detecting, code and hence may be used to generally obtain more code characters for a given character length than are obtainable in the k, (k+a) -case. If the channel is highly asymmetric, it may be sufficient to detect and correct only one type of error. An earlier paper considered the case of single 1-error correction and showed that it was always possible to obtain more code characters than exist in known single error correcting codes of equivalent character length except in cases where the symmetric code is "close-packed." In this paper codes are developed for k -tuple 1-error correction which also yield more code characters than symmetrical k -tuple error correcting codes of the same length. The correction scheme is generally symbol-correcting, but may require message-correction of binary sequences whose length is approximately (k+l)^{-1} that of the code characters. A double 1-error correcting code is discussed in some detail and examples of code generation and correction are included.

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 problem of finding the cycle representatives of a cyclic code is considered. In a recent paper, Tavares, Allard and Shiva, provided a solution to this problem for all cyclic codes having a parity check polynomial which satisfies either of the following conditions: (i) h ( x ) consists entirely of factors having exponent n , (ii) the exponents of the factors of h ( x ) are relatively prime to each other. For other cyclic codes, the solution remained incomplete. In this paper we provide a complete solution of the problem.

A code which is to be used for error control on a real data system is necessarily restricted by the nature of the transmitting equipment. These restrictions have no connection with the primary function of the code; indeed, they frequently eliminate most of the codes about which anything is known at present. For example, the code to be used for error control by detection and retransmission on the trunks between data switching centers is required to be a cyclic (or truncated cyclic) code with 744 information places and 20 parity check bits. The computational problem in this case is to locate those cyclic codes which have exactly 20 parity checks and a block length of 764 or greater, and pick the one which is best suited for error control over a particular channel. This paper outlines a procedure for attacking such problems. It describes how to locate the cyclic codes with a fixed block length and a fixed number of parity checks, if any such exist, and gives some methods of finding the number of code words of each weight in a particular code. If one knows the statistics of the channel it is then possible to estimate the error control properties of the code. The procedure depends on an analysis of the algebraic structure of cyclic codes, which is given in Section II of this paper. Section I contains step-by-step instructions with no mathematical justification. It is hoped that the theory presented in Section II may be useful in other applications.

This paper will investigate the properties of cyclic codes under the transformation,$ It is discovered that for all the non-shortened cyclic codes (binary or (/-nary), if (g(x), (x−1)) =1 then the set of all the codewords is invariant under the transformation fb. If (g(x), Lx−1)) = (x; − 1), then the set of all the code words is generated by g(x)/(x − 1). Next this paper shows a systematic method for the construction of orthogonal cyclic codes in which all the code vectors are orthogonal to each other even to itself

In previous papers the technique of error correction of digital data through the use of interleaved cyclic codes and a set of probability functions for the evaluation of error patterns have been presented. In this paper the previous results are extended to a wide range of BCH and symbol codes. A set of simple equations is presented for the description of an interleaved cyclic code and its associated delay, and a method is presented which allows for a significant increase in error rate improvement at a reduction in the delay time introduced into the channel. It is demonstrated that the performance of interleaved cyclic codes is sufficient to correct all types of measured HF error patterns; that, using delay as a basis of comparison, only the total bit interleaving is important in achieving error correction; and that it is possible to get almost 100 percent error correction for delays under 3 seconds for all channel conditions measured.

Recent papers have described controlled shift register systems with which conversion can be made between pure binary code and 8421 binary-decimal code. This paper shows how this technique may be extended to other weighted binary-decimal codes, and puts forward a wider theory of which 8421 b.c.d. is a special case.

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.

The present paper describes an error correcting code. It is a linear systematic (7,4) code which is capable of detecting two errors and correcting a single error. The encoding and decoding circuits have also been described.

This paper gives two new bounds for the code word length n which is required to obtain a binary group code of order 2k with mutual distance d between code words. These bounds are compared with previously known bounds, and are shown to improve upon them for certain ranges of k and d. Values of k and d are given for which one of these bounds can actually be achieved; in such cases, the structure of the resulting codes is shown to satisfy a certain condition.

In certain digital communication systems data is coded into cyclic code words for error correction or detection. To safeguard certain aspects of the system, all the code words of a message may have the same identifying pattern in a group of digits. This increases the redundancy of the message. This paper proposes a method of doing this using little or no redundancy. The message identification (MI) would be contained in a code syndrome which is added to each code word (except the first) of the message. These syndromes are ones that are unused for error correction by the cyclic code. Simple decoding procedures can determine if code words of different messages have been interchanged in certain parts of the system. Random and burst error correction codes are examined to determine suitable syndromes.

In this paper we show that the dual code of a g-ary Hamming single error-correcting code is a constant weight cyclic code with weight q(m-1). We give, as a consequence, a very simple alternative derivation of the weight enumerator formula for the q-ary Hamming single error-correcting code. We show also that a binary cyclic equidistant code can be derived from this dual code

This paper emphasizes that coordinates of an error-correcting code are functions. We have incorporated certain ideas already present in the literature into an axiomatic treatment of error-correcting codes. The usual “coordinates” are functions defined on a set of messages, with values in a given set K (classically, K = 0, 1). These functions are required to satisfy a certain “Coding Axiom”. In Section II we treat linear codes, K now being a finite ring; and we also give a treatment of cyclic codes, where we prove that the minimum distance is at least n/k , where n is the block length and k the dimension. In Section III we prove our main result, the Mapping Theorem, which relates the weights in a code A to those in an image-code B ; image-codes are defined simply in our terms. A number of corollaries are noted, including a formula for the sum of the squares of the weights of all code elements.

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 many communication systems, variable-redundancy coding schemes are highly desirable either due to the fact that messages of various degrees of importance are present, or due to some change in the real communication channel. A class of “cyclic product codes” presented in this paper is capable of operating in variable redundancy modes. In the simplest case, the generator polynomial in the high redundancy mode is g(x) = g1(x)g2(x), while the generator polynomial in the low redundancy mode is only g1(x). It is shown that efficient product codes can be constructed offering different degrees of protection against independent errors, burst errors, and multiple burst errors. It is also shown that particularly simple implementation for cyclic product codes is possible. In fact, the complexity of the entire decoder can be made roughly the same as that of the decoder for the high redundancy code alone. Hence, the implementation of low-redundancy codes is accomplished with little extra cost.

This paper is a study of a large class of cyclic and shortened cyclic binary codes for multiple random error correction. The major result is: If g ( x ) = π i =1} 2 l g i ( x ) generates a basic BCH code of length N with minimum weight ⩾ 2 lt + 1, then g ( x ) = π j =1} l [ g j ( x )] i j . [π j =( l +1)} 2 l g j ( x )], where i 1 > i 2 > - - - > i l > 1 generates a shortened cyclic or nonshortened cyclic code of length (σ j =1} l i j ) N with minimum weight at least 2 lt + 1. Three classes of cyclic codes will be presented. Class I and Class III codes are cyclic codes. Class II codes are shortened cyclic 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 concept of a difference-set cyclic code has been described previously. It was shown that such a code is almost as powerful as a Bose-Chaudhuri code and considerably simpler to implement. It is the purpose of this paper to determine some of the more important properties of this code and its dual code (cf. Sec. IV). It may be pointed out that the problems we consider are equivalent to determining certain properties of incidence matrices associated with a class of balanced incomplete block designs formed from simple difference sets.

There are two well-known necessary conditions for the existence of a perfect error-correcting code. Combination of these leads to a Diophantine equation. It is proved that this equation has no solutions for n > 2, q > 3 (q a prime power) in the case of two errors. Furthermore we prove that the Golay (23, 12) code is the only nontrivial perfect 3-error-correcting code over any alphabet GF(q).

This paper delineates an application of two classes of parity-check codes to the design for failure-tolerant counters. They are 1) a modified first-order Reed-Muller code and 2) the perfect Hamming code. The first code employs a majority element for implementing the error-correcting scheme while the second one makes use of a variable 2j-2+1-out-of-2j-1+1 majority element. These coding techniques can be applied in principle to other logic hardware to increase its reliability.

This paper introduces a new class of nonlinear binary codes. For each l = 2, 3,… we present a code with 2 41 codewords of length N = 4 l and distance d = (4 l — 2 l )/2. Each code is a supercode of the 1st-order Reed-Muller (RM) code and a subcode of the 2nd-order RM code. These codes are the “duals≓ of the extended nonlinear Preparata codes in the sense that their weight distributions satisfy the MacWilliams identities.

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.

This paper considers the problem of simultaneous error-correction and burst-error detection using binary linear cyclic codes. For certain types of teletype channels, it pays to correct random errors and to detect bursts. It is shown that the burst-error detecting capability drops by one more than the length of the largest gap in the recursion polynomial when a binary linear cyclic code is used to correct single errors. Only special cases of this result are obtained for multiple-error-correction. The single-error result is applied to develop a new criterion for primitivity of polynomials over the two-element field. The criterion depends on the largest gap in the recursion polynomial corresponding to the polynomial to be tested for primitivity.

This paper presents a new class of synchronizable error-correcting codes which are derivable from cyclic codes by restraining some of their information symbols. They are called subset codes because each code constitutes a subset of code words in the parent cyclic code. The ability of the subset codes to detect and correct loss of synchronism, or slip, in both noiseless and noisy channels is examined. In particular, given a t-error-correcting cyclic code, there exists a subset code that can correct any combination of slip and additive error whose total magnitude does not exceed t. Moreover, when the received word is in synchronism, the decoder automatically corrects any additive error pattern the parent cyclic code could correct. For channels in which slip is small and occurs infrequently, the subset codes appear to be the most efficient available. In other situations they are generally efficient and in addition their decoding procedures are straightforward. The manner in which the information symbols are restrained is the same as for the extended cyclic codes of Bose and Caldwell [1], and Weldon [2]. However, unlike the extended cyclic codes which have redundant symbols added to both ends of each code word, the block length of the subset codes is the same as the parent cyclic codes.

The class of codes described in this paper is used for single-error correction and double-error detection (SEC-DED). It is equivalent to the Hamming SEC-DED code in the sense that for a specified number k of data bits, the same number of check bits r is used. The minimum odd-weight-column code is suitable for applications to computer memories or parallel systems. A computation indicates that this code is better in performance, cost and reliability than are conventional Hamming SEC-DED codes.

This paper will present a class of minimum redundancy multiple burst-error-correcting cyclic codes. Although the rate of transmission is poor, it has a very easy decoding algorithm.

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.

The weight distribution of the code vectors of a binary group code has been referred to as the spectrum of the code. This paper presents a technique for calculating the spectrum of such a code, the spectra of shortened codes obtainable from the code, and what are defined as the level weight structures of the code. The method is conceptually straightforward and readily adaptable to digital computers. It involves operations no more complex than the addition of two (n − k)-tuples, the determination of the weight of certain (n − k)-tuples, and the ordinary addition of certain integers. Its computational complexities are independent of the code parameters. In principle, it may be used for any binary group code, but it is particularly useful for codes in which the number of parity check positions per code vector is rather small although the number of information positions may be large.

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.

Evaluation of the performance of error-correcting codes has, in the past, been severely hampered by the lack of functional relationships between the uncoded and coded binit error rates. In this paper, such relationships yielding the exact decoder output error rates are developed for Hamming SED codes of lengths n = 2m - 1, m = 1, 2, 3,···, and for Hamming SEC/DED codes of length n = 2m, m = 1, 2, 3,···. In addition, for the DED codes, a similar family of formulas are derived for the probability that a received information binit is contained in a word containing an error pattern that can be detected but not corrected. A criterion of merit for the coded versus uncoded systems is postulated. A similar criterion is developed based upon word error rates. It is demonstrated that the latter results, in general, in highly erroneous conclusions regarding the comparative worth of coded systems. Graphs are presented illustrating the numerical results based on these formulas for codes ranging in length from 7/8 binits up to and including 511/512 binits, for uncoded channel error rates of 0.5 to 10-10. Similar graphs of code merit, based upon modulation systems for which detection is a linear operation (PSK-MF, for example), are constructed. From these, ranges of channel (uncoded) error probability over which particular code lengths result in the best performance that can be obtained from that type of code are extracted and tabulated.

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.

The notion of an extended cyclic code has recently been formulated. It is known that, subject to certain polynomial constraints, certain random-error-correcting cyclic codes can be extended to form codes capable of automatically recovering from synchronization losses. It is shown in this paper that the above-mentioned constraints are unnecessary and that this synchronization recovery technique can be used with any additive-error-correcting cyclic code.

The paper introduces a super-orthogonal space-time block coding scheme. The code construction is based on the expansion of an orthogonal block code via a unitary matrix transformation. By expanding the orthogonal block code, we can both increase the code rate and improve the performance in terms of E/sub b//N/sub 0/, with a moderate increase of the receiver complexity. The performance is compared with orthogonal and quasi-orthogonal block codes in computer simulation.

Expressions for the probabilities of multiple error patterns in symbols consisting of N bits are needed to evaluate the effectiveness of applying error correcting codes to these information channels. For example, if a Hamming single error correcting code is applied to the information, the probabilities of all errors greater than one should be established. This will indicate the number of times the single error correcting code has failed.

In the past few years, a large number of results have appeared in the literature concerning the distribution of weights in various codes. Explicit formulas are now known for the number of codewords of each weight in several infinite classes of codes. As mentioned earlier in this paper, these results allow one to compute the probability of decoding failure and the probability of decoding error when one of these codes is decoded by a t-error-correcting decoding algo — rithm, where t may be any number less than half of the code’s minimum distance.

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.

Two procedures for modifying linear block error-correction codes are proposed. The first is based on the deletion of x rows and y columns from the parity-check matrix of a given (n, k) code, in such a way that the minimum Hamming distance of the resulting (n−y, k+x−y) code remains equal to that of the original. It is shown that if x is unity, then y may be as low asthe minimum Hamming distance of the (n, n−k) dual of the original (n, k) code. This procedure of deleting rows and columns when applied to the known linear binary block code yields a family of codes, some of which have better rates than those of the best previously known codes of identical Hamming distance and the same number of paritycheck digits. 17 examples of such new codes are derived and included in the paper. It is also shown that apart from appropriate slight modification, the coding and decoding algorithms for this family of modified codes are similar to those of the original code. The second proposed procedure of code modification entails lengthening the original (n, k) linear block code by annexing k′ message digits. If the original code is capable of correcting t random errors or less, then the resulting modified (n+k′,k+k′) code has a rate higher than that of the original (n, k) code. Moreover, its error-correcting capability is such that it will correct t random errors or less if at least one of these occurs in the block of k message digits and s random errors or less, where 1≤s