東北大理学研究科数学専攻では代数幾何や代数の先生が指導する院生が、代数幾何符号な どのサーベイの修士論文を提出することがあります。私は計算機数学を担当しているのですが、院生がやや工学的な符号理論の数学の本を持ってきたことがあります。 その本は復号化アルゴリズムに重点を置き、 章末問題やプログラミング課題をやるように書いてあったので、院生のプログラミングの負担が 軽くなるように、私がC++のプログラムのお手本を書き彼に渡し、また、より数理的なプログラムは プログラミングの負担が軽くなるように Mapleという数式処理システムでより抽象的なプログラムを作るように指導しました。 なぜMapleかというと、Mapleは廉価で、し かも東北大数学科・数学専攻に所属している人は無料で使えて教育目的にはよいと 考えたからです。Mapleは数式処理システムMathematicaよりCなどの手続き型言語に近く、C++/Javaなどのオブジェクト指向プログラミングもある程度できるようです。実際、 Mapleでは 有限体のオブジェクトを作成するための組み込みのコンストラクタを持ち、有限体 上の四則演算、原始根の確認をする関数などが、有限体オブジェクトのメソッ ドとしてあります。数式処理システムはオブジェクト指向でないと複雑な数学的構造を 綺麗に記述するのが面倒と、日本の数式処理システム開発者から聞いたことがあります。 これら符号理論関係の、C++のプログラムとMapleのプログラムを、数学や情報学科の学部生の教育に役立てばと 思い公開します。

  1. 2013/7/22

    [1] Jorn Justesen and Tom Hoholdt. A Course In Error-Correcting Codes, European Mathematical Society, 2004. (正誤表は http://www2.mat.dtu.dk/publications/books/ACourseInErrorCorrectingCodes/ から取得可能)

    の1.3節 "Syndrome decoding and the Hamming bound" と

    [2] Pless, Introduction to the Theory of Error-Correcting Codes, Wiley, 1990.

    に基づき, 線形符号のsyndrome decoder のプログラムをC++で作成し, [1]の Problem 1.5.20の the self-dual (32,16)-code, および Example 1.3.1 の (6,3)-codeに対して実行して見ました. また, weight enumeratorのプログラムを作成し [1]のProblem 1.5.8, Problem 1.5.9および Problem 1.5.22を解いてみました. ここからプログラムとプログラムの実行結果が取得できます.
  2. (n,k)-Reed-Solomon 符号化とは, n+1元体上の k次元ベクトルの後ろに0を詰めて, 1の原始n乗根による離散フーリエ変換をすることです。従って、高速フーリエ変換に類似の非常に高速な復号化アルゴリズムがありNASAの標準になっています。

    しかし、[Jorn Justesen and Tom Hoholdt, A Course In Error-Correcting Codes, European Mathematical Society, 2004]に従って、error locator polynomialを用いる古典的な復号化アルゴリズムを勉強してみました。

    ある(n,k)-Reed-Solomon 符号においては、符号語でない受信語があって、Peterson復号化ア ルゴリズムに入力すると、その受信語の最小次数のerror locator polynomial は n+1元体にその次数より小さな個数の解しか持たず、それら解に対応する桁に受信語が 持つ誤り量をそのアルゴリズムは0と計算してしまい、さらに悪いことに、それら誤り量 をシンドロームから効率よく計算しようとして、復号化アルゴリズムで有名なForney 法は 用いると、別の値が誤り量として出てきます。このように、Reed-Solomon符号や その拡張である代数幾何符号の符号化アルゴリズムの中心概念である error locator polynomial は微妙な問題があるかもしれません。

    なお, Peterson による復号化アルゴリズムを数式処理システムMapleでプログラムし 計算させました。プログラムとその計算結果はJustesenDecoderOfReedSolomonCodes.zipを見てください。 プログラムでは、最小次数のerror locator polynomialと桁に含まれるエラー量の計算を、 [11章, 1]のユークリッドの互除法とForney法で行っています。 検算をするには、プログラムのオプション引数で指定すれば、 より遅いけれど自明なアルゴ リズムによる計算結果を出力します。その自明なアルゴリズムとは、行列の 階段形を用いて最小次数のerror locator polynomialを計算し、ガウス・ジョルダンの掃 き出し法を用いてエラー量を求めるものです。行列の階段形を用いる計 算方法についてはJustesenDecoderOfReedSolomonCodes.zipに同梱の echelon.pdfをご覧ください。

    著者たちもReed-Solomon符号の復号化アルゴリズムをMapleで作成しています (http://www2.mat.dtu.dk/publications/books/ACourseInErrorCorrectingCodes/) が、Error locator polynomial を求めるのに、行列の零空間を求めるための Mapleの組み込み関数を利用しています。そのため、著者たちのMapleのプログ ラムの実行過程において、error locator polynomialは次数が最小でなく、 受信語の桁で誤りがないにもかかわらず無駄に誤り量が0であることを計 算する可能性があります。

    付言すると、Mapleの日本代理店からの情報ですが、Mapleを用いた数学授業システムを 高専が開発しているそうです。学生はシステムと対話し、システムは微積などの問題を出題し、学生が答えていくというシステムらしいです。

    なお、プログラム言語C/C++でより高速に実装したい場合は、PARIという計算機代数の高速計算用の C ライブラリを利用するのが一案です。

  3. 2013/8/6(火) に数学棟107号室で1330からセミナーを行います。
  4. 2013/8/27(火) に数学棟107号室で1000からセミナーを行います。 代数幾何符号の章に入れれば良いと思います。 テキストの入手法などは気軽にお問い合わせください。邦訳も出版されています。
    誤り訂正符号入門 / イエルン ユステセン, トム ホーホルト著 ; 阪田省二郎 [ほか] 訳
    森北出版, 2005
    邦訳では正誤表が反映され、訳者による脚注もあり読みやすくなっています。 しかし、セミナーなどでは、正誤表を使わずに原典を読み、プログラムを作成して例など をプログラムで計算し、章末問題も解き、セミナーが「本の朗読会」に堕することを防ぎ、併せて、セミナーに参加している学生のプログラミング・スキルの向上をはかるのが良いと思います。