Numero minimo di stringhe per coprire l'intero spazio all'interno della distanza di Hamming
-
05-11-2019 - |
Domanda
Dato $ (n, k) $:
- 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}} $$
- 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.)
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange