ハミングスキーム

リチャード・ハミングにちなんで名付けられたハミング方式は、超三次関連方式としても知られ、符号理論の最も重要な例です。^{[1] [2] [3]}この方式では、長さのバイナリベクトルの集合と、2つのベクトルがハミング距離だけ離れている場合、それらのベクトルは - 番目の関連です。 ${\displaystyle X={\mathcal {F}}^{n},}$${\displaystyle n,}$${\displaystyle x,y\in {\mathcal {F}}^{n}}$${\displaystyle i}$ ${\displaystyle i}$

関連付けスキームは、ラベル付きの辺を持つ完全グラフとして視覚化されることを思い出してください。グラフには、 の各点に 1 つずつ頂点があり、頂点 と を結ぶ辺は、とが- 番目の関連付けである場合にラベルが付けられます。各辺には一意のラベルがあり、固定された底辺 と のラベルが付いた三角形の数は、底辺の選択に依存しますが、底辺の選択には依存しません。特に、各頂点は のラベルが付いた辺と正確に接続されます。は、関係の結合価です。ハミングスキームにおける は、次のように与えられます。 ${\displaystyle v}$${\displaystyle X,}$${\displaystyle x}$${\displaystyle y}$${\displaystyle i}$${\displaystyle x}$${\displaystyle y}$${\displaystyle i}$${\displaystyle k}$${\displaystyle i}$${\displaystyle j}$${\displaystyle c_{ijk},}$${\displaystyle i,j,k}$${\displaystyle c_{ii0}=v_{i}}$${\displaystyle i}$${\displaystyle v_{i}}$ ${\displaystyle R_{i}.}$${\displaystyle c_{ijk}}$

${\displaystyle c_{ijk}={\begin{cases}{\dbinom {k}{{\frac {1}{2}}(i-j+k)}}{\dbinom {nk}{{\frac {1}{2}}(i-j+k)}}&i+jk\equiv 0{\pmod {2}}\\\\0&i+jk\equiv 1{\pmod {2}}\end{cases}}}$

ここで、およびボーズ・メスナー代数の行列は、行と列がベクトルでラベル付けされた行列である。特に、の番目の要素がであるのは、${\displaystyle v=|X|=2^{n}}$${\displaystyle v_{i}={\tbinom {n}{i}}.}$${\displaystyle 2^{n}\times 2^{n}}$ ${\displaystyle x\in {\mathcal {F}}^{n}.}$${\displaystyle (x,y)}$${\displaystyle D_{k}}$${\displaystyle 1}$${\displaystyle d_{H}(x,y)=k.}$