On the existence of optimum cyclic burst correcting codes over GF(q)

A cyclic b-burst correcting code over GF(q) of redundancy r and length n=(q^r-b+1-1)/(q-1) is said to be optimum. It is proved that a necessary condition for the existence of such a code is the existence of a square-free polynomial in GF(q)[x] of degree b-1 which is not divisible by x such that its period and the degrees of its irreducible factors are relatively prime to q-1. Moreover, if such a polynomial exists, then there are an infinite number of optimum cyclic b-burst correcting codes over GF(q)     

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     

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     

Identities and approximations for the weight distribution of q-ary codes

An explicit formula is derived that enumerates the complete weight distribution of an (n, k, d) linear code using a partially known weight distribution. An approximation formula for the weight distribution of q-ary linear (n, k , d) codes is also derived. It is shown that, for a given q-ary linear (n, k, d) code, the ratio of the number of codewords of weight u to the number of words of weight u approaches the constant Q=q ^-(n-k) as u becomes large. The error term is a decreasing function of the minimum weight of the dual. The results are also valid for nonlinear (n, M, d) codes with the minimum weight of the dual replaced by the dual distance     

Pseudocyclic maximum-distance-separable codes

The (n, k) pseudocyclic maximum-distance-separable (MDS) codes modulo (xⁿ- a) over GF(q) are considered. Suppose that n is a divisor of q+1. If n is odd, pseudocyclic MDS codes exist for all k. However, if n is even, nontrivial pseudocyclic MDS codes exist for odd k (but not for even k) if a is a quadratic residue in GF(q), and they exist for even k (but not for odd k) if a is not a quadratic residue in GF(q). Also considered is the case when n is a divisor of q-1, and it is shown that pseudocyclic MDS codes exist if and only if the multiplicative order of a divides (q-1)/n, and that when this condition is satisfied, such codes exist for all k. If the condition is not satisfied, every pseudocyclic code of length n is the result of interleaving a shorter pseudocyclic code     

Optimal selection of Reed-Solomon code rate and the number offrequency slots in asynchronous FHSS-MA networks

The performance of Reed-Solomon codes in an asynchronous frequency-hop spread-spectrum multiple-spectrum (FHSS-MA) network is discussed. When q denotes the number of frequency slots available to the network and r denotes the rate of the Reed-Solomon code, optimal (q,r) pairs that meet a given performance criterion with minimum bandwidth expansion (q/r) for a given number of active users are obtained. It is shown that the optimal code rate rapidly converges to a constant value and the optimum number of slots increases approximately linearly as the number of active users increases. This suggests that one should fix the code rate and increase the number of slots to accommodate the increasing number of users in the network under a given performance criterion with minimum bandwidth expansion     

Relationships between m-sequences over GF(q) andGF(qm)

It is shown that m-sequences over GF(q^m ) of length q^nm-1 corresponding to primitive polynomials in GF[q^m,x] of degree n can be generated from known m-sequences over GF(q) of length q^nm-1 obtained from primitive polynomials in GF[q,x] of degree mn. A procedure for generating the m-sequences over GF(q²) from m-sequences over GF(q) was given which enables the generation of m-sequences over GF( p²ⁿ). In addition it was shown that all of the primitive polynomials in GF[q,^m,x] can be obtained from a complete set of the primitive polynomials in GF[q ,x]     

Packet error probabilities in frequency-hopped spread-spectrumpacket radio networks-memoryless frequency-hopping patterns considered

The packet error probability induced in a frequency-hopped spread-spectrum packet radio network is computed. The frequency spectrum is divided into q frequency bins. Each packet is exactly one codeword from an (M, L) Reed-Solomon code [M=number of codeword symbols (bytes); L=number of information symbols (bytes)]. Every user in the network sends each of the M bytes of his packet at a frequency chosen among the q frequencies with equal probability and independently of the frequencies chosen for other bytes (i.e., memoryless frequency-hopping patterns). Statistically independent frequency-hopping patterns correspond to different users in the network. Provided that K users have simultaneously transmitted their packets on the channel and a receiver has locked on to one of these K packets, the probability that this packet is not decoded correctly is evaluated. It is also shown that although memoryless frequency-hopping patterns are utilized, the byte errors at the receiver are not statistically independent; instead they exhibit a Markovian structure     

New multilevel codes over GF(q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GFⁿ¹(q) (n1⩽q ), and it is shown how to construct both multilevel block codes and multilevel trellis codes over GF(q). Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d_min⩾d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes     

New array codes for multiple phased burst correction

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors     

Bounds on the undetected error probabilities of linear codes forboth error correction and detection

The author investigates the (n, k, d⩾2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) [2^n-k-n]^-1 when used on a binary symmetric channel with transition probability less than 2/n     

Capture models for mobile packet radio networks

The probability q_i of successful reception in a nonfading mobile radio channel with i contending mobiles transmitting to a central base station is studied for a number of different capture and spatial distribution models. It is shown that a generalized capture model can be used to estimate q_i's for a simplified example system which uses noncoherent frequency shift keying modulation. This model can be applied to other systems as well. An example of the use of the q_i 's in the throughput evaluation of a finite population slotted ALOHA system is given. In most practical systems, the mobiles cannot get arbitrarily close to the base station. The effect of this constraint on q_i is examined. Finally, the dependence of the capture probability for a test mobile on its distance from the base station is obtained     

Capture probability in a mobile packet radio system

The probability of q_i of successful packet reception when i users transmit simultaneously in a mobile packet radio system is shown to decrease monotonically with i for a number of commonly used capture and spatial distribution models, with no fading. Examples of both noiseless and noisy systems in which q_i is not monotonically decreasing with i are also given     

On (k, t)-subnormal covering codes

The concept of a (k, t)-subnormal covering code is defined. It is discussed how an amalgamated-direct-sumlike construction can be used to combine such codes. The existence of optimal (q, n, M) 1 codes C is discussed such that by puncturing the first coordinate of C one obtains a code with (q, 1)-subnorm 2     

Lower bounds for q-ary covering codes

The authors prove combinatorial lower bounds for K_q (n,R), the minimal cardinality of any q-ary code of length n and covering radius R. Tables of lower bounds for K_q(n,R) are presented for q=3, 4, 5     

Error detecting capabilities of the shortened Hamming codes adoptedfor error detection in IEEE Standard 802.3

Investigates the error detecting capabilities of the shortened hamming codes adopted for error detection in IEEE Standard 802.3. These codes are also used for error detection in the data link layer of the Ethernet, a local area network. The authors compute the weight distributions for various code lengths. From the results, they show the probability of undetectable error and that of detectable error for a binary symmetric channel with bit-error rate 10^-5⩽ϵ⩽ 1/2. They also find the minimum distance of the shortened code of length n for 33 ⩽n ⩽12144 and the double-burst detecting capabilities     

Optimum codes of dimension 3 and 4 over GF(4)

n_q(k,d), the length of a q-ary optimum code for given k and d, for q=4 and k=3, 4 is discussed. The problem is completely solved for k=3, and the exact value of n₄(4,d) is determined for all but 52 values of d     

On the average delay for routing subject to independent deflections

Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p . At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is roughly, at least H(p)/(1-h(q), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable in the case where the packet always begins at a fixed node. Also considered is the maximum, over all pairs of nodes in a graph, of the mean transit time from one node to the other. The work is motivated by the search for graphs that work well in conjunction with deflection routing in communication networks     

On the decoding of algebraic-geometric codes

A decoding algorithm for algebraic-geometric codes arising from arbitrary algebraic curves is presented. This algorithm corrects any number of errors up to [(d-g-1)/2], where d is the designed distance of the code and g is the genus of the curve. The complexity of decoding equals σ(n³) where n is the length of the code. Also presented is a modification of this algorithm, which in the case of elliptic and hyperelliptic curves is able to correct [(d-1)/2] errors. It is shown that for some codes based on plane curves the modified decoding algorithm corrects approximately d/2-g/4 errors. Asymptotically good q-ary codes with a polynomial construction and a polynomial decoding algorithm (for q⩾361 on some segment their parameters are better than the Gilbert-Varshamov bound) are obtained. A family of asymptotically good binary codes with polynomial construction and polynomial decoding is also obtained, whose parameters are better than the Blokh-Zyablov bound on the whole interval 0<σ<1/2