The Hamming scheme, named after

Richard Hamming Richard Wesley Hamming (February 11, 1915 – January 7, 1998) was an American mathematician whose work had many implications for computer engineering and telecommunications. His contributions include the Hamming code (which makes use of a Ha ...

, is also known as the hyper-cubic association scheme, and it is the most important example for

coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...

.F. J. MacWilliams and N. J. A. Sloane, ''The Theory of Error-Correcting Codes'', Elsevier, New York, 1978. In this scheme

X=\mathcal^n,

the set of binary vectors of length

n,

and two vectors

x, y\in \mathcal^n

are

i

-th associates if they are

Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...

i

apart. Recall that an

association scheme The theory of association schemes arose in statistics, in the theory of experimental design for the analysis of variance. In mathematics, association schemes belong to both algebra and combinatorics. In algebraic combinatorics, association schemes ...

is visualized as a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

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

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_,

depending on

i,j,k

but not on the choice of the base. In particular, each vertex is incident with exactly

c_=v_i

edges labeled

i

;

v_

is the

valency Valence or valency may refer to: Science * Valence (chemistry), a measure of an element's combining power with other atoms * Degree (graph theory), also called the valency of a vertex in graph theory * Valency (linguistics), aspect of verbs re ...

of the relation

R_i.

The

c_

in a Hamming scheme are given by :

c_ = \begin \dbinom \dbinom & i+j-k \equiv 0 \pmod 2 \\ \\ 0& i+j-k \equiv 1 \pmod 2 \end

Here,

v=, X, =2^n

and

v_i=\tbinom.

The

matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

in the Bose-Mesner algebra are

2^n\times 2^n

, with rows and columns labeled by vectors

x\in \mathcal^n.

In particular the

(x,y)

-th entry of

D_

1

if and only if

d_(x,y)=k.

References

{{DEFAULTSORT:Hamming Scheme Coding theory