ゴレイ符号のソースを表示

'''ゴレイ符号'''（{{lang-en-short|Golay code}}）は、数学の[[散在型単純群]]の理論に基づく[[符号]]の種類である。名前の由来はスイスの数学者{{仮リンク|マルセル・J・E・ゴレイ|en|Marcel J. E. Golay}}。

== 2元ゴレイ符号 ==
[[File:BinaryGolayCode.svg|thumb|right|拡張2元ゴレイ符号の生成行列]]
'''2元ゴレイ符号'''（{{lang-en-short|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'''<sub>2</sub><sup>24</sup> の12次[[線型部分空間|部分空間]] ''W'' からなり、''W'' の任意の2つの元は少なくとも8箇所の座標位置が異なる。同様に ''W'' の任意のゼロでない元は、少なくとも8箇所の座標がゼロでない。
* ''W'' 上に分布するゼロでない座標の集合 ''w'' が符号語の集合である。拡張2元ゴレイ符号では、全ての符号語の[[ハミング重み]]は、0, 8, 12, 16, 24 のいずれかである。
* 座標の再ラベル付けまで、''W'' は一意である。

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

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

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

=== 構築 ===
# 辞書式符号（Lexicographic code）: ''V'' 上のベクトルを[[辞書式順序]]で並べ替える（すなわち、ベクトルを24ビットの2進数整数と見て順に並べる）。''w''<sub>1</sub> = 0 を起点とし、整数として小さいほうから順に ''w''<sub>2</sub>, ''w''<sub>3</sub>, ..., ''w''<sub>12</sub> と定義していく。このとき、既定の元の全ての線型合成と比較して少なくとも8箇所の座標が異なるものを選んでいく。''W'' は ''w''<sub>1</sub>, ..., ''w''<sub>12</sub> のスパンとして定義される。
# [[平方剰余符号]]: [[平方剰余の相互法則|平方非剰余]] (mod 23) の集合 ''N'' を考える。これは[[巡回群]] '''Z'''/23'''Z''' の11要素の部分集合である。この部分集合の変換 ''t''+''N'' を考える。各変換で要素 ∞ を追加することで12要素の集合 ''S''<sub>''t''</sub> を作る。そして ''V'' の基底要素を 0, 1, 2, ..., 22, ∞ でラベル付けすると、''W'' は ''S''<sub>''t''</sub> の各元と全基底ベクトルから成る元のスパンとして定義できる。完全符号は、∞ を除けばよい。
# [[巡回符号]]: 完全 G<sub>23</sub> 符号は <math>x^{23}-1</math> の因数分解からも構築できる。つまり符号は式 <math>x^{11}+x^{10}+x^6+x^5+x^4+x^2+1 / x^{23}-1</math> から生成される。
# R. T. Curtis の "Miracle Octad Generator": 4&times;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元ゴレイ符号の[[重み多項式]]は次の通り。
:<math>x^{12}+y^{12}+z^{12}+22(x^6y^6+y^6z^6+z^6x^6)+220(x^6y^3z^3+y^6z^3x^3+z^6x^3y^3)</math>

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

拡張3元ゴレイ符号の自己同型群は 2.''M''<sub>12</sub> であり、''M''<sub>12</sub> は[[マシュー群]]である。

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

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

== ゴレイ符号の応用例 ==
=== NASAの宇宙探査 ===
[[ボイジャー計画]]では、[[木星]]と[[土星]]のフライバイの際に多数のカラー画像を転送する必要があったが、当時の通信帯域幅は技術的に限られていた。
* カラー画像転送では3倍の量のデータを送る必要があり、ゴレイ (24,12,8) 符号が使われた<ref>{{Cite web |url=http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf |title=Combinatorics in Space - The Mariner 9 Telemetry System |last=Cherowitzo |first=Bill |date=2005-12-04 |publisher=University of Colorado Denver|access-date=2022-12-22}}</ref>
* このゴレイ符号は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) のように記述する。最初の数は訂正可能ビット数、次の数が検出可能ビット数である。

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* Curtis, R. T. A new combinatorial approach to M<sub>24</sub>. 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.  

{{DEFAULTSORT:これいふこう}}

[[Category:誤り検出訂正]]
[[Category:数学に関する記事]]