称 号 及 び 氏 名

博士（

学位授与の日付

平成２１年

論「 Extendability of Ternary Linear Codes and itsGeneralizations（３元線形符号の拡張可能性とその一般化に関する研究）｣文

名論 文 審 査 委 員理学）

岡本

けい

３月３１日

主査 丸田 辰哉
副査 入江 幸右衛門
副査 大内 本夫

論文要旨
符号理論は情報理論の一分野である。
符号理論のはじまりは 1948 年のシャノン(C.E. Shannon) の論文であると言われている。
その最初の動機は、送信したデータが雑音のある通信路を通ると、その雑音によってデータに誤りが生じる場合があるという技術的問題の解決であった。例えば、雑音のある通信路を通して、できるだけ早く正確にデータを送りたいとする。通信路は電話線であるかもしれないし、高周波ラジオ線かもしれないし、通信衛星かもしれない。雑音は、人間の誤り・電光・熱雑音・設備の欠陥などが考えられる。そして、誤りが生じるために、受け取ったデータが送ったものとは異なってしまう。誤り訂正符号の目的は、情報に適当な冗長度を加えて符号化し、送信中に誤りが生じても、受信後に元の情報に復元できるようにすることである。
誤り訂正符号は、データ通信やコンパクトディスクの記録方式など、実際に多くの分野で実用化されている。携帯電話の普及やデジタルテレビ放送など、ネットワーク化が著しい昨今の状況は、実は符号理論なくしては実現できないのである。
このように、符号理論は多くの実用的な利用があると同時に、数学の分野で独自に発展している。数学の分野においては、最適符号化や復号化のアルゴリズムのように符号理論の主題に関連した多くの研究がなされている。誤り訂正符号の一種である線形符号は、数学的に扱いやすく、最も多く実用化されていることから、広く研究されている。
一般に、 q 元符号とは符号語と呼ばれる記号の系列の集合であり、各々の記号は、 q 個の元からなる集合 F から選ばれる。集合 F は符号アルファベットと呼ばれていて、よく集合Z q = {0, 1, 2, ・・・, q - 1} が F として用いられている。しかしながら、 q が素数べきであるときは、よく位数 q の有限体（ q 元体）を符号アルファベットとして用いる。
q 元体上の n 次元行ベクトル空間の k 次元部分空間 C を、長さ n、次元 k の q 元線形符号([n, k] q 符号)と呼ぶ。Cの最小距離（異なる符号語間のハミング距離の最小値）が d のとき、[n, k, d] q 符号と呼ぶ。できるだけ n を小さくすることでより高速な通信ができ、できるだけ d を大きくすることでより多くの誤り訂正を行うことができる。このような n,dを持つ符号を「良い符号」と呼んでいる。
「良い符号」を見つける問題は、符号理論の研究において最もよく取り組まれている問題である。[n, k, d] q 符号 C の生成行列に 1 列を追加して [n+1, k, d+1] q 符号を作ることができるとき、C は拡張可能である(extendable) とい-1-う。「良い符号」が拡張可能である場合、拡張された符号もやはり「良い符号」となる。
このため、符号の拡張可能性の研究は「良い符号」を見つける問題において有用である。
q = 2（いわゆるバイナリーコード）の場合、d が奇数のとき、[n, k, d] 2 符号が拡張可能であることはよく知られている。ところが、 q が 3 以上の q 元線形符号が拡張可能であるための条件はあまり知られていない。そこで本論文では、３元線形符号の拡張可能性とその一般化について考察する。まず、符号の拡張に関連のある diversity を定義し、符号の拡張可能性や diversity を射影幾何でどのようにとらえるかを述べる。次に、diversity と対応するスペクトルを完全に決定し、３元線形符号が拡張可能であるための幾何学的な必要十分条件を与える。最後に、３元線形符号に関する結果を一般化した 3-weight (mod q) 符号の拡張可能性について述べる。
本論文を構成する各章の概要は、以下の通りである。
第１章では、本論文の序論と本研究の背景、目的を説明し、線形符号の基本概念やよく知られている定理などを紹介する。また、線形符号の拡張可能性について知られている結果を紹介し、本研究において最も重要なキーワードである diversity の定義を与える。
更に、３元線形符号の拡張可能性について、diversity を用いて既に知られている定理を紹介する。diversity とは、符号の重み分布から計算される整数の組のことで、gcd(q, d)=1 であるような [n,k,d] q 符号に対して定義される。
３元以上の線形符号の拡張可能性を考察するには、線形符号や diversity を幾何学的な観点でとらえる必要がある。本章の最後に、射影幾何の概念を説明した上で、３元線形符号の拡張可能性や diversity を射影幾何でどのようにとらえるかを説明する。
第２章では、前章で説明した幾何学的な観点から、３元線形符号の拡張可能性を考える上で重要な diversity と、それに対応するスペクトルを完全に決定する。また、diversity とスペクトルの幾何学的構造を考えるために、axis を定義し、これを用いて diversity とスペクトルの幾何学的な特徴づけを行う。この axis を用いて、３元線形符号が拡張可能であるための必要十分条件を考える上で必要な１０種類の幾何学的条件(Ck-1)-(Ck-10)を示す。
そして、それらの条件を用いて本論文の主題である３元線形符号が拡張可能であるための必要十分条件を与える。最後に、結果を用いた例を紹介する。
第３章では、３元線形符号の拡張可能性に関する結果の最適線形符号問題への応用として、[n,6,d] 3 符号が存在するような n の最小値を求める問題に取り組み、新しく得られた結果を示す。具体的には、[458,6,304] 3 , [467,6,310] 3 , [471,6,313] 3 , [522,6,347] 3 をパラメータとする３元線形符号の非存在性や [406,6,270] 3 符号の構成などである。
第４章では、重みが q を法として 0, 1, -1 のいずれかと合同で、最小距離 d が q を法として -1 と合同であるような、3-weight (mod q) 符号と呼ばれる q 元線形符号の拡張可能性について得られた結果を述べる。主な結果は下記の２つである。
重みが q を法として 0, 1, -1 のいずれかと合同で、最小距離 d が q を法として -1 と合同であるような 3-weight (mod q) [n, k, d] q 符号は・ q が偶数の場合は常に拡張可能である。
・q が奇数の場合は diversity に関する４つの条件のいずれかを満たすとき、拡張可能である。
q = 3 の場合、２つ目の結果は d ≡ 2 (mod 3) のときの３元線形符号の拡張定理となる。
すなわち、この定理は３元線形符号の拡張定理の一般化であることが分かる。

-2-

審査結果の要旨

q 元体上の線形符号（ q 元線形符号）には、３つの重要なパラメータ、すなわち、符号の伝送速度に影響する長さ n、符号語の個数を決定する次元 k、誤り訂正能力を表す最小距離d がある（このような線形符号を [n,k,d] q 符号と呼ぶ）。与えられた k, d, q の値に対して[n,k,d] q 符号が存在するような n の最小値 n q (k,d) を求める問題は、符号理論において最も基礎的な研究課題の一つで、最適線形符号問題と呼ばれている。具体的には、既知の符号より最小距離が大きい（誤り訂正能力の高い）新しい線形符号の構成、及び、存在性が不明な線形符号の非存在の証明が必要になる。この最適線形符号問題を考える上で強力な手掛かりになるのが、本研究で扱っている線形符号の拡張可能性である。線形符号の拡張可能性を考察するには、線形符号の生成行列から定義される射影空間の部分集合（ F 0 , F 1 ）の幾何学的な構造を調べる必要があるが、先行研究では、拡張可能であるための十分条件がいくつか知られているだけであった。特に３元線形符号については、常に拡張可能であるよう なdiversity（符号の幾何学的な構造を分類するための指標）が各次元で４種類存在することは知られていたが、その他の diversity が何種類存在するのかさえ、低次元の場合を除いて不明であった。本論文の内容は、以下の通りである。
1. ３元線形符号の全ての diversity、及び、それらに付随するスペクトル（射影空間の超平面の種類とそれらの個数）を全ての次元で決定した。更に、そのスペクトルから F 0と F 1 の幾何学的な構造の特徴付けを行い、それらを基にして、３元線形符号が拡張可能であるための必要十分条件を与えた。また、一度 diversity として現れたものは、より高い次元でもそれに対応するものが遺伝して現れることを示し、新たに定義した axisの概念を用いてそれらの幾何学的な構造を明らかにした。
2. n 3 (6,d) を求める最適線形符号問題に取り組み、拡張定理を用いていくつかの３元線形符号の非存在を証明したり、新しい符号を構成する等の成果を上げた。
3. 最小距離が３を法として２と合同な値のときの３元線形符号の拡張定理を、最小距離がq を法として -1 と合同な値で、符号の重みが q を法として 0, 1, -1 と合同な値しか現れないときの q 元線形符号の拡張定理に一般化することに成功した。この定理は、符号の重みが q を法として 0 か -1 しか現れないときによく引用される Hill & Lizak(1995) の拡張定理の一般化にもなっている重要な結果である。
以上得られた成果は、有限体上の線形符号の基礎研究に大きく貢献するものであり、本委
員会は、学位論文の審査および最終試験の結果から、申請者に対して博士（理学）の学位を授与することを適当と認める。

-3-