ゴッパ符号のソースを表示

'''ゴッパ符号'''（ゴッパふごう、{{lang-en-short|Goppa code}}）または'''代数幾何符号'''（だいすうきかふごう、{{lang-en-short|algebraic geometric code}}）は、[[有限体]] <math>\mathbb{F}_q</math> 上の[[代数曲線]] ''X'' を使って構築される[[線型符号]]である。V. D. Goppa が考案した。場合によっては、興味深い極値特性（extremal property）を示すことがある。

ゴッパ符号は、<math>\mathbb{F}_q</math> 上で定義された非特異の[[代数多様体]] ''X'' のいくつかの[[有理点]]

:''P''<sub>1</sub>, ''P''<sub>2</sub>, ..., ''P''<sub>n</sub>

を使って構築でき、''X'' 上の[[因子 (代数幾何学)|因子]] ''G'' は <math>P_i</math> とは互いに素な有理点からのみ得られる。[[リーマン＝ロッホの定理]]によれば、因子 '''G''' に対応して、一意な有限次元のベクトル空間 <math>L(G)</math> が存在する。このベクトル空間は <math>X</math> の関数空間の部分空間である。

このような情報を使って構築されるゴッパ符号には、2種類のものが存在する。

== 関数型符号 ==
曲線 '''X'''、因子 '''G'''、有理点群 <math>P_i</math> から構築される関数型符号は以下の通りである。

<math>\mathbb{F}_q</math> 上の ''L''(''G'') の固定基底

:''f''<sub>1</sub>, ''f''<sub>2</sub>, ..., ''f''<sub>k</sub>

について、対応する <math>\mathbb{F}_q^n</math> 内のゴッパ符号は、

:(''f''<sub>''i''</sub>(''P''<sub>1</sub>), ''f''<sub>''i''</sub>(''P''<sub>2</sub>), ..., ''f''<sub>''i''</sub>(''P''<sub>n</sub>))

というベクトルによって <math>\mathbb{F}_q</math> 上に分布する。等価的に

:<math>\alpha : L(G) \longrightarrow \mathbb{F}^n</math>

の像としても定義され、ここで ''f'' は <math>f \longmapsto (f(P_1), \dots ,f(P_n))</math> で定義される。

上記で定義された <math> P_i </math> を使って因子を <math>D = P_1 + P_2 + \cdots + P_n</math> とする。通常ゴッパ符号は ''C''(''D'',''G'') と記述される。

次に、''C'' 上の因子 ''D'' と符号のパラメータの関係を示す。''l''(''D'') という記法は ''L''(''D'') の次元を意味する。

'''命題''' ゴッパ符号 ''C''(''D'',''G'') の次元は

:<math>k = l(G) - l(G-D)</math>

であり、2つの符号語間の最小[[ハミング距離]]は

:<math>d \geq n - \deg(G)</math>

である。

'''証明''' 

:<math>C(D,G) \cong L(G)/\ker(\alpha) </math> 

なので、次が成り立つことを示さなければならない。

:<math>\ker(\alpha)=L(G-D) </math>

<math>f \in \ker(\alpha)</math> と仮定する。すると <math>f(P_i)=0, i=1, \dots ,n</math> なので、<math>\mathrm{div}(f) > D </math> である。従って <math>f \in L(G-D)</math> である。逆に <math>f \in L(G-D)</math> と仮定する。すると

:<math>P_i < G, i=1, \dots ,n</math>

なので

:<math>\mathrm{div}(f)> D</math> 

である（''G'' は <math>-D</math> で問題を解かないので、代わりに ''f'' でそれをする必要がある）。従って

:<math>f(P_i)=0, i=1, \dots ,n</math>

となる。<math>d \geq n - \deg(G)</math> を示すため、<math>\alpha(f)</math> の[[ハミング重み]]を ''d'' とする。これはつまり、<math>n-d</math> 個の <math>P_i</math> （例えば <math>P_{i_1}, \dots ,P_{i_{n-d}}</math>）について <math>f(P_i)=0</math> であることを意味する。従って <math>f \in L(G-P_{i_1} - \dots - P_{i_{n-d}})</math> であり、

:<math>\mathrm{div}(f)+G-P_{i_1} - \dots - P_{i_{n-d}}> 0</math>

である。

:<math>\deg(\mathrm{div}(f))=0</math>

であることに着目して両辺の次数をとると

:<math>\deg(G)-(n-d) \geq 0</math>

が得られる。従って

:<math>d \geq n - \deg(G)</math>

である。Q.E.D.

== 留数型符号 ==
留数型符号は関数型符号の双対として定義されるか、<math>P_i</math> における何らかの関数の留数として定義される。

== 応用 ==
[[暗号理論]]において、ゴッパ符号は[[マックエリス暗号]]で使われている。

一般にゴッパ符号は性質の良い線型符号と見なされ、

:<math> {n^k} \choose {\log_2 n}</math> 

の誤りを訂正可能である。また復号も簡単で、[[ユークリッドの互除法]]と[[ベールカンプ＝マッシー法]]を使えばよい。

== 関連図書 ==
* Henning Stichtenoth、新妻弘（訳）：「代数関数体と符号理論」、共立出版、ISBN 978-4-320-11045-8 (2013年8月25日).

== 外部リンク ==
* {{Cite journal|和書|author=水野弘文 |date=2004-04 |url=https://hdl.handle.net/2433/25267 |title=代数幾何符号の歩み (符号と暗号の代数的数理) |journal=数理解析研究所講究録 |ISSN=1880-2818 |publisher=京都大学数理解析研究所 |volume=1361 |pages=143-151 |hdl=2433/25267 |CRID=1050282677085218432}}
* [http://upload.wikimedia.org/wikibooks/en/7/71/Algebraic_Geometric_Coding_Theory.pdf An undergraduate thesis on Algebraic Geometric Coding Theory]
* {{Cite journal|和書|author=上原剛 |date=2002 |url=http://www.jssac.org/Editor/Suushiki/V09/No2/V9N2_104.pdf |format=PDF |title=代数幾何符号に関する研究 |journal=数式処理 |ISSN=09191410 |publisher=日本数式処理学会 |volume=9 |issue=2 |pages=32-41 |CRID=1520572358731480448}}


{{DEFAULTSORT:こつはふこう}}

[[Category:誤り検出訂正]]
[[Category:数学に関する記事]]
[[Category:代数曲線]]
[[Category:符号理論]]
[[Category:有限体]]