Density of constant radius normal binary covering codes

DOI10.1016/J.DISC.2007.08.042MaRDI QIDQ941385zbMATH OpenOpenAlexFDO

Publication date 4 September 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0409171

covering radius probabilistic methods asymmetric covering code normal covering code

Combinatorial aspects of packing and covering (05B40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: A binary code with covering radius

R

is a subset

C

of the hypercube

Q_{n} = {0, 1}^{n}

such that every

x i n Q_{n}

is within Hamming distance

R

of some codeword

c i n C

, where

R

is as small as possible. For a fixed coordinate

i i n [n]

, define

C (b, i)

, for

b = 0, 1

, to be the set of codewords with a

b

in the

i

th position. Then

C

is normal if there exists an

i i n [n]

such that for any

v i n Q_{n}

, the sum of the Hamming distances from

v

to

C (0, i)

and

C (1, i)

is at most

2 R + 1

. We newly define what it means for an asymmetric covering code to be normal, and consider the worst case asymptotic densities

u^{*} (R)

and

u_{+}^{*} (R)

of constant radius

R

symmetric and asymmetric normal covering codes, respectively. Using a probabilistic deletion method, and analysis adapted from previous work by Krivelevich, Sudakov, and Vu, we show that both are bounded above by

e (R l o g R + l o g R + l o g l o g R + 4)

, giving evidence that minimum size constant radius covering codes could still be normal.

Recommendations

Cites work

This page was built for publication: Density of constant radius normal binary covering codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q941385)