Mathematics – Combinatorics
Scientific paper
2004-09-09
Mathematics
Combinatorics
15 pages
Scientific paper
A binary code with covering radius $R$ is a subset $C$ of the hypercube $Q_n=\{0,1\}^n$ such that every $x\in Q_n$ is within Hamming distance $R$ of some codeword $c\in C$, where $R$ is as small as possible. For a fixed coordinate $i\in[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\in[n]$ such that for any $v\in Q_n$, the sum of the Hamming distances from $v$ to $C(0,i)$ and $C(1,i)$ is at most $2R+1$. We newly define what it means for an asymmetric covering code to be normal, and consider the worst case asymptotic densities $\nu^*(R)$ and $\nu^*_+(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\log R + \log R + \log\log R+4)$, giving evidence that minimum size constant radius covering codes could still be normal.
No associations
LandOfFree
Density of normal binary covering codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Density of normal binary covering codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Density of normal binary covering codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-245560