符号理論コミュの最良符号探索への誘い：　符号理論の基本問題

最良符号探索への誘い：符号理論の基本問題【その２】

符号長ｎが２５６以下の2元線形符号において、その情報
点数をｋ（＜２５６）とするとき、最も大きな最小距離ｄ
を有する符号の構成問題を最良符号探索問題(best code
search)と呼びます。

この最良符号の（ｎ、ｋ、ｄ）のパラメータは以下の
表（データベース）で管理されています。
Bounds on the minimum distance of linear codes
http://www.rz.uni-karlsruhe.de/~kg11/codetables/BKLC/BKLC_query.php

1948年のシャノンにおける通信路符号化定理以来の現在に
続く問題となっています。特に1960年代、70年代に大きな
成果があり、現在でも最良符号となる符号構成が発見、発
明されました。特に60年代、70年代には、日本の研究者が
多くの最良符号を発見しています。

60年代には嵩忠雄先生、たとえば
===============
(127,43,31)符号
===============
From Brouwer's table (as of 2007-02-13)Lb(125,40) = 32 is found by
shortening of:
Lb(128,43) = 32 is found by adding a parity check bit to:
Lb(127,43) = 31 BCH

Ub(125,40) = 40 is found by considering shortening to:
Ub(112,27) = 40 otherwise adding a parity check bit would contradict:
Ub(113,27) = 41 Bro

References
BCH: T. Kasami & N. Tokura, Some remarks on BCH bounds and minimum
weights of binary primitive BCH codes, IEEE Trans. Inform. Theory IT-15
(May 1969) 408-413.
Or: a BCH code.

Bro: A.E. Brouwer, The linear programming bound for binary linear codes,
IEEE Trans. Inform. Th. 39 (1993) 677-680.
=====

70年代には、杉山康夫先生, 笠原正雄先生, 平沢茂一先生,
滑川敏彦先生らです。たとえば、
===============
(156,96,17)符号
===============
From Brouwer's table (as of 2007-02-13)Lb(156,96) = 17 Su

Ub(156,96) = 26 is found by considering shortening to:
Ub(124,64) = 26 otherwise adding a parity check bit would contradict:
Ub(125,64) = 27 BK

References
BK: Detlef Berntzen & Peter Kemper, email, Feb. 1993.
Su: Y. Sugiyama, M. Kasahara, S. Hirasawa & T. Namekawa, Some efficient
binary codes constructed using Srivastava codes, IEEE Trans. Inform.
Theory IT-21 (Sep. 1975) 581-582. Y. Sugiyama, M. Kasahara, S. Hirasawa
& T. Namekawa, Further results on Goppa codes and their applications to
constructing efficient binary codes, IEEE Trans. Inform. Theory IT-22
(Sep. 1976) 518-526.
=====
90年代に入ってからは、森井昌克らがいくつかの最良符号
を発見しています。たとえば、
===============
(241,25,93)符号
===============
From Brouwer's table (as of 2007-02-13)Lb(241,25) = 93 MYI

Ub(241,25) = 106 follows by a one-step Griesmer bound from:
Ub(134,24) = 53 is found by considering shortening to:
Ub(132,22) = 53 BK

References
BK: Detlef Berntzen & Peter Kemper, email, Feb. 1993.
MYI: M. Morii, T. Yoshimura & Y. Itoh, email comm. Feb-Mar 1995.
=====
2000年代に入ると、毛利公美先生らが最良符号を数多く
登録しています。たとえば、
===============
(151,61,31)符号
===============
From Brouwer's table (as of 2007-02-13)Lb(151,61) = 31 MMT

Ub(151,61) = 42 is found by considering shortening to:
Ub(121,31) = 42 otherwise adding a parity check bit would contradict:
Ub(122,31) = 43 Bro

References
Bro: A.E. Brouwer, The linear programming bound for binary linear codes, IEEE Trans. Inform. Th. 39 (1993) 677-680.
MMT: Hideaki TANAKA, Masami MOHRI, Masakatu MORII, email, comm. Feb 2005.
=====
です。

次回から、いかにして最良符号を発見するかとう戦略について述べていくこととしましょう。

最良符号探索への誘い：符号理論の基本問題【その３】

60年代、70年代の最良符号構成はいくつかの例外を除い
て、純代数的に構成し、その符号構成で最小重みを有す
る符号の重みの下限を与えることによって、最良符号で
あることを示しています。

90年代になってからの、特に我々の最良符号構成は、代数
的な符号構成と計算機探索を併せ持った構成法となってい
ます。90年代中頃から末にかけて、10以上のパラメータで
最良符号を構成しています。2000年に入ってからの毛利公
美先生らの最良符号構成は、彼女らの開発した、巡回符号
に対する確定的高速重み分布導出法、および確率的重み分
布導出法によるところが大です。

最良符号のデータベースをみると、符号長ん、情報点数ｋ
の符号に対して２つの数値が与えられています。たとえば、
前述の(151,61,31)符号であれば、
Lb(151,61) = 31
Ub(151,61) = 42
という数字です。Lb(151,61) = 31 の意味は、符号長151、
情報点数61で現在、具体的構成法が知られている、最良符
号の最小距離は31ということです。Lbはlower boundの略
で下限です。下限という意味は、符号長151、情報点数61
の最良符号は、少なくとも最小距離31の符号だということ
です。32以上かも知れないのですが、現在知られている構
成法では、31しか実現できないという意味です。対して、
Ub(151,61) = 42という意味は、符号長151、情報点数61の
最良符号は、どのような構成法を考えたとしても、42まで
の最小距離の符号しか構成できないという意味です。最小
距離43の符号は絶対に構成できません。Ubはupper bound
の略で上限です。

上限と言うのは、最良符号を構成する際の一つの目安にな
っています。つまり、上限と下限が一致していれば、もはや
最良符号を改善することはできないという意味になります。
このことから、上限と下限が著しくかけ離れている場合、
改善できる、すなわちさらに良い符号が構成できて、最良
符号を導出できる可能性が高いと言えなくはありません。

適当に符号を作って（線形符号ですので、実際には符号の
生成行列、もしくは検査行列を適当に作って）、その最小
距離が従来と比較して、改善する、つまり新たな最良符号
となる確率は、符号長および情報点数、そしてこの上界に
よって評価されると言えます。特に上限に近い符号を構成
するほど、難しい、つまり確率的に低くなりますから、上
限からかけ離れた最小距離でも、新たな最良符号になる場
合は、確率的に高くなります。符号長と情報点数に比較し
て、上限と下限の差が大きければ、最良符号が構成できる
可能性が高いということです。

策なく、むやみに符号（生成行列、検査行列）を作っても、
たとえ上限と下限の差が大きくかけ離れていても、最良符号
を導出できる可能性はありません。探索に要する計算量が
莫大なものとなるからです。

さらに上限と下限の差が大きいだけでは、（結果的にですが）
探索を効率よくできる方法はありません。では、どの符号長
で、検査点がいくらの場合、探索に要する計算量が著しく削
減でき、かつ有限時間で解を得られる可能性が高くなるので
しょうか。

つまり、探索方法、構成方法は別として、その符号長、およ
び検査点数であれば、最良符号を構成できる可能性が高いので
しょうか。

この点について、次回に述べることとします。

最良符号探索への誘い：　最良符号構成（その１）

今年も残すところ、あとわずか、押し詰まってきました。
前回、最良符号データベースの存在とそのデータとして
の符号長ｎ、情報点数ｋの2元符号の上限と下限について
説明を与えました。上限とは理論的に構成可能な限界、
つまりその値より大きなｄ（最小距離）の符号はあり得な
いということです。また、下限とは実際に構成できた符号
です。つまり、具体的な生成行列を与えて、その最小距離
が下限の値自体、もしくはその値より大きいことを証明し
ています。

1枚目の図表は、符号長31から39、情報点数11から20まで
の最良符号表です。ただし、1997年9月現在、つまり12年
前の表です。2枚目の図表は、同じパラメータで、現在の
表になっています。ここでは、12年にわたって更新はあり
ません。1枚目の図表で、符号長36、情報点数14の最小距
離は11となっており、上界と下界が一致します。つまり、
これ以上の最良符号は存在しません。この符号についている、
Ｍｏという記号はMoriiのＭｏです。1993年に私が構成した
符号です。この構成前までは、上界は11であり、下界は
10でした。

============
Construction
============
Construction type: Mo

Construction of a linear code
[36,14,11] over GF(2):
[1]: [36, 14, 11] Linear Code over GF(2)
Construction from a stored generator matrix

last modified: 2001-01-30

=======================================
From Brouwer's table (as of 2007-02-13)
=======================================
Lb(36,14) = 11 Mo

Ub(36,14) = 11 is found by considering shortening to:
Ub(35,13) = 11 Ja

References
Ja: D.B. Jaffe, Binary linear codes: new results on nonexistence, 1996, code.ps.gz.
Mo: M. Morii, email comm., Sept. 1993.

この符号の構成法（作り方）を与えましょう。

最良符号探索への誘い：　最良符号構成（その２）

(36,14,11)符号の構成法です。その前に、改めて符号を定義しておき
ましょう。符号はn-k行n列のパリティ検査行列によって定義されます
（図表１式(1)）。このとき、符号は図表1式(2)のcを満足する、すべ
てのnビットのベクトルとなります。たとえばパリティ検査行列を図表
２式(3)のように与えれば、図表2式(4)を満たず、すべてのベクトルcが
符号となります。図表3式(5)および式(6）の7ビットのベクトルは、
すべて符号です。

最良符号探索への誘い：　最良符号構成（その３）

改めて、パリティ検査行列を図表１式(1)のように与えます。このとき、
符号長nと情報点数k、さらに検査点数n-kは与えられていますが、その
能力の重要な一つの指標である最小距離は明示されていません。最小距
離とは、任意の異なる2つの符号語のハミング距離を考えたとき、その
最小の値dです。簡単な議論からすべての組み合わせを考える必要はなく、
パリティ検査行列から生成される符号すべてのなかで、符号の重み（１
の総数）を考えて、一番小さな重みが最小距離dと等しくなっています。

上記の符号語の最小重みdとしての最小距離をパリティ検査行列に対して
陽に関連付ければ、任意のd-1列以下に関しては線形独立であり、ある
d列で初めて線形従属になる場合に相当します。つまり適当なパリティ検査
行列を持ってきたとき、上記を満足すれば、その最小距離はdとなるわけ
です。

さて、図表１式(2)のようなパリティ検査行列があったとして、任意の10列
以下に関しては線形独立であり、ある11列で初めて線形従属であったとす
れば、(36,14,11)符号が構成できたことになります。問題は如何にして、
この22行36列のパリティ検査行列（単なる2元要素の行列）を作るかという
問題になります。

一番単純な方法は、まず10列の22次元の2元ベクトルを作り、1列毎に新たな
ベクトルを生成し、条件を満足するか否かを検査し、満足すれば新たな１列を
追加し、満足しなければそれを捨て、新たなベクトルを候補とする、この検査
を繰り返していく方式です。しかし、この方法では組み合わせに関する計算量
的に破たんすることが明白です。

次に図表2式(3)のように図表１式(2)のパリティ検査行列を変形します。すな
わち行列操作によって、左単位行列を作ります。この単位行列部分は、どの
ような列ベクトルをとろうが独立であることは自明です。問題は条件を満足す
る14列のベクトルを以下に構成するかです。先ほどの単純な方法よりも幾分
簡単になっています。

なお、条件も以下のように読みかえることができます。つまり、最初の一列の
条件は、そのベクトルの重みが10以上になります。なぜならば、9以下であれば
そのベクトルとそのベクトルの１が立っている部分に対応する単位行列の列ベク
トルを加えれば０ベクトル（すべての要素が0であるベクトル）になり、１０
本以下のベクトルで一次従属になってしまいます。次の一列を選ぶ際も、やはり
同様な理由で10以上の重みが必要です。さらに先に選んだベクトルとの和となる
ベクトルの重みが9以上である必要があります。なぜならば、その2つの和のベク
トルの重みが8以下であったとすると、そのベクトルでの１が立っている部分に
対応する単位行列の列ベクトルを加えれば０ベクトルになり、合計１０本以下の
ベクトルで一次従属になるからです。これを繰り返していくと、i本目が最小距離
11を満足するための条件は、
１）i本目のベクトルは重み10以上であること。
２）そのi本から任意のj（j=<i)本を選び、その和のベクトルが重みが11-j以上。
となります。

以上を繰り返し、図表2式(4)のようにkを増加させていき、kが１４になった時点で
最良符号となります。基本的にはこの方法をベースに、1993年、この符号を構成
しました。その時に求めた14本のベクトルを図表3に与えます。

最良符号探索への誘い：　最良符号構成(補足１)

今年も残すところ、あと十数時間です。ここでは、時間を見つけては、
仕事（WORK)でもあり、趣味でもあり、ライフワーク？？？の一部分でも
ある、最良符号構成について、適当（？）に書いてきました。この問題
でも、さまざまなアプローチがあります。純粋に代数的に構成する方法
から計算機に頼って力ずくで作ってしまう（探索という言葉はこのニュ
アンスを含んでいるのですが…）方法です。

もともと数論のほうに興味があり、その中で素数と素数探索法にのめり
込んだ時期があるわけですが（主に学生の時ですが、思い出したように、
5年周期ぐらいで、効率的な素数探索法について考えたりしています）、
素数探索も当然、幾分代数的なアプローチを導入しなければ、高速な
探索など実現しません。当然ですが、リーマン予想ですら証明できない
現在、特殊なものを除いて、一般的に素数を生成することは困難です。

符号のほうも、最良符号を見つけるということだけ考えるなら、代数的に
構成するだけでなく、計算機に頼って探索するという方法も考えられます。
ただし、計算機の能力は人間の思考に比べて非力ですから、限界があり、
少し大きな問題になれば探索時間（計算量）の関係で事実上困難になって
しまいます。素数の探索法と同様、幾分代数的なアプローチを導入して、
効率的な最良符号構成（最良符号探索）を行おうとするのが、我々が以前
から行っている一つのアプローチの方法です。

実際、このアプローチが無意味でない証拠に、いくつもの（１０を超える）
最良符号を導出しています。

今回、そのアプローチの基本的方法を述べています。今までの話は基礎的な
ものですが、この考え方を少し拡張するだけで、まだまだ新たな最良符号を
導出できる可能性があります。次回以降（いつになるかわかりませんが）も
思い立ったこと（このアプローチに基づく過去に提案した方法のまとめとし
て）を書いていきます。

とりあえず、今回は図表として、(36,14,11)符号の構成法について、堅めに
書いた文章をつけておきます（こちらのほうが簡潔で分かりやすいのですが）。

最良符号探索への誘い：　最良符号構成(補足２)

前回の続き（図表）です。

最良符号探索への誘い：　最良符号を探索するためには（その１）

約３か月ぶりの御無沙汰です。前回まで最良符号とは何かという
ことと、その構成法の基本、特に問題意識としての、代数的な
符号構成と計算機探索の関係について述べてきました。

復習しますと、符号長ｎ、情報点数ｋの線形符号において、その
符号の誤り訂正に関する性能を大きく左右する最小距離ｄが最大
となる符号を構成する問題が最良符号構成問題、あるいは最良符
号探索問題と呼ばれています。特に2元符号、つまり0と1の並び
で記述される符号で、符号長256以下の符号において、その具体的
な構成方法が議論（競争）されています。線形符号であることか
ら、具体的な構成方法として、その生成行列を与えることが通例
です。

符号長256（ビット）の符号で競われる一つの理由として、従来
から、その最良符号がネットワーク上で公開されたデータベース
として管理されていることにあります。現在は、Markus Grassl
によって管理されています。そのデータベースは以下の通りです。
http://www.rz.uni-karlsruhe.de/~kg11/codetables/BKLC/BKLC_query.php

先にも紹介しましたように、我々（現在、神戸大学大学院工学研
究科電気電子工学専攻情報通信研究室）は最良符号探索に関する
研究に携わっています。今回は、Markus Grasslのデータベースを
もとに、最良符号探索を行う際に、その支援するシステム（最良
符号探索支援データベース）を公開します。このシステムは、現
在、大学院生である山崎達彦が開発したものです。まだ、一部、
未完成であり、探索可能性の評価については検討を要する部分も
残していますが、公開いたします。
http://www.websinka.net:8080/updatedb/

半年ぶりのご無沙汰です。最良符号探索再開です。山崎
くんは引退したのですが（現在も大学院生ですが、別テ
ーマに挑むことになりましたので）、新たな学生さんが
取り組むことになりましたので。
http://www.websinka.net:8080/updatedb/

ということで、予告でした。

【追伸】符号理論に関わっている人は少なくないはずな
のですが、mixiのコミュでは寂しい限りです。