Density of normal binary covering codes
| dc.creator | Ellis, Robert B. | |
| dc.date | 2004-09-09 | |
| dc.date.accessioned | 2026-07-07T05:12:00Z | |
| dc.date.available | 2026-07-07T05:12:00Z | |
| dc.description | 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 $ν^*(R)$ and $ν^*_+(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. | |
| dc.description | 15 pages | |
| dc.identifier | https://arxiv.org/abs/math/0409171 | |
| dc.identifier | http://arxiv.org/abs/math/0409171 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72435 | |
| dc.subject | Combinatorics | |
| dc.subject | 94B75 (Primary) 05D40 (Secondary) | |
| dc.title | Density of normal binary covering codes | |
| dc.type | text |