张量积码的多重覆盖半径

码的多重覆盖半径是最近对码的通常覆盖半径的一个推广．本文研究了由两个二元线性码构成的张量积码的多重覆盖半径．并得到了该张量积码的多重覆盖半径的界．     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

The multicovering radius problem for some types of discrete structures

The covering radius problem is a question in coding theory concerned with finding the minimum radius r such that, given a code that is a subset of an underlying metric space, balls of radius r over its code words cover the entire metric space. Klapper (IEEE Trans. Inform. Theory 43:1372–1377, 1997) introduced a code parameter, called the multicovering radius, which is a generalization of the covering radius. In this paper, we introduce an analogue of the multicovering radius for permutation codes (Des. Codes Cryptogr. 41:79–86, cf. 2006) and for codes of perfect matchings (cf. 2012). We apply probabilistic tools to give some lower bounds on the multicovering radii of these codes. In the process of obtaining these results, we also correct an error in the proof of the lower bound of the covering radius that appeared in (Des. Codes Cryptogr. 41:79–86, cf. 2006). We conclude with a discussion of the multicovering radius problem in an even more general context, which offers room for further research.     

The Reed-Muller Code R(1,7) Is Normal

We prove that the Reed-Muller code R(1,7) is normal. The normality of R(1,7) was a long-standing open question, and has an important consequence in a conjecture about the function t[n,k], the smallest covering radius of any [n,k] binary linear code.     

New Linear Codes with Covering Radius 2 and Odd Basis

On the way of generalizing recent results by Cock and the second author, it is shown that when the basis q is odd, BCH codes can be lengthened to obtain new codes with covering radius R=2. These constructions (together with a lengthening construction by the first author) give new infinite families of linear covering codes with codimension r=2k+1 (the case q=3, r=4k+1 was considered earlier). New code families with r=4k are also obtained. An updated table of upper bounds on the length function for linear codes with 24, R=2, and q=3,5 is given.     

A Gap in GRM Code Weight Distributions

The weight distribution of GRM (generalized Reed-Muller) codes is unknown in general. This article describes and applies some new techniques to the codes over F3. Specifically, we decompose GRM codewords into words from smaller codes and use this decomposition, along with a projective geometry technique, to relate weights occurring in one code with weights occurring in simpler codes. In doing so, we discover a new gap in the weight distribution of many codes. In particular, we show there is no word of weight 3^m–2 in GRM₃(4,m) for m>6, and for even-order codes over the ternary field, we show that under certain conditions, there is no word of weight d+, where d is the minimum distance and is the largest integer dividing all weights occurring in the code.     

Nonlinearity of Some Invariant Boolean Functions

One of the hardest problems in coding theory is to evaluate the covering radius of first order Reed–Muller codes RM(1,m), and more recently the balanced covering radius for crypto graphical purposes. The aim of this paper is to present some new results on this subject. We mainly study boolean functions invariant under the action of some finite groups, following the idea of Patterson and Wiedemann [The covering radius of the (1, 15) Reed-Muller Code is atleast 16276. IEEE Trans Inform Theory. Vol. 29 (1983) 354.]. Our method is Fourier transforms and our results are both theoretical and numerical.     

Subcodes of the Projective Generalized Reed-Muller Codes Spanned by Minimum-Weight Vectors

We use methods of Mortimer [19] to examine the subcodes spanned by minimum-weight vectors of the projective generalized Reed-Muller codes and their duals. These methods provide a proof, alternative to a dimension argument, that neither the projective generalized Reed-Muller code of order r and of length over the finite field F _q of prime-power order q, nor its dual, is spanned by its minimum-weight vectors for 0<r<m–1 unless q is prime. The methods of proof are the projective analogue of those developed in [17], and show that the codes spanned by the minimum-weight vectors are spanned over F _q by monomial functions in the m variables. We examine the same question for the subfield subcodes and their duals, and make a conjecture for the generators of the dual of the binary subfield subcode when the order r of the code is 1.     

Further results on the covering radius of small codes

The minimum number of codewords in a code with t ternary and b binary coordinates and covering radius R is denoted by K(t,b,R). In the paper, necessary and sufficient conditions for K(t,b,R)=M are given for M=6 and 7 by proving that there exist exactly three families of optimal codes with six codewords and two families of optimal codes with seven codewords. The cases M?5 were settled in an earlier study by the same authors. For binary codes, it is proved that K(0,2b+4,b)?9 for b?1. For ternary codes, it is shown that K(3t+2,0,2t)=9 for t?2. New upper bounds obtained include K(3t+4,0,2t)?36 for t?2. Thus, we have K(13,0,6)?36 (instead of 45, the previous best known upper bound).     

Optimal doubly constant weight codes

A doubly constant weight code is a binary code of length n₁ + n₂, with constant weight w₁ + w₂, such that the weight of a codeword in the first n₁ coordinates is w₁. Such codes have applications in obtaining bounds on the sizes of constant weight codes with given minimum distance. Lower and upper bounds on the sizes of such codes are derived. In particular, we show tight connections between optimal codes and some known designs such as Howell designs, Kirkman squares, orthogonal arrays, Steiner systems, and large sets of Steiner systems. These optimal codes are natural generalization of Steiner systems and they are also called doubly Steiner systems. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 137–151, 2008     

On the Covering Radius of Ternary Extremal Self-Dual Codes

In this paper, we investigate the covering radius of ternary extremal self-dual codes. The covering radii of all ternary extremal self-dual codes of lengths up to 20 were previously known. The complete coset weight distributions of the two inequivalent extremal self-dual codes of length 24 are determined. As a consequence, it is shown that every extremal ternary self-dual code of length up to 24 has covering radius which meets the Delsarte bound. The first example of a ternary extremal self-dual code with covering radius which does not meet the Delsarte bound is also found. It is worth mentioning that the found code is of length 32.     

Artin–Schreier curves and weights of two-dimensional cyclic codes

Let be the finite field with q elements of characteristic p, be the extension of degree m>1 and f(x) be a polynomial over . The maximum number of affine -rational points that a curve of the form y^q−y=f(x) can have is q^m+1. We determine a necessary and sufficient condition for such a curve to achieve this maximum number. Then we study the weights of two-dimensional (2-D) cyclic codes. For this, we give a trace representation of the codes starting with the zeros of the dual 2-D cyclic code. This leads to a relation between the weights of codewords and a family of Artin–Schreier curves. We give a lower bound on the minimum distance for a large class of 2-D cyclic codes. Then we look at some special classes that are not covered by our main result and obtain similar minimum distance bounds.     

Weight enumeration of codes from finite spaces

We study the generalized and extended weight enumerator of the q-ary Simplex code and the q-ary first order Reed-Muller code. For our calculations we use that these codes correspond to a projective system containing all the points in a finite projective or affine space. As a result from the geometric method we use for the weight enumeration, we also completely determine the set of supports of subcodes and words in an extension code.     

An updated table of binary/ternary mixed covering codes

An updated table of K_2,3(b,t;R)—the minimum cardinality of a code with b binary coordinates, t ternary coordinates, and covering radius R—is presented for b + t ≤ 13, R ≤ 3. The results include new explanations of short binary and ternary covering codes, several new constructions and codes, and a general lower bound for R = 1. © 2004 Wiley Periodicals, Inc.     

A note on Reed-Muller codes

In this paper we study linear codes that are obtained by annexing some vectors to the basis vectors of a Reed-Muller code of order r.     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

On non-antipodal binary completely regular codes

Binary non-antipodal completely regular codes are characterized. Using a result on nonexistence of nontrivial binary perfect codes, it is concluded that there are no unknown nontrivial non-antipodal completely regular binary codes with minimum distance d?3. The only such codes are halves and punctured halves of known binary perfect codes. Thus, new such codes with covering radius ρ=6 and 7 are obtained. In particular, a half of the binary Golay [23,12,7]-code is a new binary completely regular code with minimum distance d=8 and covering radius ρ=7. The punctured half of the Golay code is a new completely regular code with minimum distance d=7 and covering radius ρ=6. The new code with d=8 disproves the known conjecture of Neumaier, that the extended binary Golay [24,12,8]-code is the only binary completely regular code with d?8. Halves of binary perfect codes with Hamming parameters also provide an infinite family of binary completely regular codes with d=4 and ρ=3. Puncturing of these codes also provide an infinite family of binary completely regular codes with d=3 and ρ=2. Both these families of codes are well known, since they are uniformly packed in the narrow sense, or extended such codes. Some of these completely regular codes are new completely transitive codes.     

Some Upper Bounds on the Covering Radii of Linear Codes Over Fq and Their Applications

We show that the covering radius R of an [n,k,d] code over F_q is bounded above by R n-n _q(k, d/q). We strengthen this bound when R d and find conditions under which equality holds.As applications of this and other bounds, we show that all binary linear codes of lengths up to 15, or codimension up to 9, are normal. We also establish the normality of most codes of length 16 and many of codimension 10. These results have applications in the construction of codes that attain t[n,k,/it>], the smallest covering radius of any binary linear [n,k].We also prove some new results on the amalgamated direct sum (ADS) construction of Graham and Sloane. We find new conditions assuring normality of the ADS; covering radius 1 less than previously guaranteed for ADS of codes with even norms; good covering codes as ADS without the hypothesis of normality, from concepts p- stable and s- stable; codes with best known covering radii as ADS of two, often cyclic, codes (thus retaining structure so as to be suitable for practical applications).     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

Fast Decoding Algorithms for First Order Reed-Muller and Related Codes

Fast decoding algorithms for short codes based on modifications of maximum likelihood decoding algorithms of first order Reed-Muller codes are described. Only additions-subtractions, comparisons and absolute value calculations are used in the algorithms. Soft and hard decisions maximum likelihood decoding algorithms for first order Reed-Muller and the Nordstrom-Robinson codes with low complexity are proposed.