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

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.     

On the Distance Distributions of BCH Codes and Their Duals

Based on new bounds on the values of Krawtchoukpolynomials, we improve earlier known estimates forcomponents of the distance distributions of BCH codes and theirduals. Moreover, we show that if one uses estimates on Krawtchoukpolynomials for bounding the error term in the binomial approximationto the distance distribution of BCH codes, the given results are actuallythe best possible. One of the advantages of the proposed approach isthat it provides estimates with no restrictions on the minimumdistance of the code.     

Hypercubic 4 and 5-Designs from Double-Error-Correcting BCH Codes

An ordered orthogonal array OOA(, k, n) is a binary 2 ^k × n matrix with the property that for each complete -set of columns, each possible -tuple occurs in exactly 2 ^k– rows of those columns (for definition of a complete -set, see below). Constructions of OOA(, k, n) for = 4 and = 5 are given.     

The Automorphism Groups of BCH Codes and of Some Affine-Invariant Codes Over Extension Fields

Affine-invariant codes are extended cyclic codes of length p ^m invariant under the affine-group acting on . This class of codes includes codes of great interest such as extended narrow-sense BCH codes. In recent papers, we classified the automorphism groups of affine-invariant codes berg, bech1. We derive here new results, especially when the alphabet field is an extension field, by expanding our previous tools. In particular we complete our results on BCH codes, giving the automorphism groups of extended narrow-sense BCH codes defined over any extension field.     

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.     

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

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

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

关于设计距离为7的BCH码的非循环等价类

利用Mobius公式给出了设计距离为7的二元BCH码的非循环等价类的精确计数．     

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.     

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.     

Fast parallel decoding of double-error-correcting binary BCH codes

This paper presents a new high speed parallel decoding algorithm for double-error-correcting binary BCH 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.     

The Theory of Cyclic Codes and a Generalization to Additive Codes

We present a new approach to the theory of cyclic and constacyclic codes and generalize the theory to cover the family of additive (not necessarily linear) cyclic codes. The approach is based on the action of the Galois group (cyclotomic cosets). The conventional representation of cyclic codes as ideals in a factor ring of the polynomial ring is not needed.     

New Quaternary Linear Codes with Covering Radius 2

A new quaternary linear code of length 19, codimension 5, and covering radius 2 is found in a computer search using tabu search, a local search heuristic. Starting from this code, which has some useful partitioning properties, different lengthening constructions are applied to get an infinite family of new, record-breaking quaternary codes of covering radius 2 and odd codimension. An algebraic construction of covering codes over alphabets of even characteristic is also given.     

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.