Minimum number of strings to cover entire space within Hamming distance
-
05-11-2019 - |
سؤال
Given $(n, k)$:
- What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?
- Is there an asymptotic expansion or lower bound, at least?
- A somewhat-trivial lower bound is as follows:
- There's $\sum_{i=0}^{k} {n \choose i}$ strings within distance $k$ of a given string.
- There's $2^{n}$ strings total.
- Each string can be counted no less than once.
- So we have a lower bound of: $$x \ge \frac{2^{n}}{\sum_{i=0}^{k} {n \choose i}}$$
- Is there an explicit formula that maps an index $1..k$ (or $0..(k-1)$) to these strings? (I am aware that this is likely not unique.)
This is closely related to error-correcting codes, but ultimately distinct. (In an error correcting code you (usually) want to have every string within distance $k$ (or $k/2$, etc, etc) of no more than one codeword, whereas here you want to have every string within distance $k$ of at least one codeword.)
لا يوجد حل صحيح
لا تنتمي إلى cs.stackexchange