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 chan ...

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 sch ...

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 is c ...

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 of the

relation Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...

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