三元ゴレイコード

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

拡張三元ゴレイコード
名前の由来	マルセル・J・E・ゴレイ
分類
タイプ	線形ブロックコード
ブロック長	12
メッセージの長さ	6
レート	6/12 = 0.5
距離	6
アルファベットのサイズ	3
表記	${\displaystyle [12,6,6]_{3}}$-コード
ヴ 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&0&0&0&0\\2&2&1&2&0&1&0&0&0&0&0&0&0&0&2&1&0&0&0&0&0&0&0&0&0&1&0\\2&0&1&2&2&0&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\\0&1&0&0&0&0&1&1&2&2&0\\0&0&1&0&0&0&1&2&0&2&0&0&0&0&1&0&2&1&0&2\\0&0&0&0&0&0&1&0&2&0&1&2&1\\0&0&0&0&0&0&0&1&0&2&2&1&1\\\end{array}}\right].}$

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

拡張された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. M 12 であり、ここで_M 12は_マシュー群M ₁₂である。

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

拡張コードのすべてのコードワードのうち、6 桁の非ゼロの数字だけを持つものを検討します。これらの非ゼロの数字が発生する位置の集合は、シュタイナー システムS(5, 6, 12) を形成します。

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

${\displaystyle \left[{\begin{array}{cccccc|cccccc}1&0&0&0&0&0&0&1&1&1&1\\0&1&0&0&0&0&0&1&0&1&2&2&1\\0&0&1&0&0&0&0&1&0&1&0&1&2&2\\0&0&0&0&0&1&0&1&0&1&2&2&1&0&1\\0&0&0&0&0&1&0&1&2&2&1&0&1\\0&0&0&0&0&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]

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

• バーグ、アレクサンダー (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」、北ホランド数学図書館、第 54 巻、アムステルダム: 北ホランド、ISBN 0-444-82511-8、MR  1453577
• トンプソン、トーマス・M（1983）、誤り訂正符号から球面パッキングを経て単純群まで、Carus Mathematical Monographs、第21巻、ワシントンDC：アメリカ数学協会、ISBN 0-88385-023-0、MR  0749038