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     

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.     

Dominating sets with small clique covering number

Motivated by earlier work on dominating cliques, we show that if a graph G is connected and contains no induced subgraph isomorphic to P₆ or H_t (the graph obtained by subdividing each edge of K_1,t, t ≥ 3, by exactly one vertex), then G has a dominating set which induces a connected graph with clique covering number at most t − 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 101–105, 1997     

Switching of covering codes

Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length $n\ge 3$, the semiautomorphisms are exactly the bijections that preserve the set of $r$-balls for each radius $r$. Switching of optimal codes of size at most 7 and of codes attaining $K(8,1)=32$ is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes.     

The covering radius of extreme binary 2-surjective codes

The covering radius of binary 2-surjective codes of maximum length is studied in the paper. It is shown that any binary 2-surjective code of M codewords and of length has covering radius if M − 1 is a power of 2, otherwise . Two different combinatorial proofs of this assertion were found by the author. The first proof, which is written in the paper, is based on an existence theorem for k-uniform hypergraphs where the degrees of its vertices are limited by a given upper bound. The second proof, which is omitted for the sake of conciseness, is based on Baranyai’s theorem on l-factorization of a complete k-uniform hypergraph.      

Hyper-bent functions and cyclic codes

Bent functions are those Boolean functions whose Hamming distance to the Reed-Muller code of order 1 equal 2^n-1-2^n/2-1 (where the number n of variables is even). These combinatorial objects, with fascinating properties, are rare. Few constructions are known, and it is difficult to know whether the bent functions they produce are peculiar or not, since no way of generating at random bent functions on 8 variables or more is known.The class of bent functions contains a subclass of functions whose properties are still stronger and whose elements are still rarer. Youssef and Gong have proved the existence of such hyper-bent functions, for every even n. We prove that the hyper-bent functions they exhibit are exactly those elements of the well-known PS_ap class, introduced by Dillon, up to the linear transformations x?δx, . Hyper-bent functions seem still more difficult to generate at random than bent functions; however, by showing that they all can be obtained from some codewords of an extended cyclic code H_n with small dimension, we can enumerate them for up to 10 variables. We study the non-zeroes of H_n and we deduce that the algebraic degree of hyper-bent functions is n/2. We also prove that the functions of class PS_ap are some codewords of weight 2^n-1-2^n/2-1 of a subcode of H_n and we deduce that for some n, depending on the factorization of 2ⁿ-1, the only hyper-bent functions on n variables are the elements of the class , obtained from PS_ap by composing the functions by the transformations x?δx, δ≠0, and by adding constant functions. We prove that non- hyper-bent functions exist for n=4, but it is not clear whether they exist for greater n. We also construct potentially new bent functions for n=12.     

A class of generalized cyclic codes

1. IntroductionPrange was considered to be first person to study cyclic codes at the end of 1950s, seeIll and [2]. Since then, cyclic codes are the mostly studied of all codes, because they are easyto encode, and include an important family of BCH codes. A code C is cyclic if it is linearand if any cyclic shift of a codeword is also a codeword, i.e., whenever (co, of,' 1 on--l ) is inC then so is (c.--1, co j', c.--2). In fact, one could define a cyclic code to be an ideal in thering of…     

Dominated error correcting codes with distance two

We study the hamiltonicity of certain graphs obtained from the hypercube as a means of producing a binary code of distance two and length n, whose codewords are ordered so that for each two consecutive codewords, one dominates the other. One vector dominates the other, if and only if, in all the positions where one of them has a zero, the other has a zero too. These dominated codes have applications in group testing for consecutive defectives. We also determine when the vectors can be ordered so that every two consecutive vectors have the domination property, and are at distance two; this is a natural generalization of Gray codes. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 294–302, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10012     

Extremal self-dual codes of length 64 through neighbors and covering radii

We construct extremal singly even self-dual [64,32,12] codes with weight enumerators which were not known to be attainable. In particular, we find some codes whose shadows have minimum weight 12. By considering their doubly even neighbors, extremal doubly even self-dual [64,32,12] codes with covering radius 12 are constructed for the first time.     

On a class of binary linear completely transitive codes with arbitrary covering radius

An infinite class of new binary linear completely transitive (and so, completely regular) codes is given. The covering radius of these codes is growing with the length of the code. In particular, for any integer ρ≥2, there exist two codes in the constructed class with d=3, covering radius ρ and lengths and , respectively. The corresponding distance-transitive graphs, which can be defined as coset graphs of these completely transitive codes are described.     

一类Z2k-线性的二元码

我们记Tk为Galois环GR（2^k,m)到Z2^k的迹映射，ξ是GR（2^k,m)中的本原元，ξ2^m-1=1,ιk,m={0,1,ξ，…，ξ2^m-2}，来讨论一类Z2^k-线性码{Tk(a0x 2^k-2a1x^3 2^k-1,a2x^5) b|a0∈GR(2^k,m),a1∈ιk,m 2ιk,m,a2∈ιk,m,b∈Z2^k}x∈ιk的广义Gray映射下的象所构成的二元码，这类二元码也具有很好的参数性质，优于一些已知的二元码，例如广义的Kerdock码或广义的Delsarte-Goethals码。     

Bounds for short covering codes and reactive tabu search

Given a prime power q, c_q(n,R) denotes the minimum cardinality of a subset H in such that every word in this space differs in at most R coordinates from a multiple of a vector in H. In this work, two new classes of short coverings are established. As an application, a new optimal record-breaking result on the classical covering code is obtained by using short covering. We also reformulate the numbers c_q(n,R) in terms of dominating set on graphs. Departing from this reformulation, the reactive tabu search (a variation of tabu search heuristics) is developed to obtain new upper bounds on c_q(n,R). The algorithm is described and conclusions on the results are drawn; they identify the advantages of using the reactive mechanism for this problem. Tables of lower and upper bounds on c_q(n,R), q=3,4, n≤7, and R≤3, are also presented.     

Locality of optimal binary codes

The locality of locally repairable codes (LRCs) for a distributed storage system is the number of nodes that participate in the repair of failed nodes, which characterizes the repair cost. In this paper, we first determine the locality of MacDonald codes, then propose three constructions of LRCs with $r=1,2\text{ and }3$. Based on these results, for $2\le k\le 7$ and $n\ge k+2$, we give an optimal linear $[n,k,d]$ code with small locality. The distance optimality of these linear codes can be judged by the codetable of M. Grassl for $n<2(2^k-1)$ and by the Griesmer bound for $n\ge 2(2^k-1)$. Almost all the $[n,k,d]$ codes ($2\le k\le 7$) have locality $r\le 3$ except for the three codes, and most of the $[n,k,d]$ code with $n<2(2^k-1)$ achieves the Cadambe–Mazumdar bound for LRCs.     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

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.     

Further results on the covering radius of small codes

The minimum number of codewords in a code with t ternary and b binary coordinates and covering radius R is denoted by K(t,b,R). In the paper, necessary and sufficient conditions for K(t,b,R)=M are given for M=6 and 7 by proving that there exist exactly three families of optimal codes with six codewords and two families of optimal codes with seven codewords. The cases M?5 were settled in an earlier study by the same authors. For binary codes, it is proved that K(0,2b+4,b)?9 for b?1. For ternary codes, it is shown that K(3t+2,0,2t)=9 for t?2. New upper bounds obtained include K(3t+4,0,2t)?36 for t?2. Thus, we have K(13,0,6)?36 (instead of 45, the previous best known upper bound).     

有限域上长为2mpn 的负循环码

设F_q 是奇数阶有限域. 本文主要借助X^2mpn+1 在F_q 上的不可约因式分解来确定有限域F_q上所有长为2^mpⁿ 的负循环码和自对偶的负循环码的生成多项式, 这里p 是q-1 的奇素因子, m 和n是正整数.     

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