Some new upper bounds on the covering radius of binary linear codes

A Griesmer-like upper bound on the covering radius, R, is given. To the author's knowledge this is the only upper bound which explicitly depends on all three parameters n, k, and d. An upper bound on R for cyclic codes is then given which depends on the generator polynomial of the cyclic code and which, in many cases, leads to an improvement of the previous bound. An upper bound on the irreducible generator polynomial cyclic codes is also given. New interpretations and applications of the so-called Norse bounds and necessary and sufficient conditions to attain one of these bounds are provided. Generalizations of most of the results for codes over GF(q) are outlined     

On the covering radius of codes

The covering radiusRof a code is the maximal distance of any vector from the code. This work gives a number of new results concerningt[n, k], the minimal covering radius of any binary code of lengthnand dimensionk. For examplet[n, 4]andt[n, 5]are determined exactly, and reasonably tight bounds ont[n, k]are obtained for anykwhennis large. These results are found by using several new constructions for codes with small covering radius. One construction, the amalgamated direct sum, involves a quantity called the norm of a code. Codes with normleq 2 R + 1are called normal, and may be combined efficiently. The paper concludes with a table giving bounds ont[n, k]forn leq 64.     

Further results on the covering radius of codes

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) leq K(n, R)holds for sufficiently largen.     

New lower bounds for covering codes

Some new lower bounds on |C| for a binary linear [n, k]R code C with n+1=t(R +1)-r(0⩽r<R+1, t>2 odd) or with n+1=t(R+1)-1(t>2 even) are obtained. These bounds improve the sphere covering bound considerably and give several new values and lower bounds for the function t[n, k], the smallest covering radius of any [n, k] code     

Lower bounds for binary covering codes

G.D. Chen et al. (ibid., vol.IT-32, p.680-94, 1986) presented two new lower bounds for K(n,R), where K(n,R) denotes the minimum cardinality of a binary code of length n and covering radius R. The author shows that a slight modification gives further improvements and some examples are given to confirm the argument. Codes that have a certain partitioning property are considered     

Short codes with a given covering radius

The covering radius r of a code is the maximum distance from any vector in the space containing the code to the nearest codeword. The authors introduce a new function l(m,r), called the length function, which equals the smallest length of a binary code of codimension m and covering radius r. They investigate basic properties of the length function. Projective geometries over larger fields are used to construct families of codes which improve significantly the upper bound for l(m,2) obtained by amalgamation of Hamming codes. General methods are developed for ruling out the existence of codes of covering radius 2 with a given codimension and length resulting in lower bounds for l(m,2). A table is presented which gives the best results now known for l(m,r) with m⩽12 and r⩽12     

Improved upper bounds on sizes of codes

Let A(n,d) denote the maximum possible number of codewords in a binary code of length n and minimum Hamming distance d. For large values of n, the best known upper bound, for fixed d, is the Johnson bound. We give a new upper bound which is at least as good as the Johnson bound for all values of n and d, and for each d there are infinitely many values of n for which the new bound is better than the Johnson bound. For small values of n and d, the best known method to obtain upper bounds on A(n,d) is linear programming. We give new inequalities for the linear programming and show that with these new inequalities some of the known bounds on A(n,d) for n⩽28 are improved     

On the covering radius of binary codes (Corresp.)

Upper bounds on the covering radius of binary codes are studied. In particular it is shown that the covering radiusr_{m}of the first-order Reed-Muller code of lenglh2^{m}satisfies2^{m-l}-2^{lceil m/2 rceil -1} r_{m} leq 2^{m-1}-2^{m/2-1}.     

Divisibility properties for covering radius of certain cyclic codes

We are presenting a new method to obtain the covering radius of codes and in particular to prove quasi-perfection in codes. Our techniques combine divisibility results of Ax-Katz and Moreno-Moreno as well as coding theoretic methods. We answer a problem posed by Cohen-Honkala-Litsyn-Lobstein in the book covering radius for Bose-Chaudhuri-Hocquenghem (BCH) codes. We also obtain the covering radius for many new classes of codes.     

New covering radius of Reed-Muller codes for t-resilient functions

In this paper, we introduce a new covering radius of RM(r,n) from cryptography viewpoint. It is defined as the maximum distance between t-resilient functions and the rth order Reed-Muller code RM(r,n). We next derive its lower and upper bounds. We further present a table of numerical data of our bounds.     

Bounds for abnormal binary codes with covering radius one

The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K(n,R). It is assumed that C is an (n,M)R code, that is, a binary code of length n with M codewords and covering radius R. It is shown that if C is an (n,M)1 code, then it is easy to find a normal (n ,M)1 code by changing C in a suitable way, and that all the optimal (n,M)1 codes (i.e. those for which M=K(n,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n,M) code, then n⩾9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n,M)1 code is abnormal, then M⩾96     

Improved asymptotic bounds for error-correcting codes

The author has previously developed a new upper bound on nonsystematic binary error-correcting codes, using a sphere-packing approach and combinatorial analysis. A significant refinement is now added; together with a detailed study of the asymptotic behavior of the upper bound, this enables one to show that any large code must {em correct} almost all sequences with a larger number of errors than the code was designed for. This excess is expressed numerically as a fraction of the designed error-correcting capability of the code. The fraction is a function of the ratio of the sequence length and the designed error-correcting capability. A possible application might be in the use of a larger code giving almost certain error correction rather than a smaller one with certain correction capability.     

Improved tangential sphere bound on the bit-error probability ofconcatenated codes

The tangential sphere bound (TSB) of Poltyrev (1994) is a tight upper bound on the word error probability P_w of linear codes with maximum likelihood decoding and is based on the code's distance spectrum. An extension of the TSB to a bound on the bit-error probability P_b is given by Sason/Shitz (see IEEE Trans. Inform. Theory, vol.46, p.24-47, 2000). We improve the tangential sphere bound on P_b and apply the new method to some examples. Our comparison to other bounds as well as to simulation results shows an improved tightness, particularly for signal-to-noise ratios below the value corresponding to the computational cutoff rate R_o     

On the least covering radius of binary linear codes with small lengths

Using classification of codes with a certain covering radius it is proved that the least covering radius t[17,6]=5; t[17,8]=4; t[18,7]=5; t[19,7]=5; t[20,8]=5; and t[21,7]=6. As a corollary, four improvements on the length function l(m,R) are found. It is also shown that there exists a unique[14,6] code with covering radius 3.     

On the structure of linear codes with covering radius two and three

We obtain new bounds on l(m,r), the minimum length of a linear code with codimension m and covering radius r. All bounds are derived in a uniform way. We employ results from coding theory, some earlier results on covering codes, and combinatorial arguments. We prove the following bounds: l(6, 2)=13, l(7,2)=19, l(8,2)⩾25, l(9,2)⩾34, l(2m-l,2)⩾2^m+1 for m⩾3, l(14,2)⩾182, l(16,2)⩾363, l(18,2)⩾725, l(20,2)⩾1449, l(22,2)⩾2897, l(24,2)⩾5794, l(9,3)⩾17, l(10,3)⩾21, l(12,3)⩾31, l(13,3)⩾38     

Improved bounds for the rate loss of multiresolution source codes

We present new bounds for the rate loss of multiresolution source codes (MRSCs). Considering an M-resolution code, the rate loss at the ith resolution with distortion D/sub i/ is defined as L/sub i/=R/sub i/-R(D/sub i/), where R/sub i/ is the rate achievable by the MRSC at stage i. This rate loss describes the performance degradation of the MRSC compared to the best single-resolution code with the same distortion. For two-resolution source codes, there are three scenarios of particular interest: (i) when both resolutions are equally important; (ii) when the rate loss at the first resolution is 0 (L/sub 1/=0); (iii) when the rate loss at the second resolution is 0 (L/sub 2/=0). The work of Lastras and Berger (see ibid., vol.47, p.918-26, Mar. 2001) gives constant upper bounds for the rate loss of an arbitrary memoryless source in scenarios (i) and (ii) and an asymptotic bound for scenario (iii) as D/sub 2/ approaches 0. We focus on the squared error distortion measure and (a) prove that for scenario (iii) L/sub 1/<1.1610 for all D/sub 2/相似文献   

Lower bounds for q-ary covering codes

The authors prove combinatorial lower bounds for K_q (n,R), the minimal cardinality of any q-ary code of length n and covering radius R. Tables of lower bounds for K_q(n,R) are presented for q=3, 4, 5     

Some 3-error-correcting BCH codes have covering radius 5 (Corresp.)

The coset leader of greatest weight in the 3-error-correcting BCH code of length2^{m}-1has weight 5, for oddm geq 5.     

The covering radius of cyclic codes of length up to 31 (Corresp.)

The covering radius is given for all binary cyclic codes of length less than or equal to31. Many of these codes are optimal in the sense of having the smallest possible covering radius of any linear code of that length and dimension.     

Improved upper bounds on the ensemble performance of ML decoded lowdensity parity check codes

In this letter, we study improved upper bounds on the performance of low density parity check codes over binary-input additive white Gaussian noise channels, assuming that the codes are maximum-likelihood decoded. The results demonstrate the phenomenal performance of the low density parity check codes