代数幾何学コード

代数幾何学コード（ AGコードとも略される）は、リード・ソロモンコードを一般化した線形コードの一種である。ロシアの数学者VDゴッパが1982年に初めてこのコードを構築した。^{[ 1 ]}

歴史

これらの符号の名称は、ゴッパによる論文発表以来、変化してきました。歴史的には、これらの符号は幾何学ゴッパ符号とも呼ばれてきましたが^{[ 2 ]} 、これはもはや符号理論の文献では標準的な用語ではありません。これは、ゴッパ符号が1970年代初頭にゴッパによって構築された独自の符号クラスであるためです^{[ 3 ] [ 4 ] [ 5 ] 。}

これらのコードは、ギルバート・ヴァルシャモフ限界を超える能力を持っているため、符号理論コミュニティの関心を集めました。この発見当時、ギルバート・ヴァルシャモフ限界は発見以来30年間破られていませんでした。^{[ 6 ]}これは、コード構築が発表されたのと同じ年に、Tfasman、Vladut、Zink によって論文「モジュラー曲線、志村曲線、ゴッパコード、ヴァルシャモフ・ギルバート限界よりも優れている」で実証されました。^{[ 7 ]}この論文のタイトルは、1980 年代から 1990 年代の符号理論の文献全体を通じて代数幾何学コードへの言及に影響を与える混乱の原因の 1 つである可能性があります。

工事

この節では、代数幾何学符号の構築について説明します。まず、代数幾何学符号の構築の動機となるリード・ソロモン符号の背後にある考え方について説明します。

リード・ソロモン符号

代数幾何学符号はリード・ソロモン符号の一般化である。 1960年にアーヴィング・リードとギュスターヴ・ソロモンによって構築されたリード・ソロモン符号は、有限体上の点において十分小さい次数の多項式を評価することで、一変数多項式を用いて符号語を形成する。^{[ 8 ]}${\displaystyle \mathbb {F} _{q}}$

正式には、リード・ソロモン符号は次のように定義される。 とする。正の整数 とする。リード・ソロモン符号は評価符号である。${\displaystyle \mathbb {F} _{q}=\{\alpha _{1},\dots ,\alpha _{q}\}}$ ${\displaystyle k\leq n\leq q}$ $${\displaystyle \mathbb {F} _{q}[x]_{<k}:=\left\{f\in \mathbb {F} _{q}[x]:\deg f<k\right\}}$$ ${\displaystyle RS(q,n,k)}$ $${\displaystyle RS(q,n,k)=\left\{\left(f(\alpha _{1}),f(\alpha _{2}),\dots ,f(\alpha _{n})\right):f\in \mathbb {F} _{q}[x]_{<k}\right\}\subseteq \mathbb {F} _{q}^{n}.}$$

代数曲線からのコード

ゴッパは、 は射影直線に対応するアフィン直線とみなせることを指摘した。すると、 における多項式（すなわち、 において次数未満の多項式）は、における無限遠点における極許容度がを超えない多項式として考えることができる。^{[ 6 ]}${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$ ${\displaystyle \mathbb {F} _{q}[x]_{<k}}$ ${\displaystyle k}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle k}$ ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$

この考えを念頭に、ゴッパはリーマン・ロッホの定理に着目した。リーマン・ロッホ空間の元とは、与えられた閾値以下に極位数が制限された関数と全く同じであり、^{[ 9 ]} 、この制限は対応する因子の係数に符号化されている。これらの関数を代数曲線上の有理点（つまり、曲線上の点）で評価すると、リード・ソロモン構成と同じ意味でのコードが得られる。 ${\displaystyle X}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q}^{2}}$ ${\displaystyle X}$

しかし、代数幾何学符号のパラメータは代数関数体と結びついているため、符号の定義は有限体上の代数関数体の言語で与えられることが多い。^{[ 10 ]}それでも、代数曲線との結びつきを覚えておくことは重要であり、これはAG符号をリード・ソロモン符号の拡張として考える上で、より幾何学的に直感的な方法を提供する。^{[ 9 ]}

正式には、代数幾何学コードは以下のように定義される。^{[ 10 ]}は代数関数体、は次数1の異なる位数の和、はから互いに素な台を持つ因子とする。因子とに関連付けられた代数幾何学コードは、次のように定義される。これらのコードに関する詳細は、入門書^{[ 6 ]}と符号理論の上級書の両方に記載されている。^{[ 10 ] [ 11 ]}${\displaystyle F/\mathbb {F} _{q}}$ ${\displaystyle D=P_{1}+\dots +P_{n}}$ ${\displaystyle n}$ ${\displaystyle F/\mathbb {F} _{q}}$ ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle C_{\mathcal {L}}(D,G)}$ ${\displaystyle D}$ ${\displaystyle G}$ $${\displaystyle C_{\mathcal {L}}(D,G):=\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(G)\rbrace \subseteq \mathbb {F} _{q}^{n}.}$$

例

リード・ソロモン符号

次のようなことが分かります

${\displaystyle RS(q,n,k)={\mathcal {C}}_{\mathcal {L}}(D,(k-1)P_{\infty })}$

ここで、 は射影直線上の無限遠点であり、は他の -有理点の合計です。 ${\displaystyle P_{\infty }}$ ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$ ${\displaystyle D=P_{1}+\dots +P_{q}}$ ${\displaystyle \mathbb {F} _{q}}$

1点エルミート符号

エルミート曲線は体 上の方程式で与えられる。^{[ 2 ]}この曲線はハッセ・ヴァイユ境界を等式で満たし、したがって 上のアフィン点の数が最大となるため、特に重要である。^{[ 12 ]}代数幾何学コードに関して言えば、これはエルミートコードが定義されているアルファベットに比べて長いことを意味する。^{[ 13 ]}$${\displaystyle x^{q+1}=y^{q}+y}$$ ${\displaystyle \mathbb {F} _{q^{2}}}$ ${\displaystyle \mathbb {F} _{q^{2}}}$

エルミート関数体のリーマン・ロッホ空間は次のように与えられる。^{[ 2 ]}で与えられ、に対して のエルミート関数体に対して、リーマン・ロッホ空間は であり、は 上の無限遠点である。 ${\displaystyle \mathbb {F} _{q^{2}}(x,y)}$ ${\displaystyle x^{q+1}=y^{q}+y}$ ${\displaystyle m\in \mathbb {Z} ^{+}}$ ${\displaystyle {\mathcal {L}}(mP_{\infty })}$ $${\displaystyle {\mathcal {L}}(mP_{\infty })=\left\langle x^{a}y^{b}:0\leq b\leq q-1,aq+b(q+1)\leq m\right\rangle ,}$$ ${\displaystyle P_{\infty }}$ ${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$

これを用いて、1点エルミート符号は次のように定義できます。を 上で定義されたエルミート曲線とします。 ${\displaystyle {\mathcal {H}}_{q}}$ ${\displaystyle \mathbb {F} _{q^{2}}}$

を 上の無限大点とし、を以外の上の異なる-有理点によってサポートされる因子とします。 ${\displaystyle P_{\infty }}$ ${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$ $${\displaystyle D=P_{1}+\cdots +P_{n}}$$ ${\displaystyle n:=q^{3}}$ ${\displaystyle \mathbb {F} _{q^{2}}}$ ${\displaystyle {\mathcal {H}}_{q}}$ ${\displaystyle P_{\infty }}$

1点エルミートコードは ${\displaystyle C(D,mP_{\infty })}$

${\displaystyle C(D,mP_{\infty }):=\left\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(mP_{\infty })\right\rbrace \subseteq \mathbb {F} _{q^{2}}^{n}.}$

参考文献

1. ゴッパ、ヴァレリー・デニソヴィッチ(1982)。「代数幾何学コード」。イズベスティア・ロシイスコイ・アカデミ・ナウク。セリヤ・マテマチェスカヤ。46 (4): 726– 781 – ロシア科学アカデミー、ロシアのステクロフ数学研究所経由。
2. Stichtenoth, Henning (1988). 「GF(q^2)上のエルミート符号に関する注記」 IEEE Transactions on Information Theory 34 ( 5): 1345– 1348 – IEEE経由.
3. ゴッパ、ヴァレリー・デニソヴィッチ(1970). 「新しいクラスの線形誤り訂正符号」 . Probl. Inf. Transm . 6 : 300–304 .
4. Goppa, Valerii Denisovich (1972). 「(L,g)-コードに基づいて構築されたコード」 . Problemy Peredachi Informatsii . 8 (2): 107– 109 – ロシア科学アカデミー情報学・コンピュータ機器・部門経由.
5. Berlekamp, Elwyn (1973). 「Goppaコード」 . IEEE Transactions on Information Theory . 19 (5): 590– 592 – IEEE経由.
6. ウォーカー、ジュディ・L. (2000).コードと曲線. アメリカ数学会. p. 15. ISBN 0-8218-2628-X。
7. マイケル、ツファスマン;ヴラドゥット、セルジュ。ジンク、トーマス(1982)。「モジュラー曲線、志村曲線、Goppa コードは、Varshamov-Gilbert 限界よりも優れています。 」数学的表現。
8. リード、アーヴィング；ソロモン、ギュスターヴ(1960). 「特定の有限体上の多項式コード」 . Journal of the Society for Industrial and Applied Mathematics . 8 (2): 300– 304 – SIAM経由.
9. ホーホルト、トム;ヴァン・リント, ジェイコバス;ペリカーン、ルード (1998)。「代数幾何学コード」(PDF)。コーディング理論のハンドブック。1 (パート 1): 871–961 – エルゼビア アムステルダム経由。
10. Stichtenoth, Henning (2009).代数的関数体とコード（第2版）. Springer Science & Business Media. pp.  45– 65. ISBN 978-3-540-76878-4。
11. ヴァン・リント、ヤコブス (1999).符号理論入門（第3版）. シュプリンガー. pp.  148– 166. ISBN 978-3-642-63653-0。
12. ガルシア、アルノルド;パウロ、ヴィアナ (1986)。「ワイエルシュトラスの点は、特定の非古典的曲線上にあります。 」数学のアーカイブ。46 : 315– 322 – スプリンガー経由。
13. Tiersma, HJ (1987). 「エルミート曲線からの符号に関する考察」 IEEE Transactions on Information Theory . 33 (4): 605– 609 – IEEE経由.