New covering radius of Reed-Muller codes for t-resilient functions

In this paper, we introduce a new covering radius of RM(r,n) from cryptography viewpoint. It is defined as the maximum distance between t-resilient functions and the rth order Reed-Muller code RM(r,n). We next derive its lower and upper bounds. We further present a table of numerical data of our bounds.     

Further results on the covering radius of codes

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) leq K(n, R)holds for sufficiently largen.     

Projective Reed-Muller codes

A class of codes in the Reed-Muller family, the projective Reed-Muller codes (PRM codes), is studied. The author defines the PRM codes of all orders and discusses their relation to polynomial codes. The exact parameters of PRM codes are given. The duals are characterized, and, in parallel to the classical works on generalized Reed-Muller codes, the cyclic properties are studied. Tables over parameters of the codes are given     

Weighted Reed-Muller codes and algebraic-geometric codes

A generalization of the Reed-Muller codes, the weighted Reed-Muller codes, is presented. The code parameters are estimated and the duals are shown also to be weighted Reed-Muller codes. It is shown how the minimum distance of certain algebraic-geometric codes in many cases can be determined exactly or an upper bound can be found, using subcodes which are weighted Reed-Muller codes     

Binary multilevel coset codes based on Reed-Muller codes

We study the construction and decoding of binary multilevel coset codes. This construction, originally introduced by Blokh and Zyablov in 1974 and by Zinov'ev in 1976, shows remarkable analogies with most recent schemes of coded modulations. Basic elements of the construction are an inner code, head of a partition chain having suitable distance properties, and a set of outer codes, generally nonbinary. For each partition level there is an outer code whose alphabet has the same order of the partition: in this way it is possible to associate every partition subset to a code symbol. It is well known that these codes can be efficiently decoded by the so called “multistage decoding.” We show that good codes (in terms of performance/complexity) can be constructed using Reed-Muller (RM) codes as inner codes. To this aim RM codes are revisited in the framework of the above construction and decoding techniques. In particular we describe a family of decoders for RM codes which include Forney's (1988) and Hemmati's (1989) decoders as special cases. Finally, we present some examples of efficient binary codes based on RM codes, and assess their performance via computer simulation     

Some results on the norm of codes

Two upper bounds for the norm N(C) of a binary linear code C with minimal weight d and covering radius R are given. The second of these bounds implies that C is normal if R=3     

On the weight structure of Reed-Muller codes

The following theorem is proved. Letf(x_1,cdots, x_m)be a binary nonzero polynomial ofmvariables of degreenu. H the number of binarym-tuples(a_1,cdots, a_m)withf(a_1, cdots, a_m)= 1 is less than2^{m-nu+1}, thenfcan be reduced by an invertible affme transformation of its variables to one of the following forms. begin{equation} f = y_1 cdots y_{nu - mu} (y_{nu-mu+1} cdots y_{nu} + y_{nu+1} cdots y_{nu+mu}), end{equation} wherem geq nu+muandnu geq mu geq 3. begin{equation} f = y_1 cdots y_{nu-2}(y_{nu-1} y_{nu} + y_{nu+1} y_{nu+2} + cdots + y_{nu+2mu -3} y_{nu+2mu-2}), end{equation} This theorem completely characterizes the codewords of thenuth-order Reed-Muller code whose weights are less than twice the minimum weight and leads to the weight enumerators for those codewords. These weight formulas are extensions of Berlekamp and Sloane's results.     

On covering radii and coset weight distributions of extremal binaryself-dual codes of length 56

We present a method to determine the complete coset weight distributions of doubly even binary self-dual extremal [56, 28, 12] codes. The most important steps are (1) to describe the shape of the basis for the linear space of rigid Jacobi polynomials associated with such codes in each index i, (2) to describe the basis polynomials for the coset weight enumerators of the assigned coset weight i by means of rigid Jacobi polynomials of index i. The multiplicity of the cosets of weight i have a connection with the frequency of the rigid reference binary vectors v of weight i for the Jacobi polynomials. This information is sufficient to determine the complete coset weight distributions. Determination of the covering radius of the codes is an immediate consequence of this method. One important practical advantage of this method is that it is enough to get information on 8190 codewords of weight 12 (minimal-weight words) in each such code for computing every necessary information     

Orphans of the first order Reed-Muller codes

If C is a code, an orphan is a coset that is not a descendant. Orphans arise naturally in the investigation of the covering radius. Case C has only even-weight vectors and minimum distance of at least four. Cosets that are orphans are characterized, and then the existence is proved of a family of orphans of first-order Reed-Muller codes R(1, m). For m⩽5 all orphans of R(1, m) are identified     

List decoding of q-ary Reed-Muller codes

The q-ary Reed-Muller (RM) codes RM/sub q/(u,m) of length n=q/sup m/ are a generalization of Reed-Solomon (RS) codes, which use polynomials in m variables to encode messages through functional encoding. Using an idea of reducing the multivariate case to the univariate case, randomized list-decoding algorithms for RM codes were given in and . The algorithm in Sudan et al. (1999) is an improvement of the algorithm in , it is applicable to codes RM/sub q/(u,m) with u相似文献   

Soft-decision decoding of Reed-Muller codes as generalized multipleconcatenated codes

Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long codes     

Soft-decision majority decoding of Reed-Muller codes

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2^m transmitted symbols are recalculated into the reliabilities of 2^m-r parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log₁₀(π/2)≈2 dB at any given output error probability. For fixed code rate R and m→∞, our algorithm increases almost 2^r/2 times the correcting capability of soft-decision bounded distance decoding     

Some new upper bounds on the covering radius of binary linear codes

A Griesmer-like upper bound on the covering radius, R, is given. To the author's knowledge this is the only upper bound which explicitly depends on all three parameters n, k, and d. An upper bound on R for cyclic codes is then given which depends on the generator polynomial of the cyclic code and which, in many cases, leads to an improvement of the previous bound. An upper bound on the irreducible generator polynomial cyclic codes is also given. New interpretations and applications of the so-called Norse bounds and necessary and sufficient conditions to attain one of these bounds are provided. Generalizations of most of the results for codes over GF(q) are outlined     

Weight enumerator for second-order Reed-Muller codes

In this paper, we establish the following result. Theorem:A_i, the number of codewords of weightiin the second-order binary Reed-Muller code of length2^mis given byA_i = 0unlessi = 2^{m-1}or2^{m-1} pm 2^{m-l-j}, for somej, 0 leq j leq [m/2], A_0 = A_{2^m} = 1, and begin{equation} begin{split} A_{2^{m-1} pm 2^{m-1-j}} = 2^{j(j+1)} &{frac{(2^m - 1) (2^{m-1} - 1 )}{4-1} } \ .&{frac{(2^{m-2} - 1)(2^{m-3} -1)}{4^2 - 1} } cdots \ .&{frac{(2^{m-2j+2} -1)(2^{m-2j+1} -1)}{4^j -1} } , \ & 1 leq j leq [m/2] \ end{split} end{equation} begin{equation} A_{2^{m-1}} = 2 { 2^{m(m+1)/2} - sum_{j=0}^{[m/2]} A_{2^{m-1} - 2^{m-1-j}} }. end{equation}     

Generalized Hamming weights of q-ary Reed-Muller codes

The order bound on generalized Hamming weights is introduced in a general setting of codes on varieties which comprises both the one point geometric Goppa codes as well as the q-ary Reed-Muller codes. For the latter codes it is shown that this bound is sharp and that they satisfy the double chain condition     

Some results on the weight distribution of linear codes

By studying the algebraic structure of the parity check matrix of a linear code we show that the weight distribution is a function only of the quantitiesN_{upsilon}^{u}, the number ofupsiloncolumns of the parity check matrix with ranku. We apply this to obtain a new formula for the weight distribution of the distance3 s-ary Hamming code and for the distance4 s-ary conic code. We give the definition of a conic code and some of its properties.     

Efficient decoding algorithms for generalized Reed-Muller codes

Previously, a class of generalized Reed-Muller (RM) codes has been suggested for use in orthogonal frequency-division multiplexing. These codes offer error correcting capability combined with substantially reduced peak-to mean power ratios. A number of approaches to decoding these codes have already been developed. Here, we present low complexity, suboptimal alternatives which are inspired by the classical Reed decoding algorithm for binary RM codes. We simulate these new algorithms along with the existing decoding algorithms using additive white Gaussian noise and two-path fading models for a particular choice of code. The simulations show that one of our new algorithms outperforms all existing suboptimal algorithms and offers performance that is within 0.5 dB of maximum-likelihood decoding, yet has complexity comparable to or lower than existing decoding approaches     

Some results on arithmetic codes of composite length

A new upper bound on the minimum distance of binary cyclic arithmetic codes of composite length is derived. New classes of binary cyclic arithmetic codes of composite length are introduced. The error correction capability of these codes is discussed, and in some cases the actual minimum distance is found. Decoding algorithms based on majority-logic decision are proposed for these codes.     

New generalizations of the Reed-Muller codes--I: Primitive codes

First it is shown that all binary Reed-Muller codes with one digit dropped can be made cyclic by rearranging the digits. Then a natural generalization to the nonbinary case is presented, which also includes the Reed-Muller codes and Reed-Solomon codes as special cases. The generator polynomial is characterized and the minimum weight is established. Finally, some results on weight distribution are given.     

Concatenated Reed-Muller codes for unequal error protection

We present a new coding scheme that combines the advantages of a product-like concatenation of Reed-Muller codes with so-called iterative “turbo” decoding and provides powerful unequal error protection abilities. It is shown that various levels of error protection can be realized using a sophisticated encoding scheme for Reed-Muller codes. A discussion of this code construction, the resulting distance profile between the different levels and the iterative decoding scheme is given. The results are very promising and impressively confirm the unequal error protection capabilities of the presented coding scheme