情報理論の初歩

テキスト、画像、音声などのデータをコンピューターで扱うには、\(\TT 0\) と \(\TT 1\) の並びに変換する必要があります。この変換の規則を符号、変換の操作を符号化とよびます。変換前の記号を情報源記号、変換後の記号を符号記号とよび、情報源記号1つに割り当てられる符号記号の並びを符号語とよびます。同様に、変換前後の記号の並びをそれぞれ情報源記号列、符号記号列とよびます。

たとえば、新型コロナウイルスのゲノム配列に現れる4種類の記号 \(\TT A, \TT C, \TT U, \TT G\) は、次の符号 \(C_a\) でビット列に変換できます。

符号 \(C_a\) で記号列 \(\TT{ACACGU}\) を変換すると、次の図のようになります。

このように各記号に同じ長さの符号語を割り当てた符号を固定長符号といいます。文字コードの章で学んだASCIIも7ビットの固定長符号です。記号 \(x\) の符号語を \(C(x)\)、その長さ（符号語長）を \(|C(x)|\) と表します。記号列の符号化は、各記号の符号語を順につなげるだけです。記号列 \(x_1 x_2\cdots x_k\) を符号化して得られる符号記号列を \(C^+(x_1 x_2\cdots x_k)=C(x_1)C(x_2)\cdots C(x_k)\) と書きます。

1830年代に生まれたモールス符号では、英語で最も頻度の高い \(\TT E\) に最短の符号語「・」が割り当てられています。頻度の高い記号に短い符号語を与えれば、全体の長さは短くなる——これがモールス以来のデータ圧縮の基本原理です。記号ごとに符号語の長さが異なる符号を可変長符号といいます。

10文字の記号列 \(\TT{ACAAUAACAG}\) で試してみます。この記号列では \(\TT A\) が6回と多く出現するので、\(\TT A\) に短い符号語を割り当てる次の符号 \(C_b\) を考えます。

固定長符号 \(C_a\) では20ビットだったものが16ビットになりました。情報源記号1つあたりに換算すると、記号列の平均符号語長は2ビットから16/10=1.6ビットに短くなっています。

可変長符号では、符号記号列のどこが符号語の切れ目かがわからなくなるという問題が生じます。モールス符号は符号語の間に時間的な間を入れて切れ目を表していますが、これは切れ目のための第3の記号を追加していることに他ならず、その分データ量が増えます。切れ目の記号なしで復号できる符号はどのようなものでしょうか。次の2つの符号を見てください。

符号 \(C_2\) で符号記号列 \(\TT{01001111000}\) を復号してみると、

と、少なくとも二通りに復号できてしまいます。どの符号記号列も高々一通りにしか復号できない符号を一意復号可能な符号といいます。\(C_2\) は一意復号可能でない符号であり、実用には使えません。

一方、符号 \(C_1\) で \(\TT{1000100110101}\) を復号すると、

のように、左から読み進めるだけで、先読みも後戻りもせずに記号を確定してゆけます。このような符号を瞬時符号といいます。瞬時符号であるための条件は簡単で、

ことです（語頭条件）。\(C_2\) では \(C_2(\TT a)=\TT 0\) が \(C_2(\TT d)=\TT{01}\) の語頭になっているのに対し、\(C_1\) はどの符号語も他の符号語の語頭になっていません。

この条件は、符号を符号木という木構造で表すとよく見えます。根から葉に向かって辺をたどり、分岐の上側を \(\TT 0\)、下側を \(\TT 1\) と読むと、根からの経路が符号語に対応します。語頭条件は「すべての記号が葉に配置されている」ことと同じです。

\(C_2\) では記号 \(\TT a\) が葉ではなく途中のノードにあるため、\(\TT 0\) を読んだ時点で「\(\TT a\) で確定」か「\(\TT d\) の途中」かが区別できません。瞬時符号なら、葉に到達するたびに記号を1つ確定して根に戻る、という機械的な操作で復号できます。

では、瞬時符号の中で平均符号語長を最小にするには、どのように符号語を割り当てればよいのでしょうか。この問題を解くのがハフマン符号です。アルゴリズムはとても単純です。

記号列 \(\TT{cbaccbcdacadbbc}\)（15文字）で試してみます。頻度は次のとおりです。

まず最小の \(\TT d\)(2)と \(\TT a\)(3)をまとめて頻度5のノードを作ります。次に残りの中で最小の \(\TT b\)(4)と今作ったノード(5)をまとめて頻度9のノードを、最後に \(\TT c\)(6)と(9)をまとめて根を作ります。分岐の上側の辺に \(\TT 0\)、下側に \(\TT 1\) を割り振ると、根から各葉までの辺の数字を並べたものが符号語になります。この手順を図にすると次のとおりです。

葉の側から根に向かって木を組み立てていくので、頻度の小さい記号ほど根から遠く、つまり長い符号語になります。

作り方から、すべての記号は葉に配置されるので、ハフマン符号はつねに瞬時符号です。元の記号列を符号化したときの長さは、各記号の（出現回数）×（符号語長）の合計で

となり、平均符号語長は29/15≈1.93ビットです（2ビットの固定長符号より短くなりました）。

ハフマン符号は一通りには決まりません。\(\TT 0\) と \(\TT 1\) の割り振り方を変えても各記号の符号語長は変わりません。また、頻度の同じノードが複数あるときはどれを選んでもよく、選び方によって符号語長の組が変わることもありますが、平均符号語長はどれも同じ最小値になります。

そして、ハフマン符号については次のことが証明されています（証明は専門書に譲ります）。

友人が1から8までの数を1つ思い浮かべ、あなたが「はい/いいえ」で答えられる質問で当てるとします。「5以上？」「3以上？」のように候補を半分ずつに絞れば、ちょうど3回の質問で答えが決まります。8通りから1つを知ることは、2択の答え3回分、つまり3ビット分の情報を得ることだと考えられます。候補が等確率で8通りなら、1つの候補の確率は1/8であり、\(3=\log_2 8=-\log_2\frac18\) です。

この考え方を、確率が等しくない場合にも広げたのがシャノンの定義です。確率 \(P(x)\) で生起する事象 \(x\) が起きたことを知ったとき、得られる情報量（自己情報量）を

と定義します。単位はシャノンにちなんでSh（シャノン）またはビットです。公平なコインの表が出たと知る情報量は \(-\log_2\frac12=1\) Shです。この定義は次の2つの直観を数式にしたものです。

情報源が記号 \(x_1, x_2, \ldots, x_n\) をそれぞれ確率 \(P(x_1), P(x_2), \ldots, P(x_n)\) で、毎回独立に生成するとします（記憶のない情報源）。この情報源から記号を1つ受け取るときに得られる情報量の期待値

を情報源のエントロピー（平均情報量）とよびます。確率0の項は \(0\log_2 0=0\) とする約束で扱います。エントロピーは「次に何が出るかの予測しにくさ」の平均的な大きさです。たとえば公平なコインのエントロピーは \(\frac12\cdot 1+\frac12\cdot 1=1\) Shですが、表が確率0.9で出る偏ったコインでは

と小さくなります。ほとんど表が出るとわかっているので、結果を知っても平均的にはあまり驚かないからです。\(n\) 種類の記号をもつ情報源のエントロピーは、すべての記号が等確率のとき最大値 \(\log_2 n\) をとります。

この例でハフマン符号を構成すると、符号語は \(C(\TT e)=\TT 0\), \(C(\TT a)=\TT{10}\), \(C(\TT d)=\TT{110}\), \(C(\TT b)=\TT{1110}\), \(C(\TT c)=\TT{1111}\) となり、各記号の符号語長はちょうど \(-\log_2 P(x)\) に一致します。平均符号語長も1.875ビットで、エントロピーと一致します。これは偶然ではありません。

シャノンは、エントロピーが圧縮の限界であることを証明しました。

つまり、平均符号語長はエントロピー未満にはできず、かつエントロピーに1を加えた値未満までは近づけられます。この下限 \(H(X)\) を情報源符号化におけるシャノン限界とよびます。前節の例のように、すべての生起確率が \(2^{-k}\)（\(k\) は正の整数）の形のときはハフマン符号がちょうど限界を達成し、一般のときも記号をいくつかまとめて符号化（ブロック符号化）すれば、1記号あたりの平均符号語長をいくらでも \(H(X)\) に近づけられます。

ハフマン符号の節の例でも確かめてみます。記号列 \(\TT{cbaccbcdacadbbc}\) の各記号の出現割合 \(\frac{3}{15},\frac{4}{15},\frac{6}{15},\frac{2}{15}\) を生起確率とみなすと、エントロピーは

です。ハフマン符号の平均符号語長1.93ビットは、たしかに \(1.89\leq L<2.89\) の範囲に入っています。確率が \(2^{-k}\) の形ではないため、ぴったり1.89にはなりません。

シャノン限界まで圧縮されたビット列はどのような姿をしているでしょうか。符号記号が \(\TT 0\) と \(\TT 1\) の2種類で、\(\TT 0\) の生起確率を \(p\) とすると、符号記号1つが運べる情報量は、確率 \(p\), \(1-p\) の2値情報源のエントロピーを \(p\) の関数とみたエントロピー関数

で与えられます。グラフを見ると、\(H(p)\) が最大値1をとるのは \(p=0.5\) のとき、つまり \(\TT 0\) と \(\TT 1\) が等確率で現れるときだけです。\(p=0.1\) なら \(H(0.1)\approx 0.469\) で、符号記号1つが運ぶ情報量は半分以下になります（この値は後の通信路容量でも使います）。

圧縮に使える規則性が残っていれば、まだ圧縮できる余地があります。ただし、0と1が半々に現れるだけでは「ランダム」とはいえません。01010101… も半々ですが、次のビットを簡単に予測できます。記号同士の依存関係も調べる必要があります。

十分に圧縮したファイルは、同じ方式でもう一度圧縮してもほとんど縮まないことが多く、むしろヘッダー分だけ大きくなることもあります。しかし、形式を示すヘッダーや別のモデルで捉えられる規則性が残るため、「圧縮データはランダム列と区別できない」と一般には断言できません。圧縮と暗号化も別の処理です。

英語のアルファベット26文字と空白の27記号がすべて等確率で現れるとすれば、1文字のエントロピーは \(\log_2 27\approx 4.75\) Shです。しかし実際の英文では文字の頻度に偏りがあり（\(\TT e\) や空白が多い）、さらに \(\TT t\) の後には \(\TT h\) が来やすいといった強い文脈依存があります。シャノンは1951年、英文の続きの文字を人に1文字ずつ当てさせる実験を行い、100文字ほどの文脈があれば次の1文字のもつ情報量はおよそ1 Sh（推定の上限で1.3 Sh、下限で0.6 Sh程度）まで下がると見積もりました（Shannon, Prediction and Entropy of Printed English）。最大値4.75 Shに対する差の割合を冗長度といい、上限の1.3 Shを使っても

です。シャノン自身は冗長度をおよそ75%としています。つまり英文の7割以上は、前後から予測できる冗長な部分だとみなせます（この種の推定値は、対象記号や推定方法によって文献ごとに幅があります）。日本語など他の言語でも、大きな冗長性が報告されています。冗長だからこそ、多少聞き取れなくても会話が成立し、流し読みでも大意がつかめるのです。この「冗長性はノイズへの耐性を生む」という観察が、次の話題への橋渡しになります。

ここまでは、データから冗長性を取り除く話でした。今度は逆に、冗長性をあえて足す話です。

通信路や記憶装置には、電波干渉、ディスクの傷、宇宙放射線などによるノイズが避けられません。デジタルデータでは、たった1ビットの反転がプログラムのクラッシュや暗号データの復号不能を引き起こすことがあります。

シャノンは通信を次の図のようにモデル化しました。送信者のメッセージは符号化されて通信路に送り出され、通信路ではノイズによって一部の記号が化けます。受信側は受け取った記号列を復号して、元のメッセージを取り出します。前節までの圧縮は「符号化で冗長性を除く」操作でした。ここから扱う誤り訂正は、「符号化で冗長性を足し、復号でその冗長性を使って誤りを直す」操作です。

話を単純にするため、次のモデルを考えます。送信する記号は \(\TT 0\) と \(\TT 1\) のみで、通信路を通ると、各記号は確率 \(p\) で独立に反転して（\(\TT 0\) なら \(\TT 1\) に、\(\TT 1\) なら \(\TT 0\) に化けて）受信されます。\(p\) をビット誤り率とよび、このような通信路を2元対称通信路とよびます。「対称」とは、\(\TT 0\) が \(\TT 1\) に化ける確率と \(\TT 1\) が \(\TT 0\) に化ける確率が同じ \(p\) だという意味です。

たとえば \(p=0.1\)（1割のノイズ）の通信路に白黒画像の各画素を1ビットとして通すと、左の画像は右のようになります。

必要とされる信頼性は、この例よりはるかに高いのが普通です。たとえば毎日1GBを1年間読み出すと約2.9×10¹²ビットになりますから、年間を通してどこか1ビットでも誤る確率を数%に抑えたければ、1記号あたりの誤り率を10^-14程度にまで下げる必要があります。1割も誤る通信路で、どうすればそんな信頼性を実現できるのでしょうか。

すぐ思いつくのは、同じ記号を繰り返し送ることです。\(\TT 0\) を \(\TT{000}\)、\(\TT 1\) を \(\TT{111}\) と3倍にして送り、受信側は3個ずつ区切って多数決をとります。記号列 \(\TT{01001}\) なら次のようになります（赤が水増しした分）。

これを繰り返し符号といいます。受信側で多数決をとる様子を次の図に示します。

3個のうち1個までの反転なら正しく復号でき、2個以上反転すると誤ります。2個だけ反転する確率は、どの2個かの選び方が3通りあるので \(3p^2(1-p)\)、3個とも反転する確率は \(p^3\) です。したがって復号後の誤り率は

となり、\(e_3(0.1)=0.03-0.002=0.028\) です。誤り率10%が約3%に下がりました（下図）。

反転が独立で \(0\leq p<0.5\) なら、繰り返し回数 \(N\)（多数決のため奇数とします）を増やせば、誤り率はいくらでも下げられます。しかし、ただではすみません。1ビットの情報を送るのに \(N\) 個の記号を使うので、記号1つあたりが運ぶ情報量、つまり伝送速度は

に落ちてしまいます。\(p=0.1\) の通信路で目標の誤り率10^-14を達成するには \(N=57\) が必要で、伝送速度は57分の1、つまり1GBを送るのに57GB送ることになります。これではとても使い物になりません。

このグラフが示すとおり、繰り返し符号では誤り率を0に近づけようとすると、伝送速度も0に近づいてしまいます。

シャノンが登場するまで、通信技術者の常識はこの繰り返し符号の延長線上にありました。つまり、

という見方です。信頼性と速度は際限のないトレードオフの関係にあり、「ノイズのある通信路で、速度を保ったまま誤りをほぼなくす」などということは、繰り返し符号だけからは実現できそうに見えません。これがすべての符号の限界なのでしょうか。

シャノンはこの常識を根底から覆しました。

この定理の要点は \(R<C\) という条件の意味にあります。速度を0に向かって下げ続ける必要はなく、容量 \(C\) を下回る一定の速度を保ったまま、誤り率だけを好きなだけ0に近づけられるのです。ただし、そのためには符号のブロック長を十分長くする必要があり、遅延や計算量などの代償があります。有限の長さの実用的な符号では、速度と誤り率の間のトレードオフは残ります。ここでは、各回の通信が独立な、記憶のない通信路について述べています。

次の図は、容量 \(C\) が「誤り率を限りなく0に近づけられる速度の上限」であることを示す概念図です。\(R>C\) でも、ある程度の誤りを許せば通信できます。例えば \(p=0.1\) の通信路で符号化せずに送れば、\(R=1\)、ビット誤り率0.1です。容量を超える速度の点すべてが達成不可能なわけではありません。参照：Shannon, A Mathematical Theory of Communication（1948）。

ただし、シャノンの証明は「そのような符号が存在する」ことを示す存在証明であって、実用的な符号の作り方を与えるものではありませんでした。圧縮のほうはハフマンのアルゴリズムがすぐに見つかったのと対照的に、容量に迫る実用的な誤り訂正符号は長年見つかりませんでした。1993年に発表されたターボ符号や、1960年代初めに考案されながら長く顧みられず1990年代に再発見されたLDPC符号によって限界にほぼ迫れるようになるまで、定理の発表から半世紀近くかかりました。現在では、携帯電話（5G）、Wi-Fi、QRコード、深宇宙探査機との通信まで、あらゆる場面で誤り訂正符号が働いています。傷のついたCDが再生でき、かすれたQRコードが読み取れるのは、この理論の恩恵です。

通信路容量 \(C\) の正確な定義（相互情報量の最大値）は専門書に譲り、ここでは結果だけ示します。ビット誤り率 \(p\) の2元対称通信路の容量は、エントロピー関数 \(H(p)\) を用いて

となります。直観的には、記号1つは本来1ビットの情報を運べるはずですが、受信者から見ると「受け取った記号が反転したものかどうか」という不確かさ \(H(p)\) が残るため、そのぶんを差し引いた量が実際に伝わる、と読めます。

\(p=0.1\) の通信路で3回繰り返し符号を使うと、速度は \(R=1/3\approx 0.33\) で容量0.53より小さいのに、誤り率は0.028までしか下がりませんでした。定理は、同じ速度1/3のままでも、もっと長いブロックでうまく作った符号を使えば誤り率をいくらでも小さくできる、と言っています。繰り返し符号は、容量を使い切れていない符号なのです。

では、繰り返し符号より効率のよい符号は、どのように誤りを直すのでしょうか。容量に迫る符号の仕組みは本書の範囲を超えるので、ここでは最も基本的な2つの考え方を紹介します。