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$ ?

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

3 Asked on February 21, 2021 by always-newbie

1 Asked on February 20, 2021 by saku

1 Asked on February 20, 2021 by rossko_dca

1 Asked on February 17, 2021 by donvitomarco

0 Asked on February 16, 2021 by von-spotz

0 Asked on February 13, 2021 by adam-cole

a star search algorithms euclidean distance graphs shortest path

1 Asked on February 13, 2021 by aviv-barel

5 Asked on February 10, 2021 by gizmo

0 Asked on February 10, 2021 by arthur-b

1 Asked on February 8, 2021 by keith-paton

1 Asked on February 7, 2021 by user3661613

1 Asked on February 6, 2021 by builderthebob00

0 Asked on February 5, 2021 by pookie

1 Asked on February 4, 2021 by retsek680

1 Asked on February 3, 2021 by stark2022

0 Asked on February 1, 2021 by david-grnberger

0 Asked on January 30, 2021 by tzlil

0 Asked on January 29, 2021 by angelic-demonic

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?

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