Numero minimo di stringhe per coprire l'intero spazio all'interno della distanza di Hamming

Question

Dato $ (n, k) $:

1. Qual è il numero minimo $ x $ di stringhe (binarie) in modo tale che tutte le stringhe $ n $-bit (binarie) si trovano a una distanza di $ K $ Hamming da qualche stringa?
   • C'è un'espansione asintotica o un limite inferiore, almeno?
   • Un limite inferiore in qualche modo banale è il seguente:
     • C'è $ sum_ {i = 0}^{k} {n scegli i} $ stringhe entro la distanza $ k $ di una determinata stringa.
     • Ci sono $ 2^{n} $ stringhe in totale.
     • Ogni stringa può essere contata non meno di una volta.
     • Quindi abbiamo un limite inferiore di: $$ x ge frac {2^{n}} { sum_ {i = 0}^{k} {n scegli i}} $$
2. Esiste una formula esplicita che mappa un indice $ 1..k $ (o $ 0 .. (k-1) $) a queste stringhe? (Sono consapevole che questo non è probabilmente unico.)

Ciò è strettamente correlato ai codici di correzione degli errori, ma alla fine distinti. (In un errore di correzione degli errori, tu (di solito) vuoi avere ogni stringa a distanza $ k $ (o $ k/2 $, ecc.) Di non più di una parola codifica, mentre qui vuoi avere ogni stringa a distanza $ k $ di almeno una Codice.)