Finite Projective Geometries and Classification of the Weight Hierarchies of Codes （Ⅰ）

The weight hierarchy of a binary linear [n,κ] code C is the sequence (d1,d2,...,dκ), where dr is the smallest support of an r-dimensional subcode of C. The codes of dimension 4 are collected in classes and the possible weight hierarchies in each class is determined by finite projective geometries.The possible weight hierarchies in class A, B, C, D are determined in Part (Ⅰ). The possible weight hierarchies in class E, F, G, H, I are determined in Part (Ⅱ).     

A Class of Perfect Ternary Constant-Weight Codes

We construct a class of perfect ternary constant-weight codes of length 2 ^r , weight 2 ^r -1 and minimum distance 3. The codes have codewords. The construction is based on combining cosets of binary Hamming codes. As a special case, for r=2 the construction gives the subcode of the tetracode consisting of its nonzero codewords. By shortening the perfect codes, we get further optimal codes.     

Weight Hierarchies of Linear Codes Satisfying the Chain Condition

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,...,d_k) where d_r is the smallest support of an r–dimensional subcode of C. By explicit construction, it is shown that if a sequence (a₁,a₂,...,a_k) satisfies certain conditions, then it is the weight hierarchy of a code satisfying the chain condition.     

Antichain Codes

We show that almost all codes satisfy an antichain condition. This states that the minimum length of a two dimensional subcode of a code C increases if the subcode is constrained to contain a minimum weight codeword. In particular, almost no code satisfies the chain condition. In passing, we study the typical behaviour of codes with respect to generalized distances and show that almost all lie on a generalized Varshamov-Gilbert bound.     

On the Generalized Weights of a Class of Trace Codes

We build a class of codes using hermitian forms and the functional trace code. Then we give a general expression of the rth minimum distance of our code and compute general bounds for the weight hierarchy by using exponential sums. We also get the minimum distance and calculate the rth generalized Hamming weight d_r in some special cases.     

On the second greedy weight for linear codes of dimension 3

The difference g₂−d₂ for a q-ary linear [n,3,d] code C is studied. Here d₂ is the second generalized Hamming weight, that is, the smallest size of the support of a 2-dimensional subcode of C; and g₂ is the second greedy weight, that is, the smallest size of the support of a 2-dimensional subcode of C which contains a codeword of weight d. For codes of dimension 3, it is shown that the problem is essentially equivalent to finding certain weighting of the points in the projective plane, and weighting which give the maximal value of g₂−d₂ are determined in almost all cases. In particular max(g₂−d₂) is determined in all cases for q⩽9.     

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.     

Higher Weights of Anticodes and the Generalized Griesmer Bound

We show that the minimum r-weight d_r of an anticode can be expressed in terms of the maximum r-weight of the corresponding code. As examples, we consider anticodes from homogeneous hypersurfaces (quadrics and Hermitian varieties). In a number of cases, all differences (except for one) of the weight hierarchy of such an anticode meet an analog of the generalized Griesmer bound.     

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.     

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     

Testing algebraic geometric codes

Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally te...     

Shadow Codes over 4

The notion of a shadow of a self-dual binary code is generalized to self-dual codes over ₄. A Gleason formula for the symmetrized weight enumerator of the shadow of a Type I code is derived. Congruence properties of the weights follow; this yields constructions of self-dual codes of larger lengths. Weight enumerators and the highest minimum Lee, Hamming, and Euclidean weights of Type I codes of length up to 24 are studied.     

A restriction on the weight enumerator of a self-dual code

Gleason's theorem gives the general form of the weight enumerator of a linear binary self-dual code; it is a linear combination with integral coefficients of certain polynomials. When the subcode of words whose weights are multiples of 4 is not the whole code, the MacWilliams identities applied to that subcode yield divisibility conditions on those coefficients. The conditions show that there are no further extremal codes, for Case 1 in the sense of Mallows and Sloane, than the ones known.     

A result on the weight distributions of binary quadratic residue codes

Truong et al. [7]proved that the weight distribution of a binary quadratic residue code C with length congruent to −1 modulo 8 can be determined by the weight distribution of a certain subcode of C containing only one-eighth of the codewords of C. In this paper, we prove that the same conclusion holds for any binary quadratic residue codes.     

On the Construction of Some Type II Codes over Z 4×Z4

We consider here the construction of Type II codes over the abelian group Z₄×Z₄. The definition of Type II codes here is based on the definitions introduced by Bannai [2]. The emphasis is given on the construction of these types of codes over the abelian group Z₄×Z₄ and in particular, the methods applied by Gaborit [7] in the construction of codes over Z₄ was extended to four different dualities with their corresponding weight functions (maps assigning weights to the alphabets of the code). In order to do this, we use the flattened form of the codes and construct binary codes analogous to the ones applied to Z₄ codes. Since each duality generates more than one weight function, we focus on those weights satisfying the squareness property. Here, by the squareness property, we mean that the weight function wt assigns the weight 0 to the Z₄×Z₄ elements (0, 0),(2, 2) and the weight 4 to the elements (0, 2) and (2, 0). The main results of this paper are focused on the characterization of these codes and provide a method of construction that can be applied in the generation of such codes whose weight functions satisfy the squareness property.     

On the Minimum Weight of Codes over F5 Constructed from Certain Conference Matrices

In this paper, codes over F₅ with parameters [36, 18, 12], [48, 24, 15], [60, 30, 18], [64, 32, 18] and [76, 38, 21] which improve the previously known bounds on the minimum weight for linear codes over F₅ are constructed from conference matrices. Through shortening and truncating, the above codes give numerous new codes over F₅ which improve the previously known bounds on minimum weights.     

Exact Bounds on the Sizes of Covering Codes

A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c _r(X). Answering a question of Hämäläinen et al. [10], we show further connections between Turán theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n ₀(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}ⁿ. We prove that c _r(B _n(0, r + 2)) = _{1 i r + 1} ( ^{(n + i – 1) / (r + 1) 2}) + n / (r + 1) and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts.     

Small weight codewords in the codes arising from Desarguesian projective planes

We study codewords of small weight in the codes arising from Desarguesian projective planes. We first of all improve the results of K. Chouinard on codewords of small weight in the codes arising from PG(2, p), p prime. Chouinard characterized all the codewords up to weight 2p in these codes. Using a particular basis for this code, described by Moorhouse, we characterize all the codewords of weight up to 2p + (p−1)/2 if p ≥ 11. We then study the codes arising from . In particular, for q ₀ = p prime, p ≥ 7, we prove that the codes have no codewords with weight in the interval [q + 2, 2q − 1]. Finally, for the codes of PG(2, q), q = p ^h , p prime, h ≥ 4, we present a discrete spectrum for the weights of codewords with weights in the interval [q + 2, 2q − 1]. In particular, we exclude all weights in the interval [3q/2, 2q − 1]. Geertrui Van de Voorde research is supported by the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen) Joost Winne was supported by the Fund for Scientific Research - Flanders (Belgium).     

Combinatorial S >n-Modules as Codes

Certain -modules related to the kernels ofincidence maps between types in the poset defined by the natural productorder on the set of n-tuples with entries from {1, ,m} are studied as linear codes (whencoefficients are extended to an arbitrary field K). Theirdimensions and minimal weights are computed. The Specht modules areextremal among these submodules. The minimum weight codewords of theSpecht module are shown to be scalar multiples of polytabloids. Ageneralization of t-design arising from the natural permutationS _n-modules labelled by partitions with mparts is introduced. A connection with Reed-Muller codes is noted and acharacteristic free formulation is presented.     

Greedy posets for the bump-minimizing problem

A bump (x _i,x _i+1) occurs in a linear extension L={x ₁<...n} of a poset P, if x _ii+1 in P. L. is greedy if x _ij for every j>i, whenever (x _i x _i+1) in a bump in L. The purpose of this paper is to give a characterization of all greedy posets. These are the posets for which every greedy linear extension has a minimum number of bumps.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.