線形代数だけで理解する代数幾何符号

松本隆太郎東京工業大学電気電子工学科坂庭研究室〒 152-8552 目黒区大岡山 2-12-1 E-mail: ryutaroh@ss.titech.ac.jp URL: http://tsk-www.ss.titech.ac.jp/˜ ryutaroh/

1999 年 12 月 11 日^{∗}

1 はじめに

Goppa により 1981 年に提案された代数幾何符号 [3] は文字通り代数幾何の概念を使って定義されるので, 代数幾何に馴染みの無い人には大変取っ付きにくい分野であった. しかし, Høholdt らにより導入された重み関数の概念を用いることにより, 代数幾何符号を代数幾何を用いずともごまかし無しに理解することが可能になった. 本稿では代数幾何符号の主要な概念を線形代数と初等環論のみを用いて解説する. 命題にはすべて完全な証明を付けている. 第 2 節では代数幾何符号の Feng-Rao 復号アルゴリズムと Feng-Rao 限界を任意の線形符号に適用できるように, 線形代数だけを用いて定義し直す. 第 3 節では Høholdt らにより提案された線形代数と初等環論だけを用いた代数幾何符号の定義を紹介する.

小文を通して, F_{q} を要素数 q の有限体とし, F_{q}^{n} を有限体の要素を n 個並べたベクトルからなる線形空間とする. また {u_{1}, …, u_{n}}, {v_{1}, …, v_{n}}, {w_{1}, …, w_{n}} を F_{q}^{n} の基底とする. W を {w_{1}, …, w_{n}} の空でない真部分集合とし, W の要素を検査行列の行に持つ線形符号を C(W) で表す.

2 Feng-Rao 限界と Feng-Rao 復号アルゴリズム

この節では 1993 年に Feng と Rao により提案された復号アルゴリズム [1], および符号の誤り訂正能力を損なわずに検査シンボル数を減らす方法 [2] を紹介する. ここで紹介する内容は三浦の論文 [10, 3 章], [11] を多少一般化したものである.

2.1 Feng-Rao 限界

本小節では C(W) の最小距離の下界を与える. ベクトル a, b ∈ F_{q}^{n} に対し a ∗ b は a と b を座標ごとに掛けて得られるベクトルとする.

∗2000 年 6 月 1 日に参考文献の “to appear” になっている部分を実際の巻数, ページ数に更新した.

定義 2.1 W_{i} を w_{1}, …, w_{i} で張られる線形空間とし W_{0} = {0} とする. (u_{i}, v_{j}) が, ある 1 ≤ s ≤ n に対し u_{i} ∗ v_{j} ∈ W_{s} \ W_{s−1} かつすべての 1 ≤ u ≤ i, 1 ≤ v ≤ j, (u, v) ≠ (i, j) について u_{u} ∗ v_{v} ∈ W_{s−1} となるとき, 振舞いが良いという. 1 ≤ s ≤ n について M(s) := {(i, j) | u_{i} ∗ v_{j} ∈ W_{s} \ W_{s−1} かつ (u_{i}, v_{j}) は振舞いが良い } と定義する.

定義 2.2 C(W) に対する Feng-Rao 限界は

δ_{FR}(W) := min{♯M(s) | w_{s} ∉ W }

で定義される. 但し, ♯M は集合 M の要素数を表す.

定義 2.3 ベクトル y = (y_{1}, …, y_{n}) ∈ F_{q}^{n} に対しシンドローム行列 S(y) を

S(y) := ( u_{1} ; ⋮ ; u_{n} ) ( \begin{matrix}y_{1} \\ & . & . & . \\ & & & & y_{n} \end{matrix} ) ( v_{1} ; ⋮ ; v_{n} )^{T}

で定義する. また w(y) で y のハミング重みを表す.

命題 2.4 ベクトル y に対し rank S(y) = w(y). また S(y) の (i, j) 成分は ⟨y, u_{i} ∗ v_{j}⟩ で与えられる. 但し ⟨, ⟩ はベクトルの内積を表す.

証明: 最初の主張は S(y) の定義より明らか. また,

S(y) = ( y ∗ u_{1} ; ⋮ ; y ∗ u_{n} ) ( v_{1} ; ⋮ ; v_{n} )^{T}

であるので, S(y) の (i, j) 成分は ⟨y ∗ u_{i}, v_{j}⟩ になるが, これは ⟨y, u_{i} ∗ v_{j}⟩ に等しい.

命題 2.5 C(W) の最小距離は δ_{FR}(W) 以上である.

証明: y を C(W) の 0 でない符号語とし, ある整数 s に対し ⟨y, w_{1}⟩ = ⋯ = ⟨y, w_{s−1}⟩ = 0, ⟨y, w_{s}⟩ ≠ 0 が成立しているとする. このとき w_{s} ∉ W である. 一方, 任意の (i, j) ∈ M(s) に対し S(y) の (i, j) 成分は非零である. なぜならば u_{i} ∗ v_{j} は w_{1}, …, w_{s} の線形結合で書け, 線形結合の w_{s} の係数は非零なので,

⟨y, u_{i} ∗ v_{j}⟩ = ⟨y, ∑_{ℓ=1}^{s} c_{ℓ}w_{ℓ}⟩
= ∑_{ℓ=1}^{s} c_{ℓ}⟨y, w_{ℓ}⟩
= c_{s}⟨y, w_{s}⟩
≠ 0.

また同様にすべての 1 ≤ u ≤ i, 1 ≤ v ≤ j, (u, v) ≠ (i, j) について S(y) の (u, v) 要素は 0 である. M(s) の要素は行列の右上から左下にかけて並んでいるので, rank S(y) ≥ ♯M(s) ≥ δ_{FR}(W) を得る.

例 2.6 (Reed-Solomon 符号) Reed-Solomon 符号の最小距離が Feng-Rao 限界の特殊な場合として得られることを例を挙げて示す. α を F_{q} の原始元, i = 1, …, n(= q −1) に対し u_{i} = v_{i} = w_{i} = (1^{i}, α^{i}, …, α^{i(q−2)}) とする. このとき u_{i}∗v_{j} = w_{i+j−1} なので, M(s) = {(1, s), (2, s−1), …, (s, 1)} となる. W = {w_{1}, …, w_{r}} と取る. このとき C(W) は [q − 1, q − 1 − r] Reed-Solomon 符号になり, δ_{FR}(W) = r + 1 はその最小距離に等しい.

W として添え字が小さい順に {w_{1}, …, w_{r}} と取るのが従来の代数幾何符号に相当するが, Feng と Rao は設計距離 d を実現するために集合 W を

W (d) := {w_{s} | ♯M(s) ≤ d − 1}

のように取ると検査シンボル数をより少なくできることを明らかにした [2]. この構成法は改良代数幾何符号と呼ばれる.

2.2 Feng-Rao 復号アルゴリズム

符号を実用に供するためには効率的な復号アルゴリズムが不可欠である. 本小節では C(W) に通信の過程で生じた ⌊(δ_{F R}(W) − 1)/2⌋ 個以下の誤りを O(n^{3}) 回の有限体の演算で訂正する Feng-Rao 復号アルゴリズムを示す.

符号語 c ∈ C(W) が送信され c + e が受信されたとする. ⟨e, w_{1}⟩, …, ⟨e, w_{n}⟩ が分かれば行列の掛け算により O(n^{2}) 回の演算で誤りベクトル e を求めることができる.

w_{s} ∈ W なら ⟨c + e, w_{s}⟩ = ⟨e, w_{s}⟩ である. 従って, u_{i} ∗ v_{j} が W の要素の線形結合で書ける場合, 受信語から S(e) の (i, j) 成分を知ることができる. S(e) の既知の部分から未知の部分を正しく推測するアルゴリズムを以下に示す.

A を対角成分がすべて 1 の n × n 下三角行列とする. B := AS(e) とおく. B の各々の行 i につき A の左下部分を適当に設定して min{j | B の (i, j) 成分は非零 } を最大化することを考える. 今ある行 i について min{j′ | B の (i, j′) 成分は非零 } を最大化し j になったとする. このとき (i, j) を S(e) の discrepancy と呼ぶ. 以下 S(e) のすべての要素が分かっているという仮定のもとで discrepancy を求めるアルゴリズムを示す. B の (i, j) 成分が零になるように, B の i 行に i′(< i) 行の定数倍を加える操作を, すべての (i, j) について行うだけのアルゴリズムである.

アルゴリズム 2.7

A を単位行列に初期化する. for i = 1, …, n do

for j = 1, …, n do if B_{ij} ≠ 0 かつすべての j′ < j について B_{ij′} = 0 then if ある i′ < i が存在して B_{i′j} ≠ 0 かつすべての j′ < j について B_{i′j′} = 0 then

A の i 行から A の i′ 行を B_{ij}/B_{i′j} 倍して引く. このとき B_{ij} = 0 となり (i, j) は discrepancy ではない.

else 今 B_{ij} ≠ 0 かつすべての i′ < i, j′ < j について B_{i′j} = B_{ij′} = 0 である. B_{ij} = ⟨A の i 行, S(e) の j 列 ⟩ である. また, i 番目が 1 で i + 1, …, n 番目が 0 であるすべての横ベクトルは A の 1, …, i 行の線形結合でかけるが, A の i 行をどのような A の 1, …, i 行の線形結合 (但し A の i 行の係数は 1) で置き換えても B_{ij} を 0 にすることはできない. なぜならばすべての j′ < j について B_{ij′} = 0 だからである. したがって (i, j) は discrepancy である.

endif else

B_{ij} = 0 または (i, j) の左に既に discrepancy があるので, (i, j) は discrepancy ではない.

endif endfor

endfor

上記のアルゴリズムからすべての行 i について min{j | B の (i, j) 成分は非零 } を最大にする行列 A が存在することと, 各行各列につき discrepancy は高々1 個しかないことがわかる. アルゴリズム 2.7 実行後 B の discrepancy に相当する成分の左にある成分および上にある成分はすべて 0 である. したがって B の階数は discrepancy の総数に等しく, S(e) の階数は discrepancy の総数に等しい.

L(s) := {(u, v) | ある t ≤ s に対し (i, j) ∈ M(t) が存在して 1 ≤ u ≤ i, 1 ≤ v ≤ j かつ (u, v) ≠ (i, j) である } とする. L(s) に対応する S(y) のすべての成分がわかっているとする. このときアルゴリズム 2.7 を (i, j) 成分に対して実行するとき S(e) のすべての (u, v) 成分 (但し u ≤ i, v ≤ j) が既知であればアルゴリズムが実行できるので, L(s) に含まれる要素に限定してアルゴリズム 2.7 を実行することができる. このとき以下のように ⟨e, w_{s}⟩ の値を正しく推測することができる.

(i, j) ∈ M(s) の左または上に discrepancy が無かった場合, S(e) の (i, j) 成分を (i, j) が discrepancy にならないように推測する. 具体的には

− ∑_{i=1}^{i−1} A_{ik}S(e)_{kj}

と推測する. (i, j) 成分に対する推測値から ⟨e, w_{s}⟩ の推測値が決定される. この推測が真の値に等しい (i, j) の数を T, 間違っている数を F, L(s) の中で既に見つかっている discrepancy の数を K とする. このとき推測が誤っているのは (i, j) が discrepancy になっているときだけなので K +F ≤ discrepancy の総数 = rank S(e) = w(e) が成り立つ. また推測の仕方より ♯M(s) ≤ T +F +2K が成り立つ. もし 2w(e) < δ_{FR}(W) (≤ ♯M(s)) ならばこれらの不等式より T > F が成り立つ. このとき ⟨e, w_{s}⟩ の推測値の中で多数を占めるものが正しい値になる. ⟨e, w_{s}⟩ の値から L(s + 1) \ L(s) にあたる S(e) の成分が計算できる. このあと L(s + 1) \ L(s) の成分についてアルゴリズム 2.7 を実行し, S(e) の M(s + 1) に対応する成分を推測する. M(s) に対応する S(e) の成分を推測した後, L(s) の成分についてアルゴリズム 2.7 を実行しても結果は変わらないので, 実行する必要はない.

より高速な復号アルゴリズムについては [13, 14] を参照せよ.

注 2.8 本稿では u_{i} = v_{i} = w_{i} となる例しか挙げないが, L 型代数幾何符号の復号では u_{i} ≠ v_{i} = w_{i} とすると高い誤り訂正能力を実現できる [8].

3 線形代数だけを使った代数幾何符号の定義

Høholdt, van Lint, Pellikaan は [4, 5] において代数幾何符号を線形代数と重み関数という概念を使って定式化し直した. 本節では彼らの定式化を紹介する.

3.1 重み関数と符号

定義 3.1 [5, Definition 3.5] R を F_{q} を含む可換環とし, N_{0} を非負整数の集合とする. このとき写像 ρ : R → N_{0} ∪ {−∞} がすべての f, g ∈ R について以下の条件を満たすとき重み関数という.

1. ρ(f) = −∞ ⇔ f = 0.

2. すべての 0 ≠ c ∈ F_{q} について ρ(cf) = ρ(f).

3. ρ(f + g) ≤ max{ρ(f), ρ(g)}. 等号は ρ(f) ≠ ρ(g) のとき成立.

4. ρ(f) = ρ(g) ≠ −∞ なら, ρ(f − cg) < ρ(g) となる c ∈ F_{q} が存在する.

5. ρ(fg) = ρ(f) + ρ(g).

d が ρ(R \ {0}) の最大公約数なら ρ/d も重み関数である. 簡単のため以降では重み関数 ρ の最大公約数は 1 とする. また R ≠ F_{q} を常に仮定する.

命題 3.2 [5, Proposition 3.12] お互いに重み関数 ρ の値が異なる R の F_{q} 基底が存在する.

証明: 各々の i ∈ ρ(R \ {0}) について ρ(h_{i}) = i となる h_{i} を任意に選ぶ. このとき重み関数の定義より {h_{i} | i ∈ ρ(R\{0})} は F_{q} 上線形独立である. なぜなら線形結合 d_{1}h_{1} +⋯+d_{t}h_{t} に非零な係数があったとすると, ρ(d_{1}h_{1} + ⋯ + d_{t}h_{t}) = max{ρ(h_{i}) | d_{i} ≠ 0} ≠ −∞ より d_{1}h_{1} + ⋯ + d_{t}h_{t} ≠ 0 だからである.

g ∈ R \ {0} とすると, ある c ∈ F_{q} が存在し, ρ(g − ch_{ρ(g)}) < ρ(g) とできる. この議論を高々 (ρ(g) + 1) 回繰り返すことにより

g − ∑_{i∈ρ(R\{0})} c_{i}h_{i}

の重み関数 ρ の値を −∞ にする {c_{i} | i ∈ ρ(R \ {0})} が存在することが分かる. つまり g は {h_{i}} の線形結合で書ける.

ρ(f_{i}) < ρ(f_{i+1}) を満たす R の基底 {f_{i} | i = 1, 2, …} をこれ以降固定する. また F_{q}^{n} に座標ごとの積を導入して環と見なし, 環の全射準同型 φ : R → F_{q}^{n} が与えられているとする. {g_{1}, …, g_{n}} := {f_{i} | φ(f_{i}) は φ(f_{1}), …, φ(f_{i−1}) で張られる線形空間に属さない } とし ρ(g_{1}) < ⋯ < ρ(g_{n}) と添え字付けされているとする. 第 1 節に述べた F_{q}^{n} の基底 {u_{1}, …, u_{n}} などを u_{i} = v_{i} = w_{i} = φ(g_{i}) と定義する. 性能の良い線形符号を作るためには ♯M(s) は大きいほど良いが, 以上のように u_{i} などを定めたとき ♯M(s) はあまり小さくならないことを以下に示す.

補題 3.3 ρ(g_{i}) + ρ(g_{j}) = ρ(g_{s}) ならば (i, j) ∈ M(s) である.

証明: ρ(h) ≤ ρ(g_{s}) である h ∈ R について

φ(h) ∈ W_{s} \ W_{s−1} if ρ(h) = ρ(g_{s}),
φ(h) ∈ W_{s−1} if ρ(h) < ρ(g_{s})

である. すべての 1 ≤ u ≤ i, 1 ≤ v ≤ j, (u, v) ≠ (i, j) について ρ(g_{u}g_{v}) < ρ(g_{s}) であることから主張は導かれる.

g := ♯(N_{0} \ ρ(R \ {0})) とする.

命題 3.4 [5, Theorem 5.24] ♯M(s) ≥ s − g.

証明: まず ρ(g_{i}f_{j}) = ρ(g_{s}) を満たす (g_{i}, f_{j}) の数を数える. ある g_{i} に対して ρ(g_{i}f_{j}) = ρ(g_{s}) となる f_{j} が存在しないのは ρ(g_{s}) − ρ(g_{i}) ∈ N_{0} \ ρ(R \ {0}) となるときに限る. 従って ρ(g_{i}f_{j}) = ρ(g_{s}) を満たす (g_{i}, f_{j}) の数は s − g 以上である.

つぎに ρ(g_{i}f_{j}) = ρ(g_{s}) なら g_{j′} = f_{j} となる添え字 j′ が存在することを示す. これが示されれば前補題より主張の証明が終了する. もしそのような添え字 j′ が存在しないとすると

φ(f_{j}) = ∑_{ℓ=1}^{j−1} c_{ℓ}φ(f_{ℓ})

と書ける. 従って φ(g_{s}) が

φ(g_{s}) = dφ(g_{i}f_{j}) + ∑_{k=1}^{s−1} e_{k}φ(g_{k})
= ∑_{ℓ=1}^{j−1} dc_{ℓ}φ(g_{i}f_{ℓ}) + ∑_{k=1}^{s−1} e_{k}φ(g_{k})

のように g_{s} より真に重み関数の値が小さい要素に写像 φ を作用させて得られるベクトルの線形和で書けることになり, g_{s} の定義に矛盾する.

命題 3.4 より, W = {φ(g_{1}), …, φ(g_{n−k})} と取ると, C(W) は [n, k, d] 線形符号 (d ≥ n−k+1−g) になることが分かる. 情報レート k/n に対し相対最小距離 d/n を大きくするためには g に比較して n を大きく取る必要がある. [7] の結果と Hasse-Weil-Serre の定理 [15, Theorem V.3.1] より n の最大値は q + 1 + g⌊2\sqrt{q}⌋ であることがわかる. 符号長 n を g に対して大きく取れる環 R の構成法は次節で述べる.

3.2 可換環 R と重み関数 ρ の具体例

実際に符号を構成するためには g_{1}, …, g_{n} および φ が計算可能である必要がある. 以下符号構成が可能な可換環 R と重み関数 ρ の例を挙げる. 2 ≤ a < b を互いに素な整数とし, F (X, Y) を

Y^{a} + X^{b} + ∑_{ai+bj<ab} α_{i,j}X^{i}Y^{j}

という形の二変数多項式とおく. I を F (X, Y) で生成される二変数多項式環 F_{q}[X, Y] のイデアルとし, R := F_{q}[X, Y]/I とする. このとき

B := {X^{i}Y^{j} | 0 ≤ i, 0 ≤ j ≤ a − 1},

とすると {X^{i}Y^{j} mod I | X^{i}Y^{j} ∈ B} は剰余類環 R の基底になる. 単項式 X^{i}Y^{j} の重み付き次数を ai + bj と定め, 非零な多項式の重み付き次数を最大の重み付き次数を持つ項の重み付き次数とする. G(X, Y) が B の要素の非零な線形結合で表される多項式であるとき, G(X, Y) mod I ∈ R に対し重み関数 ρ の値を G(X, Y) の重み付き次数と定め, ρ(0) = −∞ と定める. B に含まれる単項式は互いに異なる重み付き次数を持つため, 上に定めた ρ が重み関数の定義を満たすことを確認するには, f, g ∈ R に対し ρ(fg) = ρ(f) + ρ(g) を確認すればよい.

G_{1}(X, Y), G_{2}(X, Y) が非零な B の単項式の線形結合で表される多項式とし, 各々の重み付き次数が最高の項を X^{i_{1}}Y^{j_{1}}, X^{i_{2}}Y^{j_{2}} とすると, G_{1}(X, Y)G_{2}(X, Y) の重み付き次数最高の項は X^{i_{1}+i_{2}}Y^{j_{1}+j_{2}} である. G_{1}(X, Y)G_{2}(X, Y) を Y を変数とする一変数多項式と見て F (X, Y) で割り算をすることにより得られる余りを H(X, Y) とすると G_{1}(X, Y)G_{2}(X, Y) mod I = H(X, Y) mod I であるが, F (X, Y) の形から H(X, Y) の重み付き次数は a(i_{1} + i_{2}) + b(j_{1} + j_{2}) で G_{1}(X, Y) と G_{2}(X, Y) の重み付き次数の和に等しい. 従って上に定めた ρ が重み関数の定義を満たすことが確認できた. 従って, {f_{1}, f_{2}, …} は B に含まれる単項式で代表される R の剰余類に取ることができる.

♯(N_{0} \ ρ(R \ {0})) が ♯M(s) の下界を決めたがこの場合

N_{0} \ ρ(R \ {0}) = N_{0} \ {ia + bj | 0 ≤ i, 0 ≤ j ≤ a − 1}

であるので, g = ♯(N_{0} \ ρ(R \ {0})) = (a − 1)(b − 1)/2 である.

最後に符号構成を行うために全射準同型 φ を具体的に計算する必要がある. x := X mod I, y := Y mod I とし, (α_{1}, β_{1}), …, (α_{n}, β_{n}) を方程式 F (X, Y) = 0 の F_{q}^{2} における相異なる解とする. M_{i} を R の x−α_{i}, y−β_{i} で生成される極大イデアルとすると, G(X, Y) mod I ∈ R に G(α_{i}, β_{i}) を対応させる写像は G(X, Y) mod I ∈ R に G(X, Y) mod I で代表される剰余類環 R/M_{i} の要素を対応させているとみることができる. 写像

R ⟶ F_{q}^{n},
G(X, Y) mod I ⟼ (G(α_{1}, β_{1}), …, G(α_{n}, β_{n}))

は写像

R ⟶ F_{q}^{n},
g ⟼ (g mod M_{1}, …, g mod M_{n})

に等しく, M_{1}, …, M_{n} は相異なる極大イデアルなので, 中国の剰余定理^{1}よりこの写像は全射になる. 従って φ として F (X, Y) = 0 の異なる解を代入する写像を選んで良い. {φ(g_{1}), …, φ(g_{n})} は φ(f_{1}), φ(f_{2}), … を計算したあと線形従属なベクトルを除くことで得られる.

注 3.5 (α, β) が F (X, Y) = 0 の解でなければ, G(X, Y) mod I ∈ R に (α, β) を「代入」する操作はそもそも写像にならない. G(X, Y) mod I と G(X, Y) + F (X, Y) mod I は R に属する同じ要素だが G(α, β) ≠ G(α, β) + F (α, β) だからである.

注 3.6 本小節で述べた形の多項式 F (X, Y) は 1992 年に三浦により代数幾何符号の構成に必要な情報がすべてわかる代数曲線族 C_{a}^{b} 曲線として提案された [9].

例 3.7 情報レート k/n に対し相対最小距離 d/n が大きい符号を作るには g = ♯(N_{0} \ρ(R\{0})) = (a − 1)(b − 1)/2 に対し解の数が多い多項式 F (X, Y) が必要だが, 例えば

F (X, Y) = Y^{q} + Y − X^{q+1} = 0

は F_{q^{2}} 内に q^{3} 個の解を持ち, g = q(q − 1)/2 となる多項式の中で F_{q^{2}}^{2} 内の解の数が最大の多項式である. g に対し解の数が多い多項式はコンピュータによる全数探索以外に見つける方法は無いと思われる. 多くの解を持つ多項式の表が [9] にある.

注 3.8 重み関数を持つ環の構成法は他に [5, Proposition 3.17, Example 3.22], [10, 定理 5.17], [12, p.1401 主定理] に示されている. 特に [10, 定理 5.17], [12, p.1401 主定理] は重み関数を持つすべての環を与える構成法になっている.

1初等代数の教科書を見よ.

3.3 従来の代数幾何符号との関係

本節で述べた Høholdt らの線形符号の構成法と従来の代数幾何符号の関係を述べる. 読者が代数幾何を用いて代数幾何符号を理解していることを前提として記述する. 特に断らない限り表記法は Stichtenoth の教科書 [15] に従う. F/F_{q} を一変数代数関数体, P_{1}, …, P_{n}, Q を相異なる一次の座, D := P_{1} + ⋯ + P_{n} とする. このとき代数幾何符号 C_{Ω}(D, mQ) は符号

{(f(P_{1}), …, f(P_{n})) | f ∈ L(mQ)}

の双対符号として与えられる. これは 3.1 節の構成法を使い以下のように構成できる. L(∞Q) := ⋃_{i=1}^{∞} L(iQ) とおくと L(∞Q) は関数体 F の部分環になる. また ρ を Q における離散付値を −1 倍したものとすると ρ は L(∞Q) の重み関数になる. f ∈ L(∞Q) に (f(P_{1}), …, f(P_{n})) を対応させる写像 φ は L(∞Q) から F_{q}^{n} への全射準同型である. g_{1}, …, g_{n} を 3.1 節のように定め, W := {φ(g_{i}) | ρ(g_{i}) ≤ m} とすれば C(W) は C_{Ω}(D, mQ) に等しい. このとき命題 3.4 における g は関数体 F の種数に等しくなり, d を C_{Ω}(D, mQ) の最小距離とすると命題 3.4 から直ちに Goppa 限界 d ≥ ♯W + 1 − g を導くことができる.

逆に 3.1 節で構成した符号と従来の代数幾何符号の関係は以下のようになる. 重み関数 ρ を持つ環 R は無限遠に唯一つの F_{q} 有理的な座 Q を持つアフィン代数曲線のアフィン座標環になり, 重み関数 ρ は Q における離散付値の負の整数倍で与えられることが示される [7]. R のもとになるアフィン代数曲線が非特異であるとき 3.1 節で示した符号は代数幾何符号 C_{Ω}(D, mQ) またはその改良代数幾何符号になる. 但し, 座 P_{1}, …, P_{n} は全射 φ から決まる.

アフィン代数曲線が特異なとき構成される符号は三浦により提案された特異曲線上の線形符号 [10, 12] に等しくなる. 但し, この場合曲線を正規化して得られる非特異曲線上の符号に比べて性能の良い符号は得られない [6].

4 まとめ

代数幾何符号のために提案された Feng-Rao 限界と Feng-Rao 復号アルゴリズムを線形代数だけを用いて定義し, 直し任意の線形符号に適用できるようにした三浦の結果を紹介した. また, 代数幾何符号の構成法を線形代数だけで定義した Høholdt らの結果を紹介した.

謝辞

原稿の間違いおよび分かりにくい部分を指摘して頂いた東工大の坂庭好一教授, ソニーの三浦晋示博士, 阪大の池上大介氏, 東工大の武井由智氏に感謝する.

参考文献

[1] G.L. Feng and T.R.N. Rao, “Decoding algebraic geometric codes up to the designed minimum distance,” IEEE Trans. Inform. Theory, vol.39, pp.36–47, 1993.

[2] , “Improved geometric Goppa codes part I, basic theory,” IEEE Trans. Inform. Theory, vol.41, no.6, pp.1678–1693, 1995.

[3] V.D. Goppa, “Codes on algebraic curves,” Soviet Math. Dokl., vol.24, no.1, pp.170–172, 1981.

[4] T. Høholdt, J.H. van Lint, and R. Pellikaan, “Order functions and evaluation codes,” Proc. AAECC-12, Lecture Notes in Computer Science, vol.1255, pp.138–150, Springer-Verlag, 1997.

[5] , “Algebraic geometry codes,” in Handbook of Coding Theory, V.S. Pless and W.C. Huffman, eds., pp.871–961, Elsevier, 1998.

[6] R. Matsumoto, “Linear codes on nonsingular curves are better than those on singular curves,” IEICE Trans. Fundamentals, vol.E82-A, no.4, pp.665–670, April 1999.

[7] , “Miura’s generalization of one-point AG codes is equivalent to Høholdt, van Lint and Pellikaan’s generalization,” IEICE Trans. Fundamentals, vol.E82-A, no.10, pp.2007–2010, Oct. 1999.

[8] R. Matsumoto and S. Miura, “On the Feng-Rao bound for the L-construction of algebraic geometry codes,” IEICE Trans. Fundamentals, vol.E83-A, no.5, pp.923–926, May 2000.

[9] 三浦晋示, “ある平面曲線上の代数幾何符号,” 電子情報通信学会論文誌, vol.J75-A, no.11, pp.1735–1745, Nov. 1992.

[10] , “代数幾何に基づく誤り訂正符号の研究,” 博士論文, 東京大学, May 1997.

[11] , “アフィン代数多様体上の線形符号,” 電子情報通信学会論文誌, vol.J81-A, no.10, pp.1386–1397, Oct. 1998.

[12] , “アフィン代数曲線上の線形符号,” 電子情報通信学会論文誌, vol.J81-A, no.10, pp.1398–1421, Oct. 1998.

[13] 阪田省二郎, “代数幾何符号とその復号法について,” 数理科学, no.421, pp.33–40, July 1998.

[14] , “代数幾何符号とその復号法について (続),” 数理科学, no.422, pp.58–65, Aug. 1998.

[15] H. Stichtenoth, “Algebraic function fields and codes,” Springer-Verlag, 1993.