Plan de Hamming

El esquema de Hamming , que lleva el nombre de Richard Hamming , también se conoce como esquema de asociación hipercúbica , y es el ejemplo más importante para la teoría de la codificación . ^{[ 1 ] [ 2 ] [ 3 ]} En este esquema${\displaystyle X={\mathcal {F}}^{n},}$el conjunto de vectores binarios de longitud${\displaystyle n,}$y dos vectores${\displaystyle x,y\in {\mathcal {F}}^{n}}$son${\displaystyle i}$-asociados si están a distancia de Hamming${\displaystyle i}$aparte.

Recordemos que un esquema de asociación se visualiza como un grafo completo con aristas etiquetadas. El grafo tiene${\displaystyle v}$vértices, uno por cada punto de${\displaystyle X,}$y la arista que une los vértices${\displaystyle x}$y${\displaystyle y}$está etiquetado${\displaystyle i}$si${\displaystyle x}$y${\displaystyle y}$son${\displaystyle i}$-asociados. Cada arista tiene una etiqueta única y el número de triángulos con una base fija etiquetada${\displaystyle k}$tener los otros bordes etiquetados${\displaystyle i}$y${\displaystyle j}$es una constante${\displaystyle c_{ijk},}$Dependiendo de${\displaystyle i,j,k}$pero no en la elección de la base. En particular, cada vértice es incidente con exactamente${\displaystyle c_{ii0}=v_{i}}$bordes etiquetados${\displaystyle i}$;${\displaystyle v_{i}}$es la valencia de la relación${\displaystyle R_{i}.}$El${\displaystyle c_{ijk}}$en un esquema de Hamming se dan por

${\displaystyle c_{ijk}={\begin{cases}{\dbinom {k}{{\frac {1}{2}}(i-j+k)}}{\dbinom {nk}{{\frac {1}{2}}(i+jk)}}&i+jk\equiv 0{\pmod {2}}\\\\0&i+jk\equiv 1{\pmod {2}}\end{cases}}}$

Aquí,${\displaystyle v=|X|=2^{n}}$y${\displaystyle v_{i}={\tbinom {n}{i}}.}$Las matrices en el álgebra de Bose-Mesner son${\displaystyle 2^{n}\times 2^{n}}$matrices , con filas y columnas etiquetadas por vectores${\displaystyle x\in {\mathcal {F}}^{n}.}$En particular el${\displaystyle (x,y)}$-entrada de${\displaystyle D_{k}}$es${\displaystyle 1}$si y solo si${\displaystyle d_{H}(x,y)=k.}$