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. In this scheme the set of binary vectors of length and two vectors are -th associates if they are Hamming distance apart.
Recall that an association scheme is visualized as a complete graph with labeled edges. The graph has vertices, one for each point of and the edge joining vertices and is labeled if and are -th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled having the other edges labeled and is a constant depending on but not on the choice of the base. In particular, each vertex is incident with exactly edges labeled ; is the valency of the relation The in a Hamming scheme are given by
Here, and The matrices in the Bose-Mesner algebra are matrices, with rows and columns labeled by vectors In particular the -th entry of is if and only if