2
$\begingroup$

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.)

$\endgroup$
3
$\begingroup$

The object you are interested in is called a covering code. While less popular than error-correcting codes, covering codes share many of the same difficulties. In particular, there is little hope for an exact formula for the minimal size of a covering code.

$\endgroup$
  • $\begingroup$ That's too bad... Thank you for the answer though! $\endgroup$ – TLW Jul 22 '18 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.