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 - version of the 4/6/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.