Shriek map: Difference between revisions

Revision as of 04:37, 11 November 2013

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

c_{i j k} = {\begin{cases} (\binom{k}{\frac{i - j + k}{2}}) (\binom{n - k}{\frac{i + j - k}{2}}), & if i + j - k is even, \\ 0, & if i + j - k is odd. \end{cases}

Here, $v = | X | = 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 ℱ^{n}$ . In particular the $(x, y)$ -th entry of $D_{k}$ is $1$ if and only if $d_{H} (x, y) = k$ .

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

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

[1] P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory,“ IEEE Trans. Inform. Theory, vol. 44, no. 6, pp. 2477–2504, 1998.

[2] 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.

[3] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier, New York, 1978.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-Im addicted to my hobby Travel. Appears boring? Not!<br>I also  to learn Turkish in my spare time.<br><br>My page; [http://tinyurl.com/pch83be cheap ugg boots]
+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]].<ref>P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory,“  ''IEEE Trans. Inform. Theory'', vol. 44, no. 6, pp. 2477–2504, 1998.</ref><ref>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.</ref><ref>F. J. MacWilliams and N. J. A. Sloane, ''The Theory of Error-Correcting Codes'', Elsevier, New York, 1978.</ref> In this scheme <math>X=\mathcal{F}^n</math>, the set of binary vectors of length <math>n</math>, and two vectors <math>x</math>, <math>y\in \mathcal{F}^n</math> are <math>i</math>-th associates if they have [[Hamming distance]] <math>i</math> apart.
+Recall that an [[association scheme]] is visualized as a [[complete graph]] with labeled edges. The graph has <math>v</math> vertices, one for each point of <math>X</math>, and the edge joining vertices <math>x</math> and <math>y</math> is labeled <math>i</math> if <math>x</math> and <math>y</math> are <math>i</math>-th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled <math>k</math> having the other edges labeled <math>i</math> and <math>j</math> is a constant <math>c_{ijk}</math>, depending on <math>i,j,k</math> but not on the choice of the base. In particular, each vertex is incident with exactly <math>c_{ii0}=v_{i}</math> edges labeled <math>i</math>; <math>v_{i}</math> is the [[Adjacency relation|valency]] of the [[Relation (mathematics)|relation]] <math>R_{i}</math>.
+The <math>c_{ijk}</math> in a '''Hamming scheme''' are given by
+: <math>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} </math>
+Here, <math>v=\left|X\right|=2^{n}</math> and <math>v_{i}=\binom{n}{i}</math>. The [[Matrix (mathematics)|matrices]] in the [[Bose–Mesner algebra|Bose-Mesner algebra]] are <math>2^{n}\times 2^{n}</math> [[Matrix (mathematics)|matrices]], with rows and columns labeled by vectors <math>x\in \mathcal{F}^{n}</math>. In particular the <math>\left(x,y\right)</math>-th entry of <math>D_{k}</math> is <math>1</math> if and only if
+<math>d_{H}(x,y)=k</math>.
+==References==
+{{reflist}}
+{{DEFAULTSORT:Hamming Scheme}}
+[[Category:Coding theory]]

Shriek map: Difference between revisions

Revision as of 04:37, 11 November 2013

References

Navigation menu

Search