情報源符号化と通信路符号化クラフトの不等式・ハフマン符号・通信路容量・ハミング符号

記号ごとの瞬時符号の平均符号長 $L$ はエントロピー以上で、最適な符号では $H(X) \le L < H(X) + 1$ となり、確率の小さい2つを繰り返しまとめるハフマン符号がその最適符号を与える。通信路の容量は $C = \max_{p(x)} I(X;Y)$ で、二元対称通信路では $C = 1 - h(p)$ である。符号化率 $R < C$ なら誤り確率をいくらでも小さくできる符号が存在し、 $R > C$ では不可能である（通信路符号化定理）。

情報理論の第2単元（全2単元）。先に読む単元：エントロピーと相互情報量

情報系院試の問題集・ロードマップ

東大情報理工・東京科学大・阪大の大学別に、出題マップと類題を1冊にした教材（各4,980円）。収録内容と見本を商品ページで確認できる。

情報系の教材を見る

符号・瞬時符号・通信路の定義

定義

一意復号可能な符号と瞬時符号

情報源の各記号 $x$ に2元の符号語 $c(x) \in \{0,1\}^*$ を割り当てる。符号語を連結した列がつねに1通りにしか区切れないとき、一意復号可能という。どの符号語も他の符号語の先頭部分（接頭語）でないとき、瞬時符号（語頭符号、prefix code）という。瞬時符号は一意復号可能で、符号語を読み終えた時点で復号できる。平均符号長は $L = \sum_x p(x)\,\ell(x)$ （ $\ell(x)$ は符号語の長さ）。

定義

離散無記憶通信路と通信路容量

入力 $X \in \mathcal{X}$ に対して出力 $Y \in \mathcal{Y}$ が条件付き確率 $p(y \mid x)$ で決まり、各時刻で独立に働く通信路を離散無記憶通信路という。その通信路容量を

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

で定める。 $n$ 個の通信路記号で $M$ 通りの通報を送る符号の符号化率は $R = (\log_2 M)/n$ である。

定義

ハミング距離と最小距離

同じ長さの2元系列 $\boldsymbol{u}, \boldsymbol{v}$ で値の異なる位置の数をハミング距離 $d(\boldsymbol{u}, \boldsymbol{v})$ という。符号の異なる2符号語の距離の最小値を最小距離 $d_{\min}$ という。線形符号では $d_{\min}$ は零でない符号語の重み（1の個数）の最小値に等しい。

クラフトの不等式と情報源符号化定理

定理・法則

クラフトの不等式とマクミランの定理

条件

記号数 $m$ 、2元符号、符号語の長さ $\ell_1, \dots, \ell_m$ （正の整数）。

主張

この長さの瞬時符号が存在するための必要十分条件は

\sum_{i=1}^{m} 2^{-\ell_i} \le 1

である。一意復号可能な符号の長さも同じ不等式を満たす（マクミランの定理）。

要点

長さを短い順に並べ、二分木の深さ $\ell_i$ の節点を順に割り当て、その下の部分木を使用済みにすると瞬時符号が作れる。マクミランの定理から、一意復号可能な符号に広げても平均符号長は短くならない。

定理・法則

情報源符号化定理（記号ごとの符号）

条件

離散無記憶情報源 $X$ 、2元の一意復号可能な符号。

主張

どの符号でも $L \ge H(X)$ で、 $\ell(x) = \lceil -\log_2 p(x) \rceil$ （シャノン符号）とすれば $L < H(X) + 1$ となる。最適な符号の平均符号長 $L^*$ は $H(X) \le L^* < H(X) + 1$ を満たす。

要点

$n$ 記号をまとめて符号化すると1記号あたり $H(X) \le L_n/n < H(X) + 1/n$ となり、 $n \to \infty$ で $H(X)$ に近づく。 $L = H(X)$ となるのは、すべての $p(x)$ が $2^{-\ell}$ の形のときに限る。

ハフマン符号は次の手順で作る。

各記号を、確率を重みとする葉にする。
重みの最も小さい2つを選び、それらを子とする新しい節点（重みは2つの和）に置き換える。
節点が1つになるまで2を繰り返す。
根から各葉への経路で、左の枝に $0$ 、右の枝に $1$ を割り当てて符号語とする。

ハフマン符号は瞬時符号の中で平均符号長が最小である。同じ重みが複数あるときの選び方で符号語の長さの組は変わり得るが、平均符号長はどれも最小値に等しい。

通信路容量と通信路符号化定理

定理・法則

通信路符号化定理

条件

容量 $C$ の離散無記憶通信路。

主張

$R < C$ なら、任意の $\varepsilon > 0$ に対して、十分大きな $n$ で符号化率 $R$ 以上、最大誤り確率 $\varepsilon$ 未満の符号が存在する。 $R > C$ なら、どの符号でも $n \to \infty$ で誤り確率は0に近づかない。

要点

定理は符号の存在を示すもので、符号の作り方は与えない。 $R < C$ で誤り確率を小さくするには、一般に符号長 $n$ を大きくする必要がある。

代表的な通信路の容量

二元対称通信路（BSC）: $P(Y \ne X) = p \ \Rightarrow\ C = 1 - h(p)$
入力が一様分布のときに $I(X;Y)$ が最大になる。 $p = 1/2$ で $C = 0$ 。 $p$ と $1 - p$ で容量は同じ。
二元消失通信路（BEC）: $P(Y = \mathrm{e}) = \varepsilon \ \Rightarrow\ C = 1 - \varepsilon$
$\mathrm{e}$ は消失を表す出力記号。 $I(X;Y) = (1 - \varepsilon)H(X)$ 。
雑音のない通信路: $Y = X,\ |\mathcal{X}| = m \ \Rightarrow\ C = \log_2 m$

定理・法則

最小距離と誤り訂正・検出

条件

最小距離 $d_{\min}$ のブロック符号。復号は受信語に最も近い符号語を選ぶ（最小距離復号）。

主張

$d_{\min} \ge 2t + 1$ なら $t$ 個以下の誤りを必ず訂正できる。 $d_{\min} \ge s + 1$ なら $s$ 個以下の誤りを必ず検出できる。

要点

符号語を中心とする半径 $t$ の球が互いに交わらないことによる。長さ $n$ 、通報 $2^k$ 個で $t$ 誤りを訂正する符号は $2^k\sum_{i=0}^{t}\binom{n}{i} \le 2^n$ （ハミング限界）を満たし、等号の符号を完全符号という。

ハフマン符号・通信路容量・ハミング符号の計算例

計算例

ハフマン符号の構成

記号 $a, b, c, d, e$ の確率が $0.4, 0.2, 0.2, 0.1, 0.1$ のとき、ハフマン符号を作り、平均符号長とエントロピーを比べよ。

解答

$d\,(0.1)$ と $e\,(0.1)$ をまとめて $0.2$ 。
$b\,(0.2)$ と $c\,(0.2)$ をまとめて $0.4$ 。
$\{d,e\}\,(0.2)$ と $\{b,c\}\,(0.4)$ をまとめて $0.6$ 。
$a\,(0.4)$ と残りの $0.6$ をまとめて根にする。

符号語の例は $a \mapsto 11$ 、 $b \mapsto 00$ 、 $c \mapsto 01$ 、 $d \mapsto 100$ 、 $e \mapsto 101$ で

L = 0.4\cdot 2 + 0.2 \cdot 2 + 0.2 \cdot 2 + 0.1 \cdot 3 + 0.1\cdot 3 = 2.2

エントロピーは $H = -\sum p_i \log_2 p_i \approx 2.122$ で、 $H \le L < H + 1$ を満たす。

検算

クラフトの和は $3 \cdot 2^{-2} + 2\cdot 2^{-3} = 1$ 。手順2で $b$ と $\{d,e\}$ をまとめる選び方では $a, c, b, d, e$ の長さが $1, 2, 3, 4, 4$ になるが、平均は $0.4 + 0.4 + 0.6 + 0.4 + 0.4 = 2.2$ で同じ。クラフトの不等式を満たす長さの組を全部調べても平均の最小は $2.2$ 。シャノン符号の長さ $(2, 3, 3, 4, 4)$ の平均は $2.8$ で、ハフマン符号のほうが短い。

計算例

2記号をまとめて符号化する

$0, 1$ を確率 $0.9, 0.1$ で出す情報源について、1記号ずつの符号と、2記号ずつのハフマン符号の1記号あたりの平均符号長を比べよ。

解答

1記号ずつでは符号語の長さは1以上なので $L = 1$ 。エントロピーは $h(0.1) \approx 0.469$ 。

2記号の組 $00, 01, 10, 11$ の確率は $0.81, 0.09, 0.09, 0.01$ 。ハフマン符号は長さ $1, 2, 3, 3$ になり、平均は

L_2 = 0.81 \cdot 1 + 0.09 \cdot 2 + 0.09 \cdot 3 + 0.01 \cdot 3 = 1.29

で、1記号あたり $L_2/2 = 0.645$ 。

検算

$H \le L_2/2 < H + 1/2$ 、つまり $0.469 \le 0.645 < 0.969$ を満たす。まとめる記号数を増やすと、1記号あたりの平均符号長は $0.469$ に近づく。

計算例

二元対称通信路の容量と繰り返し符号

誤り確率 $p = 0.1$ の二元対称通信路の容量を求めよ。また、各ビットを3回送って多数決で復号する符号の、ビットあたりの誤り確率と符号化率を求めよ。

解答

C = 1 - h(0.1) \approx 1 - 0.469 = 0.531 \ \text{bit/通信路記号}

繰り返し符号では、3ビット中2ビット以上が反転すると誤る。

P_e = \binom{3}{2}(0.1)^2(0.9) + (0.1)^3 = 0.027 + 0.001 = 0.028

符号化率は $R = 1/3$ 。

検算

入力分布 $P(X = 1) = a$ を $0.001$ 刻みで動かすと $I(X;Y)$ の最大は $a = 0.5$ での $0.531$ で、 $1 - h(p)$ と一致する。 $R = 1/3 < C$ なので、通信路符号化定理からは、符号長を大きくすれば同じ符号化率で誤り確率をいくらでも小さくできる符号が存在する。繰り返し符号は回数を増やすと誤り確率は下がるが、符号化率も0に近づく。

計算例

ハミング (7,4) 符号のシンドローム復号

パリティ検査行列を $H = \begin{pmatrix} 1&0&1&0&1&0&1 \\ 0&1&1&0&0&1&1 \\ 0&0&0&1&1&1&1 \end{pmatrix}$ （第 $j$ 列は $j$ の2進表示を下位桁から上に並べたもの）とする。符号語 $0110011$ を送り、受信語が $\boldsymbol{r} = 0110111$ だった。誤りの位置を求めよ。

解答

シンドローム $\boldsymbol{s} = H\boldsymbol{r}^{\mathsf T} \pmod 2$ を行ごとに計算する。第1行は位置 $1,3,5,7$ の和 $0 + 1 + 1 + 1 \equiv 1$ 、第2行は位置 $2,3,6,7$ の和 $1 + 1 + 1 + 1 \equiv 0$ 、第3行は位置 $4,5,6,7$ の和 $0 + 1 + 1 + 1 \equiv 1$ 。

$\boldsymbol{s} = (1, 0, 1)^{\mathsf T}$ は $H$ の第5列で、2進数 $101_2 = 5$ に当たる。第5ビットを反転して $0110011$ に戻す。

検算

送った $0110011$ では3行とも和が偶数でシンドロームは $\boldsymbol{0}$ 。符号語は $H\boldsymbol{c}^{\mathsf T} = \boldsymbol{0}$ の解で $2^4 = 16$ 個、零でない符号語の最小重みは3なので $d_{\min} = 3$ で1誤りを訂正できる。 $2^4(1 + 7) = 2^7$ でハミング限界の等号が成り立ち、完全符号である。

答案でよくある誤り

1
クラフトの不等式を満たす長さなら、どの符号語の割り当ても瞬時符号になると考える。不等式は長さの組についての存在条件で、具体的な符号語は接頭語にならないように選ぶ（ $\{0, 01\}$ は長さの和 $3/4 \le 1$ だが瞬時符号でない）。
2
ハフマン符号の平均符号長がエントロピーに等しいと書く。等しいのは確率がすべて2のべきのときで、一般には $H \le L < H + 1$ 。
3
二元対称通信路の容量を $1 - p$ とする。それは消失通信路の容量で、二元対称通信路では $1 - h(p)$ 。 $p = 0.1$ で $0.9$ と $0.531$ の差がある。
4
通信路容量の定義で入力分布の最大化を落とし、与えられた入力分布での $I(X;Y)$ を容量と書く。容量は $\max_{p(x)} I(X;Y)$ で、問題の入力分布での値はそれ以下である。
5
最小距離3の符号で2個の誤りも訂正できるとする。 $d_{\min} = 3$ で訂正できるのは1誤りまで（検出なら2誤りまで）で、2誤りは別の符号語の近くに移って誤って訂正される。