La distanza di Hamming è il numero di posizioni in cui due sequenze di uguale lunghezza differiscono. Introdotta da Richard Hamming nel suo articolo del 1950 sui codici a rilevazione e correzione di errore, costituisce uno dei fondamenti della teoria della codifica e delle comunicazioni digitali.

Un codice a blocchi le cui parole di codice sono separate da una distanza di Hamming minima d può rilevare fino a d − 1 errori su singolo bit e correggerne fino a ⌊(d − 1) / 2⌋. Ad esempio, un codice di ripetizione che trasmette ogni bit tre volte ha distanza minima 3: rileva qualsiasi errore su due bit e corregge qualsiasi errore su un bit.

Oltre alla correzione degli errori, la distanza di Hamming trova applicazione in crittografia (somiglianza tra chiavi), bioinformatica (confronto di sequenze di DNA) e apprendimento automatico (ricerca dei vicini più prossimi tramite funzioni hash).

Sì. La distanza di Hamming è definita solo per sequenze di uguale lunghezza, perché confronta i simboli nelle posizioni corrispondenti — la posizione 1 con la posizione 1, la posizione 2 con la posizione 2, e così via. Se le stringhe hanno lunghezze diverse, non esiste un criterio naturale per allineare i simboli in eccesso.

Per sequenze di lunghezza diversa, l'alternativa standard è la distanza di Levenshtein (distanza di edit), che conta il numero minimo di inserimenti, eliminazioni e sostituzioni di singoli caratteri necessari per trasformare una stringa nell'altra.