动机
压缩与纠错提出的是不同的问题。信源编码去除消息中可预测的结构;信道编码则引入结构,使接收方在噪声之后仍能区分不同的消息。仅仅数一数输出符号的个数,并不能衡量有多少信息得以保留:一个信道可以输出与输入无关的公平随机比特,其输出熵为一比特,却完全没有传达任何关于输入的信息。
真正相关的量,是观察到输出之后关于输入的不确定性的减少量。我们先对有限字母表建立这个量,再把它与译码错误概率联系起来。由此得到的逆定理之所以有用,是因为它适用于满足该模型的每一个编码器和译码器,包括我们从未见过其算法的那些。它给出的是一个必要的码率界;构造能够达到该界的码则是另一个定理。
我们使用以二为底的对数,并沿用前缀码(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 的编码理论入门讲义 。本文的有限字母表推导使模型以及这里所证明的有限逆定理变得明确。