相対エントロピーから情報と物理を組み立てる 第1部 第6章 §1.6.3 ★★★ 速さ R < C R<C R < C R > C R>C R > C
符号と速さ
送りたい内容を M M M v ∈ { 1 , … , M } v\in\{1,\dots,M\} v ∈ { 1 , … , M } n n n
定義 1.6.7（符号・速さ・誤りの確率）
長さ n n n M M M 符号 は、符号化 v ↦ x n ( v ) ∈ X n v\mapsto x^n(v)\in\mathcal X^n v ↦ x n ( v ) ∈ X n g : Y n → { 1 , … , M } g:\mathcal Y^n\to\{1,\dots,M\} g : Y n → { 1 , … , M } x n ( 1 ) , … , x n ( M ) x^n(1),\dots,x^n(M) x n ( 1 ) , … , x n ( M ) 符号語 と呼ぶ。符号の速さ を
R = ln M n [ nat／回 ] (1.6.11) R=\frac{\ln M}{n}\quad[\text{nat／回}]\tag{1.6.11} R = n ln M [ nat ／回 ] ( 1.6.11 )
で定める（ビットで言うときは log 2 M / n \log_2M/n log 2 M / n V V V
P e r r ( n ) = Pr ( g ( Y n ) ≠ V ) = 1 M ∑ v = 1 M Pr ( g ( Y n ) ≠ v ∣ x n ( v ) を送った ) P_{\mathrm{err}}^{(n)}=\Pr\bigl(g(Y^n)\neq V\bigr)=\frac1M\sum_{v=1}^M\Pr\bigl(g(Y^n)\neq v\,\big|\,x^n(v)\text{ を送った}\bigr) P err ( n ) = Pr ( g ( Y n ) = V ) = M 1 v = 1 ∑ M Pr ( g ( Y n ) = v x n ( v ) を送った )
とする。
速さ R R R 1 3 \frac13 3 1 0 0 0 0 0 0 0 0 0 C C C 0 0 0
定理 1.6.8（通信路符号化定理（Shannon 1948） ★★★）
離散無記憶通信路の容量を C C C
(i) （順定理）R < C R<C R < C R R R P e r r ( n ) → 0 P_{\mathrm{err}}^{(n)}\to0 P err ( n ) → 0 n → ∞ n\to\infty n → ∞ (ii) （逆定理）速さ R R R
P e r r ( n ) ≥ 1 − C R − ln 2 n R . (1.6.12) P_{\mathrm{err}}^{(n)}\ \ge\ 1-\frac CR-\frac{\ln2}{nR}.\tag{1.6.12} P err ( n ) ≥ 1 − R C − n R ln 2 . ( 1.6.12 )
したがって R > C R>C R > C n n n 1 − C / R > 0 1-C/R>0 1 − C / R > 0
逆定理のほうが短いので先に示す。
逆定理：Fano の不等式とデータ処理不等式
補題 1.6.9（Fano の不等式 ★★）
V V V V ^ \hat V V ^ M M M P e r r = Pr ( V ^ ≠ V ) P_{\mathrm{err}}=\Pr(\hat V\neq V) P err = Pr ( V ^ = V )
H ( V ∣ V ^ ) ≤ h b ( P e r r ) + P e r r ln ( M − 1 ) ≤ ln 2 + P e r r ln M . (1.6.13) H(V\,|\,\hat V)\le h_{\mathrm b}(P_{\mathrm{err}})+P_{\mathrm{err}}\ln(M-1)\le\ln2+P_{\mathrm{err}}\ln M .\tag{1.6.13} H ( V ∣ V ^ ) ≤ h b ( P err ) + P err ln ( M − 1 ) ≤ ln 2 + P err ln M . ( 1.6.13 )
証明 誤りの有無を表す変数 E E E V ^ ≠ V \hat V\neq V V ^ = V 1 1 1 0 0 0 E E E ( V , V ^ ) (V,\hat V) ( V , V ^ ) H ( V ∣ V ^ ) = H ( V , E ∣ V ^ ) H(V\,|\,\hat V)=H(V,E\,|\,\hat V) H ( V ∣ V ^ ) = H ( V , E ∣ V ^ ) H ( V , E ∣ V ^ ) = H ( E ∣ V ^ ) + H ( V ∣ E , V ^ ) H(V,E\,|\,\hat V)=H(E\,|\,\hat V)+H(V\,|\,E,\hat V) H ( V , E ∣ V ^ ) = H ( E ∣ V ^ ) + H ( V ∣ E , V ^ ) H ( E ) = h b ( P e r r ) H(E)=h_{\mathrm b}(P_{\mathrm{err}}) H ( E ) = h b ( P err ) E = 0 E=0 E = 0 V = V ^ V=\hat V V = V ^ 0 0 0 E = 1 E=1 E = 1 V V V V ^ \hat V V ^ M − 1 M-1 M − 1 ln ( M − 1 ) \ln(M-1) ln ( M − 1 ) P e r r ln ( M − 1 ) P_{\mathrm{err}}\ln(M-1) P err ln ( M − 1 )
Fano の不等式は「誤りが少ないなら、推定値を知ったあとの元の値の不確かさは小さい」ことを量で言う。逆向きに読むと、受け手の手元に残る不確かさが大きければ誤りは減らせない。
補題 1.6.10（無記憶通信路の相互情報量 ★★）
入力の列 X n X^n X n Y n Y^n Y n
I ( X n ; Y n ) ≤ ∑ i = 1 n I ( X i ; Y i ) ≤ n C . (1.6.14) I(X^n;Y^n)\le\sum_{i=1}^nI(X_i;Y_i)\le nC .\tag{1.6.14} I ( X n ; Y n ) ≤ i = 1 ∑ n I ( X i ; Y i ) ≤ n C . ( 1.6.14 )
証明 I ( X n ; Y n ) = H ( Y n ) − H ( Y n ∣ X n ) I(X^n;Y^n)=H(Y^n)-H(Y^n\,|\,X^n) I ( X n ; Y n ) = H ( Y n ) − H ( Y n ∣ X n ) (1.6.1) から、x n x^n x n Y 1 , … , Y n Y_1,\dots,Y_n Y 1 , … , Y n Y i Y_i Y i x i x_i x i H ( Y n ∣ X n ) = ∑ i H ( Y i ∣ X i ) H(Y^n\,|\,X^n)=\sum_iH(Y_i\,|\,X_i) H ( Y n ∣ X n ) = ∑ i H ( Y i ∣ X i ) H ( Y n ) ≤ ∑ i H ( Y i ) H(Y^n)\le\sum_iH(Y_i) H ( Y n ) ≤ ∑ i H ( Y i ) 相対エントロピーから情報と物理を組み立てる 第1部第3章 ）。差をとると1つ目の不等号が出る。各項 I ( X i ; Y i ) I(X_i;Y_i) I ( X i ; Y i ) X i X_i X i C C C
逆定理 (ii) の証明 メッセージ V V V H ( V ) = ln M = n R H(V)=\ln M=nR H ( V ) = ln M = n R V → X n → Y n → V ^ = g ( Y n ) V\to X^n\to Y^n\to\hat V=g(Y^n) V → X n → Y n → V ^ = g ( Y n ) V V V X n X^n X n Y n Y^n Y n 相対エントロピーから情報と物理を組み立てる 第1部第4章 ）を2回使うと I ( V ; V ^ ) ≤ I ( X n ; Y n ) I(V;\hat V)\le I(X^n;Y^n) I ( V ; V ^ ) ≤ I ( X n ; Y n ) (1.6.13) ・補題 1.6.10 から
n R = H ( V ) = H ( V ∣ V ^ ) + I ( V ; V ^ ) ≤ ln 2 + P e r r ( n ) n R + n C . nR=H(V)=H(V\,|\,\hat V)+I(V;\hat V)\le\ln2+P_{\mathrm{err}}^{(n)}\,nR+nC . n R = H ( V ) = H ( V ∣ V ^ ) + I ( V ; V ^ ) ≤ ln 2 + P err ( n ) n R + n C .
両辺を n R nR n R (1.6.12) になる。
逆定理の証明に通信路の細かい形は一度も出てこない。使ったのは「内容は通信路を通る間に増えない」というデータ処理不等式と、1回あたりの上限 C C C D D D D D D
順定理：ランダムな符号と同時典型性
順定理の証明は、良い符号を具体的に作らずに「乱数で作った符号の誤りを平均すると小さい、だから小さいものが少なくとも1つある」という論法をとる。道具は典型系列（相対エントロピーから情報と物理を組み立てる 第1部第2章 ）を入力と出力の組に広げたものである。
定義 1.6.11（同時典型集合）
結合分布 p X Y p_{XY} p X Y δ > 0 \delta>0 δ > 0 ( x n , y n ) (x^n,y^n) ( x n , y n ) 同時典型集合 A δ ( n ) A_\delta^{(n)} A δ ( n )
∣ − 1 n ln p n ( x n ) − H ( X ) ∣ < δ , ∣ − 1 n ln q n ( y n ) − H ( Y ) ∣ < δ , ∣ − 1 n ln p X Y n ( x n , y n ) − H ( X , Y ) ∣ < δ . \Bigl|-\tfrac1n\ln p^n(x^n)-H(X)\Bigr|<\delta,\quad\Bigl|-\tfrac1n\ln q^n(y^n)-H(Y)\Bigr|<\delta,\quad\Bigl|-\tfrac1n\ln p^n_{XY}(x^n,y^n)-H(X,Y)\Bigr|<\delta . − n 1 ln p n ( x n ) − H ( X ) < δ , − n 1 ln q n ( y n ) − H ( Y ) < δ , − n 1 ln p X Y n ( x n , y n ) − H ( X , Y ) < δ .
ここで p n ( x n ) = ∏ i p ( x i ) p^n(x^n)=\prod_ip(x_i) p n ( x n ) = ∏ i p ( x i ) n n n
補題 1.6.12（同時典型性 ★★）
( X n , Y n ) (X^n,Y^n) ( X n , Y n ) p X Y p_{XY} p X Y n n n
(a) Pr ( ( X n , Y n ) ∈ A δ ( n ) ) → 1 \Pr\bigl((X^n,Y^n)\in A_\delta^{(n)}\bigr)\to1 Pr ( ( X n , Y n ) ∈ A δ ( n ) ) → 1 n → ∞ n\to\infty n → ∞ (b) ∣ A δ ( n ) ∣ ≤ e n ( H ( X , Y ) + δ ) |A_\delta^{(n)}|\le\mathrm{e}^{n(H(X,Y)+\delta)} ∣ A δ ( n ) ∣ ≤ e n ( H ( X , Y ) + δ ) (c) X ′ n X'^n X ′ n Y ′ n Y'^n Y ′ n p n p^n p n q n q^n q n 互いに独立に 引くと
Pr ( ( X ′ n , Y ′ n ) ∈ A δ ( n ) ) ≤ e − n ( I ( X ; Y ) − 3 δ ) . (1.6.15) \Pr\bigl((X'^n,Y'^n)\in A_\delta^{(n)}\bigr)\le\mathrm{e}^{-n(I(X;Y)-3\delta)} .\tag{1.6.15} Pr ( ( X ′ n , Y ′ n ) ∈ A δ ( n ) ) ≤ e − n ( I ( X ; Y ) − 3 δ ) . ( 1.6.15 )
証明 (a) 3つの条件はどれも、独立な確率変数 − ln p ( X i ) -\ln p(X_i) − ln p ( X i ) 1 1 1 相対エントロピーから情報と物理を組み立てる 第1部第2章 ）。(b) A δ ( n ) A_\delta^{(n)} A δ ( n ) p X Y n ≥ e − n ( H ( X , Y ) + δ ) p^n_{XY}\ge\mathrm{e}^{-n(H(X,Y)+\delta)} p X Y n ≥ e − n ( H ( X , Y ) + δ ) 1 1 1 e n ( H ( X , Y ) + δ ) \mathrm{e}^{n(H(X,Y)+\delta)} e n ( H ( X , Y ) + δ ) A δ ( n ) A_\delta^{(n)} A δ ( n ) p n ( x n ) ≤ e − n ( H ( X ) − δ ) p^n(x^n)\le\mathrm{e}^{-n(H(X)-\delta)} p n ( x n ) ≤ e − n ( H ( X ) − δ ) q n ( y n ) ≤ e − n ( H ( Y ) − δ ) q^n(y^n)\le\mathrm{e}^{-n(H(Y)-\delta)} q n ( y n ) ≤ e − n ( H ( Y ) − δ )
Pr ≤ ∑ ( x n , y n ) ∈ A δ ( n ) p n ( x n ) q n ( y n ) ≤ e n ( H ( X , Y ) + δ ) e − n ( H ( X ) − δ ) e − n ( H ( Y ) − δ ) = e − n ( H ( X ) + H ( Y ) − H ( X , Y ) − 3 δ ) . \Pr\le\sum_{(x^n,y^n)\in A_\delta^{(n)}}p^n(x^n)q^n(y^n)\le\mathrm{e}^{n(H(X,Y)+\delta)}\,\mathrm{e}^{-n(H(X)-\delta)}\,\mathrm{e}^{-n(H(Y)-\delta)}=\mathrm{e}^{-n(H(X)+H(Y)-H(X,Y)-3\delta)} . Pr ≤ ( x n , y n ) ∈ A δ ( n ) ∑ p n ( x n ) q n ( y n ) ≤ e n ( H ( X , Y ) + δ ) e − n ( H ( X ) − δ ) e − n ( H ( Y ) − δ ) = e − n ( H ( X ) + H ( Y ) − H ( X , Y ) − 3 δ ) .
指数の H ( X ) + H ( Y ) − H ( X , Y ) H(X)+H(Y)-H(X,Y) H ( X ) + H ( Y ) − H ( X , Y ) I ( X ; Y ) I(X;Y) I ( X ; Y )
(c) の指数 I ( X ; Y ) = D ( p X Y ∥ p X p Y ) I(X;Y)=D(p_{XY}\,\|\,p_Xp_Y) I ( X ; Y ) = D ( p X Y ∥ p X p Y ) p X p Y p_Xp_Y p X p Y p X Y p_{XY} p X Y D D D e − n D \mathrm{e}^{-nD} e − n D e − n D \mathrm{e}^{-nD} e − n D 相対エントロピーから情報と物理を組み立てる 第1部第8章 で一般の形に直す。
順定理 (i) の証明の骨格 容量を達成する入力 p ∗ p^* p ∗ R < C R<C R < C δ > 0 \delta>0 δ > 0 R < C − 3 δ R<C-3\delta R < C − 3 δ M = ⌈ e n R ⌉ M=\lceil\mathrm{e}^{nR}\rceil M = ⌈ e n R ⌉ x n ( 1 ) , … , x n ( M ) x^n(1),\dots,x^n(M) x n ( 1 ) , … , x n ( M ) p ∗ p^* p ∗ y n y^n y n 1 1 1 x n ( 1 ) x^n(1) x n ( 1 ) y n y^n y n x n ( v ) x^n(v) x n ( v ) v ≠ 1 v\neq1 v = 1 y n y^n y n 0 0 0 v ≠ 1 v\neq1 v = 1 y n y^n y n
Pr ( ほかの符号語が同時典型 ) ≤ ( M − 1 ) e − n ( C − 3 δ ) ≤ e n R e − n ( C − 3 δ ) = e − n ( C − 3 δ − R ) → 0. \Pr(\text{ほかの符号語が同時典型})\le(M-1)\,\mathrm{e}^{-n(C-3\delta)}\le\mathrm{e}^{nR}\mathrm{e}^{-n(C-3\delta)}=\mathrm{e}^{-n(C-3\delta-R)}\to0 . Pr ( ほかの符号語が同時典型 ) ≤ ( M − 1 ) e − n ( C − 3 δ ) ≤ e n R e − n ( C − 3 δ ) = e − n ( C − 3 δ − R ) → 0.
符号の作り方についての平均の誤り確率が 0 0 0
なぜ e n C \mathrm{e}^{nC} e n C
入力が典型的なら、出力の典型系列はおよそ e n H ( Y ) \mathrm{e}^{nH(Y)} e n H ( Y ) e n H ( Y ∣ X ) \mathrm{e}^{nH(Y|X)} e n H ( Y ∣ X ) e n H ( Y ) / e n H ( Y ∣ X ) = e n I ( X ; Y ) \mathrm{e}^{nH(Y)}/\mathrm{e}^{nH(Y|X)}=\mathrm{e}^{nI(X;Y)} e n H ( Y ) / e n H ( Y ∣ X ) = e n I ( X ; Y ) e n C \mathrm{e}^{nC} e n C
定理が言わないこと
順定理は符号が存在することを言うが、作り方と復号の手間については何も言わない。乱数の符号を表で引いて復号すると、手間は M = e n R M=\mathrm{e}^{nR} M = e n R n → ∞ n\to\infty n → ∞ n n n 0 0 0 D D D 相対エントロピーから情報と物理を組み立てる 第1部第8章 の大偏差の道具で扱う。逆定理の式 (1.6.12) は R > C R>C R > C 1 − C / R 1-C/R 1 − C / R R > C R>C R > C 1 1 1
例題 1.6.3 容量を超えた速さで送るときの誤りの下限 ★★
オリジナル BSC(0.1 0.1 0.1 C = ln 2 − h b ( 0.1 ) C=\ln2-h_{\mathrm b}(0.1) C = ln 2 − h b ( 0.1 ) 1.6.6 節で確かめる）。
C C C 速さ 0.75 0.75 0.75 n = 100 n=100 n = 100 n → ∞ n\to\infty n → ∞
速さ 0.5 0.5 0.5 n = 100 n=100 n = 100
解答 (1) h b ( 0.1 ) = − 0.1 ln 0.1 − 0.9 ln 0.9 ≈ 0.3251 h_{\mathrm b}(0.1)=-0.1\ln0.1-0.9\ln0.9\approx0.3251 h b ( 0.1 ) = − 0.1 ln 0.1 − 0.9 ln 0.9 ≈ 0.3251 C ≈ 0.6931 − 0.3251 = 0.3681 C\approx0.6931-0.3251=0.3681 C ≈ 0.6931 − 0.3251 = 0.3681 ln 2 \ln2 ln 2 0.5310 0.5310 0.5310
(2) 式 (1.6.12) はビットで書いても形が変わらず、ln 2 n R \frac{\ln2}{nR} n R l n 2 R R R 1 n R ビット \frac{1}{nR_{\text{ビット}}} n R ビット 1
P e r r ≥ 1 − 0.5310 0.75 − 1 100 × 0.75 ≈ 1 − 0.708 − 0.013 = 0.279. P_{\mathrm{err}}\ge1-\frac{0.5310}{0.75}-\frac{1}{100\times0.75}\approx1-0.708-0.013=0.279 . P err ≥ 1 − 0.75 0.5310 − 100 × 0.75 1 ≈ 1 − 0.708 − 0.013 = 0.279.
n → ∞ n\to\infty n → ∞ 1 − 0.708 = 0.292 1-0.708=0.292 1 − 0.708 = 0.292
(3) M = 2 n R = 2 50 ≈ 1.13 × 10 15 M=2^{nR}=2^{50}\approx1.13\times10^{15} M = 2 n R = 2 50 ≈ 1.13 × 1 0 15 0.5 0.5 0.5 0.531 0.531 0.531 n n n n = 100 n=100 n = 100
AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。 連絡先：support@tecktom.com
