動機
壓縮與糾錯提出的是不同的問題。信源編碼去除訊息中可預測的結構;通道編碼則引入結構,使接收方在噪聲之後仍能區分不同的訊息。僅僅數一數輸出符號的個數,並不能衡量有多少資訊得以保留:一個通道可以輸出與輸入無關的公平隨機位元,其輸出熵為一位元,卻完全沒有傳達任何關於輸入的資訊。
真正相關的量,是觀察到輸出之後關於輸入的不確定性的減少量。我們先對有限字母表建立這個量,再把它與解碼錯誤概率聯繫起來。由此得到的逆定理之所以有用,是因為它適用於符合該模型的每一個編碼器和解碼器,包括我們從未見過其算法的那些。它給出的是一個必要的碼率界;構造能夠達到該界的碼則是另一個定理。
我們使用以二為底的對數,並沿用前綴碼(prefix code)一章中有限熵的定義。所有隨機變量的取值範圍都是有限的,形如 0 log 0 0\log 0 0 log 0 的項取為零。
定義
從字母表 X \mathcal X X 到字母表 Y \mathcal Y Y 的有限通道 ,是一族概率 W ( y ∣ x ) ≥ 0 W(y\mid x)\ge0 W ( y ∣ x ) ≥ 0 ,且對每個輸入 x x x 都有 ∑ y W ( y ∣ x ) = 1 \sum\limits_yW(y\mid x)=1 y ∑ W ( y ∣ x ) = 1 。輸入分佈 p ( x ) p(x) p ( x ) 產生聯合分佈 p ( x , y ) = p ( x ) W ( y ∣ x ) p(x,y)=p(x)W(y\mid x) p ( x , y ) = p ( x ) W ( y ∣ x ) 。通道規定了每個輸入會發生甚麼;至於以多大頻率使用各個輸入,則是額外的數據。
條件熵 定義為
H ( X ∣ Y ) = ∑ y : p ( y ) > 0 p ( y ) H ( X ∣ Y = y ) . H(X\mid Y)=\sum_{y:p(y)>0}p(y)H(X\mid Y=y). H ( X ∣ Y ) = y : p ( y ) > 0 ∑ p ( y ) H ( X ∣ Y = y ) . 在熵的求和中代入 p ( x , y ) = p ( y ) p ( x ∣ y ) p(x,y)=p(y)p(x\mid y) p ( x , y ) = p ( y ) p ( x ∣ y ) 並拆分對數,即得鏈式法則 H ( X , Y ) = H ( Y ) + H ( X ∣ Y ) H(X,Y)=H(Y)+H(X\mid Y) H ( X , Y ) = H ( Y ) + H ( X ∣ Y ) 。互資訊 定義為
I ( X ; Y ) = H ( X ) − H ( X ∣ Y ) = H ( Y ) − H ( Y ∣ X ) . I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X). I ( X ; Y ) = H ( X ) − H ( X ∣ Y ) = H ( Y ) − H ( Y ∣ X ) . 第二個等號由鏈式法則得出,並給出對稱性。該定義並不要求輸入服從均勻分佈。二元熵函數為 h 2 ( u ) = − u log 2 u − ( 1 − u ) log 2 ( 1 − u ) h_2(u)=-u\log_2u-(1-u)\log_2(1-u) h 2 ( u ) = − u log 2 u − ( 1 − u ) log 2 ( 1 − u ) ,其在端點處按連續性取值為零。
交叉概率為 p p p 的二元對稱通道 (BSC)滿足 Y = X ⊕ Z Y=X\oplus Z Y = X ⊕ Z ,其中 Z Z Z 是參數為 p p p 、與輸入獨立的伯努利(Bernoulli)隨機變量。我們取 0 ≤ p ≤ 1 / 2 0\le p\le1/2 0 ≤ p ≤ 1/2 。擦除概率為 ϵ \epsilon ϵ 的二元擦除通道 (BEC)以概率 1 − ϵ 1-\epsilon 1 − ϵ 返回輸入位元,否則返回一個不同的符號 ? ? ? ;擦除事件與輸入獨立。擦除會暴露其位置;翻轉的位元則不會。
對於 n n n 次無記憶使用,條件分佈為 W n ( y n ∣ x n ) = ∏ i = 1 n W ( y i ∣ x i ) W^n(y^n\mid x^n)=\prod\limits_{i=1}^nW(y_i\mid x_i) W n ( y n ∣ x n ) = i = 1 ∏ n W ( y i ∣ x i ) 。各個輸入不必互相獨立。本章中的區塊碼從 K ≥ 2 K\ge2 K ≥ 2 種可能中均勻地選取訊息 M M M ,將其確定性地編碼為 X n X^n X n ,並用確定性函數 M ^ = g ( Y n ) \widehat M=g(Y^n) M = g ( Y n ) 來估計它。其平均錯誤概率為 P e = Pr ( M ^ ≠ M ) P_e=\Pr(\widehat M\ne M) P e = Pr ( M = M ) ,碼率為 R = ( log 2 K ) / n R=(\log_2K)/n R = ( log 2 K ) / n 位元每次使用。我們在訊息均勻分佈的約定下界定平均錯誤;這並不自動等同於對所有訊息取最大值的保證。
定理/命題
互資訊非負,且恰當 X X X 與 Y Y Y 互相獨立時為零。對於輸入滿足 Pr ( X = 1 ) = θ \Pr(X=1)=\theta Pr ( X = 1 ) = θ 的 BSC,
I ( X ; Y ) = h 2 ( p + ( 1 − 2 p ) θ ) − h 2 ( p ) ≤ 1 − h 2 ( p ) . I(X;Y)=h_2\bigl(p+(1-2p)\theta\bigr)-h_2(p)\le1-h_2(p). I ( X ; Y ) = h 2 ( p + ( 1 − 2 p ) θ ) − h 2 ( p ) ≤ 1 − h 2 ( p ) . 對於 BEC,I ( X ; Y ) = ( 1 − ϵ ) H ( X ) ≤ 1 − ϵ I(X;Y)=(1-\epsilon)H(X)\le1-\epsilon I ( X ; Y ) = ( 1 − ϵ ) H ( X ) ≤ 1 − ϵ 。均勻二元輸入可以分別達到上述兩個上界。這些都是對單次使用的互資訊所作的最大化;其編碼意義的詮釋還需要另外的可達性論證。
定理 3.3.6
(Fano 不等式與 BSC 的必要碼率界)
對於上述區塊碼模型,
H ( M ∣ Y n ) ≤ h 2 ( P e ) + P e log 2 ( K − 1 ) . H(M\mid Y^n)\le h_2(P_e)+P_e\log_2(K-1). H ( M ∣ Y n ) ≤ h 2 ( P e ) + P e log 2 ( K − 1 ) . 對於交叉概率為 p p p 的 n n n 次無記憶 BSC 使用,每個這樣的碼因而都滿足
( 1 − P e ) log 2 K ≤ n ( 1 − h 2 ( p ) ) + 1. (1-P_e)\log_2K\le n\bigl(1-h_2(p)\bigr)+1. ( 1 − P e ) log 2 K ≤ n ( 1 − h 2 ( p ) ) + 1. 因此,對於滿足 n → ∞ n\to\infty n → ∞ 且 P e → 0 P_e\to0 P e → 0 的碼序列,其碼率的上極限至多為 1 − h 2 ( p ) 1-h_2(p) 1 − h 2 ( p ) 。
證明思路或證明
展開定義得
I ( X ; Y ) = ∑ x , y : p ( x , y ) > 0 p ( x , y ) log 2 p ( x , y ) p ( x ) p ( y ) . I(X;Y)=\sum_{x,y:p(x,y)>0}p(x,y)
\log_2\frac{p(x,y)}{p(x)p(y)}. I ( X ; Y ) = x , y : p ( x , y ) > 0 ∑ p ( x , y ) log 2 p ( x ) p ( y ) p ( x , y ) . 這是聯合分佈相對於其邊緣分佈之乘積的散度。熵一章中證明的散度不等式使它非負,且等號成立當且僅當這兩個分佈相同。分子為正的項不會有零分母,因為聯合質量為正蘊含兩個邊緣質量均為正。等號成立的條件恰好就是獨立性。在每個條件分佈內部應用同樣的論證,還可得 I ( X ; Y ∣ Z ) ≥ 0 I(X;Y\mid Z)\ge0 I ( X ; Y ∣ Z ) ≥ 0 ,從而條件作用不會使熵增加:H ( X ∣ Y , Z ) ≤ H ( X ∣ Z ) H(X\mid Y,Z)\le H(X\mid Z) H ( X ∣ Y , Z ) ≤ H ( X ∣ Z ) 。特別地,H ( X ∣ Y ) ≤ H ( X ) H(X\mid Y)\le H(X) H ( X ∣ Y ) ≤ H ( X ) 。
在 BSC 中,輸出為一的概率是 ( 1 − θ ) p + θ ( 1 − p ) (1-\theta)p+\theta(1-p) ( 1 − θ ) p + θ ( 1 − p ) 。對於任一固定的輸入,輸出熵都是 h 2 ( p ) h_2(p) h 2 ( p ) ,故 H ( Y ∣ X ) = h 2 ( p ) H(Y\mid X)=h_2(p) H ( Y ∣ X ) = h 2 ( p ) 。從 H ( Y ) H(Y) H ( Y ) 中減去它即得公式。二元變量的熵至多為一,這由與均勻分佈的散度比較得出。均勻輸入使輸出也均勻,從而達到該界,端點情形也包括在內。
在 BEC 中,觀察到未被擦除的符號即可確定 X X X ,所以相應的條件熵為零。擦除與輸入無關,不改變其原有分佈,所以其條件熵為 H ( X ) H(X) H ( X ) 。取平均得 H ( X ∣ Y ) = ϵ H ( X ) H(X\mid Y)=\epsilon H(X) H ( X ∣ Y ) = ϵH ( X ) ,公式隨之成立。這一證明準確刻劃了擦除符號告訴接收方的內容,而不是把它當作普通的輸入位元。
當解碼器出錯時令 E = 1 E=1 E = 1 ,否則令 E = 0 E=0 E = 0 。由於 E E E 由 M M M 和 Y n Y^n Y n 確定,鏈式法則給出
H ( M ∣ Y n ) = H ( E ∣ Y n ) + H ( M ∣ E , Y n ) . H(M\mid Y^n)=H(E\mid Y^n)+H(M\mid E,Y^n). H ( M ∣ Y n ) = H ( E ∣ Y n ) + H ( M ∣ E , Y n ) . 第一項至多為 H ( E ) = h 2 ( P e ) H(E)=h_2(P_e) H ( E ) = h 2 ( P e ) 。當 E = 0 E=0 E = 0 時,訊息就是已知的值 g ( Y n ) g(Y^n) g ( Y n ) ,所以其剩餘的熵為零。當 E = 1 E=1 E = 1 且輸出固定時,至多還有 K − 1 K-1 K − 1 個訊息是可能的。至多取 K − 1 K-1 K − 1 個值的變量,其熵至多為 log 2 ( K − 1 ) \log_2(K-1) log 2 ( K − 1 ) ,這同樣由與這些值上的均勻分佈的散度得出。取平均即證明 Fano 不等式,錯誤概率為零的情形亦包括在內。零概率事件上的條件分佈可以略去。
Fano 不等式現在與通道的無記憶結構結合起來。
對於無記憶 BSC,一旦整個輸入被固定,各條件噪聲便互相獨立。因此 H ( Y n ∣ X n ) = n h 2 ( p ) H(Y^n\mid X^n)=nh_2(p) H ( Y n ∣ X n ) = n h 2 ( p ) 。由於編碼器是確定性的,且通道只透過編碼字依賴於訊息,故同樣有 H ( Y n ∣ M ) = n h 2 ( p ) H(Y^n\mid M)=nh_2(p) H ( Y n ∣ M ) = n h 2 ( p ) 。反覆使用鏈式法則以及條件作用使熵減小,得
H ( Y n ) = ∑ i = 1 n H ( Y i ∣ Y 1 , … , Y i − 1 ) ≤ ∑ i = 1 n H ( Y i ) ≤ n . H(Y^n)=\sum_{i=1}^nH(Y_i\mid Y_1,\ldots,Y_{i-1})
\le\sum_{i=1}^nH(Y_i)\le n. H ( Y n ) = i = 1 ∑ n H ( Y i ∣ Y 1 , … , Y i − 1 ) ≤ i = 1 ∑ n H ( Y i ) ≤ n . 由此 I ( M ; Y n ) = H ( Y n ) − H ( Y n ∣ M ) ≤ n ( 1 − h 2 ( p ) ) I(M;Y^n)=H(Y^n)-H(Y^n\mid M)\le n(1-h_2(p)) I ( M ; Y n ) = H ( Y n ) − H ( Y n ∣ M ) ≤ n ( 1 − h 2 ( p )) 。這一步允許輸入相關,而實際的碼字通常正是如此。最後,
log 2 K = H ( M ) = I ( M ; Y n ) + H ( M ∣ Y n ) ≤ n ( 1 − h 2 ( p ) ) + 1 + P e log 2 K . \log_2K=H(M)=I(M;Y^n)+H(M\mid Y^n)
\le n(1-h_2(p))+1+P_e\log_2K. log 2 K = H ( M ) = I ( M ; Y n ) + H ( M ∣ Y n ) ≤ n ( 1 − h 2 ( p )) + 1 + P e log 2 K . 我們用到了 h 2 ( P e ) ≤ 1 h_2(P_e)\le1 h 2 ( P e ) ≤ 1 和 log 2 ( K − 1 ) ≤ log 2 K \log_2(K-1)\le\log_2K log 2 ( K − 1 ) ≤ log 2 K 。移項即得有限區塊長度的界。對於 P e → 0 P_e\to0 P e → 0 的序列,在足夠後面的項上除以 n ( 1 − P e ) n(1-P_e) n ( 1 − P e ) ,便證明了碼率的結論。這一論證中從未假設編碼後的各座標互相獨立。
證明透視
均勻性、無記憶性與 Fano 不等式在哪裏進入 M M M 的均勻性只用了一次,即 log 2 K = H ( M ) \log_2K=H(M) log 2 K = H ( M ) 。無記憶性也只用了一次,即 H ( Y n ∣ M ) = n h 2 ( p ) H(Y^n\mid M)=nh_2(p) H ( Y n ∣ M ) = n h 2 ( p ) :給定碼字後,n n n 個噪聲位元互相獨立,每個貢獻 h 2 ( p ) h_2(p) h 2 ( p ) 。編碼器的確定性使這個值在以 M M M 為條件時成立,而不僅是以 X n X^n X n 為條件時成立。
關鍵的一步是用次可加性來控制 H ( Y n ) H(Y^n) H ( Y n ) ,而不是把它算出來。次可加性對每個聯合分佈都成立,所以碼字的各座標可以任意相關;用到的只是二元輸出的界 H ( Y i ) ≤ 1 H(Y_i)\le1 H ( Y i ) ≤ 1 。Fano 不等式提供餘下的鬆弛量 1 + P e log 2 K 1+P_e\log_2K 1 + P e log 2 K ,論證最後只需把一個關於 log 2 K \log_2K log 2 K 的線性不等式移項。常見錯誤中的反例說明:對相關噪聲而言,失效的是無記憶這一步,而不是次可加性這一步。
處理觀察結果不能創造資訊
還有一個相關的結構性事實,說明了為何選用巧妙的解碼器也無法規避資訊界。設 X , Y , Z X,Y,Z X , Y , Z 具有有限的聯合分佈,並且在給定 Y Y Y 的條件下,Z Z Z 與 X X X 獨立。換言之,一旦 Y Y Y 已知,產生 Z Z Z 的規則就不再能接觸到 X X X 。這就是馬爾可夫(Markov)條件 X → Y → Z X\to Y\to Z X → Y → Z 。確定性處理 Z = g ( Y ) Z=g(Y) Z = g ( Y ) 是一個重要的特例,但使用全新的獨立隨機性的隨機化處理同樣被涵蓋在內。
若取值有限的隨機變量構成馬爾可夫鏈 X → Y → Z X\to Y\to Z X → Y → Z ,則 I ( X ; Z ) ≤ I ( X ; Y ) I(X;Z)\le I(X;Y) I ( X ; Z ) ≤ I ( X ; Y ) 。
互資訊的鏈式法則可由展開條件熵得到,它以兩種方式給出同一個量:
I ( X ; Y , Z ) = I ( X ; Y ) + I ( X ; Z ∣ Y ) = I ( X ; Z ) + I ( X ; Y ∣ Z ) . I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)
=I(X;Z)+I(X;Y\mid Z). I ( X ; Y , Z ) = I ( X ; Y ) + I ( X ; Z ∣ Y ) = I ( X ; Z ) + I ( X ; Y ∣ Z ) . 條件獨立使第一個條件互資訊為零。再由第二個條件互資訊的非負性,便證明了數據處理不等式 I ( X ; Z ) ≤ I ( X ; Y ) I(X;Z)\le I(X;Y) I ( X ; Z ) ≤ I ( X ; Y ) 。這兩個要素都很重要:僅僅說 Z Z Z 是後來計算出來的,並不能保證馬爾可夫條件成立,因為其計算過程可能還看到了關於 X X X 的額外資訊。
作一個具體的比較:取擦除概率為二分之一的 BEC,並把每個擦除替換為一個新的公平猜測位元。所得的二元輸出與輸入不同的概率為四分之一:出錯需要先發生擦除,再猜錯。如果各次使用之間所有的猜測和擦除互相獨立,那麼每次通道使用現在是交叉概率為四分之一的 BSC。在均勻輸入下,原來的觀察保留二分之一位元,而猜測位元的觀察大約保留 0.1887 0.1887 0.1887 位元。損失的原因是替換隱藏了哪些觀察是擦除。若保留擦除標記,就能保住這部分額外的資訊。
數據處理並不是說解碼不能降低錯誤概率。碼約束了可能的輸入區塊,解碼器可以利用這些約束把帶噪的區塊變為準確的訊息估計。該不等式說的是:這個最終估計所含的關於訊息的互資訊,不可能多於整個被觀察到的區塊已經含有的互資訊。Fano 不等式把該估計的質素與必須已經存在的資訊聯繫起來。這兩個論證因而互相補足:一個控制觀察結果,另一個控制成功解碼所需要的條件。
例題詳解
設 X X X 是均勻位元,並取 p = 1 / 2 p=1/2 p = 1/2 的 BSC。則 Y Y Y 也是均勻的,但每個輸出都與輸入獨立:四個輸入輸出對的概率都是 1 / 4 1/4 1/4 。因此 H ( Y ) = 1 H(Y)=1 H ( Y ) = 1 ,H ( Y ∣ X ) = 1 H(Y\mid X)=1 H ( Y ∣ X ) = 1 ,I ( X ; Y ) = 0 I(X;Y)=0 I ( X ; Y ) = 0 。若 M = X M=X M = X 且接收方猜測 M ^ = Y \widehat M=Y M = Y ,則錯誤概率為 1 / 2 1/2 1/2 ,這與 Fano 界一致:H ( M ∣ Y ) = 1 ≤ h 2 ( 1 / 2 ) = 1 H(M\mid Y)=1\le h_2(1/2)=1 H ( M ∣ Y ) = 1 ≤ h 2 ( 1/2 ) = 1 。
取均勻輸入,事件概率為 1 / 4 1/4 1/4 。BEC 每次使用保留 1 − 1 / 4 = 3 / 4 1-1/4=3/4 1 − 1/4 = 3/4 位元。BSC 每次使用保留 1 − h 2 ( 1 / 4 ) 1-h_2(1/4) 1 − h 2 ( 1/4 ) ,約為 0.1887 0.1887 0.1887 位元。它們的事件概率相等,但擦除明確地標出了受損的觀察。驗證 BSC 的數值:h 2 ( 1 / 4 ) = 1 / 2 − ( 3 / 4 ) log 2 ( 3 / 4 ) ≈ 0.8113 h_2(1/4)=1/2-(3/4)\log_2(3/4)\approx0.8113 h 2 ( 1/4 ) = 1/2 − ( 3/4 ) log 2 ( 3/4 ) ≈ 0.8113 。把擦除替換為猜測位元會丟棄有用的資訊;這並不保持原來的通道模型。
設一個長度為 100 100 100 、p = 1 / 4 p=1/4 p = 1/4 的 BSC 碼有 K = 2 50 K=2^{50} K = 2 50 個等可能的訊息。則
( 1 − P e ) 50 ≤ 100 ( 1 − h 2 ( 1 / 4 ) ) + 1 ≈ 19.87. (1-P_e)50\le100(1-h_2(1/4))+1\approx19.87. ( 1 − P e ) 50 ≤ 100 ( 1 − h 2 ( 1/4 )) + 1 ≈ 19.87. 因此 P e ≳ 0.6026 P_e\gtrsim0.6026 P e ≳ 0.6026 。無論解碼器多麼巧妙,這個不等式都排除了在該區塊長度和訊息數下錯誤概率為 0.01 0.01 0.01 的聲稱。近似的小數只是為了方便顯示;精確的熵表達式才是真正的界。僅憑這個逆定理,既不能構造出更好的碼,也不能確定最小可能的錯誤概率。
當 R > 0 R>0 R > 0 時,碼率界也可寫成 P e ≥ 1 − C / R − 1 / ( n R ) P_e\ge1-C/R-1/(nR) P e ≥ 1 − C / R − 1/ ( n R ) ,其中 C = 1 − h 2 ( p ) C=1-h_2(p) C = 1 − h 2 ( p ) 。在固定正碼率 R > C R>C R > C 下,它給出 lim inf P e ≥ 1 − C / R > 0 \liminf P_e\ge1-C/R>0 lim inf P e ≥ 1 − C / R > 0 ,無須假設錯誤概率的極限存在。當 C > 0 C>0 C > 0 時,僅此下界並不迫使錯誤概率趨於一;這種一般性的結論需要更強的逆定理,本章並未證明。當 C = 0 C=0 C = 0 時,這個特定的界確實迫使 P e → 1 P_e\to1 P e → 1 。
常見錯誤
必須區分輸出的不確定性與所傳輸的資訊。與訊息無關的公平隨機輸出使二元輸出熵最大,卻甚麼也沒有傳達。在另一個極端,常數輸入的熵為零,因此即使通過無噪通道,互資訊也為零:通道本可以承載資訊,但所選的輸入分佈沒有利用它。
無記憶性是關於給定輸入時輸出的條件性陳述。它並不斷言所選碼字的各座標互相獨立,也不斷言無條件的輸出互相獨立。熵的次可加性這一步有意避開了該假設。若不證明獨立性就使用 H ( Y n ) = ∑ i H ( Y i ) H(Y^n)=\sum\limits_iH(Y_i) H ( Y n ) = i ∑ H ( Y i ) ,則對許多碼而言會使逆定理失效。
反例模式
各座標上的噪聲互相獨立是一個真實的假設 設對每個座標加上同一個公平位元 Z Z Z ,即對所有 i i i 有 Y i = X i ⊕ Z Y_i=X_i\oplus Z Y i = X i ⊕ Z 。每個單獨的座標看上去都像交叉概率為 1 / 2 1/2 1/2 的 BSC,但區塊通道並不是無記憶的。把一個數據位元 M M M 編碼為 ( 0 , M ) (0,M) ( 0 , M ) 。接收方由輸出計算 Y 1 ⊕ Y 2 = M Y_1\oplus Y_2=M Y 1 ⊕ Y 2 = M ,沒有任何錯誤。此時 I ( M ; Y 1 , Y 2 ) = 1 I(M;Y_1,Y_2)=1 I ( M ; Y 1 , Y 2 ) = 1 ,而無記憶情形的步驟會給出 I ( M ; Y 2 ) ≤ 2 ( 1 − h 2 ( 1 / 2 ) ) = 0 I(M;Y^2)\le2\bigl(1-h_2(1/2)\bigr)=0 I ( M ; Y 2 ) ≤ 2 ( 1 − h 2 ( 1/2 ) ) = 0 ,這是錯誤的結論。同樣,把 n − 1 n-1 n − 1 個數據位元 m m m 編碼為 ( 0 , m ) (0,m) ( 0 , m ) ,可得碼率 ( n − 1 ) / n (n-1)/n ( n − 1 ) / n 而錯誤概率為零,與無記憶的零碼率界矛盾。起作用的是聯合噪聲分佈,而不僅僅是它的單座標邊緣分佈。
總結
互資訊量度的是通道所保留的依賴關係,而不是其輸出的隨機性。Fano 不等式把解碼器的錯誤概率轉化為對訊息剩餘不確定性的界。無記憶二元噪聲限制了一個區塊上可獲得的資訊,從而得出平均錯誤趨於零所需的必要碼率條件。這一論證把可達性、高效構造和更強的逆定理留作另外的問題。
練習
快速檢查
(對於輸入為一的概率是 θ \theta θ 的無噪二元通道,計算互資訊並指出使其最大的輸入。)
比較輸出等於輸入時的 H ( X ∣ Y ) H(X\mid Y) H ( X ∣ Y ) 與 H ( X ) H(X) H ( X ) 。
解答 · 答案 此時 Y = X Y=X Y = X ,所以 H ( X ∣ Y ) = 0 H(X\mid Y)=0 H ( X ∣ Y ) = 0 ,I ( X ; Y ) = h 2 ( θ ) I(X;Y)=h_2(\theta) I ( X ; Y ) = h 2 ( θ ) 。其最大值為一位元,在 θ = 1 / 2 \theta=1/2 θ = 1/2 處取得。端點處的輸入是常數,給出零。
快速檢查
(均勻輸入通過擦除概率為 0.6 0.6 0.6 的 BEC。計算 H ( X ∣ Y ) H(X\mid Y) H ( X ∣ Y ) 與 I ( X ; Y ) I(X;Y) I ( X ; Y ) 。)
解答 · 答案 發生擦除時不確定性為一位元,否則為零。因此 H ( X ∣ Y ) = 0.6 H(X\mid Y)=0.6 H ( X ∣ Y ) = 0.6 ,I ( X ; Y ) = 1 − 0.6 = 0.4 I(X;Y)=1-0.6=0.4 I ( X ; Y ) = 1 − 0.6 = 0.4 位元。
快速檢查
(設 M M M 在四個訊息上均勻分佈。一個確定性解碼器的錯誤概率為 1 / 4 1/4 1/4 。Fano 不等式給出 H ( M ∣ Y ) H(M\mid Y) H ( M ∣ Y ) 的甚麼上界?為甚麼這個值不只是 h 2 ( 1 / 4 ) h_2(1/4) h 2 ( 1/4 ) ?)
以 K = 4 K=4 K = 4 、P e = 1 / 4 P_e=1/4 P e = 1/4 代入 Fano 不等式。
解答 上界為 h 2 ( 1 / 4 ) + ( 1 / 4 ) log 2 3 h_2(1/4)+(1/4)\log_2 3 h 2 ( 1/4 ) + ( 1/4 ) log 2 3 ,約為 1.2075 1.2075 1.2075 位元。錯誤指示變量只說明猜測是否錯誤;當猜測錯誤時,仍可能有三個可能的訊息。第二項正是計入了這部分不確定性。Fano 不等式給出的是上界,不一定是等式。
快速檢查
(對於固定正碼率 R > C = 1 − h 2 ( p ) R>C=1-h_2(p) R > C = 1 − h 2 ( p ) 的無記憶 BSC 碼序列,由有限區塊長度的不等式推導平均錯誤的漸近正下界。它是否證明了錯誤趨於一?)
把 log 2 K = n R \log_2K=nR log 2 K = n R 代入有限區塊長度的不等式。
解答 代入 log 2 K = n R \log_2K=nR log 2 K = n R 得 P e ≥ 1 − C / R − 1 / ( n R ) P_e\ge1-C/R-1/(nR) P e ≥ 1 − C / R − 1/ ( n R ) 。因此 lim inf P e ≥ 1 − C / R > 0 \liminf P_e\ge1-C/R>0 lim inf P e ≥ 1 − C / R > 0 。當 C > 0 C>0 C > 0 時,該界嚴格小於一,所以它並不能證明收斂到一。當 C = 0 C=0 C = 0 而碼率保持為正時,這個特定的界確實迫使錯誤趨於一;而一般的高於容量的情形,要得出該結論還需要額外的工作。
關於更廣泛的通道編碼背景,參見 Venkatesan Guruswami 的編碼理論入門講義 。本文的有限字母表推導使模型以及這裏所證明的有限逆定理變得明確。