〈一般研究課題〉 マトロイド理論を用いた誤り訂正符号の研究
助 成 研 究 者

愛知県立大学

城本啓介

マトロイド理論を用いた誤り訂正符号の研究
城本 啓介（愛知県立大学）

1. はじめに符号理論とは、デジタル情報を伝送または記録する際に生じる誤りを検出あるいは訂正するための符号の理論であり、その符号を実際に構成して実用化を図るのが、符号理論の主要な目的である。
現代の情報通信・情報システムのいたるところで実用化（身近な所では、コンピュータ・携帯電話等）されている最先端の情報理論であり、数学や数理物理学等の他の様々な分野と大きく関わりを持つ分野である。特に、この符号理論に関して、代数的構造に着目して研究を行うのが代数的符号理論である。
有限体上の線形符号とは、有限体上のベクトル空間の部分空間である。その符号の特徴を表す重要なパラメータである最小重みとは、符号の各元（符号語）に対して取り得る値（重み）を定め（例えば、ハミング重みとは、ベクトルにおける０でない成分の個数）、その中での最小値のことであり、符号の誤り訂正能力の限界を表現したり、通信路における雑音の抑制に有効なパラメータである。符号理論における研究テーマの一つに、この最小重みに関する限界式の作成、さらにその限界式の等号を満たす線形符号の構成・解析がある（有名な例では、シングレトン限界式やグリスマー限界式がある。）。特に、有限体上の自己双対符号に関しては、N. Sloane や H. Ward らによって様々な限界式が証明され、そのことで極値的な自己双対符号（最小ハミング重みが限界値である符号）に関する存在・非存在問題がクローズアップされた。また、線形符号の各部分符号に対して値（重み）を定め、その最小値を一般化重みと言う。特に、1990年に V. Wei が一般化ハミング重みを導入し、情報セキュリティの分野への応用の可能性が指摘されたことに始まり、色々な符号に対してその重みを決定することが重要な研究であるとされている。
また、符号理論は組み合わせデザイン理論や整数論等の様々な研究分野と大きく関わっており、他の分野の手法を用いて符号を考察することも一つの重要な研究分野である。

− 23 −

2. 定義と基礎概念
まずは、本研究で重要となるマトロイドについて定義を行う。マトロイドとは、有限な集合EとEの部分集合族 I で次の性質をみたすものの順序対 M=(E, I )である。
（1）φ∈ I
（2）R ∈ I であり、R ’ ⊆ R ならばR ’ ∈ I が成立する。
（3）R , R ’ ∈ I であり、
│R ’│＜│R│ならば、元 e ∈ R -R ’ でR ’ ∪e ∈ I を満たすものが存在する。
ここで、I の元を独立集合と呼び、I の元でないものを従属集合と言う。また、極小の従属集合をサーキットといい、極大な独立集合を基底と言う。任意の部分集合X に対して、X の階数を次のように定める。
r (X )=max｛│Y│：Y ⊆ X, Y∈ I ｝
マトロイドMの双対マトロイドM＊を次のような集合を基底とするマトロイドとする。
｛ E -B：BはMの基底｝
特に、双対マトロイドの階数については、次の事実が知られている。
r＊(X )=│X│-r (M )+r (E -X )M=M＊のとき、マトロイドMを自己双対マトロイドと言う。
マトロイドM=( E , I )と任意の部分集合T ⊆ Eに対して、M \ T = (E- T,｛ R ⊆ E- T：R∈ I ｝)がマトロイドの構造を持つことが明白であり、このマトロイドをMのT によるdeletionと、言いMのT によるcontractionを次のマトロイドで定義する。
M/T=(M＊\ T)＊
ここで、deletionとcontractionの組み合わせM / T \ S をM のマイナーと言う。
G F (2 )=｛0,1｝を成分とするm ×n 行列 A に対して、E がA の列番号の集合であり、I がA の一次独立な列番号の集合族のとき、M [ A ] = (E , I )はマトロイドの構造を持ち、このマトロイドを、2元マトロイドと言う。
G F (2 )上のベクトルx=(x1,..., xn )と部分集合に対して、それぞれのサポートを次のように定義する。
supp(x)=｛ i：xi≠ 0 ｝
Supp(D)=∪supp(x)x∈D

C をG F (2 )上の[ n, k] 符号とする、つまり、G F (2 )上の n 次元ベクトル空間のk次元部分空間とする。ここで、1erekの各r に対して、r 番目の一般化ハミング重みを次のように定義する。
dr(C )=min｛│Supp(D)│：DはCの[n,r]部分符号｝
このパラメータは、V. Weiにより最初に導入され、以後暗号等の情報セキュリティ分野への応用も含めて符号における新たな重要なパラメータとして多くの研究者によって研究がなされている。
本研究の目的は、この値に関してマトロイド理論を適用することで、新たな限界式を証明することである。
3.2 元マトロイドに関する限界式
以下、本章では、Mを2元マトロイドとする。ここで、Mのgirthを次のように定義する。
g(M )=min｛│F│：FはMのサーキット｝− 24 −ここで、次の命題が知られている。

命題1.

Fを一様マトロイドUk, k+2と同型なマイナーを持たないマトロイドのサーキットとし、eをE-Fの要素とする。このとき、FはM/eにおいて、サーキットになるか、または、F-X1 ,..., F- XnがサーキットであるようなFの分割X1 ,..., Xnが存在するかのどちらかである。

ここで、上記の命題を用いると次の定理が証明できる。

定理2.

Mを階数がrであるような2元マトロイドとする。もしMが位数が i( reier+4)であるような従属集合を持ち、さらに、Fがサーキットか互いに共通部分を持たないいくつかのサーキットの和集合ならば、次の不等式が成立する。
2 g (M )-4er

証明：F が互いに共通部分を持たないいくつかのサーキットの和集合ならば、少なくとも２つの互いに共通部分を持たないサーキットでF に含まれるものが存在し、それらをF1, F2とする。このとき、次の不等式が成立する。
r+4r│F│r│F1│+│F2│r2 g (M )ここで、もしF の位数がr+2以上ならば、F はサーキットでない。従って、F は位数がrかr+1のサーキットであると仮定する。
（1）位数がr+1のとき
E-F の要素eに対して、M/eの階数はr-1であるから、F はM/eのサーキットではない。従って、命題1
よりM/eの2つの互いに共通部分を持たないサーキットF1, F2を用いてF = F1∪ F2とかける。このとき、以下の不等式が成立する。
r+1r│F1│+│F2│r(g (M )-1)+( g (M )-1)=2 g (M )-2（2）位数が r のとき
E-F の要素e1に対して、F がM/e1のサーキットではないならば、上記の（1）の場合と同様に定理を証明することが出来る。従って、F がM/e1のサーキットであると仮定する。e1と異なるE-F の要素e2に対して、M/e1/e2の階数はr-2であるから、F がM/e1 /e2のサーキットではなく、よって、M/e1/e2の２つの互いに共通部分を持たないサーキットF1, F2を用いてF = F1∪ F2とかける。このとき、以下の不等式が成立する。
rr│F1│+│F2│r(g (M )-2)+( g (M )-2)=2 g (M )-4（1）（2）より、定理における不等式が成立することが示せた。
,■

2元マトロイドMに対して、L ( M ) = ( T ( M ) )＊ とする。ここで、T ( M ) はM のtruncationを表す。このとき、L ( M ) のサーキットはM の異なる2つのサーキットの極小な和集合であることが知られている。また、命題1より以下の補題が直ちに証明できる。

補題3.

Mを階数がrであるような2元マトロイドとする。もし、Mが位数が i( reier+4)であるような従属集合Fを持ち、さらに、Fがサーキットか互いに共通部分を持たないいくつかのサーキットの− 25 −和集合ならば、次の不等式が成立する。
2 g (L (M ))+g (M )-8 e2r
また、条件を少し変更しても以下の補題が成立する。

補題4.

M を階数がr であるような2元マトロイドでr＊(M )r4とする。もし、M が位数がr かr + 1 であるようなサーキットF を持つならば、次の不等式が成立する。
2 g (L (M ))+g (M )-8 e2r

証明：

B をM の基底とし、F のある元e に対して、B ⊇F - e とする。このとき、B に対する2つの基本サーキットとして、F 1 = F ( e 1 , B ) とF 2 = F ( e 2 , B ) を考える。ここで、e 1 , e 2 ∈ E - B - e とし、e 1 ≠ e 2 とする。
（1）F の位数r + 1がのとき一般性を失うことなく、│F1│e( r + 3 )/2 かつ│F2│e( r + 3 )/2 であると仮定することができるので、次の不等式が成立する。
g (L (M )) e│F1∪F2│=│F1│+│F2│-│F1∩F2│er+3-│F1∩F2│
ここで、F1とF2の対称差F1ΔF2は、Fと等しくなく、従って、FΔF1ΔF2は空集合でなくMのサーキットを含む。よって、以下の不等式が成立する。
g (M )e│FΔF1ΔF2│=│F│+│F1ΔF2│-2(F∩(F1ΔF2))e2r+ 8 -2g (L (M ))m を1か2をあらわす数とする。r＊(M )r4より、│Fj - F│=mであるような2つのサーキットF1とF2を考えることが出来る。上記と同様の議論により、│F1│+│F2│er+2mと仮定することが出来る。従って以下の不等式を得る。
g (L (M )) er+2m-│F1∪F2│
よって、次の不等式を導くことが出来る。
- 1 ,e 2 ｝│e2r+8 - 2g(L (M ))g (M )e│FΔF1ΔF2│=│F│+│F1ΔF2│-2│F1ΔF2｛e■補題3と補題4を組み合わせて考えることで、次の定理を得る。

定理5.

M を階数がr であるような2元マトロイドでr＊(M )r4とする。もし、M が位数がi(reier+4)であるような従属集合F を持ち、さらに、F がサーキットか互いに共通部分を持たないいくつかのサーキットの和集合ならば、次の不等式が成立する。
2 g (L (M ))+g (M )-8 e2r

4.2 元符号に関する限界式
M を2元符号の生成行列から構成される2元マトロイドとしたとき、M のコサーキットはその符号の極小サポートに対応し、L ( M ) のコサーキットは2次元部分符号の極小サポートに対応することが知られている。ここで、A i を重みが i である符号語の個数とすると、定理2と定理5を符号理論へ適用することで以下の結果を得る。

− 26 −

系6.

C をGF(2)上の[n , k , d]符号とする。もし、n - k ei en - k + 4 であるi に対して、Ai ≠0であるならば、2 d -4 en -k が成立する。

系7.

C をGF(2)上の[n , k , d]符号でk e4 とする。もし、n - k ei en - k + 4 であるi に対して、Ai ≠0であるならば、2 d 2 + d-8 e2( n -k )が成立する。
任意の自然数n に対して、2元Krawtchouk多項式を以下のように定義する。
mn -xx(-1)n jPm(x )= Σm -jj =0
ここで、m= 0 , 1 , . . . , nである。この多項式を用いると、GF(2)上の[n , k ]符号Cとその双対符号C⊥にq wq w関して、マックウィリアムズ恒等式から以下の等式が成立する。
n2 kA⊥m =Σ Ai Pm ( i )i =0

さらに、2元Krawtchouk多項式については、以下の等式が証明されている。
nnn/2Pn/2(i )= (-1)i /2 n/2/ ii/2
ここで、nとi は偶数とする。以上の結果より、次の命題が成立することが分かる。

q wq w q w

命題8.

C をGF(2)上の[n , k , d]符号でn / 2 ek en / 2 + 4 とし、n を偶数とする。もし、双対符号C ⊥のすべての符号語の重みが4で割り切れるならば、2 d -4 en -k かつ2d 2 + d -8 e2( n -k )が成立する。

5. デザイン理論によるアプローチ
C をGF(2)上の重偶自己双対符号とする。つまり、C =C ⊥であり、すべての符号語の重みが4で割り切れるような符号であるとき、k=n/2であり、nは8の倍数であることが知られている。また、最小重みdに関しては、次の限界式が知られている。

yunde4 24 +4

特に、d=4yn/24u +4が成立する場合、極値的であると言う。
有限集合Pとその部分集合族Bに対して、次の条件を満たすとき、それらの組(P,B)をt -(ν,k,λ)デザインと言う。
(1)│P│=ν(2)任意の部分集合B∈B（ブロックと言う）に対して、│B│= k(3)任意の t 個の要素をからなるPの部分集合に対して、それを含むブロックの個数はλ個
ここで、極値的な重偶自己双対符号とデザインの間にはAssmus-Mattsonの定理と呼ばれる以下の関係が成立する。

定理

CをGF(2)上の極値的な[n,n/2,d=4yn/24u +4]重偶自己双対符号とする。ここで、P=｛1,2,...n｝とし、B iを重みが iであるようなすべての符号語のサポートの集合とすると、(P,B i )は t - (n ,i , A ii / n)デザインになる。
tt
この定理を用いて構成されたデザインとその構造を考察し、極値的な重偶自己双対符号の２番目qwqwの一般化ハミング重みに関しては、前章の限界式とあわせて考えることでそれほど大がかりな計算を行うことなく、以下の定理を証明できる。

− 27 −

もし、GF(2)上の極値的な[n,n/2,d=4yn/24u +4]重偶自己双対符号Cが8e ne 144において存在するならば、Cの2番目の一般化ハミング重み以下の表のように求めることが出来る。

定理9.

6. まとめ本研究においては、誤り訂正符号理論へマトロイド理論を適用することで、符号の構造の特徴を考察することであった。まず、マトロイドにおける限界式を証明し、それを符号へ適用することで符号の一般化ハミング重みに関する限界式を作成した。さらに、Assmus-Mattsonの定理から極値的な重偶自己双対符号から得られるデザインを考察し、限界式を用いることで符号長が144以下の符号に関しては、2番目の一般化ハミング重みの値もしくは限界式を証明することが出来た。
今後の課題としては、3番目以降の一般化ハミング重みに関しても、本研究と同様の結果を得ることと、それらを用いて存在の知られていない符号に関する存在・非存在の証明にもアプローチすることが考えられる。

謝辞：本研究は、日比科学技術振興財団の研究助成によって行われた研究である。

参考文献：[1] K. Shiromoto, Bounds for binary matroids, 第21回代数的組合せ論シンポジウム報告集,p.95〜101,
2004[2] K. Shiromoto, Second generalized Hamming weights for extremal self-dual codes, Proceedings ofthe International Workshop on Coding and Cryptography, p.11〜19, 2005

− 28 −