三元ゴレイコード

Pair of related error-correcting codes

完全な3値ゴレイ符号
名前の由来	マルセル・J・E・ゴレイ
分類
タイプ	線形ブロックコード
ブロック長	11
メッセージの長さ	6
レート	6/11 ~ 0.545
距離	5
アルファベットのサイズ	3
表記	${\displaystyle [11,6,5]_{3}}$-コード
v t e

拡張三元ゴレイ符号
名前の由来	マルセル・J・E・ゴレイ
分類
タイプ	線形ブロックコード
ブロック長	12
メッセージの長さ	6
レート	6/12 = 0.5
距離	6
アルファベットのサイズ	3
表記	${\displaystyle [12,6,6]_{3}}$-コード
v t e

符号理論において、3元ゴレイ符号は密接に関連した2つの誤り訂正符号である。一般的に単に3元ゴレイ符号として知られるこの符号は-符号、すなわち3元アルファベット上の線形符号である。この符号の相対距離は3元符号として可能な限り大きいため、3元ゴレイ符号は完全符号である。拡張3元ゴレイ符号は、[11, 6, 5]符号にゼロサムチェックディジットを追加することで得られる[12, 6, 6]線形符号である。有限群論では、拡張3元ゴレイ符号は3元ゴレイ符号と呼ばれることもある。^[要出典] ${\displaystyle [11,6,5]_{3}}$

プロパティ

三元ゴレイコード

3元ゴレイ符号は3 ⁶  = 729個の符号語から構成される。そのパリティ検査行列は

${\displaystyle \left[{\begin{array}{cccccc|ccccc}2&2&2&1&1&0&1&0&0&0&0\\2&2&1&2&0&1&0&1&0&0&0\\2&1&2&0&2&1&0&0&1&0&0\\2&1&0&2&1&2&0&0&0&1&0\\2&0&1&1&2&2&0&0&0&0&1\end{array}}\right].}$

任意の2つの異なる符号語は、少なくとも5つの位置で異なります。長さ11の3値語はすべて、ちょうど1つの符号語からのハミング距離が最大2です。この符号は、有限体F ₃（すなわち、ガロア体GF(3) ）上の長さ11の平方剰余符号として構成することもできます。

11 試合のフットボール プールで使用される3 進ゴレイ コードは 729 の賭けに相当し、最大 2 つの誤った結果を伴う賭けが 1 つだけであることを保証します。

ハミング重み5のコードワードセットは3-(11,5,4)設計です。

Golay (1949, 表1) によって与えられた生成行列は

${\displaystyle \left[{\begin{array}{cccccc|ccccc}1&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&1&2&2&0\\0&0&1&0&0&0&1&2&1&0&2\\0&0&0&1&0&0&2&1&0&1&2\\0&0&0&0&1&0&2&0&1&2&1\\0&0&0&0&0&1&0&2&2&1&1\\\end{array}}\right].}$

（元の）3元ゴレイコードの自己同型群はマシュー群 M 11 であり、散在単純群_の中で最小のものである。

拡張三元ゴレイ符号

拡張された3値ゴレイコードの完全な重み列挙子は

${\displaystyle x^{12}+y^{12}+z^{12}+22\left(x^{6}y^{6}+y^{6}z^{6}+z^{6}x^{6}\right)+220\left(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{6}x^{3}y^{3}\right).}$

拡張された3元ゴレイコードの自己同型群は2.M12_であり、ここでM12_はマシュー群M12_である。

拡張された3値ゴレイ符号は、体F _{3上の12次の}アダマール行列の行の範囲として構築できます。

拡張符号の符号語のうち、6桁の非ゼロ桁のみを持つものをすべて考えてみましょう。これらの非ゼロ桁が出現する位置の集合は、シュタイナー体系S(5, 6, 12)を形成します。

拡張3値ゴレイ符号の生成行列は

${\displaystyle \left[{\begin{array}{cccccc|cccccc}1&0&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&0&1&2&2&1\\0&0&1&0&0&0&1&1&0&1&2&2\\0&0&0&1&0&0&1&2&1&0&1&2\\0&0&0&0&1&0&1&2&2&1&0&1\\0&0&0&0&0&1&1&1&2&2&1&0\\\end{array}}\right]=[I_{6}|B].}$

この生成行列に対応するパリティ検査行列は であり、 は行列の転置を表します。 ${\displaystyle [-B|I_{6}]^{T}}$ ${\displaystyle T}$

このコードの代替生成行列は

${\displaystyle \left[{\begin{array}{rrrrrr|rrrrrr}1&0&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&0&1&-1&-1&1\\0&0&1&0&0&0&1&1&0&1&-1&-1\\0&0&0&1&0&0&1&-1&1&0&1&-1\\0&0&0&0&1&0&1&-1&-1&1&0&1\\0&0&0&0&0&1&1&1&-1&-1&1&0\\\end{array}}\right]=[I_{6}|B_{\mathrm {alt} }].}$

そしてそのパリティ検査行列は です。 ${\displaystyle [-B_{\mathrm {alt} }|I_{6}]^{T}}$

基礎となる有限体の3つの元は、ここでは ではなくで表されます。また、 （すなわち、 1の加法逆元）とであることも理解されます。これらの有限体元の積は、整数の積と同じです。行と列の和は3を法として評価されます。 ${\displaystyle \{0,1,-1\}}$ ${\displaystyle \{0,1,2\}}$ ${\displaystyle 2=1+1=-1}$ ${\displaystyle -2=(-1)+(-1)=1}$

行列の行の線形結合、つまりベクトル加算は、コードに含まれるすべての可能な単語を生成します。これは行のスパンと呼ばれます。生成行列の任意の2行の内積は常にゼロになります。これらの行、つまりベクトルは直交していると言われます。

生成行列とパリティ検査行列の行列積は 、すべてゼロの行列であり、意図的に となる。実際、これは生成行列に関するパリティ検査行列の定義そのものの例である。 ${\displaystyle [I_{6}|B_{\mathrm {alt} }]\,[-B_{\mathrm {alt} }|I_{6}]^{T}}$ ${\displaystyle 6\times 6}$

歴史と応用

三進法ゴレイコードはゴレイ（1949）によって発表されました。このコードは2年前にフィンランドの サッカービリヤード愛好家ユハニ・ヴィルタカリオ によって独自に発見され、1947年にサッカー雑誌『ヴェイッカヤ』第27号、第28号、第33号に掲載されました。（Barg 1993, p.25）

三元ゴレイ符号は、マジックステート蒸留と呼ばれるフォールトトレラント量子コンピューティングへのアプローチに有効であることが示されています。^[1]

参照

• ベルレカンプ – ファン リント – ザイデルのグラフ
• バイナリゴレイコード

参考文献

1. Prakash, Shiroman (2020年9月). 「三元ゴレイ符号によるマジックステート蒸留」Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences . 476 (2241) 20200187. arXiv : 2003.02717 . doi :10.1098/rspa.2020.0187.

• バーグ、アレクサンダー（1993）「符号理論の夜明け」、数学インテリジェンサー、15（1）：20-26、doi：10.1007/BF03025254、MR  1199273
• Golay, MJE (1949年6月)、「デジタル符号化に関する注記」(PDF)、IRE議事録、37 :657、MR 4021352、 2015年4月19日時点の オリジナル(PDF)からアーカイブ

さらに読む

• ブレイク、IF（1973）、代数的符号理論：歴史と発展、ペンシルベニア州ストウズバーグ：ダウデン、ハッチンソン＆ロス
• Conway, ジョンソン州; Sloane、NJA (1999)、球のパッキング、格子および群、Grundlehren der Mathematischen Wissenschaften、vol. 290 (第 3 版)、ニューヨーク: Springer-Verlag、土井:10.1007/978-1-4757-6568-7、ISBN 0-387-98585-9、MR  1662447
• Griess、Robert L. Jr. (1998)、「Twelve Sporadic Groups」、Springer Monographs in Mathematics、ベルリン: Springer-Verlag、doi :10.1007/978-3-662-03516-0、ISBN 3-540-62778-2、MR  1707296
• コーエン、ジェラール；ホンカラ、イイロ；リッツィン、シモン；ロブスタイン、アントワーヌ（1997）「Covering codes」、North-Holland Mathematical Library、第54巻、アムステルダム：North-Holland、ISBN 0-444-82511-8、MR  1453577
• トンプソン、トーマス・M.（1983）「誤り訂正符号から球面パッキングを経て単純群へ」、Carus Mathematical Monographs、第21巻、ワシントンD.C.：アメリカ数学協会、ISBN 0-88385-023-0、MR  0749038

Retrieved from "https://en.wikipedia.org/w/index.php?title=Ternary_Golay_code&oldid=1315101362"