# 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!

### Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP