ゴレイ符号

ゴレイ符号（英: 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) の元である。

構築

(一)辞書式符号︵Lexicographic code︶: V上のベクトルを辞書式順序で並べ替える︵すなわち、ベクトルを24ビットの2進数整数と見て順に並べる︶。w₁ = 0 を起点とし、整数として小さいほうから順に w₂, w₃, ..., w₁₂と定義していく。このとき、既定の元の全ての線型合成と比較して少なくとも8箇所の座標が異なるものを選んでいく。W は w₁, ..., w₁₂のスパンとして定義される。 (二)平方剰余符号: 平方非剰余 (mod 23) の集合 Nを考える。これは巡回群 Z/23Z の11要素の部分集合である。この部分集合の変換 t+N を考える。各変換で要素 ∞ を追加することで12要素の集合 S_tを作る。そして Vの基底要素を 0, 1, 2, ..., 22, ∞ でラベル付けすると、W は S_tの各元と全基底ベクトルから成る元のスパンとして定義できる。完全符号は、∞ を除けばよい。 (三)巡回符号: 完全G₂₃ 符号は

x^{23}-1

の因数分解からも構築できる。つまり符号は式

x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1/x^{23}-1

から生成される。 (四)R. T. Curtis の "Miracle Octad Generator": 4×6 の配列で、拡張2元ゴレイ符号の759個のハミング重み8の符号語 "Octad" を描く。24種類の部分集合の対称差を利用して︵つまり、2進の加算によって︶全符号語を得る。 (五)数学ゲーム 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) 符号が使われた^[1]
このゴレイ符号は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) のように記述する。最初の数は訂正可能ビット数、次の数が検出可能ビット数である。

脚注

^ Cherowitzo, Bill (2005年12月4日). “Combinatorics in Space - The Mariner 9 Telemetry System”. University of Colorado Denver. 2022年12月22日閲覧。

参考文献

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.

[1] Cherowitzo, Bill (2005年12月4日). “Combinatorics in Space - The Mariner 9 Telemetry System”. University of Colorado Denver. 2022年12月22日閲覧。

[1]