苅田 仁

称号及び氏名博士（理学）

学位授与の日付

2021 年 3 月 31 日

論

Geometric approach to the extendability of linear

文

名codes over finite fields（有限体上の線形符号の拡張可能性に関する幾何学的研究）

論文審査委員

主査
副査
副査
副査

丸田 辰哉
山口 睦
壁谷 喜継
松永 秀章

2020 年度 博士論文要旨
Geometric approach to the extendabilityof linear codes over finite fields（有限体上の線形符号の拡張可能性に関する幾何学的研究）
大阪府立大学大学院理学系研究科

数理科学専攻苅田 仁

現在、デジタル通信において、より信頼性が高くより高速な通信が望まれている。そのためには、情報を通信または記録する際に生じる誤りを正しく訂正できる確率が高い誤り訂正符号を構成する必要がある。現在実用化されている符号の多くは有限体（位数 𝑞 の有限体を 𝑞 元体と呼び、𝐺𝐹(𝑞) と表す）上の線形符号であり、線形符号の 3 つのパラメータ、長さ 𝑛、次元 𝑘、最小距離 𝑑 はそれぞれ、通信の速さ、メッセージの多様性、訂正能力の高さを表している。これらのパラメータを持つ線形符号を [𝑛, 𝑘, 𝑑]𝑞 符号と呼ぶ。この 3 つのパラメータのうち 2 つを与えて残りの 1 つを最適化する問題、最適線形符号問題（英名：
Optimal Linear Codes Problem）は、符号理論において古くから取り組まれている研究で、現在も未解決問題が多数残っている。その一つが与えられた正整数 𝑞, 𝑘, 𝑑 に対して[𝑛, 𝑘, 𝑑]𝑞 符号が存在するような 𝑛 の最小値 𝑛𝑞 (𝑘, 𝑑) （存在限界）を求める問題である。
[𝑛, 𝑘, 𝑑]𝑞 符号 𝒞 の基底を成す行ベクトルを並べてできる 𝑘×𝑛 行列を生成行列と呼ぶ。
符号に属する符号語は係数ベクトルと生成行列の積で算出できる。[𝑛,𝑘,𝑑]𝑞 符号 𝒞 の生成行列に 1 列追加して、[𝑛 + 1, 𝑘, 𝑑 + 1]𝑞 符号 𝒞′ が構成できるとき、𝒞 は拡張可能という。
符号の構成や上記の問題を解くために、符号の拡張可能性は極めて重要な役割を持つ。古くから符号の性質を調べるために、各符号語と零ベクトルとの距離である重みの分布が調べられてきた。2 元体 𝐺𝐹(2) 上の奇数の最小重み（線形性より最小距離と等しい）を持つ符号が拡張可能であることはよく知られており、パリティチェックとして実用化もされている。先行研究では、重み分布によって符号の性質が分類されることにより、𝑞 ≥ 3 に対する 𝐺𝐹(𝑞) 上の線形符号の拡張可能性が解明されてきた。例えば、2 元体上の線形符号に対する拡張定理は、R.Hill 教授の論文 “An extension theorem for linear codes, Des. CodesCryptogr. 17 (1999) 151-157” にて、 𝑞 ≥ 3 である 𝑞 元線形符号の拡張定理に一般化された。その結果は最適線形符号の存在限界の決定にも頻繁に使われている。本論文を構成する各章の概要は、以下の通りである。

第１章では、本論文の序論として、背景と目的を説明している。
第２章では、初めに有限体上の線形符号の基本的な概念やよく知られている定理を紹介する。続いて、本研究の主テーマである線形符号の拡張可能性について知られている結果を紹介する。ここで紹介する拡張可能性は 𝑞-WS (符号の重み分布から計算される 𝑞 個の整数の組) をもとに判別する。最後に、𝑞 元体上の射影幾何の概念と 𝑞-WS や生成行列を関連付ける方法を説明する。
第３章では、重みが 9 を法として 0, -1, -2 のいずれかと合同で、最小距離 𝑑 が -2 か -1と合同である 3 元線形符号が拡張可能であること証明する。この定理は 3-WS を特定しない重みが 3 種類の定理としては初である。また、その定理を応用して [512,6,340]3 符号が存在しないことも示す。
第４章と第５章では、4 元線形符号に関する研究結果を述べる。まず第 4 章では、4 元線形符号の拡張可能性に関する新しい定理をいくつか紹介する。3 次元線形符号の 4-WS や 4元体の射影空間上の odd set に関する先行研究を参照し、いくつかの 4-WS の値について、𝑘 次元符号 𝒞 に対応する射影空間 PG(𝑘 − 1, 4) 上の集合の構造を明らかにし、𝒞 が拡張可能であるための十分条件を与える。更に、その定理を適用した例を挙げる。第 5 章では、4 元 5 次元線形符号の最適線形符号問題について取り組んだ成果を述べる。ここでも、4 元線形符号の拡張定理が重要な役割を果たす。
第６章では、𝑞 元体上の線形符号に適用できるように一般化された拡張可能性に関する新しい定理を紹介する。特に特徴的な結果として、定理 6.1 は、符号語の重みが 𝑞 を法として 4 種類の 𝑞 元体上の線形符号に対する初めての拡張定理である。
最後の第７章では、第３章と第４章で更新した 𝑛3 (6, 𝑑) および 𝑛4 (5, 𝑑) の表を掲載する。

研究論文（査読付き）[1] T. Maruta, T. Tanaka, H. Kanda, New extension theorems for codes over Fq,
Proceedings of the 7th International Workshop on Optimal Codes and Related
Topics (OC 2013), Albena, Bulgaria, 2013, pp. 152-157.
[2] T. Maruta, T. Tanaka, H. Kanda, Some generalizations of extension theorems forlinear codes over finite fields, Australasian J. Combinatorics 60 (2014), pp. 150-157.
[3] H. Kanda, T. Tanaka, T. Maruta, On the l-extendability of quaternary linear codes,Finite Fields and their Applications 35 (2015), pp. 159-171.
[4] H. Kanda, T. Maruta, On the 3-extendability of quaternary linear codes, FiniteFields and their Applications 52 (2018), pp. 126-136.
[5] H. Kanda, T. Maruta, Nonexistence of some linear codes over the field of order four,
Discrete Mathematics 341 (2018), pp. 2676-2685.
[6] H. Kanda, A new extension theorem for ternary linear codes and its application,
Finite Fields and their Applications 67 (2020), Article 101711, pp. 1-9.
[7] H. Kanda, The non-existence of [383,5,286] and [447,5,334] quaternary linear codes,Serdica Math. J., to appear.

学位論文審査結果の要旨
学位論文提出者氏名：

苅田 仁

学位論文題目： Geometric approach to the extendability of linear codes over finite fields（有限体上の線形符号の拡張可能性に関する幾何学的研究）
𝑞 元体（位数 𝑞 の有限体）上の線形符号（𝑞 元線形符号）には、３つの重要なパラメータ、すなわち、符号の伝送速度に影響する長さ 𝑛、符号語の個数を決定する次元 𝑘、誤り訂正能力を表す最小距離 𝑑 がある（このような線形符号を [𝑛, 𝑘, 𝑑]𝑞 符号と呼ぶ）。与えられた 𝑞, 𝑘, 𝑑 の値に対して [𝑛, 𝑘, 𝑑]𝑞 符号が存在するような 𝑛 の最小値 𝑛𝑞 (𝑘, 𝑑) を求める問題は、符号理論において最も基礎的な研究課題の一つで、最適線形符号問題と呼ばれている。例えば、(𝑞,𝑘)=(3,6),(4,5) の場合でも多くの 𝑑 の値について𝑛𝑞 (𝑘, 𝑑) が未決定である。これを決定するには、既知の符号より最小距離が大きい（誤り訂正能力が高い）新しい符号の構成や、存在するか否か不明な線形符号の非存在証明が必要になる。最適線形符号問題を考える上で強力な手掛かりになるのが、本研究で扱っている線形符号の拡張可能性である。実際、最適な符号が拡張可能な場合は拡張された符号も最適であり、𝑑 が 𝑞 の倍数でないときの符号の非存在証明にも拡張定理が利用される場合が多い。本論文では、線形符号の生成行列から定義される射影空間の分割集合の幾何学的な構造を調べることによって線形符号の拡張可能性を考察すると共に、新たに得られた拡張定理の最適線形符号問題への適用例も示している。本論文の主な内容は、以下の通りである。
1. 𝑞 元体上の(𝑘-1)次元射影空間 Σ の各点 𝑃 に対して、[𝑛, 𝑘, 𝑑]𝑞 符号の生成行列から 𝑃 の重みが定義される。そこから自然に定義される Σ の line の重みが 𝑞 の倍数になることは知られていたが、Σ の一般の 𝑠 次元射影部分空間の重みについて成り立つ重要な等式を発見し、簡明な証明を与えた(Lemma 3.2)。これを用いて、３元及び４元線形符号に対する新しいタイプの拡張定理を証明し、それらを適用して最適線形符号問題で未解決であったいくつかの問題を解決した。
2. 𝑞 元線形符号の生成行列から定義される射影空間の分割集合が含む点の個数の組は、符号の重み分布から算出される整数の組で、𝑞-WS（weight spectrum modulo 𝑞）と呼ばれる。４元線形符号から得られる射影空間の分割集合の幾何学的な構造の多くが 4-WS によって特徴付けられることを示し、４元線形符号が複数回拡張可能となるための幾何学的な条件を求めることにより、４元線形符号が複数回拡張可能であるための新たな十分条件を示した。
3. 先行研究による拡張可能性の考察から得られたいくつかの十分条件を一般の 𝑞 元線形符号に対して成り立つ拡張定理の形に一般化することに成功した。これらの定理の一部は、既に最適線形符号問題の研究において応用されている。
上記の研究成果は、有限体上の線形符号の基礎研究に大きく貢献するものであり、今後、最適線形符号問題に関する研究において活用されることが期待される。以上により、本委員会は当該論文が学位論文として十分な内容を有しているものと判断した。
学位論文審査委員会
主査 丸田 辰哉
山口睦

壁谷 喜継
松永 秀章