ハミングスキーム

リチャード・ハミングにちなんで名付けられたハミング方式は、超三次連想方式としても知られ、符号理論の最も重要な例です。^{[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+jk)}}&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.}$

参考文献

1. P. DelsarteとVI Levenshtein、「アソシエーションスキームとコーディング理論」、 IEEE Trans. Inf. Theory、vol. 44、no. 6、pp. 2477–2504、1998年。
2. P. Camion、「コードとアソシエーション スキーム: コーディングに関連するアソシエーション スキームの基本特性」、Handbook of Coding Theory、VS Pless および WC Huffman 編、Elsevier、オランダ、1998 年。
3. FJ MacWilliams と NJA Sloane、「誤り訂正符号の理論」、Elsevier、ニューヨーク、1978 年。