Information Theory

CS专业课学习笔记

情報理論の概要、情報の表現

情報理論とは

• 情報通信の基礎となる学問，研究分野
• 1948 年の(C. E. Shannon)シャノンの論文 “A Mathematical Theory of Communication” に端を発する．
• 情報の保存: zip, lzh, DVD, CD…
• 情報の伝送:　衛星通信，携帯電話，ファクシミリ…
• 人工知能や暗号技術にも多大な影響

通信システムのモデル

情報源が発する通報を，通信路を通して宛先へ伝達する際，情報伝達の効率や信頼性について考える

実際の情報源$\cdot$通信路とモデルの対応

実際の通信システムを考えるとき，前述のモデルにどのように当てはめるかは，一意には定まらない

本科目の主題: デジタル情報源の符号化

• 情報源は記号列を出力する(デジタル情報源)
• 通信路は記号列を伝搬する(デジタル通信路)

情報理論の問題

次の二つを達成する具体的な符号化の方法とそれによってどこまで改善できるかの理論的限界を探る

• 通信路使用の効率(efficientcy)の向上
• 信頼性(reliability)の向上

情報理論が取り組む４つの問題

• 【問題1】 できるだけよい情報源符号化と復号の方法を見出す
  • 1情報源記号あたりの符号系列の長さの平均値(平均符号長という)ができるだけ小さいことが望ましい
  • 装置化が簡単で，符号化・復号による遅延が小さいほどよい
• 【問題2】情報源符号化の限界を知ること
  • 1情報源記号あたりの平均符号長をどこまで小さくできるか？
• 【問題3】できるだけよい通信路符号化と復号の方法を見出す
  • 付け加えた冗長性を信頼性向上に可能な限り有効に活用できる符号化が望ましい
  • 復号した後の記号の誤り率・冗長度の最小化
• 【問題4】通信路符号化の限界を知ること
  • 復号後の記号の誤り率をある値以下に抑えたとき，付加すべき冗長度をどこまで小さくできるか？

情報量による定量的な評価

対数をとることで情報の価値をうまく表現できる.

$$\begin{aligned} S = log_2W \end{aligned}$$

情報理論における主要な結果

• 情報源の符号化

  • データ圧縮の理論
  • zip, lzh などに応用
  • 情報源の導入
  • 平均符号長 (圧縮率)，エントロピー(entropy)による定量的な評価

• 通信路の符号化

  • 誤り訂正符号の理論
  • CD, DVD, 携帯電話, 地上波デジタル TV 放送などに応用
  • 通信による雑音の影響 = 通信路 (確率モデル) の導入
  • 伝送速度，通信路容量による定量的な評価

重要な結果: 情報源符号化定理, 通信路符号化定理

情報源符号化: 平均符号長を小さくできる(エントロピーまで圧縮可能)
通信路符号化:

• 送信者が受信者へ0,1の情報を送る
• 途中の通信路で誤りが混入する(例:$0 \rightarrow 1,1 \rightarrow 0$のように誤る))
• 元のデータに対して冗長データを追加し,雑音に対する耐性をつける

情報理論における確率の役割

情報理論では,情報の"符号化"の可能性と限界について,定量的に明らかにすることをその主な目標としている.
$\Rightarrow$現実の情報源や通信路を"確率モデル"として抽象化し,その確率モデルの数理的な性質を調べる.

確率の基礎

確率変数と確率分布

• 確率変数Xとは，標本集合Ωから実数空間$\mathbb{R}(\mathbb{R}^n)$への(確率と関連付いた)写像である
• 確率変数Xがある値になる確率を確率分布という

サイコロを振る，あるいはコインを投げる，等のように結果の集合は分かっているが，実際に行動するまでどの結果が得られるかは事前に分からない.このような行動を「確率的試行」と呼ぶ.

• 変数$X:$ ある確率的試行の結果 (確率変数)
• $\chi:X$の取りうる範囲 = 標本空間
• $x:$実際の試行で確率変数がとった値 (標本値，実現値)
• $P_r(X = x):$確率変数$X$が$x$を取る確率
  • 定義: 次の性質を満たす量$P_r(X = x)$を確率と呼ぶ
    • $^\forall x \in \chi$,$0 \leq P_r(X = x) \leq 1$
    • $\Sigma_{x \in \chi}P_r(X = x) = 1$

$X$に関する$n$個の事象$A_1,A_2,...,A_n$を考える.このと
き$A_i \cap A_j = \phi (\forall i \not= j)$であれば

$$\begin{aligned} P_r(\cup^n_{i=1}A_i) = \sum^n_{i=1}P_r(A_i) \end{aligned}$$

が成り立つ.

条件付き確率と独立性

$P(A) > 0$のとき，

$$P(B \ |\ A) = \frac{P(A \cap B)}{P(A)}$$

を，事象Aが起こったもとでの事象Bの条件付き確率と定義する．

このとき，明らかに次式が成り立つ

$$P(A \cap B) = P(A)P(B \ |\ A)$$

事象Bの起こる確率が事象Aの生起に無関係な場合，すなわち

$$P(B \ |\ A) = P(B)$$

が成り立つとき，事象Aと事象Bは独立であるという．

このとき，明らかに次式が成り立つ

$$P(B \ |\ A) = P(A)P(B)$$

情報量とエントロピー

情報量

情報には量がある

• 確率が高いことを知らされても，そのニュースは価値が低い

確率1の結果が知らされる$\Rightarrow$得られる情報量は0

• 確率が低いことを知らされたら，そのニュースは価値が高い

確率が0に近い事柄を知らされる$\Rightarrow$情報量は大！

一つの結果を知ったときの情報量

確率$p$の事象の生起を知ったときに得られる情報量を$I(p)$とすると$I(p)$は次のような性質を満たすべき

• $I(p)$は$0 < p \leq 1$で単調減少な関数である
• 確率$p_1,p_2$で起こる二つの互いに独立な事象が同時に起こる確率$p_1,p_2$について$I(p_1,p_2) = I(p_1) + I(p_2)$
• $I(p)$は$0 < p \leq 1$で連続な関数である

これらを満たす関数$I(p)$は

$$I(p) = -\log_a p$$

という形しかありえない(ただし$a > 1$)

情報量の定義

確率$p$で生起する事象が起きたことを知ったときに得られる情報$I(p)$を自己情報量と呼び

$$I(p) = -\log_a p$$

と定義する．ただし，$a$は$a > 1$の定数とする

• $a = 2$の場合，単位はビット(bit)という(確率1/2で生じる結果を知ったときの情報量 = 1 [bit])
• 自然対数で計るときはナット(nat) 1 nat $\approx$ 1.443 bit
• 10を底とする対数で計るときはハートレー(Hartley)
• もしくはディット(dit)またはデシット(decit) 1 Hartley $\approx$ 3.322 bit

平均情報量

$M$個の互いに排反な事象$a_1, a_2, \cdots, a_M$が起こる確率を$p_1, p_2, \cdots, p_M$とする(ただし，$p_1 + p_2 + \cdots + p_M = 1$)．このうち１つの事象が起こったことを知ったときに得る情報量は$-\log_2 p_i$であるから，これを平均した期待値$\overline{I}$は

$$\overline{I} = p_1(\log_2 p_1) + p_2(\log_2 p_2) + \cdots + p_M(\log_2 p_M) = -\sum_{i=1}^M p_i\log_2 p_i$$

となる．これを平均情報量(単位はビット)という

エントロピー

確率変数$X$がとりうる値が$x_1, x_2, \cdots, x_M$とし，$X$がそれぞれの値をとる確率が$p_1, p_2, \cdots, p_M$(ただし，$p_1 + p_2 + \cdots + p_M = 1$)であるとき，確率変数$X$のエントロピーを

$$H(X) = -\sum_{i=1}^M p_i\log_2 p_i$$

ビットと定義する．

エントロピーの性質

$M$個の値をとる確率変数$X$のエントロピー$H(X)$は次の性質を満たす．

• $0 \leq H(X) \leq \log_2 M$
• $H(X)$が最小値0となるのは，ある値をとる確率が1で，他の$M - 1$個の値をとる確率がすべて0のときに限る．すなわち，Xのとる値が初めから確定している場合のみである．
• $H(X)$が最大値$\log_2 M$となるのは，M個の値がすべて1/Mで等しい場合に限る

エントロピー関数

エントロピー関数とは，$0 \leq x \leq 1$で定義される関数

$$\mathcal{H}(X) = -x\log_2 x - (1 - x)\log_2 (1 - x)$$

のことをいう．

結合エントロピー

二つの情報を一度に聞いたときの情報量は？果たして$H(X,Y) = H(X) + H(Y)$だろうか？

二つの確率変数$X, Y$を考える．$X$は$x_1, x_2, \cdots, x_{M_X}$の値をとり，$Y$は$y_1, y_2, \cdots, y_{M_Y}$の値をとるものとする．確率変数の組$(X, Y)$の値が$(x, y)$となる結合確率分布を$P(x, y)$と書く.

確率変数$X$と$Y$の結合エントロピー$H(X,Y)$は

$$H(X,Y) = -\sum_{i=1}^{M_X}\sum_{j=1}^{M_Y}P(x_i,y_j)\log_2 P(x_i,y_j)$$

により定義される．これを結合エントロピーと呼ぶ．ただし，$\lbrace x_1, x_2, \cdots, x_{M_X} \rbrace$および$\lbrace y_1, y_2, \cdots , y_{M_Y} \rbrace$は，それぞれ$X$と$Y$が取りうる値の集合とする．

例題: ある日の天気$X$とコンビニのアイスクリームの売上高$Y$の結合確率分布$P(x, y)$

$P(x,y)$	Y(1万円以上)	Y(1万円未満)	$P(x)$
X(晴)	0.5	0.1	0.6
X(雨)	0.2	0.2	0.4
$P(y)$	0.7	0.3	-

$(X,Y)$の結合エントロピーは，

$$H(X,Y) = -0.5 \times \log_2 0.5 - 0.1 \times \log_2 0.1 - 0.2 \times \log_2 0.2 - 0.2 \times \log_2 0.2 \approx 1.76(bit)$$

結合エントロピーの性質

確率変数$X$と$Y$の結合エントロピー$H(X, Y)$に対し，

$$0 \leq H(X,Y) \leq H(X) + H(Y)$$

が成り立つ．また$H(X,Y)= H(X) + H(Y)$となるのは，$X$と$Y$が独立のときのみである．

条件付きエントロピー

関連情報を事前に知っていた時の情報量は？

関連する情報が既知だと，驚きは少なくなる $\Rightarrow$ エントロピーは小さくなっているはず！

確率変数$Y$で条件を付けた$X$の条件付きエントロピー$H(X\ |\ Y)$は，

$$H(X \ |\ Y) = -\sum_{j=1}^{M_Y}P(y_j)\sum_{i=1}^{M_X}P(x_i \ |\ y_j) \log_2 P(x_i \ |\ y_j)$$

により定義される．ただし，$\lbrace x_1, x_2, \cdots, x_{M_X} \rbrace$および$\lbrace y_1, y_2, \cdots, y_{M_Y} \rbrace$は，それぞれ$X$と$Y$が取りうる値の集合とする．

結合エントロピーと条件付きエントロピーの関係

$\lbrace x_1, x_2, \cdots, x_{M_X} \rbrace$および$\lbrace y_1, y_2, \cdots, y_{M_Y} \rbrace$をとりうる値の集合とする確率変数$X$および$Y$に関し，以下が成り立つ．

• $H(X \ |\ Y) = -\sum_{i=1}^{M_X} \sum_{j=1}^{M_Y} P(x_i,y_j) \log_2 P(x_i \ |\ y_j)$
• $H(X,Y) = H(X) + H(Y \ |\ X) = H(Y) + H(X \ |\ Y)$
• $0 \leq H(X \ |\ Y) \leq H(X)$
  • $H(X \ |\ Y) = H(X)$は$X$と$Y$が独立の時のみ成立
• $0 \leq H(Y \ |\ X) \leq H(Y)$
  • $H(Y \ |\ X) = H(Y)$は$X$と$Y$が独立の時のみ成立

別の情報を得ると，エントロピーは変化しないか減少する

相互情報量(mutual information)

相互情報量の定義

$$I(X;Y) = H(X) - H(X \ |\ Y)$$

と，先ほどの結合エントロピーと条件付きエントロピーの関係

$$H(X,Y) = H(X) + H(Y \ |\ X) = H(Y) + H(X \ |\ Y)$$

から，

$$\begin{aligned} I(X;Y) &= H(X) - H(X \ |\ Y) \\ &= H(X) + H(Y) - H(X,Y) \\ &= H(Y) - H(Y \ |\ X) \\ &= I(Y;X) \\ &= \sum_i \sum_j p(x_i,y_j) \log \frac{p(x_i,y_j)}{p(x_i)p(y_j)} \end{aligned}$$

が成り立つ．

• $I(X;Y)$の範囲は$0 \leq I(X;Y) \leq \min \lbrace H(X),H(Y) \rbrace$

まとめ

• 情報量
  • 確率$p$で起こる事象の自己情報量$I(p) = -\log_a p$
• エントロピー
  • 確率変数$X$の平均情報量$H(X) = -\sum_{i=1}^M p_i \log_2 p_i$
• エントロピーの性質
  • $0 \leq H(X) \leq \log_2 M$
• 結合エントロピー$H(X,Y)$
  • $H(X,Y) = -\sum_{i=1}^{M_X}\sum_{j=1}^{M_Y}P(x_i,y_j)\log_2 P(x_i,y_j)$
  • $H(X,Y) = H(X) + H(Y \ |\ X) = H(Y) + H(X \ |\ Y)$
  • $X$と$Y$が独立のとき: $H(X,Y)= H(X) + H(Y)$
• 条件付きエントロピー$H(X|Y),H(Y|X)$
  • $H(X \ |\ Y) = -\sum_{j=1}^{M_Y}P(y_j)\sum_{i=1}^{M_X}P(x_i \ |\ y_j) \log_2 P(x_i \ |\ y_j)$
  • $H(X,Y) = H(X) + H(Y \ |\ X) = H(Y) + H(X \ |\ Y)$
  • $X$と$Y$が独立のとき:
    • $H(X \ |\ Y) = H(X)$
    • $H(Y \ |\ X) = H(Y)$
• 相互情報量$I(X;Y)$
  • $I(X;Y) = H(X) - H(X \ |\ Y)$
  • $I(X;Y) = H(X) + H(Y) - H(X,Y)$
  • $I(X;Y) = H(Y) - H(Y \ |\ X)$
  • $I(X;Y) = I(Y;X)$

例題(3.1)

$X = \lbrace x_1,x_2 \rbrace, Y = \lbrace y_1,y_2 \rbrace$に対し以下の表に示すような同時確率に従う確率変数$P_{XY}(x_i,y_j)$を考える.

X/Y	$y_1$	$y_2$
$x_1$	$\frac{1}{8}$	$\frac{3}{8}$
$x_2$	$\frac{2}{8}$	$\frac{2}{8}$

(1) エントロピー$H(X), H(Y)$を求めよ

XとYの周辺確率をそれぞれ$P_x\text{と}P_y$とすれば,$P_x(x_1) = \frac{1}{2}, P_x(x_2) = \frac{1}{2}, P_y(y_1) = \frac{3}{8}, P_y(y_2) = \frac{5}{8}$となる.従って,

$$\begin{aligned} H(X) &= -\frac{1}{2} \log\frac{1}{2} - \frac{1}{2} \log\frac{1}{2} = 1 \\ H(Y) &= -\frac{3}{8} \log\frac{3}{8} - \frac{5}{8} \log\frac{5}{8} \simeq 0.9544 \end{aligned}$$

(2) 条件付きエントロピー$H(X|Y), H(Y|X)$を求めよ

$$\begin{aligned} P(X|Y) &= -\frac{1}{8} \log\frac{\frac{1}{8}}{\frac{3}{8}} - \frac{3}{8} \log\frac{\frac{3}{8}}{\frac{5}{8}} - \frac{2}{8} \log\frac{\frac{2}{8}}{\frac{3}{8}} - \frac{2}{8} \log\frac{\frac{2}{8}}{\frac{5}{8}} \simeq 0.9512 \\ P(Y|X) &= -\frac{1}{8} \log\frac{\frac{1}{8}}{\frac{4}{8}} - \frac{2}{8} \log\frac{\frac{2}{8}}{\frac{4}{8}} - \frac{3}{8} \log\frac{\frac{3}{8}}{\frac{4}{8}} - \frac{2}{8} \log\frac{\frac{2}{8}}{\frac{4}{8}} \simeq 0.9056 \end{aligned}$$

(3) 同時エントロピー$H(X, Y)$を求めよ

エントロピーの加法性より,

$$H(X,Y) = H(X) + H(Y|X) \simeq 1 + 0.9056 \simeq 1.9056$$

(4) 相互情報量$I(X; Y)$を求めよ

相互情報量とエントロピーの関係より,

$$I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) \simeq 0.0488$$

情報源のモデル

情報源の数学モデル

通報集合 (message set): 伝送したい情報の集合.名前のついた離散的な概念.{表,裏},{晴,雨,曇,雪},{$a,b,c,...,z$}等.$M$個の要素を持つ集合として次の様に書く:

$$\begin{aligned} A = \lbrace a_1,a_2,...,a_M \rbrace \end{aligned}$$

情報源 (source): 通報を定められた時点ごとに確率的に出力する.特に通報集合の大きさ(要素の個数)が$M$のとき$M$元情報源という.
このとき時点$i$の情報源の出力を$X_i(i = 1,2,...)$で表す.$X_i\text{は}a_1,a_2,...,a_M$のいずれかであるが,どれであるかは確率的に定まる,すなわち確率変数である.

結合確率分布(Joint distribution)

時点1から$n$までの出力

$$\begin{aligned} X_1,X_2,...,X_n \end{aligned}$$

を考えることが多い(これを長さ$n$の情報源系列などという).この情報源系列の統計的性質は$X_1,X_2,...,X_n$の結合確率分布(同時確率分布ともいう)

$$\begin{aligned} P_{X_1X_2...X_n}(x_1,x_2,...,x_n) = [X_1 = x_1, X_2 = x_2,...,X_n = x_n\text{となる}(\text{結合})\text{確率}] \end{aligned}$$

で完全に定まる.$P_{X_1X_2...X_n}(x_1,x_2,...,x_n)$は省略して$P(x_1,x_2,...,x_n)$と書かれることもある.

2元情報源{0,1},$n = 3$の例
$X_1,X_2,X_3$の結合確率分布

$x_1$	$x_2$	$x_3$	$P_{X_1X_2X_3}(x_1,x_2,x_3)$
0	0	0	0.648
0	0	1	0.072
0	1	0	0.032
0	1	1	0.048
1	0	0	0.072
1	0	1	0.008
1	1	0	0.048
1	1	1	0.072

一般に，結合確率$P(x_1,x_2,···,x_n)$から$X_1$の確率 $P(x_1)$を求めるには

$$\begin{aligned} P(x_1) = \sum_{x_2 \in A} ... \sum_{x_n \in A} P(x_1,x_2,...,x_n) \end{aligned}$$

を計算すればよい.これを周辺確率という.(周辺確率とは,ただ一つだけの事象が起きる確率である.)
$P(x_1,x_2)$なども同様に求められる.

$$\begin{aligned} P(x_1,x_2) = \sum_{x_3 \in A} ... \sum_{x_n \in A} P(x_1,x_2,...,x_n) \end{aligned}$$

となる.
結合確率分布が与えられれば,これに基づき様々な計算を行うことができる.例えば$X_1 = 0$となる確率$P_{X_1}(0)$は

$$\begin{aligned} P_{X_1}(0) &= \sum^1_{x_2=0} \sum^1_{x_3=0} P_{X_1X_2X_3}(0,x_2,x_3) &= 0.648 + 0.072 + 0.032 + 0.048 = 0.8 \end{aligned}$$

となることがわかる.もちろん$P_{X_1}(1) = 1 - P{X_1}(0) = 0.2$である.

周辺確率(Marginal distribution)

• 結合確率分布が与えられれば各時点の(周辺)確率分布を求めることができる.
• しかしながら$n$が大きくなると結合確率の数は爆発的に増加していく(その数は$M^n$).これら全てを考えることは現実的ではない.
• 通常は確率分布にある制約を課した情報源を考えることが多い.

情報源の分類

定常無記憶情報源 (stationary memoryless source):各時点$i$における通報の発生が同一の確率分布に従う情報源. i.i.d. (independently and identically distributed)情報源ともいう．任意の$n$について

$$\begin{aligned} P_{X_1X_2...X_n}(x_1,x_2,...,x_n) = \prod^n_{i=1}P_X(x_i) \end{aligned}$$

と書ける.この性質により$n$が大きくなり通報の数が爆発的に増加しても,その結合確率は簡単な計算により求めることができる.

定常無記憶情報源は最も簡単な情報源のモデルである. 一方現実の情報源は記憶のある情報源が多いであろう. 例えば英文を発生する情報源を考えると各時点におけるアルファベットの出現確率は独立ではない. たとえば$T$が現れればその次には$H$の出現する確率が他の場合よりも高くなる. また,$Q$のあとには$U$の現れる確率が著しく高くなる. このように連続して発生する文字の間には相関がみられ, 独立ではない.
しかしながら, 記憶のない定常情報源を考えることは, より複雑な情報源を扱う際の基本となる. この意味で極めて重要である.

確率過程

• 確率変数の列$X_1,X_2,\cdots,X_n, X_i \in A$
• 情報源記号$A$

$(x_1,x_2,\cdots,x_n) \in A^n$に対して同時確率を次式で定める.

$$\begin{aligned} P((X_1,X_2,\cdots,X_n) = (x_1,x_2,\cdots,x_n)) = P(x_1,x_2,\cdots,x_n) \end{aligned}$$

このような確率変数の列を確率過程と呼ぶ.

例: 10回のコイン投げ

$A = \lbrace 0,1 \rbrace (0:\text{表},1:\text{裏}), P(X_i = 0) = \frac{1}{2}, P(X_i = 1) = \frac{1}{2}$とし,コイン投げの表裏は各時点で独立が決まる.

$$\begin{aligned} P((X_1,X_2,\cdots,X_{10}) = P(X_1 = x_1)P(X_2 = x_2) \cdots P(X_{10} = x_{10}) = (\frac{1}{2})^{10} \end{aligned}$$

定常情報源

確率変数列の同時確率が時刻のシフトに対して変化しないとき, すなわち任意の正整数$n, k$ならびに$(x_1,x_2,\cdots,x_n) \in A^n$に対して

$$\begin{aligned} P(X_1 = x_1, X_2 = x_2,\cdots,X_n = x_n) = P(X_{1+k} = x_1, X_{2+k} = x_2,\cdots,X_{n+k} = x_n) \end{aligned}$$

が成り立つとき, この情報源を「定常である」あるいは「定常情報源」であると呼ぶ.

• 系列$x_1, x_2, \cdots, x_n$の発生する確率が時刻に応じて変化しないことを意味する.

定常無記憶情報源

コイン投げのように, 記号$A$の値をとる確率変数の列$X_1, X_2,\cdots, X_n$が互いに独立で, 同一の確率分布$Q$にしたがう場合

$$\begin{aligned} P(X_1 = x_1, X_2 = x_2,\cdots,X_n = x_n) = Q(x_1)Q(x_2) \cdots Q(x_n) \end{aligned}$$

が成り立つとき, この情報源を「定常情報無記憶源」であると呼ぶ.

• $X_i = x$となる確率は時刻によらず$Q(x)$のみによって決まる
• それ以前の系列$X_1,X_2,\cdots,X_k$には依存しない(右辺も各時点の$x_i$のみによって決まる)
• 定常情報無記憶源は「定常」である

マルコフ情報源

過去に出現したアルファベットに依存して,いま出現するアルファベットの確率が決まる. このような情報源をマルコフ (Andrei Andreyevich Markov, 1856-1922)情報源という.

任意の正整数$n$に対し, 記号$A$の値をとる確率変数列$X_1, X_2,\cdots, X_n$が全ての $(x_1, x_2,\cdots, x_n) \in A^n$ について

$$\begin{aligned} P(X_n = x_n | X_{n - 1} = x_{n - 1}, \cdots, X_1 = x_1) = P(X_n = x_n | X_{n - 1} = x_{n - 1}) \end{aligned}$$

を満足するとき, この情報源をマルコフ情報源という. さらに任意の正整数$n$ならびに任意の$x, x' \in A$に対して,

$$\begin{aligned} &P(X_n = x) = P(X_1 = x) \\ &P(X_n = x' | X_{n - 1} = x) = P(X_2 = x' | X_1 = x) \end{aligned}$$

が成り立つとき, この情報源を定常マルコフ情報源という.

マルコフ情報源では同時確率は条件付き確率の積で表すことができる.

例: 2元定常マルコフ情報源

記号$A = \lbrace 0, 1 \rbrace$をもつ2元のマルコフ情報源を考える.ある記号が出現したときに次の記号が出現する確率を以下のように定める.

$$\begin{aligned} P(0 | 0) &= 1 - a & P(1 | 0) &= a \\ P(0 | 1) &= b & P(1 | 1) &= 1 - b \end{aligned}$$

また時刻$n = 1$における確率変数$X_1$の分布を

$$\begin{aligned} P(X_1 = 0) = w \qquad P(X_1 = 1) = 1 - w \end{aligned}$$

と定める.以上によって定めた確率から確率変数の列$X_1, X_2,\cdots, X_n, X_i \in A$が発生する.

状態遷移図

• 数字の○は状態とその番号を表す
• 矢印は状態から状態への遷移を表す
• 矢印のラベル’0/a’は記号0を確率aで出力

初期状態と定常確率分布

最初の時点の確率分布(初期状態の分布)$P(X_1) = w$を定める.

• 2状態の場合では$P(X_1 = 0) = w, P(X_1 = 1) = 1 - w$
• $P(X_1 = 0) = P(X_n = 0) = w, P(X_1 = 1) = P(X_n = 1) = 1 - w$が$n = 2,3,\cdots$で成りたつ必要ある.
• 以下のように$P(X_1 = 0) = w$を導出すればよい.

$$\begin{aligned} P(X_2 = 0) &= \sum_{r = 0}^1 P(X_2 = 0, X_1 = r) \\ &= \sum_{r = 0}^1 P(X_2 = 0 | X_1 = r)P(X_1 = r) \\ &= (1 - a)w + b(1 - w) \end{aligned}$$

$P(X_2 = 0) = w$を利用すると$w = \frac{b}{a + b}$が得られる.このような$P(X_1 = 0) = \frac{b}{a + b}, P(X_1 = 1) = \frac{a}{a + b}$を定常確率分布と呼ぶ.

非定常マルコフ情報源

• $a = b = 0$だと$P(X_1 = 0) = w$が一意に定まらない
• 常に状態0もしくは状態1に滞在し続ける

まとめ

• 情報源に記憶がない(memoryless): ある時刻の通報が, それ以前の通報とは無関係に選ばれる.
• 定常(stationary)情報源: 時刻をシフトしても, 通報の確率分布が変わらない情報源

遷移確率行列($\prod$)

N個の状態$s_0, s_1, \cdots, s_{N-1}$を持つ正規マルコフ情報源を考える.状態遷移の仕方は,状態$s_i$にあるとき,次の時点で状態$s_j$に遷移する確率$p_{i,j} = P(s_j|s_i)$により決まる.これを遷移確率という.遷移確率$p_{i,j}$を(i,j)要素とする$N \times N$行列を遷移確率行列と呼ぶ.(状態数N個,行ごとに総合が1)

$$\begin{aligned} \prod = \begin{pmatrix} p_{0,0} & \cdots & p_{0,N-1} \\ \vdots & \ddots & \vdots \\ p_{N-1,0} & \cdots & p_{N-1,N-1} \end{pmatrix} \end{aligned}$$

遷移確率行列によるt時点後の遷移確率

正規マルコフ情報源の定常分布

十分時間が経過すれば,初期分布がどうであれ,状態分布は定常的な確率分布(定常分布)に落ち着く.
正規マルコフ情報源が落ち着く定常分布を

$$\mathbf{w} = (w_0,w_1,\cdots,w_{N-1})$$

とする.$w_i$は確率なので,当然ながら

$$w_0 + w_1 + \cdots + w_{N-1} = 1$$

ある時点の状態分布が定常的で$\mathbf{w}$であるとすれば,次の時点の状態分布も$\mathbf{w}$でなければならないので,$\mathbf{w}$は

$$\mathbf{w} \prod = \mathbf{w}$$

を満たさなければならない.

正規マルコフ情報源の遷移確率行列$\prod$に対しては,この式を満たす$\mathbf{w}$が唯一存在し,極限分布と一致する.

情報源符号

情報源符号化

• いかに効率よく圧縮するか
• データを小さくして保持できるか = データ圧縮

情報源符号の例(m = 4)

$a_i$	$P_X(a_i)$	$C_1$	$C_2$
$a_1$	0.6	00	0
$a_2$	0.25	01	10
$a_3$	0.1	10	110
$a_4$	0.05	11	1110

• 符号化: 記号$a_{i}$を対応する符号語へ変換する.
• 復号化: 符号語から元の通報へ復元する.
• 符号$C_1$: 符号語は$\lbrace 00,01,10,11 \rbrace$
• 符号$C_2$: 符号語は$\lbrace 0,10,110,1110 \rbrace$
• 符号$C_1,C_2$どちらが良い? $\Rightarrow$ 平均符号語長で符合を評価する.

平均符号語長

$$\begin{aligned} L(C) = E[l(X)] = \sum_{i = 1}^m P_X(a_i)l(a_i) \end{aligned}$$

$l(a_i)$:通報$a_i$から得られる符号語の符号語長とする.

例(1)
符号$C_1,C_2$について平均符号語長を計算しなさい.

$a_i$	$C_1$	$l(a_i)$	$P_X(a_i)$
$a_1$	00	2	0.6
$a_2$	01	2	0.25
$a_3$	10	2	0.1
$a_4$	11	2	0.05

$L_{(C_1)} = 2.00(bits/symbol)$

$a_i$	$C_2$	$l(a_i)$	$P_X(a_i)$
$a_1$	0	1	0.6
$a_2$	10	2	0.25
$a_3$	110	3	0.1
$a_4$	1110	4	0.05

$L_{(C_2)} = 1.60(bits/symbol)$

例(2)

$a_i$	$P_X(a_i)$	$C_1$	$C_2$	$C_3$	$C_4$	$C_5$	$C_6$
$a_1$	0.6	00	0	0	0	0	0
$a_2$	0.25	01	10	10	01	10	10
$a_3$	0.1	10	110	110	011	11	11
$a_4$	0.05	11	1110	111	111	01	0

符号$C_1,\cdots,C_6$についてそれぞれ復号して元通りに復元できるか?

情報源符号の種類

• 非特異符号: 異なる記号には異なる符号語を割り当てる.
• 一意復号可能符号: 対応する符号語から記号へ符号語の列が一意に復号できる符号.
• 語頭符号(または自己区切り符号): どの符号語も他の符号語の先頭部分と一致しない.

• 符号の包含関係:非特異符号 $\supseteq$ 一意復号可能符号 $\supseteq$ 語頭符号

語頭(prefix)

$$\begin{aligned} \text{符号語}\mathbf{C}_i = x_1^i x_2^i \cdots x_{l_i}^i \in \mathbf{C}\text{に対して}, x_1^i x_2^i \cdots x_j^i \quad 1 \leq j < l_i \text{を}(\text{符号語}\mathbf{c}_i\text{の})\text{語頭という}. \end{aligned}$$

情報源符号化の満たすべき条件

情報源符号化の満たすべき条件:

1. 一意復号可能であること, 瞬時符号が望ましい.
2. 平均符号語長が短いこと.

• 瞬時符号でないと,n文字目以降を受け取るまで,最初の復号結果すら確定できない $\Rightarrow$ 復号器内に大きなバッファが必要,大きな復号遅延の発生
• これら条件から上の6つの符号の中では$C_3$が望ましい.

瞬時復号可能性と語頭条件

符号Cが瞬時復号可能となる $\Leftrightarrow$ Cのどの符号語も,他の符号語の語頭とならないこと(語頭条件, prefix condition)

符号の木

接点(符号記号の区切り),枝(符号記号)として,各接点から２分岐(r元の場合はr分岐)させた木を符号の木という.各符号語は根から対応する接点までの経路上の符号記号の系列として求められる.

語頭条件は木で表せる

• 各符号語から枝が伸びていない = 語頭条件を満たす
• 逆に語頭条件を満たさないのは,符号語にあたる接点からさらに枝が伸びている場合

瞬時符号であるための必要十分条件:

1. 符号の木として表現したとき全ての符号語が葉に割り当てられていることである.
2. 各符号が他の符号の語頭になっていない.

クラフトの不等式(Kraft’s inequality)

情報源符号化の目標:

1. 平均符号語長が最小
2. 語頭符号$\rightarrow$クラフトの不等式を満足する

符号語長の集合が$L = \lbrace l_1, 1_2, \cdots, l_n \rbrace$であるような$r$元瞬時符号$\mathbf{C} = \lbrace c_1, c_2, \cdots, c_n \rbrace$が存在するための必要十分条件は,次式が成り立つことである.

$$\begin{aligned} \sum_{i = 1}^{n} r^{-l_i} \leq 1 \end{aligned}$$

この不等式をクラフトの不等式という.

2元符号({0,1}の符号化)の場合のクラフトの不等式

$$\begin{aligned} \sum_{i = 1}^n 2^{-l_i} \leq 1 \end{aligned}$$

注意:

1. 定理では,ある符号の符号語長がクラフトの不等式を満たすからといって,その符号が瞬時符号であることを保証している訳ではない
2. 保証していることは,クラフトの不等式を満たす符号語長であれば,そこから瞬時符号が作れる

例
符号$C_3,C_4,C_5,C_6$についてクラフトの不等式が成立するか確認せよ.

平均符号語長の限界

平均符号語長の理論的な下限

情報源が与えられたとき，一意復号可能性を保証した上で，情報源符号化によってどこまで情報源記号の平均符号長を小さくできるか？ここではその下限を与える情報源符号化定理を紹介する. すなわち, 平均符号語長をエントロピーより小さくできないことを示す.

平均符号長の限界定理

定常分布を持つ情報源Sの各情報源記号を一意復号可能なr元符号に符号化したとき,その平均符号長Lは

$$\begin{aligned} \frac{H_1(S)}{\log_2 r} \leq L \end{aligned}$$

を満たす.また,平均符号長Lが,

$$\begin{aligned} L < \frac{H_1(S)}{\log_2 r} + 1 \end{aligned}$$

となるr元瞬時符合を作ることができる.

• １記号毎でなく，いくつかの記号をまとめて符号語を割り当てることで，効率よく符号化できないだろうか？

情報源符号化定理(シャノンの第一基本定理)

情報源Sは,任意の一意復号可能なr元符号で符号化する場合,その平均符号長Lは,

$$\begin{aligned} \frac{H(S)}{\log_2 r} \leq L \end{aligned}$$

を満たす.また,任意の正数$\epsilon > 0$について平均符号長Lが,

$$\begin{aligned} L < \frac{H(S)}{\log_2 r} + \epsilon \end{aligned}$$

となるr元瞬時符合を作ることができる.(2元符号の場合,$\log_2 r = 1$)

• どんなに工夫しても,平均符号長LはエントロピーH(S)までしか改善できない(でもがんばれば,そこまではできる)

シャノンの補助定理

$q_1,q_2,\cdots,q_m$を次式を満たす任意の数とする.

$$\begin{aligned} \sum_{i=1}^m q_i = q_1 + q_2 + \cdots + q_m \leq 1 \end{aligned}$$

$q_i \geq 0(i = 1,2,\cdots,m)$かつ$P(a_i) \ne 0$の時は$q_i \ne 0$としておく.この時,

$$\begin{aligned} -\sum_{i=1}^m P(a_i)\log_{2}q_i \geq - \sum_{i=1}^m P(a_i)\log_{2}P(a_i) \end{aligned}$$

が成り立つ.等号の成立は,全ての$i=1,2,\cdots,m$について$P(a_i) = q_i$の時,またその時に限る.

情報源符号化逆定理

情報源アルファベットAの値を確率分布Pに従ってとる確率をXとする.この時,任意の語頭符号Cの平均符号語長$L(C)$をエントロピー$H(X)$より小さくすることはできません.すなわち,

$$L(C) \geq H(X)$$

が成り立つ.等号成立条件は,記号xの符号語長$l(x)$に対して,$2^{-l(x)} = P(X)$が全ての記号$x \in A$について成り立つとき.

Shannon 符号, Shannon-Fano 符号

Shannon 符号

記号x(生起確率P(x))の符号語長を

$$l(x) = \lceil -\log_2 P(x) \rceil, x \in A$$

を満足するように符号化する.ただし,$\lceil . \rceil$は天井関数である.天井関数は実数 x に対して x 以上の最小の整数と定義される(例:$\lceil 1.5 \rceil = 2$)

• 各記号$a_i$を出現確率$P(a_i)$の高い順に並べ替える
• 各記号$a_i$の符号語は以下のように割り当てる
  • 第$(i-1)$記号までに出現確率の和$\sum_{j=1}^{i-1} P(a_j)$を計算し,それを2進数に変換する
  • 得られた2進数において小数点以下$l(a_i)$桁の数を符号語にする

最良な符号

情報源逆符号化定理より$L(C) = H(X)$となるためには

$$2^{-l(x)} = P(x) \Rightarrow l(x) = -\log_2 P(x)$$

を満足すれば良い(このような符号語長を持つ符号は最良符号と呼ぶ).$-\log_2 P(x)$を理想符号語長と呼ぶが,$-\log_2 P(x)$が常に整数となるとは限らないため,天井関数$\text{「}\text{.」}$によって符号語長を定める.

Shannon-Fano符号

• 各記号$a_i$を出現確率$P(a_i)$の高い順に並べ替え(ソートする)表を作成する.
• 表を上下に分割する.ただし,確率の和がほぼ半分になるようにする.それぞれにシンボル“0”,“1”を割り当てる.
• 分割した表をさらに,確率の和がほぼ半分になるように上下に分割する.それぞれにシンボル“0”,“1”を割り当てる.
• すべての表に含まれる記号が1つになるまで3.を繰り返す
• 各記号に対して分割する際に割り当てられた“0”または“1”からなる系列をその記号の符号語とする.

情報源のエントロピーレート

情報源Xの出力列を表す確率変数を$X_1, \cdots, X_n$とする.n記号まとめて語頭符号化したときの平均符号語長の最小値$L_n^*$は

$$\frac{1}{n} H(X_1,\cdots,X_n) \leq \frac{1}{n}L_n^* \leq \frac{1}{n} H(X_1,\cdots,X_n) + \frac{1}{n}$$

を満足する.さらに情報源Xが定常情報源のときは

$$\lim_{n \rightarrow \infty} \frac{1}{n} L_n^* = H(X)$$

が成り立つ.ここでH(X)は情報源Xのエントロピーレートを表す.

例題

記号	情報源1	情報源2
$a_i$	$P(a_i)$	$P(a_i)$
$a_1$	0.25	0.25
$a_2$	0.125	0.25
$a_3$	0.5	0.25
$a_4$	0.125	0.25

(1)次の二つの情報源の2元エントロピーをそれぞれ求め, Shannon符号, Shannon-Fano符号をそれぞれ適用しなさい.

情報源1

$$\begin{aligned} H(X) &= -0.25 \log_{2}0.25 - 0.125 \log_{2}0.125 - 0.5 \log_{2}0.5 - 0.125 \log_{2}0.125 \\ &= 1.75 \end{aligned}$$

情報源2

$$\begin{aligned} H(X) &= -0.25 \log_{2}0.25 - 0.25 \log_{2}0.25 - 0.25 \log_{2}0.25 - 0.25 \log_{2}0.25 \\ &= 2 \end{aligned}$$

• Shannon符号

先排序，计算$\sum_{j=1}^{i-1} P(a_j)$后转成二进制，小数点后$l(a_i)$位即对应的符号语

• Shannon-Fano符号

先排序，然后按照概率50来上下做分割线，线以上是0，线以下是1，然后再分线，直到只有1个记号为止

(2)情報源1に対して, その記号をソートをせずに符号化したとする. このとき各符号語を求め, ソートする場合との違いを検討しなさい.

だめの例:

$a_1$と$a_3$の符号語は同じく0であるから.

ハフマン符号とLZ符号

本章では

• 最小の平均符号語長を与える語頭符号であるハフマン符号の構成法について説明する
• 情報源の確率分布を予め知られなくても、符号化する系列長が長くなるにつれて、１記号あたりの平均符号語長がエントロピーに収束するLempel-Ziv(LZ)符号について説明する

---

効率良い具体的な情報源符号化方法：ハフマン符号

ハフマン符号は１記号ずつ符号化する際，その平均符号長を最小とする効率のよい符号のことである.

拡大情報源とブロック符号化

もっと近似度を上げるために，拡大情報源という手法を導入する．Sの連続するn個の情報源記号列を情報源記号とする$q^n$元情報源をq元情報源Sのn次の拡大情報源$S^n$という．Sはいまのところ記憶のない情報源であるとしているので，Sの連続するn個の出力は互いに独立であり，その結合確率分布は

$$P(x_0,\cdots,x_{n-1}) = P(x_0) \cdots P(x_{n-1})$$

となる．

情報源Sのn次拡大情報源$S^n$の１次エントロピー$H_1(S^n)$については，

$$H_1(S^n) = nH_1(S)$$

が成り立つ．つまり，

n次に拡大された情報源の1次エントロピー：拡大される前のもとの情報源の1次エントロピーのn倍である．

拡大情報源の導入に対応してブロック符号化，つまり，

情報源から発生する記号をまとめて符号化する方法が導入される．

ブロック符号化をすることによって，平均符号長を情報源エントロピーに近づけることができる．

記号$\lbrace a1, a2 \rbrace$を発生する情報源を考える．それぞれの発生確率が 0.8, 0.2 であるとする．

$a_i, a_j$	$P(a_i,a_j)$	Fano の符号化
$a_1, a_1$	0.64	0
$a_1, a_2$	0.16	10
$a_2, a_1$	0.16	110
$a_2, a_2$	0.04	111

• このとき2個分まとめて2元符号化することで効率化できる場合がある
  • 平均符号語長は1.452(bits/2symbol) $\Rightarrow$ 0.726(bits/symbol)

この例のように一定個数の記号毎にまとめて符号化する方法をブロック符号化(block coding)といい，それにより構成される符号をブロック符号という

特に，もとの情報源Sに対し，n次拡大情報源$S^n$を考え，その上の記号に対してハフマン符号化を行う方法を，ブロックハフマン符号化(block Huffman coding)と呼ぶ

ハフマン符号の最良性

次の定理は,ハフマン符号が最良の語頭符号であることを示す

定理: ハフマン符号の平均符号語長は最小である．

ハフマン符号の構成法

各記号が下の表で与えられる確率分布で出力されるような，記憶のない５元定常情報源を考える．

情報源記号x	確率$P(x)$
A	0.55
B	0.14
C	0.06
D	0.15
E	0.1

0. まず初めに，確率の高い順に記号を並べ替える

1. 各記号に対応する符号木の葉を作る葉には確率を添えて書いておく

1. 最も確率が小さい葉を二つ選び，それを集約するためのノードを新たに作って枝で結ぶ．そのノードを新しい葉として扱い，元の二つの葉の確率を足し合わせたものを添える

1. STEP 2を，繰り返して符号木を作る．
2. 各ノードから葉へ向かう方向の２本の枝に，0と1のラベルを割り当てる．

1. 構築した符号木を用いて，根から各々の葉へ至るパスをなぞりながら，ラベルの列を符号語として記号に割り当てる

この処理過程において，符号語が符号の木の葉にだけ割り当てられているので，ハフマン符号は瞬時符号である．

例題(7.1)

情報源1:

$$\begin{aligned} L(C_1) &= 0.5 * 1 + 0.25 * 2 + 0.125 * 3 + 0.125 * 3 = 1.75 \\ H(X_1) &= -\frac{1}{2} \log_2\frac{1}{2} -\frac{1}{4} \log_2\frac{1}{4} - \frac{1}{8} \log_2 \frac{1}{8} - \frac{1}{8} \log_2 \frac{1}{8} = \frac{7}{4} \end{aligned}$$

情報源2:

$$\begin{aligned} L(C_2) &= 0.5 * 4 = 2 \\ H(X_2) &= (-\frac{1}{2} \log_2\frac{1}{2}) * 4 = 2 \end{aligned}$$

情報源3:

$$\begin{aligned} L(C_3) &= 0.3 * 2 + 0.2 * 2 + 0.16 * 3 + 0.14 * 3 + 0.13 * 3 + 0.07 * 3 = 2.5 \\ H(X_3) &= -0.3 \log_2 0.3 - 0.2\log_2 0.2 - 0.16\log_2 0.16 - 0.14\log_2 0.14 - 0.13\log_2 0.13 - 0.07\log_2 0.07 \simeq 2.4568 \end{aligned}$$

LZ符号

• ハフマン符号は最小の平均符号語長を与える
• しかし符号の構成には情報源の確率分布が必要
• 確率分布が未知でも符号を構成したい
  • そのように構成できる符号をユニバーサル符号と呼ぶ
• ユニバーサル符号としてLZ符号を扱う(正確にはLZ78 符号)

現実世界の通報系列は各通報の発生確率がわからないケースも多い

• 単純な解決法として，２スキャン方式がある
  • １回目のスキャンで各記号の発生確率を測定
  • ２回目のスキャンで符号化
  • $\Rightarrow$ 符号化遅延の発生，対応表を添付する必要性が生じる

通報の発生確率が不明でも，効率よい符号化を実現する方式：

• LZ77法
  • lha, gzip, zip, zoo 等の圧縮ツールで採用
• LZ78法
  • compress, arc, stuffit等の圧縮ツールで採用
• LZW法
  • GIF, TIFF等の画像フォーマットで採用

どのような情報源に対しても効率が良い $\Rightarrow$ ユニバーサル符号化(universal coding)

---

LZ符号は増分分解と呼ばれる方法で系列を部分列に分解し，符号語を作る

増分分解

次の 2 つの性質を有するように系列を部分列に分解することを増分分解と呼ぶ．

• 最後の部分列を除いて，分解によって得られた部分列は全て異なっている
• 最後の部分列を除いて，分解によって得られた部分列は，その部分列より前に得られた部分列の後ろに 1 記号を付け加えたものになっている

必要なビット数

• $k$番目の部分列を表す順序対$(i, x)$
• 必要なビット数は$L_k = \lceil \log_2 k \rceil + \lceil \log_2 |A| \rceil$

$k$番目の部分列を表す順序対$(i, x)$において,$i$の取りうる値は0から$k-1$までのk通り.また,xは$\lceil A \rceil$通りの値をとる.(eg.$A = \lbrace a, b, c \rbrace$)

従って,$k$番目の部分列を表すには,整数$i$を$\lceil \log_2 k \rceil$ビットの２進数で表したものの後ろに,$\lceil \log_2 |A| \rceil$ビットによる記号$x$の表示を続ければよい.これに必要なビット数$L_k$は

$$L_k = \lceil \log_2 k \rceil + \lceil \log_2 |A| \rceil$$

となり,$L_k$は符号化する系列にはよらず,情報源アルファベットが定まれば決まる.このようにして,全ての部分列を2進数で表したものを順に並べたものがLZ符号である.

LZ77方式

A. Lempel, J. Ziv により，1977年に提案された方式

通報の部分系列を，過去に出現したパターンとの最長一致により表現していく

アルゴリズム概要:

• 系列を先頭から動的にブロック化し、符号化する
• 一つのブロックを，$(i, l, x)$の３項組で表現
  • 「 $i$ 文字前から始まる長さ $l$ の系列に $x$ を追加したもの」

LZ77の符号化例

结合例题7.2一起看，分为Search Buffer和Look ahead buffer Buffer两部分，其根本就是不断的在匹配，然后不断往后继续匹配。(与前面第几个相同, 匹配几个字符, 新追加的字符)

例如图中例子，ABC进入Search Buffer后，再次出现BC发现是跟前面匹配的，再加一个D就不匹配了，于是标记为(2, 2, D)，意思是2个字符前有2个字符(BC)是匹配的，再追加新字符D。

BCD进入Search Buffer后，再次出现B发现是跟前面匹配的，再加一个D就不匹配了，于是标记为(3, 1, D)，意思是3个字符前有1个字符(B)是匹配的，再追加新字符D。

BCD进入Search Buffer后，再次出现CBCD发现是跟前面匹配的，于是标记为(6, 4, *)，意思是6个字符前有4个字符(CBCD)是匹配的。

LZ77の復号例

(0, 0, A), (0, 0, B), (0, 0, C), (2, 2, D), (3, 1, D), (6, 4, *) を復号

• 得られた符号語から，もとの通報系列を逐次構成していく

LZ77解码就很简单了，结合例题7.2，将编码的括号一个一个按照顺序解码。在解码abr之后，轮到(3,1,c)，根据3个字符前1个字符是匹配的基础上加上字符c可以得出(3,1,c)对应字符是ac，于是现在解码后的字符已经由abr增加为abr ac了。

继续看下一个编码(2,1,d)，根据2个字符前1个字符是匹配的基础上加上字符d可以得出(2,1,d)对应字符是ad，于是现在解码后的字符已经由abrac增加为abrac ad了。

继续看下一个编码(7,4,r)，根据7个字符前4个字符是匹配的基础上加上字符r可以得出(7,4,r)对应字符是abrar，于是现在解码后的字符已经由abracad增加为abracad abrar了。

继续看下一个编码(3,2,y)，根据3个字符前2个字符是匹配的基础上加上字符y可以得出(3,2,y)对应字符是ray，于是现在解码后的字符已经由abracadabrar增加为abracadabrar ray了。

---

LZ77問題点: 整数値の表現をどうする？

• 大きな整数は，それなりに大きな表現長となってしまう
• 表現長を超えるようなブロックは，分割して表現する必要あり
  • LZ78 法に比べると，若干の効率ロスがある

LZ78方式

A. Lempel, J. Ziv により，1978年に提案された方式

• パターンを，$(i, l, x)$ の３項組ではなく，$(b, x)$ の２項組で表現
  • 「 $b$ 個前のブロックに，文字 $x$ を追加したもの」

LZ78の符号化例

$A = \lbrace a,b,c \rbrace$として,系列

$$aacabbcacababcabcbc$$

をLZ符号化しなさい.ただし,符号化の際,aは00,bは01,cは10という2進列で表すことにする.

output	index	string
(0,a)	1	a
(1,c)	2	ac
(1,b)	3	ab
(0,b)	4	b
(0,c)	5	c
(2,a)	6	aca
(4,a)	7	ba
(4,c)	8	bc
(3,c)	9	abc
(8,$\epsilon$)	10	bc

The compressed message is (0,a),(1,c),(1,b),(0,b),(0,c),(2,a),(4,a),(4,c),(3,c),(8,$\epsilon$)

$$\begin{aligned} L_1 = \lceil \log_2 1 \rceil &+ \lceil \log_2 |3| \rceil = 2 \\ L_2 = \lceil \log_2 2 \rceil &+ \lceil \log_2 |3| \rceil = 3 \\ L_3 = \lceil \log_2 3 \rceil &+ \lceil \log_2 |3| \rceil = 4 \\ &\vdots \\ L_9 = \lceil \log_2 9 \rceil &+ \lceil \log_2 |3| \rceil = 6 \\ L_{10} = \lceil \log_2 10 \rceil &+ \lceil \log_2 |0| \rceil = 4 \end{aligned}$$

これらの組を2進数で表せば($k = 1$番目における順序対の変数$i$は必ず0になるため省略している)

$$00 | 1, 10 | 01, 01 | 00, 01 | 000, 10 | 010, 00 | 100, 00 | 100, 10 | 0011, 10 | 1000$$

最終的な符号語は以下の通りである.

$$0011001010001000100100010000100100011101000$$

需要注意的是新出现的单个字符是(0,新字符)，LZ78编码的括号只有两部分: (与前面第x个相同字符串部分，新追加的不同的字符)。编码时记得给每一个部分都标上顺序(index)，以此记录该部分是第几个。

注意，得到序列对$(i, x)$后，需要转换为2进制，这个地方略麻烦。

竖线是分割线的意思，逗号左边是字符块的序号(index)，右边是字符的记号.

特别注意：

• 逗号左右两边的index和记号全部转换成2进制表示，且左侧index的2进制需要的位数要根据$L_k = \lceil \log_2 k \rceil + \lceil \log_2 |A| \rceil$确定(k代表第几个序列对)
• 最左边只有00是因为index的2进制数因为等于0而省略了！(第一个序列对$i$必定是0)

LZ78の復号例

$A = \lbrace a,b,c,d \rbrace$の系列をLZ符号化して次の符号語を得た.

$$001010011001000001011001011100110010100$$

この符号語を復号して符号化した系列を復元しなさい.ただし,aは00,bは01,cは10,dは11という2進列に符号化したとする.

区切りを入れて符号語を部分列に分割すると(从最左边由$\log_2 |A|$一点一点向右划分即可)

$$00 \ |\ 1,01 \ |\ 00,11 \ |\ 00,10 \ |\ 000,01 \ |\ 011,00 \ |\ 101,11 \ |\ 001,10 \ |\ 0101,00$$

となる.ただし、 | は部分列の区切りを、 , は各部分列における部分列の番号と記号との区切りをそれぞれを表す.各区切りを部分列の番号と記号の組で表すと,

$$(0,a),(1,b),(0,d),(0,c),(0,b),(3,a),(5,d),(1,c),(5,a)$$

output	index	string
a	1	a
ab	2	ab
d	3	d
c	4	c
b	5	b
da	6	da
bd	7	bd
ac	8	ac
ba	9	ba

従って,復号した結果は

$$a \ ab \ d \ c \ b \ da \ bd \ ac \ ba$$

---

LZ78方式

• LZ77法より，符号語がコンパクト
• 一符号語が表現するブロックサイズに，上限がない
  • LZ77 法よりも，若干優れた効率を発揮

例题(7.2)

LZ77符号について調べ符号化$\cdot$復号の手順を述べよ.簡単な例に対し,符号化および復号を実行し途中経過および結果を示せ.

LZ77符号化: データを先頭から順番に符号化していく方式である.現在注目している位置から始まる記号列が,それ以前に出現していたかを探す.もし出現していたならば,記号列をその出現位置と長さのポインタに置き換える.記号列を探す範囲をスライド窓と呼ぶ.<滑动窗口中的偏移量（从头部到匹配开始的前一个字符）, 匹配中的符号个数, 匹配结束后，前向缓冲区中的第一个符号>

LZ77復号:Decoder keeps same dictionary window as encoder.For each message it looks it up in the dictionary and inserts a copy at the end of the string.

LZ符号の平均符号語長

$LZ$符号を用いて情報源アルファベット$A$上の確率分布$P$を有する定常無記憶情報源からの出力列$x_1, x_2, \cdots, x_n$を符号化するとき，符号語長$L(x_1, x_2, \cdots, x_n)$は

$$\frac{1}{n} \times L(x_1, x_2, \cdots, x_n) \leq -\frac{1}{n} \log_2 P(x_1, x_2, \cdots, x_n) + \delta_n$$

を満足する．さらに平均符号語長は

$$\frac{1}{n} E[L(x_1, x_2, \cdots, x_n)] \leq H(X) + \delta_n$$

を満足し，次式が成り立つ．

$$\lim_{n \rightarrow \infty} \frac{1}{n} E[L(x_1, x_2, \cdots, x_n)] = H(X)$$

これから,系列長を長くしたとき,LZ符号の１記号あたりの符号語長はエントロピーに収束することが分かる.

典型系列とその性質

本章では

• 確率論でよく知られている大数の法則について説明する
• 大数の法則に対応する情報理論の概念である漸近等分割性について説明する
• 漸近等分割性に基づいて,典型系列と呼ばれる系列を定義し,典型系列の性質を明らかにすると共に,典型系列が確率変数列の符号化においてどのような役割を果たすのかについて説明する

大数の法則

$A$を実数の有限集合とし,$(X_1,X_2, \cdots, X_n)$を$A$上の同一の確立分布$P$に従う互いに独立な$n$個のの列とする.この時,任意に定めた小さな数$\epsilon > 0$に対し,

$$P(|\frac{1}{n} \sum_{i=1}^n X_i - E[X]| > \epsilon) \leq \frac{V[X]}{n\epsilon^2}$$

が成り立つ.ただし,$E[X]$と$V[X]$は確立分布$P$に従う確立変数$X$の平均と分散を表し

$$E[X] = E[X_1] = E[X_2] = \cdots = E[X_n]$$

並びに

$$V[X] = V[X_1] = V[X_2] = \cdots = V[X_n]$$

が成り立つ.

---

チェビシェフの不等式(Chebyshev’s inequality)

$$P(|X- E[X]| \geq k) \leq \frac{V[X]}{k^2}$$

漸近等分割性(AEP)

$(X_1,X_2,\cdots,X_n)$を$A$上の同一確率分布$P$に従う,互いに独立な$n$個の確率変数列とする.この時,任意に定めた小さな$\epsilon > 0$に対し

$$P(|-\frac{1}{n} \log P(X_1,X_2,\cdots,X_n) - H(X)| > \epsilon) \rightarrow 0 \quad (n \rightarrow \infty)$$

が成り立つ.ただし,$H(X)$は確率分布$P$に従う確率変数$X$のエントロピーを表す.

$AEP$は$-\frac{1}{n} \log P(X_1,X_2,\cdots,X_n)$が$n \rightarrow \infty$に従い$H(X)$に収束することを意味している

典型系列

任意に定めた小さな$\epsilon > 0$と,$A$上の同一確率分布$P$に従う,互いに独立な$n$個の確率変数の列を考える.この時,系列$(x_1,x_2,\cdots,x_n)$の生起確率が

$$2^{-n (H(X) + \epsilon)} \leq P(x_1,x_2,\cdots,x_n) \leq 2^{-n (H(X) - \epsilon)}$$

を満足するとき,典型系列と呼ぶ.ただし,

$$P(x_1,x_2,\cdots,x_n) = P(x_1) P(x_2) \cdots P(x_n)$$

であり,$H(X)$は確率分布$P$に従う確率変数$X$のエントロピーを表す.また,典型系列の集合を$A_{\epsilon}^n$によって表す.

• 典型系列に属する系列は$\epsilon$-典型系列と呼ぶ

典型系列の性質

$(x_1,x_2,\cdots,x_n) \in A_{\epsilon}^n$ならば,

$$H(X) - \epsilon \leq -\frac{1}{n} \log P(x_1,x_2,\cdots,x_n) \leq H(X) + \epsilon$$

が成り立つ.

十分大きなnについて

$$P(A_{\epsilon}^n) \geq 1 - \epsilon$$

が成り立つ.すなわち,$A_{\epsilon}^n$に属する系列はほぼ確率1で生じる

典型系列の総数は

$$|A_{\epsilon}^n| \leq 2^{n (H(X) + \epsilon)}$$

を満足する

十分大きなnに対し,典型系列の総数は

$$|A_{\epsilon}^n| \geq (1 - \epsilon)2^{n (H(X) - \epsilon)}$$

を満足する

この性質から

• $A_{\epsilon}^n$に属する個々の典型系列の生起確率は$P(x_1,x_2,\cdots,x_n) \simeq 2^{-nH(X)}$である
• 典型系列の総数は$|A_{\epsilon}^n| \simeq 2^{nH(X)}$である
• 典型系列のいずれかが生じる確率は$P(A_{\epsilon}^n) \simeq 1$を満足する
• 典型系列以外の系列が生じる確率がほぼゼロである

---

典型系列に関するまとめ

十分大きな$n$に対し

• 分布$P$にしたがい $i.i.d.$ な系列$X_1, \cdots, X_n$を発生したとき，得られる系列は非常に高い確率で典型である．その確率は $2^{-nH(X)}$に非常に近い値である
• 典型系列の要素数は$2^{nH(X)}$に近い値である(確率の逆数)

典型系列の性質を用いて，以下が証明できる．

• 情報源符号化 (データ圧縮の限界)
• 通信路符号化 (誤り訂正符号の限界)

典型系列の応用(情報源符号化)

目標

• 情報源から発生した系列(分布$P$にしたがい $i.i.d.$ な系列)$X_1, \cdots, X_n$をデータ圧縮する
• 情報源として，例えば英語のテキストならば$A = \lbrace a b \cdots z , . space ; @ \# \rbrace \quad |A| = 32$
• 情報源のエントロピー$H(X)$は既知とする
• $H(X)$は各記号の出現頻度から推定可能

表現

• 長さ$n$で$|A|^n$通りの系列パターンを用意する
• それらのリストに番号付けする$\lbrace 0, 1, \cdots, |A|^n - 1 \rbrace$(用意するビット数$\lceil \log_2 |A|^n \rceil$)
• 系列あたりのビット数は$n \lceil \log_2 |A| \rceil$

典型系列を用いたデータ圧縮

• 記号集合 $A$ から記号が $n$ 個発生
  • 集合 $A^n$ で全体の円を表す
  • 集合 $A^n$ の要素数 $|A^n|$ は $|A^n| = |A|^n$
• 典型系列は $A_{\epsilon,n}$ で表す
  • 集合 $A_{\epsilon,n}$ で $A^n$ の部分集合である
  • 集合 $A_{\epsilon,n}$ の要素数 $|A_{\epsilon,n}| = 2^{n(H(X) + \epsilon)}$

集合の大きさで見れば $A_{\epsilon,n}$ が全体に占める割合は小さいが，ほぼ確率 1 で $A_{\epsilon,n}$ の要素いずれかが発生する．

圧縮方法

• 最大で $2^{n(H(X) + \epsilon)}$ 通りの $\epsilon$-典型系列がある
• $A_{\epsilon,n}$ に含まれるそれぞれの系列に対し番号付けをする (用意するビット数 $\lceil \log_2 2^{n(H(X) + \epsilon)} \rceil$)．これらの系列の先頭に 0 を付与
• 典型系列あたりのビット数は$\lceil n(H(X) + \epsilon) \rceil + 1 \leq n(H(X) + \epsilon) + 2$
• $A_{\epsilon,n}$ に含まれないそれぞれの系列に対し番号付けをする (用意するビット数 $\lceil \log_2 |A|^n \rceil$)．これらの系列の先頭に 1 を付与
• 典型系列あたりのビット数は$\lceil n \log_2 |A|^n \rceil + 1 \leq n \log_2 |A| + 2$

上記の方法によって $A^n$ に含まれる系列に対しそれぞれ異なる符号語を割り当てることができる．

平均符号長の導出

$\mathcal{l}(X^n):$ 系列 $X^n$ に割り当てられた符号語の長さ

$$\begin{aligned} E[\mathcal{l}(X^n)] &= \sum_{x^n \in A^n} P(x^n) \mathcal{l} (x^n) \\ &= \sum_{x^n \in A_{\epsilon,n}} P(x^n) \mathcal{l} (x^n) + \sum_{x^n \notin A_{\epsilon,n}} P(x^n) \mathcal{l} (x^n) \\ &\leq \sum_{x^n \in A_{\epsilon,n}} P(x^n) (n(H(X) + \epsilon) + 2) + \sum_{x^n \notin A_{\epsilon,n}} P(x^n) (n \log_2 |A| + 2) \\ &\leq 1 \times n(H(X) + \epsilon) + \epsilon \times n \log_2 |A| + 2 \\ &= n(H(X) + \epsilon^{'}) \end{aligned}$$

ここで,$\epsilon^{'} = \epsilon + \epsilon \log_2 |A| + \frac{2}{n}$である．$\epsilon^{'}$ を小さくするには $\epsilon$ を十分小さくすればよい．そして $n$ を十分大きくすることで成り立つ．

従って.この符号化の平均符号語長の上限が$nH(X)$にいくらでも近づくことが分かる

圧縮の限界

典型系列を利用した符号化の定理

$X^n = (X_1, X_2, \cdots, X_n)$を$A$上の同一確率分布$P$に従う.互いに独立な確率変数列とする.任意に小さい$\epsilon^{'} > 0$を定めたとき,$n$を十分に大きくすることで,平均符号語長が

$$E(\frac{1}{n} L(X^n)) < H(X) + \epsilon^{'}$$

を満足するように,この確率変数列を符号化することができる.

この定理は,確率変数列$X^n$を平均$nH(X)$ビットを用いて表せること.すなわち$X^n$の表示においては本質的に典型系列$A_{\epsilon}^n$のみを考慮すれば良い.

---

事実 $H(X)$ より低い圧縮率で圧縮はできない (無歪圧縮の場合)．すなわち圧縮した系列を一意に復号できる符号は次式を満足する．

$$E(\frac{1}{n} L(X^n)) \geq H(X)$$

エントロピーは無歪圧縮の理論的な限界である

• このような方法は実用的ではない.なぜなら膨大な数の符号語 (系列) のパターンを記憶しないといけないため
• 実用的な方法としてハフマン符号化や LZ 符号化が挙げられる

例题(8.1)

$\chi = \lbrace 0,1 \rbrace$として$\chi$上の確率分布Pを

$$P(X = 0) = \frac{1}{3} \qquad P(X = 1) = \frac{2}{3}$$

とする.確率分布Pにしたがい $i.i.d.$ で発生する.長さnの系列($X_1, X_2, \cdots, X_n$)によって定義される典型的系列$A_{\epsilon,n}$を考える.このとき$\epsilon = \frac{1}{6}, n = 3$として次の問題を解け.

(1)$\epsilon$-典型系列を全て示せ.

$$\begin{aligned} H(X) &= -\frac{1}{3} \log_2 \frac{1}{3} - \frac{2}{3} \log_2 \frac{2}{3} \\ &= \log_2 3 - \frac{2}{3} \end{aligned}$$

$H(X) = \log_2 3 - \frac{2}{3}$なので,よって,

$$2^{-3(\log_2 3 - \frac{2}{3} + \frac{1}{6})} \leq P(x_1,x_2,x_3) \leq 2^{-3(\log_2 3 - \frac{2}{3}) - \frac{1}{6}}$$

すなわち

$$0.1048 \leq P(x_1,x_2,x_3) \leq 0.2095$$

を満たす系列$(x_1,x_2,x_3) \in \lbrace 0,1 \rbrace^3$が典型系列となる.$X_1,X_2,X_3$は互いに独立なので,系列$(x_1,x_2,x_3) \in \lbrace 0,1 \rbrace^3$の同時確率$P(x_1,x_2,x_3)$は次の４つの値のいずれかになる.

$$\begin{aligned} P(x_1,x_2,x_3) = \begin{cases} (\frac{1}{3})^3, \qquad &(x_1,x_2,x_3)\text{が全て}0\text{の場合} \\ (\frac{1}{3})^2 (\frac{2}{3}), \qquad &(x_1,x_2,x_3)\text{のうち２つが}0\text{の場合} \\ (\frac{1}{3}) (\frac{2}{3})^2, \qquad &(x_1,x_2,x_3)\text{のうち１つが}0\text{の場合} \\ (\frac{2}{3})^3, \qquad &(x_1,x_2,x_3)\text{が全て}1\text{の場合} \end{cases} \end{aligned}$$

この４つの値のうちで,典型系列の条件を満足するものは$(\frac{1}{3})(\frac{2}{3})^2 = 0.1481$だけだ.従って,典型系列は$(x_1,x_2,x_3)$のうち１つが0の系列となり,

$$A_\epsilon^n = \lbrace (0,1,1),(1,0,1),(1,1,0) \rbrace$$

(2)$|A_{\epsilon,n}| \leq 2^{n(H(X)+\epsilon)}$

$\epsilon = \frac{1}{6}$かつ$n = 3$の場合

$$2^{n(H(X) + \epsilon) \simeq 9.5459}$$

であり,$|A_\epsilon^n| = 3$なので,$|A_\epsilon^n| \leq 2^{n(H(X) + \epsilon)}$が成り立つ.

色々な情報量

相互情報量の考え方

情報量の応用

例题(7.2)

実数上で定義された次の実関数f(x)は凸関数であるか否か(狭義であるかも)答えなさい.凸関数であれば証明を,凸関数でなければそのような判例を示しなさい.

一変数の場合は,$f''(x) \geq 0$がIの各店xで成立していると仮定する.この時fはI上の凸関数となる.
開区間$I = (a_0,b_0)$上の関数fが2階微分可能とする.この時$f''(x) > 0$が各点xにおいて成立するならばfはI上狭義凸関数である.

以上の2点で判断すれば,結果は以下の通りである.

(1)$f(x) = x^4$

狭義凸関数である.

(2)$f(x) = x^3$

x > 0において凸関数であり,x < 0において凹関数である.

(3)$f(x) = 2^x$

凸関数である.

(4)$f(x) = \log_2x$(ただしx > 0)

凹関数である.

(5)$f(x) = x\log_2x$(ただしx > 0)

凸関数である.

賭けと情報理論

Kullback-Leibler(KL)情報量

同一の事象A上に値をとる二つの確率分布PとQを考える.これらの間のKL情報量を次で定義する.(logの底は2とする.)

KL情報量:$D(P;Q) = \underset{x \in A}{\sum} P(x) \log\frac{P(x)}{Q(x)}$

KL情報量は,相対エントロピー(relative entropy)あるいは, ダイバージェンス(divergence), KL-ダイバージェンスなどと呼ばれることもある.一般的には,確率分布の違いを表す量として知られている.

定理: KL情報量の非負性 $D(P; Q) \geq 0$

等号が成立するのは二つの分布が一致する場合すなわち,全ての$x \in A$に対して$P(x) = Q(x)$のときのみである.

例題:以下の表のKL情報量D(P; Q),D(Q; P)を計算せよ.

$a_i$	$P(a_i)$	$Q(a_i)$
$a_1$	$\frac{1}{4}$	$\frac{1}{2}$
$a_2$	$\frac{1}{4}$	$\frac{1}{4}$
$a_3$	$\frac{1}{4}$	$\frac{1}{8}$
$a_4$	$\frac{1}{4}$	$\frac{1}{8}$

競走馬のオッズ

通信路のモデル

前章までに述べた情報源符号化の目的は,効率的に情報を表現することにあった.

本章からは電気や光や無線などの媒体を用いて,送信者から受信者へ情報を送り届けるについて取り扱う.

• 情報理論における通信媒体のモデルとしての通信路について説明する
• 通信路には通信路容量と呼ばれる情報伝送の限界があることを説明する

通信路

入力アルファベット $A$ 並びに出力アルファベット $B$ を有する離散的通信路は,入力記号 $\mathbf{x} \in A$ が与えられた時の出力記号 $\mathbf{y} \in B$ の条件付き確率 $P(\mathbf{y} \ |\ \mathbf{x})$ によって定まる.このように,通信路の出力の確率分布が,その時刻における入力のみ定まり,過去の入力列には依存しない時,この通信路を無記憶であるあるいは無記憶通信路と呼ぶ.

• $|A| = |B| = r$のときは，r元通信路 (𝑟-ary channel) という

雑音のない通信路

雑音のない通信路: 入力記号によって出力記号が一意に定まる通信路である.

(a) $A = B = \lbrace 0, 1 \rbrace$で与えられる通信路

この時,入出力の間の条件付き確率は

$$\begin{aligned} &P(0 \ |\ 0) = 1, \qquad P(1 \ |\ 0) = 0 \\ &P(0 \ |\ 1) = 0, \qquad P(1 \ |\ 1) = 1 \end{aligned}$$

によって定まる.

雑音のある通信路

雑音のある通信路: 出力記号が入力記号によって確率的に変化する通信路である.

© 入力アルファベット$A = \lbrace 0, 1 \rbrace$, 出力アルファベット$B = \lbrace 0, 1, 2, 3 \rbrace$で与えられる通信路

この時,入出力の間の条件付き確率は

$$\begin{aligned} &P(0 \ |\ 0) = \frac{1}{2}, \qquad P(1 \ |\ 0) = \frac{1}{2}, \qquad P(2 \ |\ 0) = P(3 \ |\ 0) = 0 \\ &P(0 \ |\ 1) = P(1 \ |\ 1) = 0, \qquad P(2 \ |\ 1) = \frac{1}{2}, \qquad P(3 \ |\ 1) = \frac{1}{2} \end{aligned}$$

によって定まる.

消失通信路

(d) 入力アルファベット$A = \lbrace 0, 1 \rbrace$, 出力アルファベット$B = \lbrace 0, 1, e \rbrace$で与えられる通信路

この時,入出力の間の条件付き確率が,ある実数$0 \leq \epsilon \leq 1$を用いて.

$$\begin{aligned} &P(0 \ |\ 0) = 1 - \epsilon, \qquad P(1 \ |\ 0) = 0, \qquad P(e \ |\ 0) = \epsilon \\ &P(0 \ |\ 1) = 0, \qquad P(1 \ |\ 1) = 1 - \epsilon, \qquad P(e \ |\ 1) = \epsilon \end{aligned}$$

によって定まる.

通信路から記号 $e$ が出力された場合,記号0か1のいずれかが送信されたかを,これだけからでは知ることはできない.

記号 $e$ のことを消失(イレージャ)と呼ぶ.

これは,通信路に入力された記号が途中で失われて何も出力されなかったという状況を表している.

2元対称通信路(BSC)

$$\begin{aligned} &P(Y = 0 \ |\ X = 0) = 1 - p, \qquad P(Y = 1 \ |\ X = 1) = 1 - p \\ &P(Y = 1 \ |\ X = 0) = p, \qquad P(Y = 0 \ |\ X = 1) = p \end{aligned}$$

• $p$は反転確率 (誤り確率): このような通信路を $BSC(p)$ と呼ぶ

符号長 $n$ を大きくするにしたがい

• 復号誤り確率は 0 に近づく (良)
• 符号化率 $\frac{1}{n}$(bits/symbol) となり，0 に近づく (悪)

復号誤り確率は0に近づけ,かつ符号化率を定数にすることはできる.

BSC(0.1)に対しては, 符号化率を大きくとも0.53(bits/symbol)で復号誤り確率を任意に小さくすることができる.

対称通信路

通信路行列において,

• 各行が最初の行の要素を並び替えたものになっているような通信路を入力対称通信路と呼ぶ
• 各列が最初の列の要素を並び替えたものになっているような通信路を出力対称通信路と呼ぶ
• 入力対称通信路であり,出力対称通信路である場合は,狭義の対称通信路と呼ぶ

入力対称通信路の例

$$\begin{vmatrix} a & b & c \\ c & b & a \end{vmatrix}$$

出力対称通信路の例

$$\begin{vmatrix} p & q \\ q & p \\ r & r \end{vmatrix}$$

狭義の対称通信路の例

$$\begin{vmatrix} a & b & c \\ c & a & b \\ b & c & a \end{vmatrix}$$

通信路容量(channel capacity)

入力アルファベット $A$ 並びに出力アルファベット $B$ を持つ無記憶通信路の入出力間の条件付き確率が$P(\mathbf{y} \ |\ \mathbf{x})(\mathbf{x} \in A, \mathbf{y} \in B)$で与えられるとする.この時,この通信路の通信路容量$C_0$を

$$C_0 = \max_{P(x)} \lbrace I(X;Y) \rbrace$$

によって定義する.ただし, $(X,Y)$は同時確率 $P(\mathbf{x}, \mathbf{y}) = P(\mathbf{x}) P(\mathbf{y} \ |\ \mathbf{x})$に従う確率変数とし,$\max$は入力アルファベット $A$ 上の確率分布 $P(\mathbf{x}) (\mathbf{x} \in A)$ を取り替えて得られる最大値を意味する.

誤りのない2元通信路容量

• $I(X;Y) = H(X) - H(X \ |\ Y) = H(X)$
• $H(X)$を最大にする$P_X = (\frac{1}{2}, \frac{1}{2})$
• $C_0 = \max_{P_X} I(X;Y) = \max_{P_X} H(X) = 1(bit/symbol)$

2元対称通信路(BSC)容量

$BSC$ では$P(0 \ |\ 0) = 1 - p, P(1 \ |\ 0) = p$である.また

$$\begin{aligned} H(Y\ |\ X = 0) &= -\sum_{y=0}^1 P(y \ |\ 0) \log_2 P(y \ |\ 0) \\ &= -P(0 \ |\ 0) \log_2 P(0 \ |\ 0) - P(1 \ |\ 0) \log_2 P(1 \ |\ 0) = h(p) \end{aligned}$$

のため,次の式が成り立つ.

$$\begin{aligned} C_0 = \max_{P_X} I(X;Y) &= \max_{P_X}(H(Y) - H(X \ |\ Y)) \\ &= \max_{P_X} (H(Y) - h(p)) \end{aligned}$$

• 最大になるのは$P_X = (\frac{1}{2}, \frac{1}{2})$の時
• 従って$C_0 = 1 - h(p)$となる
  • $p = 0, p = 1$の時1で最大となる
  • $p = 0.5$の時0で最も小さい(1番訂正が難しい)
• $p = 0.1$の時$C = 0.531(bits/symbol)$
• $BSC$は狭義の対称通信路である

2元消失通信路(BEC)容量

入力分布を$P_X(0) = a, P_X(1) = 1 - a(0 \leq a \leq 1)$とし,$C_0 = \max_{P_X} I(X;Y) = \max_{P_X} (H(Y) - H(Y|X))$を計算する.

$$\begin{aligned} &H(Y) = (1 - e)h(a) + h(e) \\ &H(Y|X) = h(e) \\ &I(X;Y) = H(Y) - H(Y|X) = (1 - e)h(a) \end{aligned}$$

• $C_0 = \max_{P_X} (1-e)h(a)$が最大となるのは$a = \frac{1}{2}$の時
• 従って$C_0 = 1 - e$である
• $e = 0.1$の時$C = 0.9(bits/symbol)$
• $BSC$より$C_0$が大きい.すなわち,$BSC$より訂正しやすいと言える
• $BEC$は入力対称通信路だが,狭義対称通信路ではない

対称通信路の通信路容量

前節述べたように,通信路容量は,入力記号の確率分布を変化させた時の相互情報量の最大値として定義された.

通信路行列

対称通信路では通信路容量の計算を簡単化できる場合がある.まず入力を表す確率変数を$X$, 出力を表す確率変数を$Y$とする.

入力対称通信路の通信路容量

$H(Y \ |\ X = x)$が$x \in A$によらず一定の値を取るため,$H(Y \ |\ X) = H(Y \ |\ X = x)$が成り立つ.従って通信路容量は以下のように求められる

$$C_0 = \max_{P_X} (H(Y) - H(Y \ |\ X = x))$$

狭義の対称通信路の通信路容量

相互情報量の最大化は $X$ が一様分布のとき達成される.

$X$ が一様分布のとき, $Y$の分布も一様分布になり, $H(Y)$は最大値$\log_2 |B|$をとる.

$$C_0 = \log_2 |B| - H(Y \ |\ X = x)$$

例題:次の通信路行列が与えられた時,通信路容量を計算しなさい

$$\begin{aligned} \begin{vmatrix} \frac{1}{4} & \frac{2}{4} & 0 & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} & \frac{2}{4} & 0 \\ \frac{2}{4} & 0 & \frac{1}{4} & \frac{1}{4} \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{2}{4} \end{vmatrix} \end{aligned}$$

$$\begin{aligned} &C_0 = \log_2|B| - H(Y \ |\ X = x) \\ &|B| = 4 \\ &H(Y \ |\ X = x) = -\sum_{y \in Y} P(y \ |\ x) \log_2 P(y \ |\ x) \end{aligned}$$

x = 0とする

$$\begin{aligned} H(Y \ |\ X = 0) &= -\frac{1}{4} \log_2 \frac{1}{4} - \frac{2}{4} \log_2 \frac{2}{4} - 0\log_2 0 - \frac{1}{4} \log_2 \frac{1}{4} = \frac{3}{2} \\ &= H(Y \ |\ X = 1) = H(Y \ |\ X = 2) = H(Y \ |\ X = 3) \end{aligned}$$

従って,

$$C_0 = \log_2|B| - H(Y \ |\ X = x) = \log_2 |B| - \frac{3}{2} = \frac{1}{2}$$

例題(9.1)

次の通信路行列によって表される条件付き確率$P(y \ |\ x)$によって定まる通信路の通信路容量を求めなさい.

(1) $x \in \lbrace 0,1 \rbrace \text{と} y \in \lbrace 0,1,2,3 \rbrace$に対して

$$\begin{aligned} \begin{vmatrix} \frac{1}{2} & \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \end{vmatrix} \end{aligned}$$

入力対称通信路なので,通信路容量$C_0$は

$$\begin{aligned} C_0 &= \max_{P_X} (H(Y) - H(Y \ |\ X = 0)) \\ &= \max_{P_X} \lbrace H(Y) - (-2 \times \frac{1}{4} \log \frac{1}{4} - \frac{1}{2} \log \frac{1}{2}) \rbrace \\ &= \max_{P_X} \lbrace H(Y) - \frac{3}{2} \rbrace \end{aligned}$$

となる.ここで,$X = 0$となる確率を$\frac{1}{2}$として,Yの周辺確率を求めると$\lbrace 0,1,2,3 \rbrace$上の一様分布になるので,この時

$$\begin{aligned} H(Y) = -4 \times \frac{1}{4} \log \frac{1}{4} = 2 \end{aligned}$$

また,エントロピーの上界式によると,$H(Y) \leq \log|4|$なので,$\max_{P_X} = 2$となる.

従って,通信路容量$C_0 = 2 - \frac{3}{2} = 0.5$

(2) $x, y \in \lbrace 0,1,2 \rbrace$に対して

$$\begin{aligned} \begin{vmatrix} \frac{4}{5} & \frac{1}{5} & 0 \\ 0 & \frac{4}{5} & \frac{1}{5} \\ \frac{1}{5} & 0 & \frac{4}{5} \end{vmatrix} \end{aligned}$$

狭義の対称通信路なので,通信路容量$C_0 = \log_2|B| - H(X \ |\ Y = 0) = \log_2 3 - (-\frac{4}{5} \log_2 \frac{4}{5} - \frac{1}{5} \log \frac{1}{5}) \simeq 0.863034405833794$

(3) $x, y \in \lbrace 0,1,2,3 \rbrace$に対して

$$\begin{aligned} \begin{vmatrix} a & 1-a & 0 & 0 \\ 1-a & a & 0 & 0 \\ 0 & 0 & a & 1-a \\ 0 & 0 & 1-a & a \end{vmatrix} \end{aligned}$$

狭義の対称通信路なので,通信路容量$C_0 = \log_2|B| - H(X \ |\ Y = 0) = \log_2 4 - h(a) = 2 - h(a)$となる.

例題(9.2)

次の通信路によって表される条件付き確率$P(y \ |\ x)$によって定まる通信路をZ-通信路と呼びます.ただし,$x,y \in \lbrace 0,1 \rbrace$です.Z-通信路に対する通信路容量と通信路容量を達成する入力分布を求めなさい.入力分布を横軸に相互情報量$I(X;Y)$のグラフを描き,通信路容量との関係を述べなさい.

$$\begin{aligned} \begin{vmatrix} 1 & 0 \\ \frac{1}{2} & \frac{1}{2} \end{vmatrix} \end{aligned}$$

ここで,まず与えられた通信路を一般の形に変わる(この問題では$p = \frac{1}{2}$)

$$\begin{aligned} \begin{vmatrix} 1 & 0 \\ p & 1-p \end{vmatrix} \end{aligned}$$

図に示したように,$P(x_1)$の確率は$1-\alpha$,$P(x_2)$の確率は$\alpha$と仮定する.

相互情報量は

$$\begin{aligned} I(X;Y) = H(Y) - H(Y \ |\ X) \end{aligned}$$

となる.

(1) Calculation of H(Y)

$$\begin{aligned} P(y_1) &= (1 - \alpha) + \alpha p \\ P(y_2) &= \alpha (1 - p) \\ H(Y) &= -(1 - \alpha + \alpha p) \log(1 - \alpha + \alpha p) - \alpha (1 - p)\log \alpha (1 - p) \end{aligned}$$

(2) Calculation of $H(Y \ |\ X)$

$$\begin{aligned} H(Y \ |\ X) = -\alpha p \log p - \alpha (1 - p) \log (1 - p) \end{aligned}$$

(3)

$$\begin{aligned} I(X;Y) &= H(Y) - H(Y \ |\ X) = -(1 - \alpha + \alpha p)\log (1 - \alpha + \alpha p) - \alpha (1 - p) \log \alpha + \alpha p \log p \\ \frac{\partial I(X;Y)}{\partial \alpha} &= 0 \Rightarrow \alpha_0 = \frac{1}{1 - p + p^{(\frac{p}{p-1})}} \end{aligned}$$

これを解くと,$\alpha_0 = \frac{2}{5}$となり,従って,$I(X;Y)$の最大値は

$$\begin{aligned} C_0 &= \max_{P(x)} I(X;Y) = -(1 - \alpha_0 + \alpha_0 p)\log (1 - \alpha_0 + \alpha_0 p) - \alpha_0 (1 - p) \log \alpha_0 + \alpha_0 p \log p \\ &= \log (1 - p + p^{\frac{p}{p-1}}) - \frac{p}{p-1} \log p \\ &= \log5 - 2 \end{aligned}$$

となる.

グラフは以下のように示した

上のグラフにも明らかに,相互情報量$I(X;Y)$と通信路容量の関係は通信路容量は,通信路の入力と出力との間の相互情報量を,入力分布に関しては最大化した時の最大値によって与えられる. 相互情報量は通信路が情報を転送する能力を表す.

例題(9.3)

2値入力$\lbrace 0,1 \rbrace$に対して消失だけでなく誤りも起こりうる次の図で定まる通信路を考えます.

(a) この通信路の通信路容量を求めなさい.

この通信路の通信路行列は

$$\begin{aligned} \begin{vmatrix} 1 - \epsilon - \delta & \epsilon & \delta \\ \delta & \epsilon & 1 - \epsilon - \delta \end{vmatrix} \end{aligned}$$

なので,この通信路は入力対称通信路である.従って,その通信路容量は

$$\begin{aligned} C_0 &= \max_{P_(x)} H(Y) - H(Y|X=x) \\ &= \max_{P_(x)} H(Y) + (1 - \epsilon - \delta) \log(1 - \epsilon - \delta) + \epsilon \log \epsilon + \delta \log \delta \end{aligned}$$

となる.また,$X = 1$となる確率をpをすると,

$$\begin{aligned} &P(Y = 0) = (1 - p)(1 - \epsilon - \delta) + p\delta, \quad P(Y = e) = \epsilon, \\ &P(Y = 1) = p(1 - \epsilon - \delta) + (1 - p)\delta \end{aligned}$$

なので,

$$\begin{aligned} H(Y) &= -((1 - p)(1 - \epsilon - \delta) + p\delta)\log((1 - p)(1 - \epsilon - \delta) + p\delta) - \epsilon \log \epsilon - (p(1 - \epsilon - \delta) + (1 - p)\delta) \log (p(1 - \epsilon - \delta) + (1 - p)\delta) \\ &= (1 - \epsilon)h(\frac{(1 - p)(1 - \epsilon - \delta) + p\delta}{1-\epsilon}) + h(\epsilon) \end{aligned}$$

となる.従って,H(Y)のpについての最大値を求めると,h(t)が$t = \frac{1}{2}$の時に最大値1を取ることから,

$$\begin{aligned} \max_{P_(x)}H(Y) = (1-\epsilon) (\max_p h(\frac{(1 - p)(1 - \epsilon - \delta) + p\delta}{1-\epsilon})) + h(\epsilon) \leq 1 - \epsilon + h(\epsilon) \end{aligned}$$

となる.ただし,等号は$\frac{\frac{(1 - p)(1 - \epsilon - \delta) + p\delta}{1-\epsilon}}{1-\epsilon} = \frac{1}{2}$の時,すなわち$p = \frac{1}{2}$において達成できる.以上から,

$$\begin{aligned} C_0 &= \max_{P_(x)} H(Y) + (1 - \epsilon - \delta) \log(1 - \epsilon - \delta) + \epsilon \log \epsilon + \delta \log \delta \\ &= (1 - \epsilon + h(\epsilon)) + (1 - \epsilon - \delta) \log(1 - \epsilon - \delta) + \epsilon \log \epsilon + \delta \log \delta \end{aligned}$$

(b) (a)で求めた通信路容量は, $\epsilon = 0$とすることで2元対称通信路の通信路容量と一致することを確かめなさい.

$\epsilon = 0$とすると,

$$\begin{aligned} C_0 = 1 + h(0) + (1-\delta) \log (1-\delta) + \delta \log \delta = 1 - h(\delta) \end{aligned}$$

となり,2元対称通信路の通信路容量となる.

© (a)で求めた通信路容量は, $\delta = 0$とすることで消失通信路の通信路容量と一致することを確かめなさい.

$\delta = 0$とすると,

$$\begin{aligned} C_0 = 1 - \epsilon + h(\epsilon) + (1-\epsilon) \log (1-\epsilon) + \epsilon \log \epsilon = 1 - \epsilon \end{aligned}$$

となり,消失通信路の通信路容量となる.

通信路符号化定理

本章では、

• 通信路符号の伝送速度が通信路容量よりも小さい場合、符号長を長くするにつれて、いくらでも復号誤り率を小さくできる通信路符号が存在することを示す

通信路符号化定理(シャノンの第２基本定理)

通信路容量 $C$ を持つ通信路に対して, $R < C$ であれば，情報速度 $R$ の符号で復号誤り率がいくらでも小さいものが存在する．しかし，$R > C$ であれば，そのような符号は存在しない．

この定理は, 伝送速度 $R$ が通信路容量 $C$ より小さければnを大きくしていけば誤り確率が任意に小さい符号化復号化が構成可能であることを示している.

• 通信路容量を超えない情報速度でなら，いくらでも精度よく通信できるような符号法がある

通信路符号

入力アルファベット $A$ の要素からなる長さ $n$ の系列の集合 $A^n$ の部分集合 $C$ を通信路符号と呼ぶ.この時, $n$ を符号長. $C$ の要素を符号語, $C$ の要素数符号語数をと呼ぶ.

符号の伝送速度

符号長 $n$ の符号 $C$ の伝送速度 $R$ は

$$R = \frac{1}{n} \log_2 |C|$$

によって定義される.

通信路符号化

最尤復号法

$y_n$を受信した際に,次式のように復号する方法

$$\psi(y^n) = \arg \max_i P(y^n \ |\ x^n(i))$$

これはつまり$y^n$が与えられたもとで,尤度$P(y^n \ |\ x^n(i))$を最大にする $i$ へと復号する方式である.

尤度$P(y^n \ |\ x^n(i))$が最大となる符号語が二つ以上あった場合どれに復号するか予め決定しておく.例えば「もっとも小さいiにする」等(これをタイブレークルール等という.)

このとき(M個の符号語が等確率で発生するという仮定の下で)平均誤り確率は

$$\begin{aligned} \epsilon_n &= \frac{1}{M} \sum_{i=1}^M (1 - \sum_{y^n \in \mathcal{Y}_n} \max_i P(y^n \ |\ x^n(i))) \\ &= 1 - \frac{1}{M} \sum_{i=1}^M \sum_{y^n \in \mathcal{Y}_n} \max_i P(y^n \ |\ x^n(i)) \end{aligned}$$

となる.簡単な考察によりこれが平均誤り確率を最小にすることがわかる.またタイブレークルールは平均誤り確率に影響しない.つまり尤度が最大の符号語が複数ある場合,どれを選んでも平均誤り確率は等しいこともわかる.

---

例題

晴れ,雨をそれぞれ1,2に対応させ$(M = 2)$,その符号語を$x^n(1) = 000, x^n(2) = 111$とする.最尤復号法は$y^n$が与えられたときに,$P(y^n | x^n(i))$を最大にする $i$ へと復号する関数であるので,$y^n = 010$のときに$P(010 \ |\ 000),P(010 \ |\ 111)$を計算し,大小を比較する.

$y^n = 010$のときは

$$\begin{aligned} P(010 \ |\ 000) &= P(0 \ |\ 0) \times P(1 \ |\ 0) \times P(0 \ |\ 0)\\ &= (1 - p) \times p \times (1 - p) \\ &= 0.8 \times 0.2 \times 0.8 = 0.128 \end{aligned}$$

$$P(010 \ |\ 000) = 0.128 > P(010 \ |\ 111) = 0.032$$

であるので,010は000を符号語として持つ符号語1$(x^n(1) = 000)$へと復号する.

$y^n = 111$のときは

$$P(111 \ |\ 000) = 0.008 < P(111 \ |\ 111) = 0.512$$

であるので$x^n(2) = 111$である符号語2へと復号する.

最尤復号法の問題点

• 最尤復号法は平均誤り確率を最小にするという意味で最適な復号法であるが,全ての符号語 $i$ に対して$P(y^n \ |\ x^n(i))$を計算し比較しなければならない.これは符号語の数 $M$ が大きくなると現実的な計算量では困難となる.
  • このため,最尤復号法は,非常に強力な復号法ではあるが限られた符号に対してしか用いられていない.計算量の観点からは次に説明する最小距離復号法の方がよい.

また各符号語 $i$ の発生確率(事前確率)を一様$(P(x^n(i)) = 1/M)$と仮定している.事前確率が非一様の場合は最尤復号法では不十分である

最小距離復号法

二つ$\mathcal{X}$上の長さ $n$ の系列を

$$a^n = a_1a_2 \cdots a^n, \quad b^n = b_1b_2 \cdots b_n$$

とする.このとき

$$d_H(a^n,b^n) = \sum_{i=1}^n \delta(a_i,b_i)$$

を系列 $a^n$ と $b^n$ の間のハミング距離と呼ぶ.ただし,

$$\begin{aligned} \delta(u,v) = \begin{cases} &0,\quad u = v \\ &1,\quad u \neq v \end{cases} \end{aligned}$$

である.

ハミング距離とはつまり,二つの系列の対応した位置にある成分のうち互いに異なるものの数である.例えば,系列000と系列111のハミング距離は$d_H(000,111) = 3$である.また$d_H(101, 111) = 1$である.なお,ハミング距離は距離の三公理を満たす.

ハミング距離に基づいて受信系列$y^n$からそれに最も近い符号語$x^n(i)$を持つ $i$ へと復号する規則を最小距離復号法という.つまり

$$\psi(y^n) = \arg \min_i d_H(y^n,x^n(i))$$

という復号化関数である.

---

例題:

先ほどの例:晴れ,雨をそれぞれ1,2に対応させる$(M=2)$と$x^n(1) = 000, x^n(2) = 111$.最小距離復号法では$y^n$が与られた時に,各符号語とのハミング距離を比較する.$y^n = 010$の時に

$y^n = 010$の時は

$$d_H(010,000) = 1 < d_H(010,111) = 2$$

であるので,010は000を符号語として持つ符号語1へ復号する.

$y^n = 111$の時は

$$d_H(111,000) = 3 > d_H(111,111) = 0$$

であるので$x^n(2) = 111$である符号語2へと復号する.

• 例から分かるように最小距離復号法を用いた復号は複雑な確率計算を必要としない.このことは,復号結果が通信路行列には依らないことを示している.
• 最小距離復号法を用いて高い誤り訂正能力,(低い誤り確率)を達成するには符号語間のハミング距離を大きくする必要がある.

符号の最小距離 $d$ とは,符号に含まれる相異なる二つの符号語のハミング距離の最小値である.

$$d = \min \lbrace d_H(x^n(i), x^n(j)) \ |\ i \neq j, 1 \leq i, j \leq M \rbrace$$

---

例題

符号語$1 \sim 4$を2元符号$C = \lbrace 00000, 11100, 00111, 11011 \rbrace$を用いて送信する.つまり$x^5(1) = 00000, x^5(2) = 11100, x^5(3) = 00111, x^5(4) = 11011$である.このとき

(1) この符号の最小距離はいくらか

(2) 系列10111を最小距離復号法により復号した結果はどうなるか

$y^n = 10111$

$i$	$d_H(y^n, x^n(i))$
1	4
2	3
3	1
4	2

符号語3

(3) 系列10011を最小距離復号法により復号した結果はどうなるか

$y^n = 10011$

$i$	$d_H(y^n, x^n(i))$
1	3
2	4
3	2
4	1

符号語4

(4) 伝送速度はいくらか

伝送速度 $R(n = 5, M = 4)$

$$\begin{aligned} &R = \frac{\log_2 M}{n} = \frac{\log_2 2^k}{n} = \frac{k}{n} \\ &\Rightarrow R = \frac{2}{5} \end{aligned}$$

---

BSCの場合における復号法

最小距離復号法と最尤復号法の復号結果は変わらない.これは偶然ではなく,誤り率p(ただしp < 0.5)のBSCにおいてはこれらの結果は常に一致する.

$$\log_2 \frac{p}{1-p} < 0$$

となるので,この符号はマイナスである.故に,

$$\begin{aligned} \argmax_i P(y^n \ |\ x^n(i)) &= \argmax_i d_H(y^n, x^n(i))\log_2 \frac{p}{1-p} \\ &= \argmin_i d_H(y^n, x^n(i)) \end{aligned}$$

となる.これはハミング距離の最小になる符号語を復号していることにほかならない.

---

例題

次の通信路行列

$$\begin{aligned} W_1 = \begin{bmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{bmatrix},\quad W_2 = \begin{bmatrix} 0.6 & 0.4 \\ 0.7 & 0.3 \end{bmatrix} \end{aligned}$$

で定義される二つの通信路があるとしよう.この通信
路上で先ほどの例と同様,符号語$1 \sim 4$を2元符号$C = \lbrace 00000, 11100, 00111, 11011 \rbrace$を用いて送信する.つまり$x^5(1) = 00000, x^5(2) = 11100, x^5(3) = 00111, x^5(4) = 11011$である.今受信系列 $y^n$ が10111であったとする.

(1) 通信路が $W_1$ であった際に,最小距離復号法と最尤復号法の復号結果を比較せよ

$$\begin{aligned} \begin{bmatrix} P(0 \ |\ 0) & P(1 \ |\ 0) \\ P(0 \ |\ 1) & p(1 \ |\ 1) \end{bmatrix} \end{aligned}$$

最尤復号法 $y^n = 10111$

i	$P(y^n \vert x^n(i))$
1	$P(1 \vert 0)P(0 \vert 0)P(1 \vert 0)P(1 \vert 0)P(1 \vert 0)$ = 0.00009
2	$P(1 \vert 1)P(0 \vert 1)P(1 \vert 1)P(1 \vert 0)P(1 \vert 0)$ = 0.00128
3	$P(1 \vert 0)P(0 \vert 0)P(1 \vert 1)P(1 \vert 1)P(1 \vert 1)$ = 0.04608
4	$P(1 \vert 1)P(0 \vert 1)P(1 \vert 0)P(1 \vert 1)P(1 \vert 1)$ = 0.01024

よって,最尤復号法の復号結果は符号語3である.

(2) 通信路が$W_2$であった際に,最小距離復号法と最尤復号法の復号結果を比較せよ

---

最大事後確率復号

最尤復号法は平均誤り確率を最小にするという意味で最適な復号法であるが,各符号語 $i$ の発生確率(事前確率)を一様$(P(x^n(i)) = \frac{1}{M})$と仮定している.

事前確率が非一様の場合は復号誤り確率を最小にするためには最尤復号法では不十分であり,最大事後確率復号法を用いる必要がある.

$$\begin{aligned} \psi(y^n) &= \argmax_i P(x^n(i) \ |\ y^n) \\ &= \argmax_i P(y^n, x^n(i)) \\ &= \argmax_i P(x^n(i)) \cdot P(y^n \ |\ x^n(i)) \end{aligned}$$

これはつまり $y^n$ が与えられたもとで,事後確率$P(x^n(i) \ |\ y^n)$を最大にする $i$ へと復号する方式である.

ベイズの定理

贝叶斯定理:贝叶斯定理是关于随机事件A和B的条件概率的一则定理。

$$\begin{aligned} P(A \ |\ B) = \frac{P(B \ |\ A)P(A)}{P(B)} \end{aligned}$$

其中A以及B为随机事件，且P(B)不为零。$P(A \ |\ B)$是指在事件B发生的情况下事件A发生的概率。

在贝叶斯定理中，每个名词都有约定俗成的名称:

• P(A|B)是已知B发生后，A的条件概率。也由于得知B的取值而被称作A的后验概率
• P(A)是A的先验概率(或边缘概率)。之所以称为"先验"是因为它不考虑任何B方面的因素
• P(B|A)是已知A发生后，B的条件概率。也由于得知A的取值而被称作B的后验概率
• P(B)是B的先验概率

按照这些术语，贝叶斯定理可描述为:后验概率 = (似然性*先验概率)/标准化常量。也就是说，后验概率与先验概率和相似度的乘积成正比。
另外，比例$P(B \ |\ A) / P(B)$也有时被称作标准似然度(standardised likelihood)，贝叶斯定理可描述为:后验概率 = 标准似然度 * 先验概率

• 最大事後確率復号法はベイズの定理を利用
• 最尤復号法は最大事後確率復号法の一例(事前確率を一様とした場合が最尤復号法)と等価

$$\begin{aligned} P(x \ |\ y) &= \frac{P(x,y)}{P(y)} \quad P(y) = \sum_x P(x,y) (\text{定数}) \\ &\propto P(x,y) \\ &= P(y \ |\ x) \cdot P(x) \end{aligned}$$

例題(10.1)

下記のような通信路Wを介して符号語$x^4(1) = 0000, x^4(2) = 0011,x^4(3) = 1100, x^4(4) = 0111$を送信する.注意:復号の結果として2つ以上の符号語が候補として挙がった場合,全て解答すること.

(1) この符号の最小距離$d_{min}$と伝送速度Rを求めよ.

図に示したように,最小距離は$d_H(0011, 0111) = 1$である.

伝送速度Rは

$$\begin{aligned} R = \frac{\log_2 M}{n} = \frac{\log_2 4}{4} = \frac{1}{2} \end{aligned}$$

となる.(M = 4, n = 4)

(2) 受信系列0010を最小距離復号法,最尤復号法,それぞれで復号した結果を求めよ.根拠も述べること.

$y^n = 0010$

最小距離法より

i	$d_H(y^n, x^n(i))$
1	1
2	1
3	3
4	2

符号語は1と2($\argmin_i d_H(y^n, x^n(i)) = 1$)

最尤復号法より

i	$P(y^n \vert x^n(i))$
1	$P(0 \vert 0)P(0 \vert 0)P(1 \vert 0)P(0 \vert 0)$ = 0.0729
2	$P(0 \vert 0)P(0 \vert 0)P(1 \vert 1)P(0 \vert 1)$ = 0.2025
3	$P(0 \vert 1)P(0 \vert 1)P(1 \vert 0)P(0 \vert 0)$ = 0.0225
4	$P(0 \vert 0)P(0 \vert 1)P(1 \vert 1)P(0 \vert 1)$ = 0.1125

符号語2($\argmax_i P(y^n \ |\ x^n(i)) = 0.2025$)

(3) 受信系列0010, 符号語の発生確率が非一様で$P(x^4(1)) = P(x^4(3)) = \frac{1}{8}, P(x^4(2)) = P(x^4(4)) = \frac{3}{8}$としたとき,最大事後確率復号法を実行したとき得られる符号語を答えよ.根拠も述べること.

$$\psi(y^n) = \argmax_i P(x^n(i)) \cdot P(y^n \ |\ x^n(i))$$

i	$\psi(y^n)$
1	$\frac{1}{8} \times 0.0729$ = 0.0091125
2	$\frac{3}{8} \times 0.2025$ = 0.0759375
3	$\frac{1}{8} \times 0.0225$ = 0.0028125
4	$\frac{3}{8} \times 0.1125$ = 0.0421875

符号語2($\psi(y^n) = \argmax_i P(x^n(i)) \cdot P(y^n \ |\ x^n(i)) = 0.0759375$)

---

誤り訂正符号

これまでに最小距離復号法,最尤復号法,最大事後確率復号法の3つの復号法を説明したが,符号化法については説明していない.

またこれまでに説明した復号法も符号語の全探索を行う必要があるため,符号語数(情報記号数kに対し符号語数は$2^k$個と膨大)が多くなるとその計算に莫大な時間がかかる.

従って,長い符号長でも復号誤り率の小さい通信路符号を効率的に構成するための方法が必要になる.

この問題に対する1つの解答が誤り訂正符号である.

「誤り訂正符号」とは,符号語の記号に生じた一定個数までの誤りを訂正できる通信路符号である.

本章では

• 誤り訂正符号の基本概念と誤り訂正の原理について説明する
• 符号語に生じた１個までの誤りを訂正できるハミング符号の構成法を示す
• ハミング符号による符号化を繰り返し行うことで,２元対称通信路において伝送速度を一定以上に保ったまま,符号長を長くすることで,いくらでも復号誤り率を小さくできる符号が作れることを明らかにし,通信路符号化定理を満足する符号の例を示す

2元ガロア体

2元のガロア体GF(2)上の要素$F = \lbrace 0, 1 \rbrace$の演算は表のように行なわれる.

a	b	a+b	a $\cdot$ b
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

表では,2元記号a,b間の演算を示す.例えば,演算で$a = 1, b = 1$のとき$a + b = 2 = 0(mod 2)$として計算される.

誤り訂正符号の実用例

• 単一パリティ検査符号
• 水平垂直パリティ検査符号
• ハミング符号(RAID2, RAM)
• Reed-Solomon符号(衛星通信, DVD, BD, CD, QRコード)
• ターボ符号(3G, 4G)
• LDPC符号(DVB-S2, IEEE802.16c)
• Polar符号(5G)

誤り訂正符号の例

長さ1の情報ビット0もしくは1を送信したい.いまそれぞれの情報ビットに対し,同じ情報を2ビットをパリティ系列として付加した系列を通信路を介して送るとする.すなわち,$0 \rightarrow 000, 1 \rightarrow 111$と符号化することである.

もし符号語$\mathbf{x} = (000)$を送って$\mathbf{y} = (010)$を受信したとする.送られた符号語は000もしくは111のいれずれかであり,これらの系列が送られる確率は等確率であり,通信路は誤り確率が$0 \leq \epsilon < 0.5$のBSCの場合,000が送られたと推定する方が妥当である.

このように誤り訂正符号では,情報系列に対してパリティ系列を付加した符号語を送信する.

しかし,1ビットの情報に対して長い系列を送ることは効率が悪く,またできるだけ短い系列で多くの情報を送信したい.誤り訂正符号では訂正能力だけでなく,送信するビット数(符号語)に対する情報系列の長さの比率(符号化率)も重要な指標である.

(n, k, d)線形ブロック符号

2元$(n, k, d)$線形ブロック符号 $C$ は長さ $n$ の2元ベクトル$\mathbf{x}$の集合であり,長さ $k$ の2元ベクトルである情報系列$\mathbf{w}$を符号化して得られる.ここで $n$ は符号長(符号語$\mathbf{x}$の長さ), $k$ は情報記号数(情報系列$\mathbf{w}$の長
さ), $d$ は最小距離である.また符号 $C$ の符号化率$\mathbf{R} = \frac{k}{n}$とする.

• 符号率$R = \frac{k}{n}$

ハミング距離

2つのベクトル$\mathbf{v} = (v_1,\cdots,v_n), \mathbf{v}^{'} = (v_1^{'}, \cdots, v_n^{'})$をその成分毎に比較し,異なる個数の数をハミング距離$\mathbf{D}_H(v_1^{'},v_n^{'})$と定義する.

$$\begin{aligned} &\mathbf{D}_H(\mathbf{v},\mathbf{v}^{'}) = \sum_{i=1}^n d_H(v_i,v_i^{'}) \\ &d_H(v_i,v_i^{'}) = \begin{cases} 0, \quad v_i = v_i^{'} \\ 1, \quad v_i \neq v_i^{'} \end{cases} \end{aligned}$$

例:$n = 8$のハミング距離

長さが$n = 8$である2つのベクトル(01001011),(01110010)のハミング距離は

$$D_H(01001011, 01110010) = 4$$

である．

最小距離

最小距離はある符号Cの中で2つの異なる符号語$\mathbf{x}, \mathbf{x}^{'}$間のハミング距離の最小値を表し,次式によって定義される.

$$\begin{aligned} d = \min_{\mathbf{x},\mathbf{x}^{'} \in C, \mathbf{x} \neq \mathbf{x}^{'}} D_H(\mathbf{x}, \mathbf{x}^{'}) \end{aligned}$$

符号語は$2^k$個存在する.$\binom{2^k}{2}$組み合わせ($C_{2^k}^2$)全てでの最小値.

• 符号Cの最小距離$d(C)$は,符号Cの符号語中に生じた何個までの誤りを訂正できるかを示す尺度になっている.

(n, n-1, 2)符号

符号語のハミング重みが偶数となるようにパリティビットを1ビット付加して符号化する.例えば,長さが4の情報系列$\mathbf{w} = (0111)$を符号化すると長さが5の符号語$\mathbf{x} = (01111)$を得る.この符号は偶重み符号とも呼ばれる.

例: (5,4,2)符号(n = 5)

$$\mathbf{w} = (0111) \rightarrow \mathbf{x} = (01111)$$

• $\mathbf{w}$八重 = 3, $\mathbf{x}$八重 = 4
• $\mathbf{x}$誤りが1個(11111): 符号語$\Rightarrow$検出できる
• $\mathbf{x}$誤りが2個(10111): 符号語$\Rightarrow$検出できない

(n, 1, n)符号

1ビットの情報記号に対し同じパリティビットをn−1個付加して符号化される.例えば,$\mathbf{w} = (1)$を符号化すると符号語$\mathbf{x} = (1111)$を得る.この符号は繰り返し符号とも呼ばれる.

例: (4,1,4)符号(n = 4)

$$\mathbf{w} = (1) \rightarrow \mathbf{x} = (1111)$$

• $\mathbf{x}$繰り返し符号

最小距離と誤り検出$\cdot$訂正能力

符号語の数は $2^k$ 個存在するが,符号語の長さはnであるため, $2^n$ 個の $n$ 次元ベクトル空間のベクトル全てに符号語が割り当てられているわけではない.したがって,もし誤りが混入した受信語がどの符号語とも異なる系列であったとすると,受信側では誤りが混入したことが分かる.これを誤り検出と呼ぶ.

• 長さがkである$\lbrace 0,1 \rbrace$の情報系列の総数は $2^k$ 個であるため

定理: $(n, k, d)$線形ブロック符号は $d-1$ 個以下の誤りを必ず検出できる.

• $(n, n-1, 2)$符号の場合,$d - 1 = 2 - 1 = 1$個の誤りは必ず検出できる.

$d$	$t$
2	0
3	1
4	1
5	2
6	2

定理: $(n, k, d)$線形ブロック符号はt個以下の誤りを必ず訂正できる.ただし,$t = \lfloor \frac{d-1}{2} \rfloor$である.(床関数$\lfloor a \rfloor$は$a$を超えない整数の中で最大の値を表す)

• $(n, 1, n)$符号で$n = 4$の場合,$t = \lfloor \frac{d-1}{2} \rfloor = t = \lfloor \frac{4-1}{2} \rfloor = t = \lfloor 1.5 \rfloor = 1$個の誤りは必ず訂正できる.

生成行列とパリティ検査行列

符号器では長さ $k$ の情報系列$\mathbf{w}$を長さ $n$ の符号語$\mathbf{x}$にする.これは,情報系列$\mathbf{w}$に$k \times n$の行列$\mathbf{G}$を乗じることで得ることが出来る.すなわち,

$$\mathbf{x} = \mathbf{w}\mathbf{G}$$

となる.生成行列$\mathbf{G}$は以下で定義される.

生成行列

$(n, k, d)$線形ブロック符号 $C$ の生成行列$\mathbf{G}$は$k \times n$の行列であり, $C$ から全零の符号語を除く $k$ 個のそれぞれ異なる符号語を取り出し,$\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_k$とし,それぞれを$\mathbf{G}$の行ベクトルとする.

$$\begin{aligned} \mathbf{G} = \begin{bmatrix} \mathbf{x}_1 \\ \mathbf{x}_2 \\ \vdots \\ \mathbf{x}_k \end{bmatrix} \end{aligned}$$

得られた$\mathbf{G}$に対して,行列の基本操作を行なっても本質的に同じ符号が得られる.したがって行列の基本操作を行い以下の構造の生成行列$\mathbf{G}^{'}$を用いた方が扱いやすい.

$$\begin{aligned} \mathbf{G}^{'} = \begin{bmatrix} \mathbf{I}_k, \mathbf{P} \end{bmatrix} \end{aligned}$$

このような形式の生成行列を用いて符号化を行うと,符号語$\mathbf{x} = \mathbf{w}\mathbf{G}^{'}$の左からkビット$\mathbf{x}_1,\cdots,\mathbf{x}_k$は情報系列$\mathbf{w}_1,\cdots,\mathbf{w}_k$と一致するため,符号語から容易に情報ビットを取り出すことができる.

ここで$\mathbf{I}_k$は$k \times k$の単位行列であり, $\mathbf{P}$は$k \times (n - k)$のパリティビット付加行列と呼ばれる.

---

例: (5, 4, 2)符号の生成行列

$$\begin{aligned} \mathbf{G}^{'} = \begin{bmatrix} 10001 \\ 01001 \\ 00101 \\ 00011 \end{bmatrix} \end{aligned}$$

情報系列$\mathbf{w} = (0101)$に対し,得られた生成行列$\mathbf{G}^{'}$を用いて符号化を行なうと

$$\mathbf{x} = \mathbf{w}\mathbf{G}^{'} = (01010)$$

が得られる.

---

パリティ検査行列

$(n, k, d)$ 線形ブロック符号のパリティ検査行列$\mathbf{H}$は$(n - k) \times n$行列であり,$\mathbf{G}\mathbf{H}^T = \mathbf{0}$を満足する.パリティ検査行列$\mathbf{H}$は生成行列が$\mathbf{G}^{'}$形であるとき

$$\begin{aligned} \mathbf{H}^{'} = \begin{bmatrix} \mathbf{P}^T, \mathbf{I}_{n-k} \end{bmatrix} \end{aligned}$$

の形となる.

$\mathbf{G}\mathbf{H}^T = \mathbf{0}$を満足することより,$\mathbf{x}$と$\mathbf{H}$の関係は

$$\mathbf{w}\mathbf{G}\mathbf{H}^T = \mathbf{x}\mathbf{H}^T = \mathbf{0}$$

となることがわかる.

長さが $n$ の通信路で雑音$\mathbf{e}$と受信語$\mathbf{y}(= \mathbf{x} + \mathbf{e})$の関係を考える.$\mathbf{G}\mathbf{H}^T = \mathbf{0}$より,もし受信語$\mathbf{y}$が$\mathbf{y}\mathbf{H}^T = (\mathbf{x} + \mathbf{e})\mathbf{H}^T \neq \mathbf{0}$である場合は,受信語に誤りが混入していることが分かる.

またここで,誤り訂正を行なうための手がかりであるシンドロームと呼ばれる長さ$n - k$のベクトルを計算する.

ハミング符号を用いた1個誤り訂正

ハミング符号は任意の$m(\geq 2)$に対して$(n, k, d) = (2^m - 1, 2^m - 1 - m, 3), m = n - k$で与えられる線形ブロック符号である.
最小距離は$d = 3$であるため,前の定理より最小距離復号法を行なうことで$t = 1$ビットを必ず訂正することができる.

以下ではパリティ検査行列$\mathbf{H}$からハミング符号を構成する方法を説明する.

まずパリティ検査行列$\mathbf{H}$を以下のように表現する.

$$\begin{aligned} \mathbf{H} = \begin{bmatrix} \mathbf{h}_1, \mathbf{h}_2, \cdots, \mathbf{h}_n \end{bmatrix} \end{aligned}$$

ここで$\mathbf{h}_i, i = 1, 2, \cdots, n$は全てが異なる長さが$n - k(= m)$の非ゼロの列ベクトルとすると,長さが $m$ となる非ゼロベクトルは$2^m - 1$個あるので,$n = 2^m - 1$であることがわかる.

(7, 4, 3)ハミング符号

次式で$m = 3$となる$(n, k, d) = (7, 4, 3)$ハミング符号の
パリティ検査行列の一例を示す.

$$\begin{aligned} \mathbf{H} = \begin{bmatrix} 0001111 \\ 0110011 \\ 1010101 \end{bmatrix} \end{aligned}$$

$\mathbf{H}^{'}$の形式に変換すると

$$\begin{aligned} \mathbf{H}^{'} = \begin{bmatrix} \mathbf{P}^T, \mathbf{I}_{7-4} \end{bmatrix} = \begin{bmatrix} 0111100 \\ 1011010 \\ 1101001 \end{bmatrix} \end{aligned}$$

となる(各列の順番を入れ替えればよい).

また$\mathbf{H}^{'}$に対応する生成行列$\mathbf{G}^{'}$は

$$\begin{aligned} \mathbf{G}^{'} = \begin{bmatrix} \mathbf{I}_4, \mathbf{P} \end{bmatrix} = \begin{bmatrix} 1000011 \\ 0100101 \\ 0010110 \\ 0001111 \end{bmatrix} \end{aligned}$$

である.ここで

$$\begin{aligned} \mathbf{P} = \begin{bmatrix} 011 \\ 101 \\ 110 \\ 111 \end{bmatrix} \end{aligned}$$

組織符号

$\mathbf{G}^{'}, \mathbf{H}^{'}$で与えられた生成行列やパリティ検査行列をもつ符号は 組織符号と呼ばれ,符号語に情報部系列がそのまま表れる(情報部と冗長部に分けられる)性質をもつ.組織符号に変換するためには,生成行列やパリティ検査行列に対し行列の基本変形を行って次式のように変形すればよい.

$$\begin{aligned} &\mathbf{G}^{'} = \begin{bmatrix} \mathbf{I}_k, \mathbf{P} \end{bmatrix} \\ &\mathbf{H}^{'} = \begin{bmatrix} \mathbf{P}^T, \mathbf{I}_{n-k} \end{bmatrix} \end{aligned}$$

ハミング符号の復号

1ビット誤り訂正法

1. シンドローム$\mathbf{s} = \mathbf{y}\mathbf{H}^T$を計算する
2. $\mathbf{s} = \mathbf{h}_l, l = 1,\cdots,n$となるビット位置$l$の受信ビット$\mathbf{y}_l$を反転させる.すなわち,$l$番目のビット位置が誤り位置であり,このビットを反転($0 \rightarrow 1, 1 \rightarrow 0$)させればよい
3. 2より復号した符号語$\hat{\mathbf{x}}$, 推定系列$\hat{\mathbf{w}}$を得る

この復号法は最小距離復号を行なっており,ハミング符号を用いて最もハミング距離が近い符号語に訂正している.

例題(11.1)

(7,4,3)ハミング符号の生成行列とパリティ検査行列を用いて情報系列$\mathbf{w} = (0011)$を送信したとする.このとき受信語 $y$ が次の2つで受信したとき,最小距離復号を行って得られる推定系列および復号成功の可否を述べなさい.

パリティ検査行列の一例を示す.

$$\begin{aligned} \mathbf{H} = \begin{bmatrix} 0001111 \\ 0110011 \\ 1010101 \end{bmatrix} \end{aligned}$$

$\mathbf{H}^{'}$の形式に変換すると

$$\begin{aligned} \mathbf{H}^{'} = \begin{bmatrix} \mathbf{P}^T, \mathbf{I}_{7-4} \end{bmatrix} = \begin{bmatrix} 0111100 \\ 1011010 \\ 1101001 \end{bmatrix} \end{aligned}$$

また$\mathbf{H}^{'}$に対応する生成行列$\mathbf{G}^{'}$は

$$\begin{aligned} \mathbf{G}^{'} = \begin{bmatrix} \mathbf{I}_4, \mathbf{P} \end{bmatrix} = \begin{bmatrix} 1000011 \\ 0100101 \\ 0010110 \\ 0001111 \end{bmatrix} \end{aligned}$$

である.ここで

$$\begin{aligned} \mathbf{P} = \begin{bmatrix} 011 \\ 101 \\ 110 \\ 111 \end{bmatrix} \end{aligned}$$

1. $\mathbf{y} = (1111000)$

符号語$\mathbf{x} = \mathbf{w}\mathbf{G}^{'} = (0,0,1,1,0,0,1)$である.

シンドローム$\mathbf{s} = \mathbf{y}\mathbf{H}^{'T} = (1,1,1)$より,$(1,1,1)^T$はパリティ検査行列$\mathbf{H}^{'}$の4番目と一致するので,4ビット目に誤りが生じたと考え,このビットの1と0を反転した$\mathbf{y}^{'} = (1,1,1,0,0,0,0)$が送信されたと見なす.

復号した推定系列$\hat{\mathbf{w}} = (1,1,1,0)$より,ハミング符号において2個以上の誤りが生じた場合,正しく復号できない.

2. $\mathbf{y} = (0111001)$

上の手順と同様に,シンドローム$\mathbf{s} = \mathbf{y}\mathbf{H}^{'T} = (1,0,1)$である.$(1,0,1)^T$はパリティ検査行列$\mathbf{H}^{'}$の2番目と一致するので,2ビット目に誤りが生じたと考え,このビットの1と0を反転した$\mathbf{y}^{'} = (0,0,1,1,0,0,1)$が送信されたと見なす.

復号した推定系列$\hat{\mathbf{w}} = (0,0,1,1)$より,正しく復号した.

例題(11.2)

ハミング符号のパラメータで$m = 4$の場合の生成行列とパリティ検査行列の一例を示しなさい.ただし組織符号化が可能な形で答えなさい.

$m = 4$となる$(n, k, d) = (15, 11, 3)$ハミング符号のパリティ検査行列の一例を示す.

組織符号化が可能な形にすると,

$$\begin{aligned} \mathbf{H}^{'} = \begin{bmatrix} \mathbf{P}^T, \mathbf{I}_{15-11} \end{bmatrix} = \begin{bmatrix} 000000001111000 \\ 000011110000100 \\ 001100110010010 \\ 010101010100001 \end{bmatrix} \end{aligned}$$

また$\mathbf{H}^{'}$に対応する生成行列$\mathbf{G}^{'}$は

$$\begin{aligned} \mathbf{G}^{'} = \begin{bmatrix} \mathbf{I}_{11}, \mathbf{P} \end{bmatrix} = \begin{bmatrix} 100000000000000 \\ 010000000000001 \\ 001000000000010 \\ 000100000000011 \\ 000010000000100 \\ 000001000000101 \\ 000000100000110 \\ 000000010000111 \\ 000000001001000 \\ 000000000101001 \\ 000000000011010 \end{bmatrix} \end{aligned}$$

である.ここで

$$\begin{aligned} \mathbf{P} = \begin{bmatrix} 0000 \\ 0001 \\ 0010 \\ 0011 \\ 0100 \\ 0101 \\ 0110 \\ 0111 \\ 1000 \\ 1001 \\ 1010 \end{bmatrix} \end{aligned}$$

暗号(Cryptography)

RSA暗号

• 受信者アリス(Alice)は鍵 $n, e, d$を作成し, $n, e$を公開し, $d$を秘密鍵として保持, $p, q$ は廃棄
• 送信者ボブ(Bob)は公開された $n, e$ を用いて, 平文 $m$ を $c \equiv m^e \bmod n$ と暗号化して, 暗号文 $c$ を送信する
• 暗号文 $c$ を受信したアリスは秘密鍵 $d$ を用いて, $c^d \bmod n$ を求めると,平文 $m$ を得る
  • $c^d \equiv (m^e)^d = m^{ed} = m^{k\phi + 1} \equiv m \bmod n$

鍵 e,d の生成

1. ２つの異なる大きな素数 $p, q$ をランダムに選び,その積 $n = pq$ を求める
2. $n = pq$ のオイラー関数 $\phi = (p - 1)(q - 1)$に対し,これと互いに素となるような整数 $e$, $(1 < e < n)$ をランダムに選ぶ
3. $ed \equiv 1 \bmod \phi$ となるような整数 $d$ を求める. すなわち, $ed = k\phi + 1$ なる $d$ , 但し, $k$ は適当な正整数, $0 < d < \phi$. $e$ と $\phi$ が素の時, このような $d$ はただ一つのみ

---

例題: $RSA$ 暗号について, 素数 $p = 3, q = 5$, 平文 $m = 3$

1. $n = pq = 15$
2. オイラー関数$\phi = (p - 1)(q -1) = 8$, 整数 $e(1 < e < n) = 7$とする
3. $ed \equiv 1 \bmod \phi$ となるような整数 $d$ を求める.

$d$	$ed$	$\bmod \phi$
1	7	7
2	14	6
3	21	5
4	28	4
5	35	3
6	42	2
7	49	1
8	56	0

よって,$d = 7$

4. 平文$m$を暗号化する

$$\begin{aligned} c &\equiv m^e \bmod n \\ &\equiv 3^7 \bmod 15 \\ &\equiv 12 \end{aligned}$$

5. 暗号文 $c$ を復号する

$$\begin{aligned} &c^d \equiv (m^e)^d = m^{ed} = m^{k\phi + 1} \equiv m \bmod n \\ &3^{49} = 3^{6 \times 8 + 1} = 3 \bmod 15 \end{aligned}$$

よって, 平文 $m = 3$ が得た

---

フェルマーの定理

• $p$：素数
• $x$: $p$ の倍数でない整数

$$\begin{aligned} x^{p - 1} \equiv 1 (mod \ p) \\ x^p \equiv x (mod \ p) \end{aligned}$$

オイラーの定理

• $k$:自然数

$$x^{k\phi + 1} \equiv x$$

香农三大定理

香农第一定理

香农第一定理又称为无失真信源编码定理或变长码信源编码定理

香农第一定理的意义：将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。

对于第一定理的说明：

• 通过对扩展信源进行可变长编码，可以使平均码长无限趋近于极限熵值，但这是以编码复杂性为代价的
• 无失真信源编码实质：对离散信源进行适当的变换，使变换后新的符号序列信源尽可能为等概率分布，从而使新信源的每个码符号平均所含的信息量达到最大
• 香农第一定理仅是一个存在性定理，没有给出更有效的信源编码的实现方法

香农第二定理

香农第二定理又称为有噪信道编码定理

对于第二定理的说明：

• 第二定理纠正了人们传统固有的可靠性和有效性矛盾的观点，为信道编码理论和技术的研究指明了方向
• 第二定理仅指出编码的存在性，未给出编码的具体方法
• 第二定理指出：$R < C$是可靠传输的必要条件，但并未指出编码序列无限长是可靠传输的必要条件
• 香农进一步证明：$R = C$时，任意小的差错概率也是可以达到的

香农第三定理

香农第三定理又称为保失真度准则下的有失真信源编码定理