Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top