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 X=ℱn, the set of binary vectors of length n, and two vectors x,y∈ℱ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 cijk, depending on i,j,k but not on the choice of the base. In particular, each vertex is incident with exactly cii0=vi edges labeled i; vi is the valency of the relation Ri. The cijk in a Hamming scheme are given by

cijk={(k12(i−j+k))(n−k12(i+j−k))i+j−k≡0(mod2)0i+j−k≡1(mod2)

Here, v=|X|=2n and vi=(ni). The matrices in the Bose-Mesner algebra are 2n×2n matrices, with rows and columns labeled by vectors x∈ℱn. In particular the (x,y)-th entry of Dk is 1 if and only if dH(x,y)=k.

See also