HOME

特集:これからの産業社会と数学

符号理論の背後にある数学

サイバネットシステム株式会社 CTO 石塚 真一

1.はじめに

今回は、数学の特集とのことですので、工学理論の中でも特 に数学理論と関係の深い符号理論を取り上げてみようと思い ます。

符号理論、つまり「誤り制御符合(ECC:Error Control Coding)」は、デジタルと名が付くシステムには必ず使用され ていると言っても過言ではありません。CDプレーヤーが世 に出て以来、デジタルサウンドも馴染み深いものとなりまし たが、その理論的背景となっているのが、この「符号理論」です。 この理論は、CDプレーヤーの他にもDVD、携帯電話など、今 や無くてはならないツールに次々と応用され、現代生活を支 えています。

さて、符号理論は工学理論の一つであると言えますが、極度 に数学的なもので、符号理論を本当に理解するためには、「群」 「環」「体」といった抽象的な代数概念を理解しなければなり ません。そうした数学理論を一から学習する難しさが符号理 論を理解する大きな障壁になっていると思われます。しかし、 工学理論としての符号理論を見た場合は、話は逆に簡単になっ ているという面もあるのです。すなわち、工学理論は実問題に 対して仮定を設け数学を応用して解を組み立てますが、実際 に適用する際には実験値や経験値を用いて解を補正していく 必要があります。しかし、符号理論の場合、その成果をほぼそ のままの形で工学的に反映でき、技術的にもシフトレジスタ を用いて簡単に実現できるのです。また、長年の研究により実 現手法も完成しており、計算手法さえ間違わなければ、とりあ えずこの理論を実際に使え、しかも実際上困ることは少ない と言えます。さて、このように優れものである符号理論ですが、 誌面の制約もありますので、ここでは符号理論の背景にある 数学理論をごく簡単にご紹介することにします。

2.符号理論はパズルだ

2. 1 距離の概念

問題1) 数並べ その1:
1 〜 9の整数を用いて、隣り合う数(縦・横)の差が 3以上になるように3行3列のマス目を埋めなさい。

解答1) 解答例を以下に示します。


図1

これくらいであれば、次々に数を並べてみることで解答で きるでしょう、では、次の問題はどうでしょう。

問題2) 数並べ その2:
1 〜 9の整数を用いて、隣り合う数(縦・横)の差が 4以上になるように3行3列のマス目を埋めなさい。

これは非常に難しい問題で、解が見つかりません。しかし、 以下のように問題を変えてみましょう。どうなるでしょうか。

問題3) 数並べ その3:
1 〜 100の整数を用いて、隣り合う数(縦・横)の 差が4以上になるように3 行3 列のマス目を埋めな さい。

解答3) 解答例を以下に示します。


図2

この問題なら、上の解以外にいくらでも正解が見出せます ね。これは、使っても良い数の範囲が1 〜 100と多くなって いるため、つまり、数の集合が大きくなっているからです。 この問題について、使う数の集合を「10 〜 100までで10飛 びの整数を用いて…」と、小さくすることもできます。即ち {10,20,… 80,90,100}の集合を使え、という制限を加えた わけですね。この集合は数もちょうど9個となり効率が良い と言えます。今、ある集合の中で「隣り合う数の差」にも注目 していますが、実は、ここに符号理論の一つの本質があり、そ れは、このようになるべく差の大きい効率の良い集合を見つ けるということです。ここでは整数を使いましたが、実際は2 進数で展開します。この、数を2進数で表した場合の1と0の 異同の数を「ハミング距離」と呼び、符号理論では、この距離 がなるべく大きくなるように数を選択するのです。たとえば、 4と6を2進数で表現すると、

4:0100 , 6:0110 となり、両者のハミング距離は1にな ります。

2. 2 有限であること

先の問題では、整数を対象にしていましたが、整数の集合の 大きさは無限大ですので、いくらでも数の組み合わせが考え られます。つまり、いくらでもハミング距離の大きな数の組み 合わせを見つけられるということです。では、次の問題はどう でしょう。

問題4) 数並べ その4:
20以下の整数を用いて、隣り合う数(縦・横)の差がなるべく大きくなるように3行3列のマス目を埋め なさい。

こうすると、かなりパズル問題らしくなり、解答にも手こず ると思われます(数独パズルなどお好きな方は挑戦してみて ください)。

実際の符号理論では、まず最初に有限の集合を考え、それを 基に集合を拡大していき、それを「ガロア体」と称すのですが、 要は、「有限の集合」を問題にしているということを意識して おけば十分だと思います。

2. 3 割り切れること

知能テストや就職試験などでもよく出題される「仲間外れ 問題」です。

問題5) 仲間外れを探せ:
次の集合で仲間外れはどれですか?また、その理由は?
{21, 9, 15, 3, 24, 7, 12, 33, 42, 18}

解答の一例として「7」。理由は「3で割り切れないから」とい うのがありえます。

では、上の例を使って情報を表現してみましょう。情報は言 葉で、「こんにちは」という挨拶です。下記のように「こんにち は」の一文字にそれぞれ、

こ ………21
ん ………12
に ……… 9
ち ………33
は ………15

と、3で割り切れる数を割り当て、適当な伝送路を介して 送ったとします。もし、伝送路にノイズがあって、「こ…21」 が「22」と受信されたとすると、これは3で割り切れないため に誤送信であることがわかり、再送を要求するなどの措置を 採ることができます。もちろん、「こ…21」が「12」と受信され た場合は、12は3で割り切れ、また「ん」という文字が割り当 てられているため、受信側で直ちに間違いと判断することは できません。しかし、各文字に割り当てる数の差、すなわち「ハ ミング距離」を大きく取っておけば、そのように迷ったり、判 定を誤ったりする確率を低くすることができます。符号理論 の本質の2つ目は、このように「割り切れるかどうか」と、割 り切れないなら、その「余り」はどうなっているかに着目する ことにあります。

3.「 体」も簡単

3. 1 「体」って何?

さて、これまでの説明で、符号理論ではどうやら割り算が重 要な役割を果たしていそうだ、ということに気づいていただ けたのではないかと思いますが、実は、符号を構成し、その誤 りを検出・訂正するには、足し算、引き算、掛け算も自由に使 いこなす必要があります。つまり、「四則演算」の全部が必要 です。そして、話を思い切り簡単にすれば、「普通に四則演算 が行える数の集合」を「体」と呼ぶのです。たとえば、整数全体 の集合は体ではありません。「1÷3」などの答は整数の中には 無いからです。分数を用いれば、答は「1/3」です。私たちの身 近な数では、有理数・実数・複素数の集合などが体になります。

3. 2 では、「ガロア体」って何?

それほど厳密ではありませんが、今、p個の正の整数の有限 集合{0,1,2,・・・,p-1}を考えます。このとき、pを素数とす ると、この有限集合は、pを法とする演算(mod p)に関して 体を成し、これをガロア体と呼びGF(p)という記号で表しま す。ガロア体は本来は剰余類という概念を用いて、整数全体 について定義されます。剰余類とは、整数をある数pで割っ たときに、同じ余りの出る集合と考えれば良いです。たとえ ば、{0,±3,±6,±9,・・・}これは、3を法とする余り0の集 合であり剰余類の一種です。符号理論でもっとも多用される2 元符号(0と1から成る符号)を例にとれば、

とすれば良いのです。証明は省きますが、ここで、1=-1と なることに注意する必要があります。

さて、大変大雑把にまとめましたが、符号理論に使われてい る数学のエッセンスはこのくらいで十分だと思います。今は、 いろいろなソフトウェアで符号理論を実感できるようなプロ グラムがありますので、そういったものに挑戦してみるのも 良いでしょう。また、符号理論の背後にある数学に興味を持た れた方は、是非、符号理論の入門書や専門書を読んでみてくだ さい。

近年では第三世代携帯電話に採用されているターボ符号な ど、ここで述べた代数学に基づく、いわゆる代数的符号とは異 なるタイプの符号も開発されています。しかし、その場合も、 符号同士の遠さ、つまり距離を利用していることには違いあ りません。これらの新しいタイプの符号については、また機会 がありましたら解説したいと思います。

最後に、この原稿を書く際に参照した書籍を参考文献とし て挙げておきます。この中からピックアップして読んでいた だいても結構ですし、また、図書館などでご自分の興味を引 かれた関連書籍を読んでみていただいても、良いと思います。 きっと符号理論と数学の深い関連性について、さまざまな発 見が楽しめることと思います。

参考文献

1) 『誤り訂正技術とその設計手法および具体例』(日本テクノセンター,1996 年刊)

2) 石田信 『代数学入門』 (実教出版,1985 年刊)

3) 今井秀樹 『情報数学』 (昭晃堂,1996 年刊)

4) 今井秀樹 『情報理論』 (昭晃堂,1996 年刊)

5) 今井秀樹 『符号理論』 (電子情報通信学会,1994 年)

6) 岩垂好裕 『符号理論入門』 (昭晃堂,1995 年)

7) 笠原正雄/田中初一 『ディジタル通信工学』 (昭晃堂,1993 年)

5/5

(6/16)