ゴレイ符号

ゴレイ符号（英: Golay code）は、数学の散在型単純群の理論に基づく符号の種類である。名前の由来はスイスの数学者マルセル・J・E・ゴレイ。

2元ゴレイ符号

拡張2元ゴレイ符号の生成行列

2元ゴレイ符号（英: Binary Golay code）は、デジタル通信に用いられる誤り訂正符号の一種である。

2元ゴレイ符号は2種類存在する。拡張2元ゴレイ符号（extended-）は12ビットのデータを24ビットの符号語に符号化し、任意の3ビットの誤りを訂正可能で、4ビットの誤りを検出可能である。完全2元ゴレイ符号（perfect-）は符号語長23ビットで、拡張2元ゴレイ符号から特定の1ビットを除いたものである（逆に完全2元ゴレイ符号にパリティビットを追加したのが拡張2元ゴレイ符号である）。これらを標準的な符号パラメータで表すと、[24, 12, 8] と [23, 12, 7] である。

数学的定義

数学的には、拡張2元ゴレイ符号は24ビット空間 V=F₂²⁴ の12次部分空間 W からなり、W の任意の2つの元は少なくとも8箇所の座標位置が異なる。同様に W の任意のゼロでない元は、少なくとも8箇所の座標がゼロでない。

• W 上に分布するゼロでない座標の集合 w が符号語の集合である。拡張2元ゴレイ符号では、全ての符号語のハミング重みは、0, 8, 12, 16, 24 のいずれかである。
• 座標の再ラベル付けまで、W は一意である。

完全2元ゴレイ符号は完全符号である。すなわち、符号を中心とする半径3の球がベクトル空間のパーティションを形成する。

完全2元ゴレイ符号の自己同型群は、マシュー群 $M_{23}$ である。拡張2元ゴレイ符号の自己同型群はマシュー群 $M_{24}$ である。他のマシュー群は、W の1つ以上の元の不変部分群として得られる。

ハミング重み 8 のゴレイ符号の符号語は、シュタイナー系 S(5,8,24) の元である。

構築

1. 辞書式符号（Lexicographic code）: V 上のベクトルを辞書式順序で並べ替える（すなわち、ベクトルを24ビットの2進数整数と見て順に並べる）。w₁ = 0 を起点とし、整数として小さいほうから順に w₂, w₃, ..., w₁₂ と定義していく。このとき、既定の元の全ての線型合成と比較して少なくとも8箇所の座標が異なるものを選んでいく。W は w₁, ..., w₁₂ のスパンとして定義される。
2. 平方剰余符号: 平方非剰余 (mod 23) の集合 N を考える。これは巡回群 Z/23Z の11要素の部分集合である。この部分集合の変換 t+N を考える。各変換で要素 ∞ を追加することで12要素の集合 S_t を作る。そして V の基底要素を 0, 1, 2, ..., 22, ∞ でラベル付けすると、W は S_t の各元と全基底ベクトルから成る元のスパンとして定義できる。完全符号は、∞ を除けばよい。
3. 巡回符号: 完全 G₂₃ 符号は $x^{23}-1$ の因数分解からも構築できる。つまり符号は式 $x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1/x^{23}-1$ から生成される。
4. R. T. Curtis の "Miracle Octad Generator": 4×6 の配列で、拡張2元ゴレイ符号の759個のハミング重み8の符号語 "Octad" を描く。24種類の部分集合の対称差を利用して（つまり、2進の加算によって）全符号語を得る。
5. 数学ゲーム Mogul の勝ちパターン: Mogul は24枚の硬貨を並べて遊ぶゲーム。初期状態は全硬貨が表。ターン毎に1枚から7枚の硬貨を裏返すが、そのうちの左端の硬貨は表から裏への裏返しでなければならない。裏返せなくなった方が負けである。表を1、裏を0と解釈すれば、拡張2元ゴレイ符号の符号語となるようなパターンにすれば必勝する。

3元ゴレイ符号

3元ゴレイ符号（英: Ternary Golay code）には、相互に関連する2種類の誤り訂正符号が存在する。通常3元ゴレイ符号と言えば、完全 (11, 6, 5) 3元線型符号を指す。拡張3元ゴレイ符号（extended-）は (12, 6, 6) 線型符号であり、(11, 6, 5) の符号にゼロサムのチェックディジットを追加したものである。

拡張3元ゴレイ符号の重み多項式は次の通り。

$x^{12}+y^{12}+z^{12}+22(x^{6}y^{6}+y^{6}z^{6}+z^{6}x^{6})+220(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{6}x^{3}y^{3})$

完全3元ゴレイ符号は、有限体 F₃ 上の長さ11の平方剰余符号として構築できる。

拡張3元ゴレイ符号の自己同型群は 2.M₁₂ であり、M₁₂ はマシュー群である。

拡張3元ゴレイ符号は、体 F₃ 上の12次アダマール行列の行のスパンから構築可能である。

ゼロでない6つの桁を持つ拡張3元ゴレイ符号の全ての符号語を考えたとき、そのゼロでない桁の位置の集合は、シュタイナー系 S(5, 6, 12) から得られる。

ゴレイ符号の応用例

NASAの宇宙探査

ボイジャー計画では、木星と土星のフライバイの際に多数のカラー画像を転送する必要があったが、当時の通信帯域幅は技術的に限られていた。

• カラー画像転送では3倍の量のデータを送る必要があり、ゴレイ (24,12,8) 符号が使われた
• このゴレイ符号は3ビットの誤りしか訂正できないが、マリナー計画で使われたアダマール符号よりもデータ転送レートを速くすることができた。

短波帯データ通信

短波帯の自動リンク確立(ALE)についてのアメリカ政府の新たな規格では、拡張 (24,12) ゴレイ符号を前方誤り訂正（FEC）に指定している。

• 指定された拡張 (24,12) ゴレイ符号は、(24,12) ブロック符号である。
• 12ビットのデータを24ビットの符号語に符号化する。
• 12ビットの元のデータは24ビットの符号語にそのまま含まれている。すなわち、体系的符号である。

任意の2つの符号語の最小ハミング距離は8であり、最大7ビットまでの誤りを検出できるか（この場合訂正できない）、最大4ビットまで誤りを検出できて3ビットまで訂正できるか、あるいはこの中間を選択可能である。

• これらの条件を (0,7), (1,6), (2,5), (3,4) のように記述する。最初の数は訂正可能ビット数、次の数が検出可能ビット数である。

参考文献

• Curtis, R. T. A new combinatorial approach to M₂₄. Math. Proc. Camb. Phil. Soc. 79 (1976) 25-42.
• Griess, Robert L.: "Twelve Sporadic Groups", Springer-Verlag, 1998.
• Thompson, Thomas M.: "From Error Correcting Codes through Sphere Packings to Simple Groups", Carus Mathematical Monographs, Mathematical Association of America, 1983.
• J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups, Springer-Verlag, New York, Berlin, Heidelberg, 1988.