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.     

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.     

张量积码的多重覆盖半径

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

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.     

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.     

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.     

A New Table of Binary/Ternary Mixed Covering Codes

A table of upper bounds for K3,2(n1,n2;R), the minimum number of codewords in a covering code with n1 ternary coordinates, n2 binary coordinates, and covering radius R, in the range n = n1 + n2 13, R 3, is presented. Explicit constructions of codes are given to prove the new bounds and verify old bounds. These binary/ternary covering codes can be used as systems for the football pool game. The results include a new binary code with covering radius 1 proving K2(13,1) 736, and the following upper bound for the football pool problem for 9 matches: K3(9,1) 1356.     

Classification of binary covering codes

The minimum size of a binary covering code of length n and covering radius r is denoted by K (n, r) and corresponding codes are called optimal. In this article a classification up to equivalence of all optimal covering codes having either length at most 8 or cardinality at most 4 is completed. Moreover, we prove that K (9, 2) = 16. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 391–401, 2000     

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.     

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.     

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.     

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.     

Optimal binary covering codes of length 2j

The minimum size of a binary covering code of length n and covering radius r is denoted by K(n,r), and codes of this length are called optimal. For j > 0 and n = 2^j, it is known that K(n,1) = 2 · K(n?1,1) = 2^{n ? j}. Say that two binary words of length n form a duo if the Hamming distance between them is 1 or 2. In this paper, it is shown that each optimal binary covering code of length n = 2^j, j > 0, and covering radius 1 is the union of duos in just one way, and that the closed neighborhoods of the duos form a tiling of the set of binary words of length n. Methods of constructing such optimal codes from optimal covering codes of length n ? 1 (that is, perfect single‐error‐correcting codes) are discussed. The paper ends with the construction of an optimal covering code of length 16 that does not contain an extension of any optimal covering code of length 15. © 2005 Wiley Periodicals, Inc. J Combin Designs     

统计学在人类基因组计划研究中的应用

首先介绍了生命信息遗传的一些基本概念 ,如细胞、染色体、密码子等 .同时 ,也简单介绍了人类基因组计划 .然后 ,给出了统计方法在人类基因组研究计划中应用的四个例子     

Generalized covering designs and clique coverings

Inspired by the “generalized t‐designs” defined by Cameron [P. J. Cameron, Discrete Math 309 (2009), 4835–4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimum sizes of these designs, and describe some methods of constructing them, which in some cases we prove are optimal. Many of our results are obtained from an interpretation of these designs in terms of clique coverings of graphs. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:378‐406, 2011     

New Codes via the Lengthening of BCH Codes with UEP Codes

We describe a code lengthening technique that uses unequal error protection codes as suffix codes and combine it with iteration of the conventional Construction X. By applying this technique to BCH codes, we obtain five new binary codes, 13 new ternary codes, and 13 new quarternary codes. An improvement of Construction XX yields two new ternary codes.     

On optimal superimposed codes

A (w,r) cover‐free family is a family of subsets of a finite set such that no intersection of w members of the family is covered by a union of r others. A binary (w,r) superimposed code is the incidence matrix of such a family. Such a family also arises in cryptography as a concept of key distribution patterns. In this paper, we develop a method of constructing superimposed codes and prove that some superimposed codes constructed in this way are optimal. © 2003 Wiley Periodicals, Inc. J Combin Designs 12: 79–71, 2004.     

Construction of some new quantum MDS codes

Quantum maximum-distance-separable (MDS) codes are an important class of quantum codes. In this paper, we mainly apply a new method of classical Hermitian self-orthogonal codes to construct three classes of new quantum MDS codes, and these quantum MDS codes provide large minimum distance.     

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.