Pour un code en blocs q-aire de longueur n, distance de Hamming minimale d et rayon de décodage unique t = floor((d-1)/2), la borne de Hamming (borne d'empaquetage en métrique de Hamming) affirme que le nombre de mots de code M satisfait M · V_q(n,t) ≤ q^n, où V_q(n,t)=∑_{i=0}^t binom(n,i)(q-1)^i est le volume d'une sphère de Hamming de rayon t. Ceci découle de l'exigence que les sphères de Hamming de rayon t autour de mots distincts soient disjointes pour assurer un décodage unique jusqu'à t erreurs.

Principe

Le comptage des sphères de décodage disjointes dans la métrique de Hamming fournit une borne supérieure sur la taille du code : la disjonction nécessaire au décodage unique implique que le volume total couvert par les sphères ne peut excéder q^n.

Démonstration

Scénario illustratif → Pour des codes binaires (q=2) de longueur n et distance minimale d=3 on a t=1. Chaque mot de code exclut ses voisins de Hamming à distance ≤1 ; comme chaque sphère de Hamming contient 1+n vecteurs, M(1+n) ≤ 2^n, ce qui limite M et montre que certaines tailles de codes sont impossibles sous décodage unique d'une erreur.

Mauvaise application

Appliquer la borne de Hamming au décodage par liste ou à des codes qui autorisent un décodage au-delà de t (par ex. en utilisant des décisions souples ou des informations auxiliaires) est une erreur ; la borne suppose un décodage unique dans le rayon t et des sphères disjointes.

Conséquence

Fournit une limite combinatoire explicite de la taille maximale d'un code pour n et d donnés ; sert à exclure certains triplets (n, M, d) et à identifier quand des codes parfaits (cas d'égalité) peuvent exister ou sont impossibles.

Inversion

La borne n'est pas applicable aux stratégies de décodage qui tolèrent le chevauchement (décodage par liste) ni aux canaux où les erreurs ne sont pas bien modélisées par la distance de Hamming ; de plus, l'approximation est serrée seulement pour des codes 'parfaits' rares — généralement la borne est lâche.

Limite

Clairement dans → codes en blocs sur alphabets finis sous métrique de Hamming avec exigence de décodage unique jusqu'à t erreurs. Cas limite → codes ayant la même distance minimale mais utilisant des décodeurs probabilistes où l'erreur moyenne importe davantage que la correction garantie. Claire­ment hors → codes évalués sous d'autres métriques (par ex. euclidienne) ou contextes avec information souple.

Tension sémantique

Borne supérieure de Hamming ↔ borne inférieure de Gilbert–Varshamov : les limites supérieures issues du comptage s'opposent aux bornes d'existence gloutonnes, produisant un intervalle possible pour M ; la tension porte sur la précision de ces bornes pour n fini.

Synthèse

La borne de Hamming est une affirmation d'impossibilité combinatoire : garantir la correction unique de t erreurs oblige à exclure autour de chaque codeword une sphère de Hamming de rayon t, et ces sphères ne peuvent se chevaucher. Elle impose des limites fermes sur la taille du code et met en évidence les cas exceptionnels où l'égalité est atteinte.