# Minimum number of strings to cover entire space within Hamming distance

Given $(n, k)$:

1. 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}}$$
2. 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.)