Binomial Moments of the Distance Distribution and the Probability of Undetected Error

In [1] K. A. S. Abdel-Ghaffar derives a lower bound on the probability of undetected error for unrestricted codes. The proof relies implicitly on the binomial moments of the distance distribution of the code. We use the fact that these moments count the size of subcodes of the code to give a very simple proof of the bound in Abdel by showing that it is essentially equivalent to the Singleton bound. This proof reveals connections of the probability of undetected error to the rank generating function of the code and to related polynomials (Whitney function, Tutte polynomial, and higher weight enumerators). We also discuss some improvements of this bound.Finally, we analyze asymptotics. We show that an upper bound on the undetected error exponent that corresponds to the bound of Abdel improves known bounds on this function.     

The non-existence of Griesmer codes with parameters close to codes of Belov type

Hill and Kolev give a large class of q-ary linear codes meeting the Griesmer bound, which are called codes of Belov type (Hill and Kolev, Chapman Hall/CRC Research Notes in Mathematics 403, pp. 127–152, 1999). In this article, we prove that there are no linear codes meeting the Griesmer bound for values of d close to those for codes of Belov type. So we conclude that the lower bounds of d of codes of Belov type are sharp. We give a large class of length optimal codes with n _q (k, d) = g _q (k, d) + 1.     

Evaluation of the Hamming weights of a class of linear codes based on Gauss sums

Linear codes with a few weights have been widely investigated in recent years. In this paper, we mainly use Gauss sums to represent the Hamming weights of a class of q-ary linear codes under some certain conditions, where q is a power of a prime. The lower bound of its minimum Hamming distance is obtained. In some special cases, we evaluate the weight distributions of the linear codes by semi-primitive Gauss sums and obtain some one-weight, two-weight linear codes. It is quite interesting that we find new optimal codes achieving some bounds on linear codes. The linear codes in this paper can be used in secret sharing schemes, authentication codes and data storage systems.     

On full-rank perfect codes over finite fields

We propose a construction of full-rank q-ary 1-perfect codes. This is a generalization of the construction of full-rank binary 1-perfect codes by Etzion and Vardy (1994). The properties of the i-components of q-ary Hamming codes are investigated, and the construction of full-rank q-ary 1-perfect codes is based on these properties. The switching construction of 1-perfect codes is generalized to the q-ary case. We propose a generalization of the notion of an i-component of a 1-perfect code and introduce the concept of an (i, σ)-component of a q-ary 1-perfect code. We also present a generalization of the Lindström–Schönheim construction of q-ary 1-perfect codes and provide a lower bound for the number of pairwise distinct q-ary 1-perfect codes of length n.     

Kernels and <Emphasis Type="Italic">p</Emphasis>-Kernels of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">r</Emphasis></Superscript>-ary 1-Perfect Codes

The rank of a q-ary code C is the dimension of the subspace spanned by C. The kernel of a q-ary code C of length n can be defined as the set of all translations leaving C invariant. Some relations between the rank and the dimension of the kernel of q-ary 1-perfect codes, over as well as over the prime field , are established. Q-ary 1-perfect codes of length n=(q^m − 1)/(q − 1) with different kernel dimensions using switching constructions are constructed and some upper and lower bounds for the dimension of the kernel, once the rank is given, are established.Communicated by: I.F. Blake     

On Application of the Partition Distance Concept to a Comparative Analysis of Psychological or Sociological Tests

Abstract

We discuss two distance concepts between q-ary n-sequences, 2 ≤ q < n, called partition distances. This distances are metrics in the space of all partitions of a finite n-set. For the metrics, we study codes called q-partition codes and present a construction of these codes based on the first order Reed–Muller codes. A random coding bound is obtained. We also work out an application of q-partition codes to the statistical analysis of psychological or medical tests using questionnaires.     

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.     

Rank metric codes and zeta functions

We define the rank metric zeta function of a code as a generating function of its normalized q-binomial moments. We show that, as in the Hamming case, the zeta function gives a generating function for the weight enumerators of rank metric codes. We further prove a functional equation and derive an upper bound for the minimum distance in terms of the reciprocal roots of the zeta function. Finally, we show invariance under suitable puncturing and shortening operators and study the distribution of zeroes of the zeta function for a family of codes.     

The homogeneous q-difference operator

We introduce a q-differential operator D_xy on functions in two variables which turns out to be suitable for dealing with the homogeneous form of the q-binomial theorem as studied by Andrews, Goldman, and Rota, Roman, Ihrig, and Ismail, et al. The homogeneous versions of the q-binomial theorem and the Cauchy identity are often useful for their specializations of the two parameters. Using this operator, we derive an equivalent form of the Goldman–Rota binomial identity and show that it is a homogeneous generalization of the q-Vandermonde identity. Moreover, the inverse identity of Goldman and Rota also follows from our unified identity. We also obtain the q-Leibniz formula for this operator. In the last section, we introduce the homogeneous Rogers–Szegö polynomials and derive their generating function by using the homogeneous q-shift operator.     

Constructions of partitions of FqN into perfect q-ary codes

Given N = (q ^m − 1)/(q − 1), where q is a power of a prime, q > 2, we present two constructions of different partitions of the set F _q ^N of all q-ary length N vectors into perfect q-ary codes of length N. The lower bounds on the number of these partitions are presented.     

Traceability codes

Traceability codes are combinatorial objects introduced by Chor, Fiat and Naor in 1994 to be used in traitor tracing schemes to protect digital content. A k-traceability code is used in a scheme to trace the origin of digital content under the assumption that no more than k users collude. It is well known that an error correcting code of high minimum distance is a traceability code. When does this ‘error correcting construction’ produce good traceability codes? The paper explores this question.Let ? be a fixed positive integer. When q is a sufficiently large prime power, a suitable Reed-Solomon code may be used to construct a 2-traceability code containing q⌈?/4⌉ codewords. The paper shows that this construction is close to best possible: there exists a constant c, depending only on ?, such that a q-ary 2-traceability code of length ? contains at most cq⌈?/4⌉ codewords. This answers a question of Kabatiansky from 2005.Barg and Kabatiansky (2004) asked whether there exist families of k-traceability codes of rate bounded away from zero when q and k are constants such that q?k². These parameters are of interest since the error correcting construction cannot be used to construct k-traceability codes of constant rate for these parameters: suitable error correcting codes do not exist when q?k² because of the Plotkin bound. Kabatiansky (2004) answered Barg and Kabatiansky's question (positively) in the case when k=2. This result is generalised to the following: whenever k and q are fixed integers such that k?2 and q?k²−⌈k/2⌉+1, or such that k=2 and q=3, there exist infinite families of q-ary k-traceability codes of constant rate.     

Linear codes with covering radius 3

The shortest possible length of a q-ary linear code of covering radius R and codimension r is called the length function and is denoted by ℓ _q (r, R). Constructions of codes with covering radius 3 are here developed, which improve best known upper bounds on ℓ _q (r, 3). General constructions are given and upper bounds on ℓ _q (r, 3) for q = 3, 4, 5, 7 and r ≤ 24 are tabulated.     

All q m -ary Cyclic Codes with Cyclic q-ary Image Are Known

We give a simpler presentation of recent work byLeonard, Séguin and Tang-Soh-Gunawan. Our methodsimply as a new result that even in the repeated-root casethere are no more q ^m -arycyclic codes with cyclic q-ary image than thosegiven by Séguin.     

A lower bound for the minimum weight of the dual 7-ary code of a projective plane of order 49

Existing bounds on the minimum weight d ^⊥ of the dual 7-ary code of a projective plane of order 49 show that this must be in the range 76 ≤ d ^⊥ ≤ 98. We use combinatorial arguments to improve this range to 88 ≤ d ^⊥ ≤ 98, noting that the upper bound can be taken to be 91 if the plane has a Baer subplane, as in the desarguesian case. A brief survey of known results for the minimum weight of the dual codes of finite projective planes is also included. Dedicated to Dan Hughes on the occasion of his 80th birthday.     

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.     

Nonbinary quantum codes derived from finite geometries

The paper gives explicit parameters for several infinite families of q-ary quantum stabilizer codes. These codes are derived from combinatorial designs which arise from finite projective and affine geometries.     

An overpartition analogue of the <Emphasis Type="Italic">q</Emphasis>-binomial coefficients

We define an overpartition analogue of Gaussian polynomials (also known as q-binomial coefficients) as a generating function for the number of overpartitions fitting inside the \(M \times N\) rectangle. We call these new polynomials over Gaussian polynomials or over q-binomial coefficients. We investigate basic properties and applications of over q-binomial coefficients. In particular, via the recurrences and combinatorial interpretations of over q-binomial coefficients, we prove a Rogers–Ramanujan type partition theorem.     

The unsatisfiability threshold revisited

The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper, we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for the occupancy problem in schemes of random allocation of balls into bins in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. In order to obtain this value, we establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients). No such bound was previously known, despite the extensive literature on q-binomial coefficients. Finally, to prove our result we had to establish certain relations among the conditional probabilities of an event in various probabilistic models for random formulas. It turned out that these relations were considerably harder to prove than the corresponding ones for unconditional probabilities, which were previously known.     

Extending MDS Codes

A q-ary (n, k)-MDS code, linear or not, satisfies n ≤ q + k − 1. A code meeting this bound is said to have maximum length. Using purely combinatorial methods we show that an MDS code with n = q + k − 2 can be uniquely extended to a maximum length code if and only if q is even. This result is best possible in the sense that there is, for example, a non-extendable 4-ary (5, 4)-MDS code. It may be that the proof of our result is as interesting as the result itself. We provide a simple necessary and sufficient condition for code extendability. In future work, this condition might be suitably modified to give an extendability condition for arbitrary (shorter) MDS codes.Received December 1, 2003     

Bounds on the sizes of constant weight covering codes

Motivated by applications in universal data compression algorithms we study the problem of bounds on the sizes of constant weight covering codes. We are concerned with the minimal sizes of codes of lengthn and constant weightu such that every word of lengthn and weightv is within Hamming distanced from a codeword. In addition to a brief summary of part of the relevant literature, we also give new results on upper and lower bounds to these sizes. We pay particular attention to the asymptotic covering density of these codes. We include tables of the bounds on the sizes of these codes both for small values ofn and for the asymptotic behavior. A comparison with techniques for attaining bounds for packing codes is also given. Some new combinatorial questions are also arising from the techniques.Part of this work was done while the first and third authors were visiting Bellcore. The third author was supported in part by National Science Foundation under grant NCR-8905052. Part of this work was presented in the Coding and Quantization Workshop at Rutgers University, NJ, October 1992.