On Lower Bounds For Covering Codes

We study lower bounds on K(n,R), the minimum number of codewords of any binary code of length n such that the Hamming spheres of radius R with center at codewords cover the Hamming space . We generalize Honkala's idea toobtain further improvements only by using some simple observationsof Zhang's result. This leads to nineteen improvements of thelower bound on K(n,R) within the range of .     

Bounds on the Covering Radius of Linear Codes

Asymptotically bounding the covering radius in terms of the dual distance is a well-studied problem. We will combine the polynomial approach with estimates of the distance distribution of codes to derive new results for linear codes.     

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.     

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.     

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

The New Minimum Distance Bounds of Goppa Codes and Their Decoding

A couple of new lower bounds of the minimum distance of Goppa codes is derived, using an extended field code for a Goppa code which contains the Goppa code as its subfield-subcode. Also presented are procedures for both error-only and error-and-erasure decoding for Goppa codes up to the new lower bounds, based on the Berlekamp-Massey algorithm and the Feng-Tzeng multisequence shift-register synthesis algorithms which have been used for decoding cyclic codes up to the BCH and HT(Hartmann-Tzeng) bounds.     

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

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

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.     

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.     

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.     

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.     

Minimum Distance Bounds for s-Regular Codes

A code C F ⁿ is s-regular provided, forevery vertex x F ⁿ, if x is atdistance at most s from C then thenumber of codewords y C at distance ifrom x depends only on i and the distancefrom x to C. If denotesthe covering radius of C and C is -regular,then C is said to be completely regular. SupposeC is a code with minimum distance d,strength t as an orthogonal array, and dual degrees ^*. We prove that d 2t + 1 whenC is completely regular (with the exception of binaryrepetition codes). The same bound holds when C is(t + 1)-regular. For unrestricted codes, we show thatd s ^* + t unless C is a binary repetitioncode.     

New Results on Codes with Covering Radius 1 and Minimum Distance 2

The minimal cardinality of a q-ary code of length n and covering radius at most R is denoted by K_q(n, R); if we have the additional requirement that the minimum distance be at least d, it is denoted by K_q(n, R, d). Obviously, K_q(n, R, d) K_q(n, R). In this paper, we study instances for which K_q(n,1,2) > K_q(n, 1) and, in particular, determine K₄(4,1,2)=28 > 24=K₄(4,1).Supported in part by the Academy of Finland under grant 100500.     

On the Minimum Distances of Non-Binary Cyclic Codes

We deal with the minimum distances of q-ary cyclic codes of length q ^m - 1 generated by products of two distinct minimal polynomials, give a necessary and sufficient condition for the case that the minimum distance is two, show that the minimum distance is at most three if q > 3, and consider also the case q = 3.     

The Two-Point Codes on a Hermitian Curve with the Designed Minimum Distance

This is the second part of the series of papers devoted to the determination of the minimum distance of two-point codes on a Hermitian curve. We study the case where the minimum distance agrees with the designed one. In order to construct a function which gives a codeword with the designed minimum distance, we use functions arising from conics in the projective plane. AMS Classification: 94B27, 14H50, 11T71, 11G20     

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 .     

Minimum Distance Estimation in AR(1)-processes

In this paper a new minimum distance estimator is defined in case that the residuals of an AR(1)-process are contaminated normally distributed. This estimator is asymtotically normally distributed and in most cases less biased than the least square estimator. Furthermore, a method is presented to numerically calculate the minimum distance estimator as a root of an implicit function.     

双圈图的距离无符号拉普拉斯谱半径

连通图$G$的距离无符号拉普拉斯矩阵定义为$\mathcal{Q}(G)=Tr(G)+D(G)$, 其中$Tr(G)$和$D(G)$分别为连通图$G$的点传输矩阵和距离矩阵. 图$G$的距离无符号拉普拉斯矩阵的最大特征值称为$G$的距离无符号拉普拉斯谱半径. 本文确定了给定点数的双圈图中具有最大的距离无符号拉普拉斯谱半径的图.     

Toward the Determination of the Minimum Distance of Two-Point Codes on a Hermitian Curve

This is a first step toward the determination of the parameters of two-point codes on a Hermitian curve. We describe the dimension of such codes and determine the minimum distance of some two-point codes.AMS Classification: 94B27, 14H50, 11T71, 11G20Masaaki Homma - Partially supported by Grant-in-Aid for Scientific Research (15500017), JSPS.Seon Jeong Kim - Partially supported by Korea Research Foundation Grant (KRF-2002-041-C00010).     

图的Laplace谱半径的几类上界

本文得到图的Laplace谱半径的几类上界.通过选取适当的对角矩阵,我们得到了在一定程度上优于其他界的上界.