Nombre minimum de chaînes pour couvrir toute l'espace à distance de Hamming

Question

Étant donné $ (n, k) $:

1. Quel est le nombre minimum $ x $ de chaînes (binaires) telles que toutes les cordes $ n $ -BIT (binaire) sont à moins de $ k $ hamming de quelques cordes?
   • Y a-t-il une expansion asymptotique ou une borne inférieure, au moins?
   • Une borne inférieure quelque peu triviale est la suivante:
     • Il y a $ sum_ {i = 0} ^ {k} {n Choose i} $ chaînes à distance $ k $ d'une chaîne donnée.
     • Il y a 2 $ ^ {n} $ cordes totales.
     • Chaque chaîne ne peut pas être comptée pas moins d'une fois.
     • Nous avons donc une limite inférieure de: $$ x ge frac {2 ^ {n}} { sum_ {i = 0} ^ {k} {n Choose i}} $$
2. Existe-t-il une formule explicite qui mappe un indice 1 $..k $ (ou 0 $ .. (k-1) $) à ces chaînes? (Je suis conscient que ce n'est probablement pas unique.)

Ceci est étroitement lié aux codes de correction des erreurs, mais finalement distincts. (Dans une erreur de correction du code, vous souhaitez (généralement) avoir toutes les chaînes à distance $ k $ (ou $ k / 2 $, etc., etc. k $ de au moins un mot de code.)