Upper bound on size of minimal binary coverage code

Computer Science Asked by dohmatob on December 7, 2020

Let $1 le r le n$ b e integer(with $n$ large) and let $mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $mathscr X_n$ such that every $x in mathscr X_n$ is within Hamming distance $le r$ of some $y in S$. A minimal $r$-coverage code is one for which the cardinality $|S|$ is minimal. Let this minimal cardinality be $N_n(r)$. Note that we have the trivial bound $N_n(r) le 2^n$.

Question. What are good upper-bounds for $N_n(r)$ in terms of $N$ and $r$ ?

One Answer

So, according to Theorem 4.3 of this monograph by Réné Struik, if we consider $q$-ary binary codes of length $n$, such that $n to infty$ with $r/n to p in [0,(q-1)/q]$, then the minimal code size has the following asymptotic limit $$ (1/n)log_q N_{n,q}(r) to 1-H_q(p), $$ where $H_q(p)$ is the $q$-ary entropy of $p$. This answers my specific problem which corresponds to $q=2$.

Answered by dohmatob on December 7, 2020

Add your own answers!

Related Questions

How to generate graphs with a Hamiltonian path?

3  Asked on February 21, 2021 by always-newbie


Wifi throughput calculation

1  Asked on February 20, 2021 by copsa


Thirty-one game. Prediction of the winner

1  Asked on February 17, 2021 by donvitomarco


speed of preorder traversal

1  Asked on February 8, 2021 by keith-paton


Mergesort and some claims on comparison

1  Asked on February 7, 2021 by user3661613


Proving the language of non-primes is in NP

1  Asked on February 6, 2021 by builderthebob00


Longest path on a full tree

1  Asked on January 27, 2021 by bm1125


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir