符号理論は,通信・記録システムの信頼性向上を目的とした符号化法に関する理論である.その歴史は1948年のシャノンの通信路符号化定理の発見,あるいは1950年のハミング符号の発明にはじまる.以来,誤りを訂正・検出する符号を構成しようという試みが次々となされ数多くの成果をあげてきた.また,実用上も非常に重要であり,現在の通信・記録システムの信頼性向上に欠かせないものとなっている.特に最近の急速なLSI技術の進歩にともない,従来までは複雑な処理が必要で装置規模も大きかった符号器,復号器がワンチップ化できるようになり,その導入は通信,コンピュータ,オーディオ・ビデオ等々各方面で必要不可欠なものとなっている.

　さて,符号理論の中心課題に「よい符号」のクラスの研究がある.「よい符号」とは,符号化・復号が実際的に実現可能であり,符号長,符号化率,相対最小距離の二つを指定するとき残りができるだけ大きい符号である.また,「よい符号」のクラスとは,次のような条件を満たすものである.

　(1)任意の符号化率に対し,符号長がいくらでも長い符号を含み,その相対最小距離がなるべく大きな正の一定値以上となる.

　(2)符号長を大きくするとき,復号の計算量が符号長の3乗程度以下で抑えられる.

　現在,「よい符号」のクラスの研究の主流をなすのは,1981年のゴッパによる代数幾何符号である.以来,数多くの成果を挙げてきた.特に,カツマンらは,1984年にこの符号のクラスは条件(1)を満たすことを示した.また,フェンとラオは,1993年に(1989年のユステセンらの復号法をもとに)この符号のクラスは(ほぼ満足できる形で)条件(2)を満たすことを示した.また,従来符号のほとんどがその復号法も含めて代数幾何符号,あるいはそれから派生する符号として解釈できることも解っている.

　しかるに,ゴッパによる代数幾何符号の定式化は抽象化された代数曲線論の深い結果に基づいておりとても構成的とは言えない.すなわち,存在は保証できても構成法は一般的には明らかになっていないのである.

　本論文は,フェンとラオのアイデアをもとに符号構成法,復号法を代数幾何の抽象理論から離れて任意一般の線形符号の問題として再構築する.次にそれを土台として,任意一般のアフィン代数多様体上の代数幾何符号の符号構成問題をまず解決し,ついで,任意一般の代数曲線を対象としたときと等価な形でゴッパの代数幾何符号の符号構成問題を解決する.

　(n,k,d_min)線形符号は一般にn-k+1≧d_minを満たす.ただし,nは符号長,kは情報長,d_minは最小距離である.本論文は,任意に指定された自然数g(＝0,1,2,3,…)に対してn-k+1≧d_min≧n-k+1-gを満たす(n,k,d_min)線形符号の一般的かつ具体的な構成法を提案する.ここに,本論文が提案する符号構成手順は次のように分解される.

図表

　ここに,導出される(n,k,d_min)線形符号は以下の条件を満たす.

　1)符号長nは定義方程式の零点集合の総数を上限に任意に設定できる.

　2)情報長kは任意に設定でき,n-k+1≧d_min≧d_FR≧d_G＝n-k+1-gを満たす.ただし,d_FRはFeng-Rao設計最小距離,d_GはGoppa設計最小距離である.

　3)t限界距離復号(d_FR≧2t+1)は工学的に実現可能である.すなわち,復号にかかる計算量は符号長nの高々3乗以下で抑えられる.

　4)途中に導出される定義方程式は,すべて一変数代数関数体のアフィンモデルを定義し,それらは手順⇒の自由度により,次数1の座を少なくとも一つは持つ種数がg以下のあらゆる一変数代数関数体のすべてを尽くす.

　これは,ゴッパによる非特異代数曲線上の(特異代数曲線上に拡張した上での)一点代数幾何符号の符号構成問題の解決となっている.さらに,それらの(ゴッパの設計最小距離の上界をなす)フェンとラオによる設計最小距離と,それが保証する限界距離復号を実現する符号器,復号器の装置化に必要となる情報のすべてを明らかにしている.これにより,符号理論の中心課題である「よい符号」の構成法の基礎理論が確立されたと言えよう.

　本論文は「代数幾何に基づく誤り訂正符号の研究」と題し,通信・記録システムの信頼性向上を目的に,幅広く利用されている誤り訂正符号の,代数幾何に基づく,一般的かつ具体的な構成法および復号法を,Goppaの理論をふまえて提案している.これにより線形符号の中心的な研究課題である「よい符号」,すなわち符号パラメータが自由に設定でき,かつ符号化・復号も実際的に実現可能な線形符号のクラスの研究のための強力な基礎理論が確立したことになる.論文の構成は「序論」を含めて8章からなる.

　第1章は「序論」であり,誤り訂正符号の中心をなす線形符号の研究の歴史に触れ,その中心課題である「よい符号」のクラスの研究は,Goppaの代数幾何符号の研究を深めることにより完成されるであろうことを,符号の漸近的ふるまい,復号問題の解決などの過去の主要な結果を引用しつつ,予想している.また,これを認めるなら,「よい符号」のクラスの研究において解決すべき課題は一般的かつ具体的な符号構成法の確立にあることを指摘し,これは,Goppaの代数幾何符号の未解決問題である符号構成問題と拡張問題との解決に完全に帰着されることを示している.

　第2章は「誤り訂正符号の基礎と線形符号」と題し,本研究を通じて用いる,情報源,通信路に関する基本的仮定を述べるとともに,誤り訂正符号とそれに付随する符号化・復号を数学的に明確に定式化し,扱う対象を特に線形符号に限る理由と線形符号に関する主な研究課題を確認している.

　第3章は「線形符号のFeng-Rao設計最小距離と限界距離復号」と題し,任意の線形符号を対象にFeng-Rao設計最小距離を定式化し,それが保証する限界距離復号はFeng-Rao復号アルゴリズムで実現できることを明らかにしている.これにより符号パラメータを自由に設定でき,かつ符号化・復号が実際的に実現可能な線形符号の具体的な構成手順が明らかになったことになる.これはGoppaの代数幾何符号の拡張問題の一つの解決になっている.以下の章では,第3章の結果に基づいて,よい符号パラメータを持つ線形符号の族の特定を具体的に実行する方法が論じられる.

　第4章は「アフィン代数多様体上の線形符号」と題し,よい符号パラメータを持つ線形符号の族の特定を目的に,任意のアフィン代数多様体上に線形符号を定義し,その具体的構成法とそれに対するFeng-Rao設計最小距離の下界を明らかにしている.また次章以下では,さらによい符号パラメータを持つ線形符号の族の特定を具体的に実行する方法が論じられる.

　第5章は「一変数代数関数体のあるアフィンモデル」と題し,Goppa代数幾何符号の符号構成問題の完全な解決の準備として代数曲線そのものの具体化を考察している.すなわち,定義方程式の決定である.

　第6章は「アフィン代数曲線上の線形符号」と題し,アフィン代数多様体を特にアフィン代数曲線に制限した場合の線形符号を定義し,その具体的構成法とそれに対するFeng-Rao設計最小距離の下界を明らかにしている.これは,Goppaの代数幾何符号の符号構成問題の一つの解決になっている.

　第7章は「具体例」と題し,本論文が提案した符号構成法を使うと,従来の符号よりも優れた符号パラメータを持つ線形符号が作れることを,具体例を挙げて確認している.

　最後に第8章は「結論」で,本研究の成果を要約し,今後の研究課題を挙げている.

　以上これを要するに,本論文は,代数幾何に基づく一般的かつ具体的な符号構成法の提案により,線形符号の中心課題である「よい符号」のクラスの今後の研究に資する強力な基礎理論を完成したものであって,これらの符号構成法に関する研究は,電子情報工学上貢献するところが少なくない.

　よって本論文は博士(工学)の学位請求論文として合格と認められる.