// Workers AI · dad joke modeWhat did the Hamming scheme say? It had a coding problem.

The Hamming scheme, named after Richard Hamming, is also known as the hyper-cubic association scheme, and it is the most important example for coding theory. In this scheme $X={\mathcal {F}}^{n},$ the set of binary vectors of length $n,$ and two vectors $x,y\in {\mathcal {F}}^{n}$ are $i$-th associates if they are Hamming distance $i$ apart.

Recall that an association scheme is visualized as a complete graph with labeled edges. The graph has $v$ vertices, one for each point of $X,$ and the edge joining vertices $x$ and $y$ is labeled $i$ if $x$ and $y$ are $i$-th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled $k$ having the other edges labeled $i$ and $j$ is a constant $c_{ijk},$ depending on $i,j,k$ but not on the choice of the base. In particular, each vertex is incident with exactly $c_{ii0}=v_{i}$ edges labeled $i$; $v_{i}$ is the valency of the relation $R_{i}.$ The $c_{ijk}$ in a Hamming scheme are given by

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

Here, $v=|X|=2^{n}$ and $v_{i}={\tbinom {n}{i}}.$ The matrices in the Bose-Mesner algebra are $2^{n}\times 2^{n}$ matrices, with rows and columns labeled by vectors $x\in {\mathcal {F}}^{n}.$ In particular the $(x,y)$-th entry of $D_{k}$ is $1$ if and only if $d_{H}(x,y)=k.$