第10章 情報理論

はじめに

情報理論は、情報の定量化、保存、伝達に関する数学的理論です。1948年のクロード・シャノンの画期的な論文により創始されたこの分野は、通信工学から始まり、今日ではデータ圧縮、暗号理論、機械学習、生物情報学など、幅広い分野で応用されています。

本章では、情報量の数学的定義から始まり、データ圧縮の理論的限界、雑音のある通信路での信頼性のある通信の可能性、そして誤り訂正符号の構成まで、情報理論の核心的な概念を体系的に学びます。これらの理論は、現代のデジタル通信システムの設計における基礎となっています。

通し例: 安全なメッセージ配送基盤 帯域制約のある環境で大量の通知やログを届けるには、圧縮率と誤り耐性を同時に考える必要があります。本章では、通し例の通信コストと信頼性をエントロピー・符号化・通信路容量の観点から読み直します。

学習目標

• 自己情報量・エントロピー・相互情報量の定義と性質を説明できる
• クラフトの不等式、接頭語符号、ハフマン符号の最適性を説明できる
• 通信路容量と通信路符号化定理（直観と代表的計算例）を説明できる
• 線形符号（生成行列、検査行列、最小距離）の基礎を説明できる
• 連続型（微分エントロピー、AWGN）への拡張の要点を述べられる

【用語の脚注】 接頭語符号（用語集）、AEP（用語集）、 相互情報量（用語集）、クラフトの不等式（用語集）、 通信路容量（用語集）、Lempel–Ziv 符号（用語集）

10.1 情報量とエントロピー

10.1.1 情報量の定義

定義 10.1 確率 p で生起する事象の自己情報量（self-information）は：

\(I(p) = -\log_2 p = \log_2(1/p)\) [bits]

性質：

1. \(0 < p \le 1\) に対して \(I(p) \ge 0\)
2. p = 1（確実な事象）のとき \(I(p) = 0\)
3. \(p_1 < p_2\) ならば \(I(p_1) > I(p_2)\)
4. 独立事象の情報量は加法的：\(I(p_1p_2) = I(p_1) + I(p_2)\)

10.1.2 Shannon エントロピー

定義 10.2 離散確率変数 X のエントロピー：

\(H(X) = -\sum_{x} p(x) \log_2 p(x) = \mathbb{E}[I(X)]\)

ここで、\(0\log_2 0 = 0\) と定義する（連続性による）。

例 10.1 二値確率変数 \(X \in \{0,1\}\)、\(\Pr[X=1]=p\) のエントロピー：

\(H(X) = -p \log_2 p - (1-p) \log_2(1-p) = h(p)\)

これを二値エントロピー関数という。h(p) は p = 1/2 で最大値 1 をとる。

直観図：二値エントロピー h(p) の曲線（底は \(\log_2\)）

定理 10.1 有限集合 \(\mathcal{X}\) 上に値を取る離散確率変数 \(X\) について：

\(0 \le H(X) \le \log_2 \lvert \mathcal{X}\rvert\)

等号は左が X が定数のとき、右が \(X\) が \(\mathcal{X}\) 上の一様分布のとき。

証明：\(\mathcal{X}\) 上の一様分布 \(U(x)=1/\lvert\mathcal{X}\rvert\) を考える。相対エントロピー（10.1.5）の非負性（情報不等式）より、 \[ \begin{aligned} D(P_X \Vert U) &= \sum_{x\in\mathcal{X}} p(x)\log_2 \frac{p(x)}{1/\lvert\mathcal{X}\rvert} \\{} &= -H(X) + \log_2 \lvert\mathcal{X}\rvert \ge 0. \end{aligned} \] よって \(H(X) \le \log_2 \lvert\mathcal{X}\rvert\)。□

10.1.3 結合エントロピーと条件付きエントロピー

定義 10.3

• 結合エントロピー：\(H(X,Y) = -\sum_{x,y} p(x,y) \log_2 p(x,y)\)
• 条件付きエントロピー：\(H(Y \mid X) = \sum_x p(x) H(Y \mid X=x)\)

定理 10.2（連鎖律）\(H(X,Y) = H(X) + H(Y \mid X)\)

証明：

\[ \begin{aligned} H(X,Y) &= -\sum_{x,y} p(x,y) \log_2 p(x,y) \\{} &= -\sum_{x,y} p(x,y) \log_2\bigl(p(x)p(y \mid x)\bigr) \\{} &= -\sum_{x,y} p(x,y) \log_2 p(x) - \sum_{x,y} p(x,y) \log_2 p(y \mid x) \\{} &= H(X) + H(Y \mid X) \end{aligned} \] □

10.1.4 相互情報量

定義 10.4 X と Y の相互情報量：

\(I(X;Y) = \sum_{x,y} p(x,y) \log_2 \frac{p(x,y)}{p(x)p(y)}\)

定理 10.3 以下の等式が成立：

1. \(I(X;Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X)\)
2. \(I(X;Y) = H(X) + H(Y) - H(X,Y)\)
3. \(I(X;Y) = I(Y;X)\)（対称性）
4. \(I(X;Y) \ge 0\)（等号は X と Y が独立）
   • 厳密には、ほぼ至る所で p(x,y) = p(x)p(y) が成り立つとき等号。

【直観（“重なり”としての理解と注意）】

• しばしば Venn 図風に、H(X), H(Y) の円の重なりが I(X;Y) と説明される。
  • \(H(X \mid Y)\) は「Y で説明できない X の不確定さ」、\(H(Y \mid X)\) も同様。
  • I(X;Y) は「X と Y の共有情報量」と見ると覚えやすい。
• ただし、エントロピーや相互情報量は測度空間上の“面積”そのものではない点に注意（特に連続の場合）。
• I(X;Y)=0 は独立に一致（非負性）。一方、線形相関が 0 でも I(X;Y)>0 となる（例：Y=X^2 のような非線形依存）。
• 連鎖律との関係：\(I(X;Y,Z) = I(X;Y) + I(X;Z \mid Y)\)。条件付きで“追加の重なり”が加算されると理解できる。

10.1.5 相対エントロピー

定義 10.5 分布 P と Q の相対エントロピー（Kullback-Leibler divergence）：

\(D(P \,\Vert\, Q) = \sum_x p(x) \log_2 \frac{p(x)}{q(x)}\)

定理 10.4（情報不等式）\(D(P \,\Vert\, Q) \ge 0\)、等号は \(P = Q\) のとき。

証明：\(\log_2\) の凹性より：

\[ \begin{aligned} -D(P \,\Vert\, Q) &= \sum_x p(x) \log_2 \frac{q(x)}{p(x)} \\{} &\le \log_2 \sum_x p(x) \cdot \frac{q(x)}{p(x)} \\{} &= \log_2 1 = 0 \end{aligned} \] □

10.1.6 エントロピーの性質

定理 10.5（条件付けによる減少）\(H(X \mid Y) \le H(X)\)、等号は \(X \perp Y\)。

定理 10.6（データ処理不等式）\(X \to Y \to Z\) がマルコフ連鎖なら：

\(I(X;Y) \ge I(X;Z)\)

10.2 情報源符号化

10.2.1 符号の定義と性質

定義 10.6 アルファベット X から符号アルファベット D への符号は、

写像 \(C: X \to D^{\ast}\)（\(D^{\ast}\) は D の有限文字列の集合）。

注意：10.1節の相対エントロピー \(D(P \,\Vert\, Q)\) の \(D\) は divergence を表す記号であり、10.2節の \(D\)（符号アルファベット）とは別物である。

定義 10.7

• 非特異符号：\(C\) は単射
• 一意復号可能：\(C\) の拡張 \(C^{\ast}: X^{\ast} \to D^{\ast}\) が単射
• 瞬時符号（prefix-free）：どの符号語も他の符号語の接頭辞でない

定理 10.7 瞬時符号 \(\subseteq\) 一意復号可能符号 \(\subseteq\) 非特異符号

10.2.2 Kraft の不等式

定理 10.8（Kraft-McMillan）D 元符号において、

符号長を \(l_1, \ldots, l_n\) とする。

1. 符号が一意復号可能ならば、\(\sum_{i=1}^{n} D^{-l_i} \le 1\) が成り立つ。
2. 逆に、\(\sum_{i=1}^{n} D^{-l_i} \le 1\) を満たす長さの組に対して、その符号長を持つ瞬時符号（prefix-free）が構成できる。

証明：

（必要性：McMillan）\(S = \sum_{i=1}^{n} D^{-l_i}\)、\(L = \max_i l_i\) とおく。任意の \(k\ge 1\) について \(S^k\) を展開すると、各項は \(k\) 個の符号語の連接に対応し、その長さは高々 \(kL\) である。一意復号可能性より、異なる \((i_1, \ldots, i_k)\) から得られる連接文字列は相異なるので、長さ \(m\) の文字列の個数は高々 \(D^m\) 個である。よって

\[ S^k = \sum_{(i_1,\ldots,i_k)} D^{-(l_{i_1}+\cdots+l_{i_k})} \le \sum_{m=0}^{kL} D^m \cdot D^{-m} = kL+1. \]

両辺の \(k\) 乗根をとり \(k\to\infty\) とすると \(S\le 1\) が従う。

（補足：瞬時符号の場合）瞬時符号では符号木が使える。\(L = \max_i l_i\) とすると、深さ \(L\) の葉は合計 \(D^L\) 個であり、長さ \(l_i\) の符号語は深さ \(L\) の葉を \(D^{L-l_i}\) 個占有する。したがって \(\sum_{i=1}^{n} D^{L-l_i} \le D^L\)、すなわち \(\sum_{i=1}^{n} D^{-l_i} \le 1\) が必要である。また、この不等式を満たす任意の符号長列に対して瞬時符号が構成できる（Kraft の不等式）。□

10.2.3 Shannon の符号化定理

定理 10.9（情報源符号化定理）

確率変数 X に対する一意復号可能な D 元符号の平均符号長 L について： \(L \ge \frac{H(X)}{\log_2 D}\)

また、\(L < \frac{H(X)}{\log_2 D} + 1\) を満たす瞬時符号が存在する。

証明：相対エントロピーの非負性を用いる。 確率分布 \(p(x)\) と \(q(x) = \frac{D^{-l(x)}}{\sum_{x^{\prime} \in X} D^{-l(x^{\prime})}}\) に対して： \(D(p \,\Vert\, q) \ge 0\) より導かれる。□

10.2.4 最適符号

Shannon 符号

符号長を \(l(x) = \lceil -\log_D p(x) \rceil\) とする。

性質：\(\frac{H(X)}{\log_2 D} \le L < \frac{H(X)}{\log_2 D} + 1\)

Huffman 符号

アルゴリズム（二元の場合）：

1. 各記号を確率付きノードとする
2. 最小確率の2ノードを選び、親ノードを作成
3. 1ノードになるまで繰り返し

定理 10.10 Huffman 符号は平均符号長を最小化する瞬時符号である。

証明：最適符号の性質を用いた帰納法による。□

10.2.5 算術符号

原理：メッセージ全体を [0,1) の部分区間として符号化。

利点：

• 記号ごとに整数ビットを割り当てる制約がない
• ブロック符号化の効果を記号ごとの処理で実現

実装上の考慮：

• 精度の管理
• アンダーフロー対策

10.2.6 ユニバーサル符号

Lempel-Ziv 符号（LZ77, LZ78）：

• 情報源の統計を知らなくても漸近的に最適
• 辞書ベースの適応的符号化

定理 10.11 定常エルゴード情報源に対して、LZ符号の圧縮率は

確率 1 でエントロピーレートに収束する。

10.3 通信路符号化

10.3.1 通信路モデル

定義 10.8 離散無記憶通信路（DMC）は、

入力アルファベット X、出力アルファベット Y、 遷移確率 \(p(y \mid x)\) で特徴付けられる。

例 10.2 二元対称通信路（BSC）：

• \(X = Y = \{0, 1\}\)
• \(p(0 \mid 1) = p(1 \mid 0) = p\)（クロスオーバー確率）
• \(p(0 \mid 0) = p(1 \mid 1) = 1 - p\)

10.3.2 通信路容量

定義 10.9 通信路の容量：

\(C = \max_{p(x)} I(X;Y)\)

定理 10.12 \(\mathrm{BSC}(p)\) の容量：\(C = 1 - h(p)\)

ここで h(p) は二値エントロピー関数。

証明：対称性より、最大化する入力分布は一様分布。 このとき \(I(X;Y) = H(Y) - H(Y \mid X) = H(Y) - h(p) \le 1 - h(p)\) □

10.3.3 Shannon の通信路符号化定理

定義 10.10 レート \(R\) の \((M, n)\) 符号：

• M 個のメッセージ
• ブロック長 n
• レート \(R = \frac{\log_2 M}{n}\)

定理 10.13（通信路符号化定理）

任意の R < C と ε > 0 に対して、十分大きな n で 誤り率 < ε となるレート R の符号が存在する。

逆に、R > C なら誤り率は 0 から離れた下界を持つ。

証明の概要（達成可能性）： ランダム符号化により、平均誤り率が小さいことを示す。 典型系列の理論と大数の法則を使用。□

10.3.4 誤り指数

定義 10.11 レート R での誤り指数：

\(E(R) = \lim_{n\to\infty} \left[-\frac{1}{n} \cdot \log_2 P_e^{(n)}\right]\)

定理 10.14 \(0 < R < C\) に対して \(E(R) > 0\)。

これは誤り率が指数的に減少することを意味する。

10.4 誤り訂正符号

10.4.1 線形符号

定義 10.12 線形符号 \(C\) は \(F_q^n\) の線形部分空間。

• n：符号長
• \(k = \log_q \lvert C\rvert\)：情報記号数（次元）
• d：最小距離

[n, k, d] 符号と表記する。

生成行列と検査行列：

• 生成行列 \(G\)（\(k \times n\)）：\(C = \{uG \mid u \in F_q^k\}\)
• 検査行列 \(H\)（\((n-k) \times n\)）：\(C = \{c \in F_q^n \mid Hc^T = 0\}\)
• \(GH^T = 0\)

10.4.2 符号の限界

定理 10.15（Hamming 限界）

最小距離 d の q 元 [n, k] 符号に対して： \(q^k \le \frac{q^n}{\sum_{i=0}^{\lfloor (d-1)/2 \rfloor} \binom{n}{i}(q-1)^i}\)

定理 10.16（Singleton 限界）

[n, k, d] 符号に対して：\(d \le n - k + 1\)

定義 10.13 \(d = n - k + 1\) を満たす符号を最大距離分離（MDS）符号という。

10.4.3 具体的な符号

Hamming 符号

• パラメータ：[2^r - 1, 2^r - r - 1, 3]
• 1誤り訂正
• 完全符号（Hamming 限界を達成）

構成：検査行列の列として、0 以外の r ビットベクトルをすべて使用。

Reed-Solomon 符号

• パラメータ：[n, k, n-k+1] over F_q（\(n \le q\)）
• MDS 符号
• バースト誤り訂正に優れる

構成：評価写像を用いる \(C = \{(f(\alpha_1), \ldots, f(\alpha_n)) \mid f \in F_q[x], \deg(f) < k\}\)

BCH 符号

• 設計距離を保証する巡回符号
• 効率的な復号アルゴリズム

10.4.4 復号アルゴリズム

症候復号

受信語 r に対して、症候 s = Hr^T を計算。 症候表を用いて誤りパターンを特定。

Reed-Solomon 符号の復号

1. 症候計算
2. 誤り位置多項式の決定（Berlekamp-Massey）
3. 誤り位置の探索（Chien search）
4. 誤り値の計算（Forney のアルゴリズム）

10.4.5 連接符号とターボ符号

連接符号：

• 内符号と外符号の組み合わせ
• 優れた性能と実装の容易さ

ターボ符号：

• 並列連接畳み込み符号
• 反復復号により Shannon 限界に接近

LDPC 符号：

• 疎な検査行列
• 信念伝播による効率的復号

10.5 連続情報理論

10.5.1 微分エントロピー

定義 10.14 連続確率変数 X の微分エントロピー：

\(h(X) = -\int f(x) \log_2 f(x)\,dx\)

注意：離散エントロピーと異なり、h(X) は負になりうる。

10.5.2 ガウス分布の特性

定理 10.17 分散 \(\sigma^2\) に制約された分布の中で、

ガウス分布 \(\mathcal{N}(\mu, \sigma^2)\) が微分エントロピーを最大化する： \(h(X) \le \frac{1}{2} \log_2(2\pi e\sigma^2)\)

10.5.3 ガウス通信路

定義 10.15 加法的白色ガウス雑音（AWGN）通信路：

\(Y = X + Z\)、\(Z \sim \mathcal{N}(0, N)\)

定理 10.18 電力制約 \(\mathbb{E}[X^2] \le P\) の下での AWGN 通信路容量：

\(C = \frac{1}{2} \log_2(1 + P/N)\) [bits/channel use]

10.5.4 帯域制限通信路

Shannon-Hartley の定理： 帯域幅 W、信号電力 P、雑音電力 N の通信路容量： C = \(W \log_2(1 + P/N)\) [bits/second]

直観図：AWGN 容量 \(C = \frac{1}{2} \log_2(1+\mathrm{SNR})\) の曲線

10.6 情報理論の応用

10.6.1 データ圧縮への応用

損失のある圧縮：

• レート歪み理論
• 量子化の最適化

例：JPEG, MP3 などの規格

10.6.2 暗号理論との関係

完全秘匿性（Shannon）： I(M;C) = 0（メッセージと暗号文が独立）

定理 10.19 完全秘匿性には \(\lvert K\rvert \ge \lvert M\rvert\)（鍵空間がメッセージ空間以上）が必要。

10.6.3 機械学習における情報理論

最大エントロピー原理： 制約を満たす分布の中でエントロピーを最大化。

情報ボトルネック法： I(X;T) を最小化しつつ I(T;Y) を最大化。

10.6.4 生物情報学での応用

配列アラインメント： 相互情報量によるモチーフ発見。

進化的距離： KL divergence による種間距離の定量化。

まとめ

• エントロピー・条件付きエントロピー・相互情報量により、不確実性と情報量を定量化できる。
• ソース符号化では、平均符号長の限界がエントロピーで与えられる（Shannon の符号化定理）。
• 通信路容量は相互情報量の最大化として定義され、誤り確率を任意に小さくできる情報率の上限となる。
• 誤り訂正符号は冗長性により誤り検出・訂正を実現し、符号化定理と結びつく。
• 連続の場合は微分エントロピーを用い、ガウス分布・AWGN 容量が基本例になる。

次章への橋渡し

情報量を定量化できるようになると、安全な通信で何を守るべきかを数学的に表しやすくなります。次章ではその延長として、計算困難性・乱数・安全性 notion を用いながら暗号の基盤を組み立てます。

補助資料を併用するなら、理論の使われ方は 付録E の第10章節、理解確認は 付録F の第10章節を参照してください。

参考文献と次の一歩

• 図版の再参照: 本章の図をまとめて見返したいときは 付録H: 図版ガイドと図一覧 を参照してください。
• 標準: Thomas M. Cover, Joy A. Thomas, 『Elements of Information Theory』. エントロピー、相互情報量、通信路容量の標準的な参照先です。
• 補助: David J. C. MacKay, 『Information Theory, Inference, and Learning Algorithms』. 符号化・推論・学習との接点まで含めて直観を補いたい読者に向いています。
• 出典メモ: 本章の中心概念は Shannon の 1948 年論文に由来します。ソース符号化と通信路符号化の定理は、その後の情報理論全体の土台です。
• 次の一歩: 情報量の視点を adversarial な通信へ持ち込むなら第11章へ進んでください。学習理論との接点を見たい読者は 付録G を併読すると射程が広がります。

  章末問題

• 代表演習と詳細解答は 付録C（第10章） を参照。

取り組み方ガイド

迷ったら次の表の順で進め、詰まったら「主に戻る節」にある定義・不等式・典型符号の構成例を先に見直してください。

基礎問題

1. 以下の確率分布のエントロピーを計算せよ： \((a) P(X) = \{1/2, 1/4, 1/8, 1/8\}\) (b) 幾何分布：\(P(X=k)=(1-p)^{k-1}p,\ k=1,2,\dots\)

2. X, Y, Z が Markov 連鎖 \(X \to Y \to Z\) をなすとき、 \(I(X;Y \mid Z) + I(X;Z) = I(X;Y)\) を証明せよ。

3. 二元対称通信路（クロスオーバー確率 0.1）において、 入力が一様分布のときの相互情報量を計算せよ。

4. {a:0.5, b:0.25, c:0.125, d:0.125} に対する Huffman 符号を構成し、 平均符号長を求めよ。

発展問題

1. Fano の不等式を証明し、通信路符号化定理の逆定理への応用を説明せよ。

2. 型（typical sequences）の理論について： (a) 弱型と強型の定義を与えよ (b) 漸近等分割性（AEP）を証明せよ

3. Slepian-Wolf の定理（分散情報源符号化）を説明し、 達成可能領域を特徴付けよ。

4. ネットワーク符号化について： (a) 最大流最小カット定理との関係を説明せよ (b) 線形ネットワーク符号の十分性を論ぜよ

探究課題

1. 量子情報理論について調査し、 von Neumann エントロピーと古典的エントロピーの違いを論ぜよ。

2. Kolmogorov 複雑性について調査し、 Shannon エントロピーとの関係を説明せよ。

3. 極符号（Polar codes）について調査し、 通信路分極現象と容量達成性を説明せよ。

4. 深層学習における情報理論的解析について調査し、 情報ボトルネック理論の応用例を示せ。