A covering code is a subset $mathcal{C} subseteq {0,1}^n$ with the property that any $z in {0,1}^n$ is close to some $c in mathcal{C}$ in Hamming distance. For every $epsilon,delta>0$, we show a construction of a family of codes with relative covering radius $delta + epsilon$ and rate $1 - mathrm{H}(delta) $ with block length at most $exp(O((1/epsilon) log (1/epsilon)))$ for every $epsilon > 0$. This improves upon a folklore construction which only guaranteed codes of block length $exp(1/epsilon^2)$. The main idea behind this proof is to find a distribution on codes with relatively small support such that most of these codes have good covering properties.
تحميل البحث