バイナリゴレイコード

拡張バイナリゴレイコード
ジェネレータマトリックス
名前の由来	マルセル・J・E・ゴレイ
分類
タイプ	線形ブロックコード
ブロック長	24
メッセージの長さ	12
レート	12/24 = 0.5
距離	8
アルファベットのサイズ	2
表記	${\displaystyle [24,12,8]_{2}}$-コード
ヴ t e

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

数学と電子工学において、バイナリ ゴレイ コードは、デジタル通信で使用される線形誤り訂正コードの一種です。バイナリ ゴレイ コードは、 3 進ゴレイ コードとともに、数学における有限散在群の理論と特に深く興味深い関係があります。 ^[1]これらのコードは、 1949 年に発表されたMarcel JE Golayの論文^{[2] が、} ER Berlekampによって「符号理論における最高の単一発表ページ」と呼ばれたことにちなんで名付けられました。^[3]

密接に関連した 2 つの 2 進ゴレイ コードがあります。拡張 2 進ゴレイ コードG 24 ₍有限群論では単に「ゴレイ コード」と呼ばれることもあります) は、3 ビットのエラーを修正したり、4 ビットのエラーを検出したりできるように、12 ビットのデータを 24 ビット ワードにエンコードします。もう 1 つは、完全 2 進ゴレイ コードG ₂₃で、コードワードの長さは 23 で、拡張 2 進ゴレイ コードから座標位置を 1 つ削除することで得られます (逆に、拡張 2 進ゴレイ コードは、完全 2 進ゴレイ コードにパリティ ビットを追加することで得られます)。標準的なコーディング表記では、コードにはパラメーター [24, 12, 8] と [23, 12, 7] があり、それぞれコードワードの長さ、コードの次元、2 つのコードワード間の最小ハミング距離に対応します。

数学的に言えば、拡張バイナリゴレイコードG _24は、空間V = Fの12次元線形部分空間 Wから構成される。²⁴
₂24 ビット ワードで構成され、Wの任意の 2 つの異なる要素は少なくとも 8 つの座標で異なります。W はベクトル空間であるため、線形コードと呼ばれます。全体として、W は4096 = 2 ¹²個の要素で構成されます。

• Wの要素はコードワードと呼ばれます。これらは 24 個の要素の集合の部分集合として記述することもできます。この場合、加算は部分集合の対称差を取ることとして定義されます。
• 拡張バイナリ ゴレイ コードでは、すべてのコード ワードのハミング重みは0、8、12、16、または 24 です。重み 8 のコード ワードはオクタッドと呼ばれ、重み 12 のコード ワードはドデカッドと呼ばれます。
• コードG ₂₄のオクタッドは、S(5,8,24)シュタイナーシステムの要素です。オクタッドは759 = 3 × 11 × 23 個あり、その補数は 759 個あります。したがって、 12 進数は2576 = 2 ⁴ × 7 × 23個あります。
• 2 つのオクタッドは、バイナリ ベクトル表現の 0、2、または 4 座標で交差します (これらはサブセット表現で可能な交差サイズです)。オクタッドとドデカッドは、2、4、または 6 座標で交差します。
• 座標の再ラベル付けまでは、W は一意です。

2進ゴレイ符号G _23は完全符号である。つまり、符号語の周りの半径3の球はベクトル空間の分割を形成する。G ₂₃は空間Fの12次元部分空間である。²³
₂。

完全二進ゴレイ符号G _{23の自己同型群（} Fの座標の順列の群S _{23の部分群を意味する）}²³
₂（G ₂₃を不変にする）はマシュー群 である。拡張バイナリゴレイ符号の自己同型群は、位数2 ¹⁰ × 3 ³ × 5 × 7 × 11 × 23のマシュー群である。は、8 元および 12 元で推移的である。他のマシュー群は、 Wの 1 つまたは複数の元の安定化群として現れる。 ${\displaystyle M_{23}}$ ${\displaystyle M_{24}}$${\displaystyle M_{24}}$

重み 24 の単一のワードがあり、これは 1 次元の不変部分空間です。したがって、 は 2 つの要素を持つ体上に 11 次元の既約表現を持ちます。さらに、バイナリ ゴレイ コードは 24 次元空間の 12 次元部分空間であるため、バイナリ ゴレイ ココードと呼ばれる12 次元商空間にも作用します。ココード内のワードは、長さ 0、1、2、3、または 4 のワードと同じコセット内にあります。最後のケースでは、6 つの (互いに素な) ココード ワードがすべて同じコセット内にあります。奇数の重みを持つココード ワードで構成される 11 次元の不変部分空間があり、これは2 つの要素を持つ体上に 2 番目の 11 次元表現を与えます。 ${\displaystyle M_{24}}$${\displaystyle M_{24}}$${\displaystyle M_{24}}$

• 辞書式コード: V内_のベクトルを辞書式に並べます(つまり、_符号なし 24 ビットの 2 進整数として解釈し、通常の順序付けを行います)。w 0 = 0 から始めて、w nが少なくとも₈つの座標で前の要素のすべての線形結合と異なる最小の整数であるという規則に従って、w ₁、w 2 、... 、 w ₁₂を定義します。次に、W をw ₁、...、w ₁₂の範囲として定義できます。
• マシュー群：1938年にウィットは拡張バイナリゴレイコードの構築に使用できる最大のマシュー群の構築を発表しました。^[4]
• 二次剰余コード:二次非剰余 (mod 23) の集合N を考えます。これは巡回群 Z /23 Zの 11 要素のサブセットです。このサブセットの変換t + Nを考えます。各変換に要素 ∞ を追加して 12 要素の集合S _tに拡張します。次に、 Vの基底要素に 0、1、2、...、22、∞ とラベルを付けると、W は、すべての基底ベクトルからなる単語と単語S _tを合わせた範囲として定義できます。(完全なコードは、∞ を省略することで得られます。)
• 巡回符号として：完全なG ₂₃符号は、 2進体GF(2)上の因数分解によって構築できます。これはによって生成される符号です。^[5] 11次の既約因数のいずれかを使用して符号を生成できます。^[6]${\displaystyle x^{23}-1}$$${\displaystyle x^{23}-1=(x-1)(x^{11}+x^{9}+x^{7}+x^{6}+x^{5}+x+1)(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1).}$$${\displaystyle \left(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1\right)}$
• 1967年のTurynの構築「バイナリゴレイコードの簡単な構築」は、長さ8のハミングコードから始まり、23を法とする二次剰余を使用していません。^[7]
• シュタイナーシステム S(5,8,24)は、24 セットの 759 個のサブセットから構成されます。各サブセットのサポートを長さ 24 (ハミング重み 8) の 0-1 コードワードとして解釈すると、これらはバイナリ Golay コードの「オクタッド」になります。Golay コード全体は、サブセットの対称差、つまりバイナリ加算を繰り返して取得できます。シュタイナーシステムとオクタッドを記述するより簡単な方法は、 RT Curtis のMiracle Octad Generatorです。これは、8 セットを 2 つの 4 セットに分割する 35 個の分割と、有限ベクトル空間を 4 つの平面に分割する 35 個の分割の間に特定の 1:1 対応を使用します。^[8]現在では、4×6 の正方形セル配列を使用する Conway の 16 進コードのコンパクトなアプローチがよく使用されます。${\displaystyle \mathbb {F} _{2}^{4}}$
• 数学ゲームMogul の勝利ポジション: Mogul のポジションは 24 枚のコインの列です。各ターンは、1 枚から 7 枚のコインを投げ、投げたコインの一番左端が表から裏に変わるようにするものです。負けポジションは、合法的な動きがないポジションです。表が 1、裏が 0 と解釈されれば、拡張バイナリ Golay コードからコードワードに移動することで、勝利を強制できることが保証されます。
• バイナリゴレイコードの生成行列はIAです。ここで、Iは12×12の単位行列、Aは二十面体の隣接行列の補行列です。

4 行 6 列の配列の座標を持つ「ミラクル オクタッド ジェネレーター」形式を使用すると便利です。加算は対称差を取ります。6 列すべてに同じパリティがあり、これは一番上の行のパリティと同じです。

6 列を隣接する 3 組に分割すると、トリオが構成されます。これは、3 つのオクタッド セットへの分割です。M ₂₄のトリオ サブグループのサブグループである射影特殊線型群PSL(2,7) x S ₃は、基底を生成するのに役立ちます。PSL(2,7) は、オクタッドを内部的に並列に並べ替えます。S _{3 は、} 3 つのオクタッドを物理的に並べ替えます。

基底はオクタッドTから始まります。

0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0

および 5 つの同様のオクタッド。これら 6 つのコード ワードの 合計Nはすべて 1 で構成されます。コード ワードに N を追加すると、その補数が生成されます。

Griess (p. 59) は次のようなラベル付けを行っています:

∞ 0 | ∞ 0 | ∞ 0
3 2 | 3 2 | 3 2
5 1 | 5 1 | 5 1
6 4 | 6 4 | 6 4

PSL(2,7)は当然、(0123456)と(0∞)(16)(23)(45)によって生成される線型分数群である。7サイクルはTに作用して、基底要素も含む部分空間を与える。

0 1 1 0 1 0
0 0 0 0 0 0
0 1 0 1 0 1
1 1 0 0 0 0

そして

0 1 1 0 1 0
0 1 0 1 0 1
1 1 0 0 0 0
0 0 0 0 0 0

結果として得られる 7 次元の部分空間は、後半の 2 つのオクタッドを無視すると 3 次元の商空間を持ちます。

同様の構造を持つコードワードが他に 4 つあり、W のこの表現の 12 個のコードワードの基礎が完成します。

_{WはPSL(2,7) x S 3}で対称な次元4の部分空間を持ち、Nと、部分集合{0,3,5,6}、{0,1,4,6}、および{0,1,2,5}から形成される3つの12進数によって張られる。

ボイジャー1号と2号の宇宙船では、メモリの制約により、事実上即座にデータをオフロードしなければならず、二度目のチャンスがなかったため、エラー訂正はデータ伝送に不可欠でした。1979年、1980年、1981年に木星と土星がフライバイした数百枚のカラー写真は、限られた通信帯域幅内で伝送されました。カラー画像の伝送には白黒画像の3倍のデータが必要だったため、マリナーの白黒画像の伝送に使用されていた7エラー訂正リード・ミュラー符号は、はるかにデータレートの高いゴレイ（24,12,8）符号に置き換えられました。^[9]

高周波無線システムにおける自動リンク確立のための米国軍事規格MIL -STD-188では、前方誤り訂正に拡張（24,12）ゴレイコードの使用を規定している。^{[10] [11]}

双方向無線通信のデジタルコード化スケルチ (DCS、CDCSS)システムでは、3 ビット以下のエラーを検出して修正できる 23 ビットの Golay (23,12) コード ワードが使用されます。

• リーチラティス
• 線形コード

• ジョン・ホートン・コンウェイ; Sloane、Neil JA (1999)、Sphere Packings、Lattices and Groups、Grundlehren der Mathematischen Wissenschaften、vol. 290 (第 3 版)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-0-387-98585-5、MR  0920369
• Curtis, RT (1976). 「M ₂₄への新しい組み合わせアプローチ」。ケンブリッジ哲学協会数学紀要。79 (1): 25–42。Bibcode :1976MPCPS..79...25C。doi :10.1017 / S0305004100052075。S2CID 122860631  。
• Greferath, Marcus (2003)。 「 Golay コード」。Proakis, John G. (編)。Encyclopedia of Telecommunications。Wiley。doi :10.1002 / 0471219282.eot371。ISBN 0471219282。
• グリース、ロバート L. (1998)。12 の散発的なグループ。スプリンガー。 p. 167.ISBN​ 978-3-540-62778-4。
• Pless, Vera (1998)、誤り訂正符号理論入門（第3版）、John Wiley & Sons、ISBN 978-0-471-19047-9
• ローマン、スティーブン（1996）、コーディングと情報理論、数学大学院テキスト＃134、シュプリンガー・フェアラーク、ISBN 0-387-97812-7
• トンプソン、トーマス M. (1983)。誤り訂正符号から球面パッキングを経て単純群まで。カルス数学モノグラフ。第 21 巻。アメリカ数学協会。ISBN 978-0-88385-023-7。
• Turyn, Richard J.; et al. (1967). コードの代数理論を開発するための研究 (セクション VI) (PDF) (レポート). 空軍ケンブリッジ研究所。2018年 10 月 30 日のオリジナル(PDF)からアーカイブ。