Density of constant radius normal binary covering codes Original Research Article

A binary code with covering radius R is a subset image of the hypercube image such that every image is within Hamming distance R of some codeword image, where R is as small as possible. For a fixed coordinate image, define image to be the set of codewords with a b in the ith position. Then image is normal if there exists an image such that for any image, the sum of the Hamming distances from image to image and image is at most image. We newly define what it means for an asymmetric covering code to be normal, and consider the worst-case asymptotic densities image and image 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 image and image, giving evidence that minimum size constant radius covering codes could still be normal.