Hamming scheme

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.[1][2][3] In this scheme ${\displaystyle X={\mathcal {F}}^{n},}$ the set of binary vectors of length ${\displaystyle n,}$ and two vectors ${\displaystyle x,y\in {\mathcal {F}}^{n}}$ are ${\displaystyle i}$-th associates if they are Hamming distance ${\displaystyle i}$ apart.

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

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

References

1. P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory,“ IEEE Trans. Inf. Theory, vol. 44, no. 6, pp. 2477–2504, 1998.
2. P. Camion, "Codes and Association Schemes: Basic Properties of Association Schemes Relevant to Coding," in Handbook of Coding Theory, V. S. Pless and W. C. Huffman, Eds., Elsevier, The Netherlands, 1998.
3. F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier, New York, 1978.