Determining the burst-correcting limit of cyclic codes

Two new computationally efficient algorithms are developed for finding the exact burst-correcting limit of a cyclic code. The first algorithm is based on testing the colmn rank of certain submatrices of the parity-check matrix of the code. An auxiliary result is a proof that every cyclic(n,k)codes with a minimum distance of at least three, corrects at least all bursts of lengthlfloor (n - 2k + 1)/2 rflooror less. The second algorithm, which requires somewhat less computation, is based on finding the length of the shortest linear feedback shift-register that generates the subsequences of lengthn - kof the sequence formed by the coefficients of the parity-check polynomialh(x), augmented withlfloor (n-k)/2 rfloor -1leading zeros and trailing zeros. Tables of the burst-correcting limit for a large number of binary cyclic codes are included.     

Implementation of burst-correcting convolutional codes

A general procedure is formulated for decoding any convolutional code with decoding delayNblocks that corrects all bursts confined toror fewer consecutive blocks followed by a guard space of at leastN-1consecutive error-free blocks. It is shown that all such codes can be converted to a form called "doubly systematic" which simplifies the decoding circuitry. The decoding procedure can then be implemented with a circuit of the same order of complexity as a parity-checking circuit for a block-linear code. A block diagram of a complete decoder is given for an optimal burst-correcting code. It is further shown that error propagation after a decoding mistake is always terminated by the occurrence of a double guard space of error-free blocks.     

A note on Gilbert burst-correcting codes

The codes discussed here, due to E. N. Gilbert, are capable of detecting and correcting certain bursts, i.e., errors which occur in clusters. In particular, it is shown that Gilbert's burst-correcting cedes have capabilities beyond those previously recognized. D. A. Huffman's graph-code formulation is used, which greatly facilitates the appreciation of the results. A cyclic code formulation is also given, and certain Gilbert codes are seen to be Fire codes.     

Limiting efficiencies of burst-correcting array codes

The author evaluates the limiting efficiencies e(-S ) of burst-correcting array codes A(n₁,n₂, -s) for all negative readouts -s as n₂ tends to infinity and n₁ is properly chosen to maximize the efficiency. Specializing the result to the products of the first i primes donated by s_i (1⩽i<∞), which are optimal choices for readouts, gives the expression e(-s_i)=(2p_i+1 -2)/(2p_i+1-1) where p_i+1 is the next prime. Previously, it was known only that e(-2)⩾4/5 and e(-1)⩾2/3. This result reveals the existence of burst-correcting array codes with efficiencies arbitrarily close to 1 and with rates also arbitrarily close to 1     

A family of efficient burst-correcting array codes

A family of binary burst correcting array codes that are defined as follows is discussed: consider an n₁×n n₂ array with n₁=4u+ν+2 and n₂=6u+2ν+5, u⩾1, ν⩾0, ν≠1 where each row and column has even parity. The bits are read diagonally starting from the upper-left corner. The columns are viewed cyclically, i.e. the array is a cylinder. If one diagonal has been read out, one proceeds with the second diagonal preceding it. It is proven that the codes of this type can correct any burst of length up to n₁. The burst-correcting efficiency of this family tends to 4/5 as u→∞. As a comparison, the burst-correcting efficiency of other families of array codes tends to 2/3; the same is true for Fire codes. A simple decoding algorithm for the codes is also presented     

Efficient encoding of QC-LDPC codes related to cyclic MDS codes

In this paper, we present an efficient systematic encoding algorithm for quasi-cyclic (QC) low-density paritycheck (LDPC) codes that are related to cyclic maximum-distance separable (MDS) codes. The algorithm offers linear time complexity, and it can be easily implemented by using polynomial multiplication and division circuits. We show that the division polynomials can be completely characterized by their zeros and that the sum of the respective numbers of their zeros is equal to the parity-length of the codes.     

Some asymptotically optimal burst-correcting codes and their relation to single-error-correcting Reed-Solomon codes

A class of asymptotically optimal burst-correcting codes that are closely related to the Fire codes is defined. The codes are quasi-cyclic as defined by Townsend and Weldon. However, decoding can be accomplished with a very simple algorithm similar to that used for cyclic burst-correcting codes. It is shown that these codes are equivalent to certain Reed-Solomon codes. From this it follows that such Reed-Solomon codes can be easily encoded and decoded without any computations in an extension field.     

A class of high-speed decodable burst-correcting codes (Corresp.)

A class of high-speed decodable burst-correcting codes is presented. This class of codes is obtained by modifying burst-correcting convolutional codes into block codes and does not require any cyclic shifts in the decoding process. With the appropriate choices of parameters, the codes can approximate minimum-redundancy codes. The high-speed decodability is expected to make these codes suitable for application to computer systems.     

Extended Varshamov- Gilbert and sphere-packing bounds for burst-correcting codes (Corresp.)

The study of burst-error-correcting codes has generally been made without weight considerations while the random-error-correcting capabilities of a linear code largely depend upon the minimum weight. In this correspondence we have obtained extensions of the Varshamov-Gilbert and sphere-packing hounds to burst-error-correcting codes.     

Repeated-root cyclic codes

In the theory of cyclic codes, it is common practice to require that (n,q)=1, where n is the word length and F_q is the alphabet. It is shown that the even weight subcodes of the shortened binary Hamming codes form a sequence of repeated-root cyclic codes that are optimal. In nearly all other cases, one does not find good cyclic codes by dropping the usual restriction that n and q must be relatively prime. This statement is based on an analysis for lengths up to 100. A theorem shows why this was to be expected, but it also leads to low-complexity decoding methods. This is an advantage, especially for the codes that are not much worse than corresponding codes of odd length. It is demonstrated that a binary cyclic code of length 2n (n odd) can be obtained from two cyclic codes of length n by the well-known | u|u+v| construction. This leads to an infinite sequence of optimal cyclic codes with distance 4. Furthermore, it is shown that low-complexity decoding methods can be used for these codes. The structure theorem generalizes to other characteristics and to other lengths. Some comparisons of the methods using earlier examples are given     

Linear codes derived from cyclic codes

This paper presents a procedure for the construction of linear block codes derived from cyclic subspaces. The distance properties of these codes are determined indirectly by the BCH bound despite the fact that they are not cyclic.     

Efficient balanced codes

Coding schemes in which each codeword contains equally many zeros and ones are constructed in such a way that they can be efficiently encoded and decoded.     

Self-synchronizing codes derived from binary cyclic codes

The sensitivity of a binary block code to loss of synchronism (misplacement of the "commas" separating codewords) can be characterized by a pair of numbers[s, delta]such that any synchronization slip of s bits or less produces an overlap sequence differing from a legitimate codeword in at leastdeltaplaces. This definition is broader than that of comma freedom of indexdelta, which is included as the special case of s equal to the integer part of half the code block length. For codes having the slip-detecting characteristic[s, delta]there exists the possibility of implementation to restore synchronism during an interval relatively free from bit errors. It is shown that certain error-correcting binary cyclic block codes can be altered to obtain the characteristic[s, delta]by the addition of a fixed binary vector to each codeword prior to transmission. These altered cyclic codes retain the full error-correcting power of the original cyclic codes. An error-detecting/correcting data format providing protection against the acceptance of misframed data is thus obtained without the insertion of special synchronizing sequences into the bit stream.     

Good block codes derived from cyclic codes

By combining irreducible cyclic codes, we obtain good quasicyclic or extended quasicyclic codes. Some of these improve on the lower bound of Helgert and Stinaff.     

Permutation-decodable binary cyclic codes

The letter develops bounds on the information rates of certain binary cyclic codes so that they are s-step permutation decodable (s=2, 3, 4).     

Locally testable cyclic codes

Cyclic linear codes of block length n over a finite field F/sub q/ are linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes. A code C is r-testable if there exists a randomized algorithm which, given a word x/spl isin//sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that 1) if x/spl isin/C then x is surely accepted; ii) if dist(x,C) /spl ges/ /spl epsi/n then x is probably rejected. ("dist" refers to Hamming distance.) A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCP's. Recently it was asked whether there exist good, locally testable families of codes. In this paper the intersection of the two questions stated is addressed. Theorem. There are no good, locally testable families of cyclic codes over any (fixed) finite field. In fact the result is stronger in that it replaces condition ii) of local testability by the condition ii') if dist (x,C) /spl ges/ /spl epsi/n then x has a positive chance of being rejected. The proof involves methods from Galois theory, cyclotomy, and diophantine approximation.     

On repeated-root cyclic codes

A parity-check matrix for a q-ary repeated-root cyclic code is derived using the Hasse derivative. Then the minimum distance of a q-ary repeated-root cyclic code is expressed in terms of the minimum distance of a certain simple-root cyclic code. With the help of this result, several binary repeated-root cyclic codes of lengths up to n=62 are shown to contain the largest known number of codewords for their given length and minimum distance. The relative minimum distance d_min/n of q-ary repeated-root cyclic codes of rate r⩾R is proven to tend to zero as the largest multiplicity of a root of the generator g(x) increases to infinity. It is further shown that repeated-root cycle codes cannot be asymptotically better than simple-root cyclic codes     

Efficient erasure correcting codes

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number ϵ a family of linear codes of rate R which can be encoded in time proportional to ln(1/ϵ) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+ϵ)Rn or more. The recovery algorithm also runs in time proportional to n ln(1/ϵ). Our algorithms have been implemented and work well in practice; various implementation issues are discussed     

Efficient multiplication-free arithmetic codes

Arithmetic coding is a powerful lossless data compression technique that has attracted much attention. It provides more flexibility and better efficiency than Huffman coding does. However, the multiplications needed in its encoding and decoding algorithms are very undesirable. Rissanen and Mohiuddin (1989) have proposed a simple scheme to avoid the multiplications. The present authors found that the performance of their proposed scheme might degrade significantly in some cases. They propose a multiplication-free multialphabet arithmetic code which can be shown to have minor performance degradation in all cases. In the proposed scheme, each multiplication is replaced by a single shift-and-add. The authors prove, by both theoretical analysis and simulation results, that the degradation of the proposed multiplication-free scheme is always several times (2-7 times in the present experiments) smaller than that of the Rissanen-Mohiuddin's scheme     

Efficient ternary transmission codes

To limit distortion in digital cable systems due to low-frequency cuts, it has been usual either to use quantised feedback or use a code with a finite digital-sum variation. It is shown that these restrictions are unnecessarily stringent. Systems typically use 3-level codes, and some codes requiring less bandwidih than the 4B3T type are analysed.