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 $X={\mathcal {F}}^{n}$ , the set of binary vectors of length $n$ , and two vectors $x$ , $y\in {\mathcal {F}}^{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 $c_{{ijk}}$ , depending on $i,j,k$ but not on the choice of the base. In particular, each vertex is incident with exactly $c_{{ii0}}=v_{{i}}$ edges labeled $i$ ; $v_{{i}}$ is the valency of the relation $R_{i}$ . The $c_{{ijk}}$ in a Hamming scheme are given by

c_{{ijk}}={\begin{cases}{\dbinom {k}{{\frac {i-j+k}{2}}}}{\dbinom {n-k}{{\frac {i+j-k}{2}}}},&{\text{if }}i+j-k{\text{ is even,}}\\\;\;\;\;\;\;\;\;\;\;0\;\;\;\;\;\;\;\;\;\;\;,\;\;&{\text{if }}i+j-k{\text{ is odd.}}\end{cases}}

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

References

↑ P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory,“ IEEE Trans. Inform. Theory, vol. 44, no. 6, pp. 2477–2504, 1998.
↑ 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.
↑ F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier, New York, 1978.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.