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.     

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.     

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.     

Asymmetric Binary Covering Codes

An asymmetric binary covering code of length n and radius R is a subset of the n-cube Q_n such that every vector xQ_n can be obtained from some vector c by changing at most R 1's of c to 0's, where R is as small as possible. K⁺(n,R) is defined as the smallest size of such a code. We show K⁺(n,R)Θ(2ⁿ/n^R) for constant R, using an asymmetric sphere-covering bound and probabilistic methods. We show K⁺(n,n− )= +1 for constant coradius iff n ( +1)/2. These two results are extended to near-constant R and , respectively. Various bounds on K⁺ are given in terms of the total number of 0's or 1's in a minimal code. The dimension of a minimal asymmetric linear binary code ([n,R]⁺-code) is determined to be min{0,n−R}. We conclude by discussing open problems and techniques to compute explicit values for K⁺, giving a table of best-known bounds.     

On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes

We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by generalizing a method due to S. Litsyn and A. Tietäväinen lt:newu and combining it with a new upper bound on the asymptotic information rate of non-binary codes. The upper bound on the information rate is an application of a shortening method of a code and is an analogue of the Shannon-Gallager-Berlekamp straight line bound on error probability. These results improve on the best presently known asymptotic upper bounds on minimum distance and covering radius of non-binary codes in certain intervals.     

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.     

New Constructions of Covering Codes

Coveringcode constructions obtaining new codes from starting ones weredeveloped during last years. In this work we propose new constructionsof such kind. New linear and nonlinear covering codes and aninfinite families of those are obtained with the help of constructionsproposed. A table of new upper bounds on the length functionis given.     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

The Length of Primitive BCH Codes with Minimal Covering Radius

It is proved that the covering radius of a primitive binary BCH code of length q-1 and designed distance 2t+1, where is exactly 2t-1 (the minimum value possible). The bound for q is significantly lower than the one obtained by O. Moreno and C. J. Moreno [9].     

Constructing Covering Codes with Given Automorphisms

Let K(n,r) denote the minimum cardinality of a binary covering code of length n and covering radius r. Constructions of covering codes give upper bounds on K(n,r). It is here shown how computer searches for covering codes can be sped up by requiring that the code has a given (not necessarily full) automorphism group. Tabu search is used to find orbits of words that lead to a covering. In particular, a code D found which proves K(13,1) 704, a new record. A direct construction of D given, and its full automorphism group is shown to be the general linear group GL(3,3). It is proved that D is a perfect dominating set (each word not in D is covered by exactly one word in D) and is a counterexample to the recent Uniformity Conjecture of Weichsel.     

The Covering Radius of Ternary Cyclic Codes with Length up to 25

The covering radius of all ternary cyclic codes of length up to 25 is given. Some of the results were obtained by computer and for others mathematical reasonings were applied. The minimal distances of all codes were recalculated.     

Singleton Bounds for Codes over Finite Rings

We introduce the Singleton bounds for codes over a finite commutative quasi-Frobenius ring.     

Some Results on NQR Codes

In [5] Tiu and Wallace have constructed a new class of linear codes called Norm Quadratic Residue code C _p for p> a prime of the form 4n+1 and determined some of its properties. It was shown that C _p p. He further conjectured that C _p = p. In the present correspondence we show that similar construction works for primes of the form 4n-1. We further show that dim C _p = p for any odd prime p and determine few elementary properties of these codes.     

一族Bloch函数的单叶半径与覆盖半径

研究了Bloch函数族B中的一个子族Bg,给出了Bg中函数的单叶半径.作为应用建立了Bg中函数的覆盖定理,从而刻画了Bg中函数的有关性质.     

Lower Bounds for Covering Problems

In this paper we present an (nlogn) lower bound proof for several covering problems including the optimal line bipartition problem, min-max covering by two axis parallel rectangles, discrete and continuous two-center problems, two-line center problem, etc. Our proofs are based on using the rotational reduce technique and well-known lower bound for the maximal gap problem.     

Meeting the Welch and Karystinos-Pados Bounds on DS-CDMA Binary Signature Sets

The Welch lower bound on the total-squared-correlation (TSC) of binary signature sets is loose for binary signature sets whose length L is not a multiple of 4. Recently Karystinos and Pados [6,7] developed new bounds that are better than the Welch bound in those cases, and showed how to achieve the bounds with modified Hadamard matrices except in a couple of cases. In this paper, we study the open cases.     

带有仲裁认证码的组合论下界

本文给出了带有仲裁认证码的组合论下界,并利用带有约束的t-设计,给出了敌方的r阶欺骗攻击成功的概率达到下界的带有仲裁认证码的组合结构。     

Asymptotic Bounds for General Covering Designs

Given five positive integers and t where and a t‐ general covering design is a pair where X is a set of n elements (called points) and a multiset of k‐subsets of X (called blocks) such that every p‐subset of X intersects at least λ blocks of in at least t points. In this article we continue the work carried out by Etzion, Wei, and Zhang [Des. Codes Cryptogr. 5 (1995), 217–239] on the asymptotic covering density of general covering designs. We will present combinatorial constructions leading to new upper bounds on the asymptotic covering density of 4‐(n, 4, 6, 1) general covering designs and 4‐ general covering designs with . The new bound on the asymptotic covering density of 4‐(n, 4, 6, 1) general covering designs is equivalent to a new lower bound for the Turán density .     

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).     

On Reed-Solomon Codes

The complexity of decoding the standard Reed-Solomon code is a well-known open problem in coding theory. The main problem is to compute the error distance of a received word. Using the Weil bound for character sum estimate, Li and Wan showed that the error distance can be determined when the degree of the received word as a polynomial is small. In the first part, the result of Li and Wan is improved. On the other hand, one of the important parameters of an error-correcting code is the dimension. In most cases, one can only get bounds for the dimension. In the second part, a formula for the dimension of the generalized trace Reed-Solomon codes in some cases is obtained.