04本篇是《信息论》的读书笔记，欢迎各位路过指正！今天十章全部更新完毕啦。
0.分章节目录
【计算机科学与技术】信息论笔记（1）：熵、相对熵与互信息【计算机科学与技术】信息论笔记（2）： 渐近均分性【计算机科学与技术】信息论笔记（3）：随机过程的熵率【计算机科学与技术】信息论笔记（4）：数据压缩【计算机科学与技术】 信息论笔记（5）：信道容量【计算机科学与技术】信息论笔记（6）：微分熵【计算机科学与技术】信息论笔记（7）：高斯信道【计算机科学与技术】信息论笔记（8）：率失真理论【计算机科学与技术】信息论笔记（9）：最大熵【计算机科学与技术】信息论笔记（10）：通用信源编码文章目录
0.分章节目录1. 熵、相对熵与互信息1.1 绪论与概述1.2 熵1.3 联合熵1.4 条件熵1.5 相对熵1.6 互信息1.7 Jensen不等式1.8 对数和不等式1.9 数据处理不等式2. 渐进均分性2.1 渐进均分性定理2.2 数据压缩2.3 高概率集与典型集3. 随机过程的熵率3.1 马尔科夫链3.2 熵率3.3 马尔科夫链的函数4. 数据压缩4.1 编码的基本概念4.2 Kraft不等式4.3 最优码4.4 Haffman编码4.5 算术编码5. 信道容量5.1 基本概念5.2 对称信道5.3 信道编码定理5.4 联合典型序列5.5 汉明码5.6 反馈容量6. 微分熵6.1 定义6.2 连续随机变量的AEP6.3 微分熵与离散的关系6.4 联合微分熵与条件微分熵6.5 相对熵与互信息6.6 微分熵、相对熵以及互信息的性质7. 高斯信道7.1 定义7.2 带宽有限信道7.3 并联高斯信道容量8. 率失真理论8.1 量化8.2 定义8.3 率失真函数的计算9. 最大熵9.1 最大熵分布9.2 谱估计9.3 高斯过程的熵率9.4 Burg最大熵定理10. 通用信源编码10.1 通用码与信道容量10.2 二元序列的通用编码10.3 算术编码10.4 Lempel-Ziv编码1. 熵、相对熵与互信息
1.1 绪论与概述
香农（C.E.Shannon）于1948年发表论文“通信的数学理论”奠定了信息论的基础。
香农第一定理（无失真信源编码定理）：给出编码极限。
香农第二定理（有噪信道编码定理）：传输速率小于信道容量，则误码率可以任意小。
香农第三定理（保失真度准则下的有失真信源编码定理）：给定失真度，只要码字足够长，就可以使编码的失真度小于给定失真度。
1.2 熵
熵的定义：H(X)=H(p1,p2,⋯,pK)=−∑n=1KpnlogpnH(X)=H\left(p_{1}, p_{2}, \cdots, p_{K}\right)=-\sum_{n=1}^{K} p_{n} \log p_{n} H(X)=H(p1,p2,⋯,pK)=−n=1∑Kpnlogpn
一元信源模型：
[Xp(x)]=[a1a2⋯aKp(a1)p(a2)⋯p(aK)]\left[\begin{array}{c}X \\ p(x)\end{array}\right]=\left[\begin{array}{cccc}a_{1} & a_{2} & \cdots & a_{K} \\ p\left(a_{1}\right) & p\left(a_{2}\right) & \cdots & p\left(a_{K}\right)\end{array}\right] [Xp(x)]=[a1p(a1)a2p(a2)⋯⋯aKp(aK)]
有0≤pn≤10 \leq p_n \leq 10≤pn≤1，∑n=1Kpn=1\sum_{n=1}^K p_n = 1∑n=1Kpn=1。若X∼p(x)X\sim p(x)X∼p(x)，则随机变量g(X)g(X)g(X)的期望为E[g(x)]=∑g(x)p(x)E[g(x)]=\sum g(x)p(x)E[g(x)]=∑g(x)p(x)。随机变量XXX的熵可看为随机变量log(1/p(X))log(1/p(X))log(1/p(X))的数学期望，其中p(x)p(x)p(x)为XXX的概率密度函数。
熵函数应符合下面三条公理：（1）对称性：交换下标不影响熵值。（2）最大值：等概分布熵值最大。（3）若pK=p11+...+p1ip_K = p_{11} + ... + p_{1i}pK=p11+...+p1i则两个分布有如下关系：
H(p1,p2,⋯,pK−1,p11,p12,⋯,p1l)=H(p1,p2,⋯,pk)+pkH(p11pK,p12pK,⋯,p1ipK)H\left(p_{1}, p_{2}, \cdots, p_{K-1}, p_{11}, p_{12}, \cdots, p_{1 l}\right)=H\left(p_{1}, p_{2}, \cdots, p_{k}\right)+p_{k} H\left(\frac{p_{11}}{p_{K}}, \frac{p_{12}}{p_{K}}, \cdots, \frac{p_{1 i}}{p_{K}}\right) H(p1,p2,⋯,pK−1,p11,p12,⋯,p1l)=H(p1,p2,⋯,pk)+pkH(pKp11,pKp12,⋯,pKp1i)
熵的含义：（1）平均意义：熵是整个集合的统计特性。（2）信息熵：H(X)H(X)H(X)表示每个消息提供的平均信息量。（3）随机性：信息熵H(X)H(X)H(X)表征了变量X的随机性。
熵的链式法则：
H(X1,X2,⋯,Xn)=∑i=1nH(Xi∣Xi−1,⋯,X1)H\left(X_{1}, X_{2}, \cdots, X_{n}\right)=\sum_{i=1}^{n} H\left(X_{i} \mid X_{i-1}, \cdots, X_{1}\right) H(X1,X2,⋯,Xn)=i=1∑nH(Xi∣Xi−1,⋯,X1)
1.3 联合熵
二元信源模型：[XYp(XY)]=[a1b1a1b2a1b3…akbJp(a1,b1)p(a1,b2)p(a1,b3)…p(aK,bJ)]\left[\begin{array}{c}X Y \\ p(X Y)\end{array}\right]=\left[\begin{array}{cccc}a_{1} b_{1} & a_{1} b_{2} & a_{1} b_{3} & \ldots & a_{k} b_{J} \\ p\left(a_{1}, b_{1}\right) & p\left(a_{1}, b_{2}\right) & p\left(a_{1}, b_{3}\right) & \ldots & p\left(a_{K}, b_{J}\right)\end{array}\right] [XYp(XY)]=[a1b1p(a1,b1)a1b2p(a1,b2)a1b3p(a1,b3)……akbJp(aK,bJ)]
其中∑k=1K∑j=1Jp(ak,bj)=1\sum_{k=1}^K \sum_{j=1}^J p (a_k,b_j) = 1∑k=1K∑j=1Jp(ak,bj)=1。
联合熵的定义：
H(X,Y)=−∑k=1K∑j=1Jp(ak,bj)logp(ak,bj)=−E[logp(X,Y)]H(X, Y)=-\sum_{k=1}^{K} \sum_{j=1}^{J} p\left(a_{k}, b_{j}\right) \log p\left(a_{k}, b_{j}\right)=-E[\log p(X,Y)] H(X,Y)=−k=1∑Kj=1∑Jp(ak,bj)logp(ak,bj)=−E[logp(X,Y)]
若独立，则联合熵等于单个随机变量熵之和；条件熵等于无条件熵（绝对熵）。
有等式
H(X,Y)=H(X)+H(Y∣X)=H(Y)+H(X∣Y)H(X,Y) = H(X) + H(Y | X) =H(Y) + H(X | Y) H(X,Y)=H(X)+H(Y∣X)=H(Y)+H(X∣Y)
1.4 条件熵
条件熵的定义：H(Y∣X)=−∑k=1K∑j=1Jp(ak,bj)logp(bj∣ak)H(Y|X) = -\sum_{k=1}^K \sum_{j=1}^J p(a_k,b_j)\log p(b_j|a_k) H(Y∣X)=−k=1∑Kj=1∑Jp(ak,bj)logp(bj∣ak)
条件熵链式法则：
H(X,Y∣Z)=H(X∣Z)+H(Y∣X,Z)H(X,Y|Z) = H(X|Z) + H(Y | X,Z) H(X,Y∣Z)=H(X∣Z)+H(Y∣X,Z)
确定关系：若XXX与YYY有确定的函数关系，且XXX可以完全确定YYY（或YYY完全确定XXX），则H(Y∣X)=H(X∣Y)=0H(Y|X) = H(X|Y) = 0H(Y∣X)=H(X∣Y)=0。
条件熵不大于绝对熵是平均意义下的结论。
1.5 相对熵
相对熵（Kullback熵） ：两个随机分布之间距离的度量。
D(p∣∣q)=∑k=1Kp(ak)logp(ak)q(ak)D(p||q) = \sum_{k=1}^Kp(a_k)\log\frac{p(a_k)}{q(a_k)} D(p∣∣q)=k=1∑Kp(ak)logq(ak)p(ak)
条件相对熵：一对随机变量的两个联合分布之间的相对熵可以展开为相对熵和条件相对熵之和。
D(p(y∣x)∥q(y∣x))=∑xp(x)∑yp(y∣x)logp(y∣x)q(y∣x)=Ep(x,y)logp(Y∣X)q(Y∣X)D(p(y \mid x) \| q(y \mid x))=\sum_{x} p(x) \sum_{y} p(y \mid x) \log \frac{p(y \mid x)}{q(y \mid x)}=E_{p(x, y)} \log \frac{p(Y \mid X)}{q(Y \mid X)} D(p(y∣x)∥q(y∣x))=x∑p(x)y∑p(y∣x)logq(y∣x)p(y∣x)=Ep(x,y)logq(Y∣X)p(Y∣X)
相对熵的链式法则：
D(p(x,y)∥q(x,y))=D(p(x)∥q(x))+D(p(y∣x)∥q(y∣x))D(p(x, y) \| q(x, y))=D(p(x) \| q(x))+D(p(y \mid x) \| q(y \mid x)) D(p(x,y)∥q(x,y))=D(p(x)∥q(x))+D(p(y∣x)∥q(y∣x))
1.6 互信息
互信息的定义：
I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)=I(Y;X)I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) = I(Y;X) I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)=I(Y;X)
也可以采用直接定义XXX与YYY之间的互信息为
I(X;Y)=∑k=1K∑j=1Jp(ak,bj)logp(ak,bj)p(ak)p(bj)I(X ; Y)=\sum_{k=1}^{K} \sum_{j=1}^{J} p\left(a_{k}, b_{j}\right) \log \frac{p\left(a_{k}, b_{j}\right)}{p\left(a_{k}\right) p\left(b_{j}\right)} I(X;Y)=k=1∑Kj=1∑Jp(ak,bj)logp(ak)p(bj)p(ak,bj)
熵与互信息的关系：互信息是随机变量之间相互依存度的度量信息。
单个互信息物理意义：Y=bjY=b_jY=bj下获得的X=akX=a_kX=ak的信息量，互信息I(X;Y)I(X;Y)I(X;Y)为单个互信息的均值。
熵可由互信息导出。自信息的数学期望就是信息熵，H(X)=E[I(ak,ak)]=E[H(ak)]H(X) = E[I(a_k,a_k)]=E[H(a_k)]H(X)=E[I(ak,ak)]=E[H(ak)]。
条件互信息：给定随机变量ZZZ时，由YYY的信息而获得的关于XXX的信息
I(X;Y∣Z)=H(X∣Z)−H(X∣Y,Z)=∑k=1K∑j=1J∑l=1Lp(ak,bj,ci)logp(ak,bj∣ci)p(ak∣ci)p(bj∣ci)I(X ; Y \mid Z)=H(X \mid Z)-H(X \mid Y, Z)=\sum_{k=1}^{K} \sum_{j=1}^{J} \sum_{l=1}^{L} p\left(a_{k}, b_{j}, c_{i}\right) \log \frac{p\left(a_{k}, b_{j} \mid c_{i}\right)}{p\left(a_{k} \mid c_{i}\right) p\left(b_{j} \mid c_{i}\right)} I(X;Y∣Z)=H(X∣Z)−H(X∣Y,Z)=k=1∑Kj=1∑Jl=1∑Lp(ak,bj,ci)logp(ak∣ci)p(bj∣ci)p(ak,bj∣ci)
互信息的链式法则：
I(X1,X2,⋯,Xn;Y)=∑i=1nI(Xi;Y∣Xi−1,⋯,X1)I\left(X_{1}, X_{2}, \cdots, X_{n} ; Y\right)=\sum_{i=1}^{n} I\left(X_{i} ; Y \mid X_{i-1}, \cdots, X_{1}\right) I(X1,X2,⋯,Xn;Y)=i=1∑nI(Xi;Y∣Xi−1,⋯,X1)
1.7 Jensen不等式
Jensen不等式：设函数f(x)f(x)f(x)是凸域DDD上的下凸函数，则对任意am∈Da_m \in Dam∈D，0≤λm≤1,λ1+...+λM=10\leq \lambda_m \leq 1, \lambda_1+ ... + \lambda_M = 10≤λm≤1,λ1+...+λM=1有
f(∑m=1Mλmαm)≤∑m=1Mλmf(αn)f\left(\sum_{m=1}^{M} \lambda_{m} \alpha_{m}\right) \leq \sum_{m=1}^{M} \lambda_{m} f\left(\alpha_{n}\right) f(m=1∑Mλmαm)≤m=1∑Mλmf(αn)
信息不等式：两个概率密度函数为p(x)p(x)p(x)和q(x)q(x)q(x)之间的鉴别信息为D(p∣∣q)D(p||q)D(p∣∣q)，则：D(p∣∣q)≥0D(p||q) \geq 0D(p∣∣q)≥0，当且仅当对任意的xxx，p(x)=q(x)p(x)=q(x)p(x)=q(x)，等号成立。
推论：
I(X;Y)≥0I(X;Y∣Z)≥0D(p(y∣x)∣∣q(y∣x))≥0I(X;Y) \geq 0\\ I(X;Y|Z) \geq 0\\ D(p(y|x)||q(y|x))\geq 0 I(X;Y)≥0I(X;Y∣Z)≥0D(p(y∣x)∣∣q(y∣x))≥0
H(X)≤log∣X∣H(X)\leq log|X|H(X)≤log∣X∣，其中∣X∣|X|∣X∣表示XXX的字母表XXX中元素的个数，当且仅当XXX服从XXX上的均匀分布时，等号成立。
意义：在平均意义下，信源的不确定性减少。
H(X)≥H(X∣Y)H ( X ) \geq H ( X | Y ) H(X)≥H(X∣Y)
熵的独立界：当且仅当XiX_iXi相互独立，等号成立。熵函数为上凸函数。
H(X1,X2,⋯,Xn)≤∑i=1nH(Xi)H\left(X_{1}, X_{2}, \cdots, X_{n}\right) \leq \sum_{i=1}^{n} H\left(X_{i}\right) H(X1,X2,⋯,Xn)≤i=1∑nH(Xi)
定理：互信息为信源概率分布的上凸函数；互信息为信道矩阵的下凸函数。
1.8 对数和不等式
上面的等式中假设信源概率分布为p:p(ak)p:p(a_k)p:p(ak)。互信息由概率分布和条件概率矩阵确定。记为Q:p(bj∣ak)Q:p(b_j|a_k)Q:p(bj∣ak)。QQQ有时也称为信道转移概率矩阵。互信息可记为I(p,Q)I ( p, Q )I(p,Q)。对数和不等式：对于非负数a1,a2,…,ana_1, a_2, …,a_na1,a2,…,an和b1,b2,…,bnb_1, b_2, …,b_nb1,b2,…,bn，当且仅当aibi\frac{a_i}{b_i}biai为常数时，等号成立 。∑i=1nailogaibi≥(∑i=1nai)log(∑i=1nai/∑i=1nbi)\sum_{i=1}^{n} a_{i} \log \frac{a_{i}}{b_{i}} \geq\left(\sum_{i=1}^{n} a_{i}\right) \log \left(\sum_{i=1}^{n} a_{i} / \sum_{i=1}^{n} b_{i}\right) i=1∑nailogbiai≥(i=1∑nai)log(i=1∑nai/i=1∑nbi)相对熵的下凸性：D(p∣∣q)D(p||q)D(p∣∣q)关于对(p,q)(p,q)(p,q)是下凸的。
1.9 数据处理不等式
数据处理不等式：数据处理都会损失信息。若X→Y→ZX\to Y\to ZX→Y→Z构成Markov链，则
I(X;Y)≥I(X;Z)I(X;Y)\geq I(X;Z) I(X;Y)≥I(X;Z)
费诺不等式：定义误差概率为Pe=Pr{X^≠X}P_e = Pr\{\hat{X} \neq X\}Pe=Pr{X^=X}。则对任何满足X→Y→X^X\to Y\to \hat{X}X→Y→X^的估计量X^\hat{X}X^,有
H(Pe)+Pelog∣X∣≥H(X∣X^)≥H(X∣Y)1+Pelog∣X∣≥H(X∣Y)H\left(P_{\mathrm{e}}\right)+P_{\mathrm{e}} \log |\boldsymbol{X}| \geq H(X \mid \hat{X}) \geq H(X \mid Y)\\ 1+P_{\mathrm{e}} \log |\boldsymbol{X}| \geq H(X \mid Y) H(Pe)+Pelog∣X∣≥H(X∣X^)≥H(X∣Y)1+Pelog∣X∣≥H(X∣Y)
意义：假定没有任何关于YYY的知识，只能在毫无信息的情况下对XXX进行推测。设X∈{1,2,…,K}X\in \{1,2,…,K\}X∈{1,2,…,K}且p1≥p2≥…≥pKp_1\geq p_2 \geq …\geq p_Kp1≥p2≥…≥pK，则对XXX的最佳估计是 X^=1\hat{X}=1X^=1，而此时产生的误差概率为Pe=1−p1P_e=1-p_1Pe=1−p1。
误差概率与熵之间的不等式：设XXX和X’X’X’为两个独立同分布的随机变量，有相同的熵H(X)H(X)H(X)，那么X=X′X=X'X=X′的概率为
Pr(X=X′)=∑p2(x)\operatorname{Pr}\left(X=X^{\prime}\right)=\sum p^{2}(x) Pr(X=X′)=∑p2(x)
2. 渐进均分性
2.1 渐进均分性定理
信息符号冗余度：冗余度高，符号携带的信息率低，易于压缩；
信源的冗余编码：提高单个信息符号所携带的信息量。
渐进等同分割性（Asymptotic Equipartition Property）结论：信源分布等概，信息熵最大。
定理2.1.1（渐进均分性）：设X1,X2,...,XnX_1,X_2,...,X_nX1,X2,...,Xn 是概率密度函数为p(x)的独立同分布(i.i.d)的随机变量，则
−1nlogp(X1,X2,⋯,Xn)→H(X)-\frac{1}{n} \log p\left(X_{1}, X_{2}, \cdots, X_{n}\right) \rightarrow H(X) −n1logp(X1,X2,⋯,Xn)→H(X)
直观解释：当序列足够长时，一部分序列就显现出这样的性质：**序列中各个符号的出现频数非常接近于各自的出现概率，而这些序列的概率则趋近于相等，且它们的和非常接近于1，这些序列就称为典型序列。**其余的非典型序列的出现概率之和接近于零。
香农在1948年的《通信的数学理论》中注意到它并表述为一个定理。后来麦克米伦在1953年发表的《信息论的基本定理》一文中严格地证明了这一结果。
定义2.1.1（典型集）：设X1,X2,...,XnX_1,X_2,...,X_nX1,X2,...,Xn 是概率密度函数为p(x)p(x)p(x)的i.i.d随机序列，如果联合分布p(x1,x2,…,xn)p(x_1, x_2,… ,x_n)p(x1,x2,…,xn)满足下列条件：
∣logp(x1,x2,⋯,xn)n+H(X)∣≤ε\left|\frac{\log p\left(x_{1}, x_{2}, \cdots, x_{n}\right)}{n}+H(X)\right| \leq \varepsilon ∣∣∣∣nlogp(x1,x2,⋯,xn)+H(X)∣∣∣∣≤ε
则称该源字母序列为典型序列（典型集），记为Aε(n)A_\varepsilon^{(n)}Aε(n)。
直观意义：（1）给定特定的误差范围ε和序列长nnn，离散无记忆信源输出序列的集中程度；（2）若固定εεε ，nnn越大，典型序列中元素个数越多；（3）若固定nnn， εεε越大，典型序列中元素个数越多；（4）典型序列中的序列趋于等概。
定理2.1.2（典型集性质）：（1）设(x1,x2,...,xn)∈Aε(n)(x_1,x_2,...,x_n)\in A_\varepsilon^{(n)}(x1,x2,...,xn)∈Aε(n)则有：H(X)−ε≤−1nlogp(x1,x2,⋯,xn)≤H(X)+εH(X)-\varepsilon \leq-\frac{1}{n} \log p\left(x_{1}, x_{2}, \cdots, x_{n}\right) \leq H(X)+\varepsilonH(X)−ε≤−n1logp(x1,x2,⋯,xn)≤H(X)+ε
（2）.当nnn充分大时，Pr{Aε(n)}>1−εPr\{A_\varepsilon^{(n)}\}>1-\varepsilonPr{Aε(n)}>1−ε。
（3）.∣Aε(n)∣⩽2n(H(X)+ε)|A_\varepsilon^{(n)}|\leqslant 2^{n(H(X)+\varepsilon)}∣Aε(n)∣⩽2n(H(X)+ε)。
（4）.当nnn充分大时，∣Aε(n)∣⩾(1−ε)2n(H(X)+ε)|A_\varepsilon^{(n)}|\geqslant (1-\varepsilon)2^{n(H(X)+\varepsilon)}∣Aε(n)∣⩾(1−ε)2n(H(X)+ε)
2.2 数据压缩
数据压缩：将集合元素按某种顺序（比如字典序）排列，指定下标可表示Aε(n)A_\varepsilon^{(n)}Aε(n)中的每个序列。这需要n(H+ε)+1n(H+\varepsilon)+1n(H+ε)+1个比特，编码前加0，共需n(H+ε)+2n(H+\varepsilon)+2n(H+ε)+2个比特。对不属于Aε(n)A_\varepsilon^{(n)}Aε(n)编码，比特数nlog∣X∣+1n\log|X|+1nlog∣X∣+1，编码前加1。
编码特点：一一映射，易于译码；第一个比特标明了编码长度；非典序列枚举扩大编码范围；典型序列编码长度为nHnHnH。分组编码作用：编码效率接近理想。
定理2.2.1（平均码长编码定理）：设XnX^nXn为服从p(x)p(x)p(x)的i.i.d序列，ε>0ε>0ε>0，则存在一个编码将长度为nnn的序列xnx_nxn映射为比特串，使得其为一一映射，（因而可逆），且对于充分大的nnn，有
E[1nl(Xn)]≤H(X)+εE\left[\frac{1}{n} l\left(X^{n}\right)\right] \leq H(X)+\varepsilon E[n1l(Xn)]≤H(X)+ε
于是平均意义上用nH(X)nH(X)nH(X)可以表示序列XnX^nXn。
2.3 高概率集与典型集
定义2.3.1（最小集）： 对每个n=1，2，…n=1，2，…n=1，2，…，设Bδ(n)⊂XnB_\delta^{(n)}\sub X^nBδ(n)⊂Xn 为满足Pr(Bδ(n))>1−δPr(B_\delta^{(n)})>1-\deltaPr(Bδ(n))>1−δ的最小集。
定理2.3.1： 设X1,X2,…,XnX_1,X_2,…,X_nX1,X2,…,Xn为服从概率密度函数p(x)p(x)p(x)的i.i.d.随机变量序列。对δ<1/2δ<1/2δ<1/2及任意δ>0δ>0δ>0，如果Pr(Bδ(n))>1−δPr(B_\delta^{(n)})>1-\deltaPr(Bδ(n))>1−δ，则当nnn充分大时，
1nlog∣Bδ(n)∣>H−δ′\frac{1}{n} \log \left|\boldsymbol{B}_{\delta}^{(n)}\right|>H-\delta^{\prime} n1log∣∣∣Bδ(n)∣∣∣>H−δ′
意义：即在一阶指数意义下， Bδn(n)\boldsymbol{B}_{\delta_{n}}^{(n)}Bδn(n)至少含有2nH2^{nH}2nH个元素。
定义2.3.2：记号an≐bna_{n} \doteq b_{n}an≐bn表示limn→∞1nlog∣bnan∣=0\lim_{n\to \infty}\frac{1}{n}\log |\frac{b_n}{a_n}|=0limn→∞n1log∣anbn∣=0也就是在一阶指数意义下相等。
最小集性质：如果δn→0\delta_n \to 0δn→0且εn→0\varepsilon_n \to 0εn→0则∣Bδn(n)∣≐∣Aεn(n)∣≐2nH\left|\boldsymbol{B}_{\delta_{n}}^{(n)}\right| \doteq\left|\boldsymbol{A}_{\varepsilon_{n}}^{(n)}\right| \doteq 2^{n H}∣∣∣Bδn(n)∣∣∣≐∣∣∣Aεn(n)∣∣∣≐2nH
3. 随机过程的熵率
3.1 马尔科夫链
本章马尔可夫链基础知识略过。
本章内容表明：熵H(X1,X2,…Xn)H(X_1, X_2, …X_n)H(X1,X2,…Xn)随nnn以速率H(X)H(\mathcal{X})H(X)（渐近地）线性增加，这个速率称为熵率。
信源：
离散无记忆信源（简单）：各符号之间相互独立，各个符号的出现概率是它自身的先验概率 。
一般平稳信源（复杂）：联合密度函数与时间起点无关。
马尔科夫信源：信源发出源字的概率，仅与当前源字及前有限个源字有关。
定义3.1.1信源联合概率分布与时间起点无关：
p(x1,x2,⋯,xn)=p(x1+1,x2+1,⋯,xn+1)p\left(x_{1}, x_{2}, \cdots, x_{n}\right)=p\left(x_{1+1}, x_{2+1}, \cdots, x_{n+1}\right) p(x1,x2,⋯,xn)=p(x1+1,x2+1,⋯,xn+1)
则称该随机过程是平稳的。实际的信源短时间内是平稳的。本章主要研究时不变马尔科夫链。称{a1,a2,...,aK}\{a_1,a_2,...,a_K\}{a1,a2,...,aK}为源字X。x1x2...xnx_1x_2...x_nx1x2...xn为输出序列。输出概率由自身和前lll个源码有关，lll个源字组成的状态组成信源状态序列s1,s2,...,sms_1,s_2,...,s_ms1,s2,...,sm。
相关概念：
过渡态：能到达其它某一状态，但不能返回；
吸收态：不能到达其它任何状态；
常返：经有限步迟早要返回该状态；
周期性：常返态中，qii(n)q_{ii}(n)qii(n)，仅当nnn能被某整数ddd整除时返回，周期性返回；
非周期：所有nnn的最大公约数为1；
遍历：非周期常返；
闭集：子集内状态不能达到子集外；
不可约：最小闭集。
定义3.1.2（各态历经信源）：各个状态都是遍历态（非周期常返）。
各态历经判定：对任意两个状态iii和jjj，如果存在正整数n0n_0n0，使所有n0n_0n0步转移概率Pij(n0)>0P_{ij}^{(n_0)}>0Pij(n0)>0则可知信源是各态历经的。
若概率矩阵PPP的mmm次幂PmP^mPm的所有元素皆为正，则该概率矩阵PPP称为正规概率矩阵。
3.2 熵率
定义3.2.1（熵率）：假设信源字母序列长度为nnn，并用(X1,X2,…,Xn)(X_1, X_2,…, X_n)(X1,X2,…,Xn)表示，这是一个随机向量，该随机矢量的联合熵为：H(X1,X2,...,Xn)H ( X_1, X_2 ,..., X_n)H(X1,X2,...,Xn) 则每个源字母的平均熵为：Hn(x)(X1,X2,...,Xn)/nH_n(x) ( X_1, X_2 ,..., X_n)/nHn(x)(X1,X2,...,Xn)/n。其极限（若存在）称为该信源的熵率：
H((X))=limn→∞1nHn(x)(X1,X2,...,Xn)H(\mathcal(X))=\lim_{n\to \infty}\frac{1}{n}H_n(x) ( X_1, X_2 ,..., X_n) H((X))=n→∞limn1Hn(x)(X1,X2,...,Xn)
定理3.2.1： 设{Xi}\{X_i\}{Xi}为平稳马式链，其平稳分布为μ\muμ，转移概率矩阵为PPP，则其熵率为
H(X)=−∑ijμiPijlogPij=−∑i=1N∑j=1NμiPijlogPijH(\mathcal{X})=-\sum_{i j} \mu_{i} P_{i j} \log P_{i j}=-\sum_{i=1}^{N} \sum_{j=1}^{N} \mu_{i} P_{i j} \log P_{i j} H(X)=−ij∑μiPijlogPij=−i=1∑Nj=1∑NμiPijlogPij
引入变量H′(X)=limn→∞H(Xn∣X1,...,Xn−1)H^\prime(\mathcal{X}) = \lim_{n \to \infty} H(X_n|X_1,...,X_{n-1})H′(X)=limn→∞H(Xn∣X1,...,Xn−1)
定理3.2.2：平稳随机过程的熵率存在，且H(X)=H′(X)H(\mathcal{X}) = H^\prime(\mathcal{X})H(X)=H′(X)
定理3.2.3： 平稳随机过程的H(Xn∣X1,...,Xn−1)H(X_n|X_1,...,X_{n-1})H(Xn∣X1,...,Xn−1)为单调递减序列。
定理3.2.4（Cesaro值）：若an→aa_n\to aan→a且bn=1n∑i=1naib_n =\frac{1}{n}\sum_{i=1}^na_ibn=n1∑i=1nai则bn→ab_n \to abn→a。
3.3 马尔科夫链的函数
定理3.3.1若X1,X2,…,XnX_1,X_2,…,X_nX1,X2,…,Xn构成平稳马尔可夫链，且Yi=Φ(Xi)Y_i=Φ(X_i)Yi=Φ(Xi)，那么
H(Yn∣Yn−1,…,Y1,X1)≤H(Y)≤H(Yn∣Yn−1,…,Y1)H\left(Y_{\mathrm{n}} \mid Y_{\mathrm{n}-1}, \ldots, Y_{1}, X_{1}\right) \leq H(\mathcal{Y}) \leq H\left(Y_{\mathrm{n}} \mid Y_{\mathrm{n}-1}, \ldots, Y_{1}\right) H(Yn∣Yn−1,…,Y1,X1)≤H(Y)≤H(Yn∣Yn−1,…,Y1)
且limH(Yn∣Yn−1,…,Y1,X1)=H(D)=limH(Yn∣Yn−1,…,Y1)\lim H\left(Y_{\mathrm{n}} \mid Y_{\mathrm{n}-1}, \ldots, Y_{1}, X_{1}\right)=H(\mathcal{D})=\lim H\left(Y_{\mathrm{n}} \mid Y_{\mathrm{n}-1}, \ldots, Y_{1}\right)limH(Yn∣Yn−1,…,Y1,X1)=H(D)=limH(Yn∣Yn−1,…,Y1)
定义3.3.1（隐马尔可夫模型）考虑XiX_iXi的随机函数YiY_iYi。由X1,X2,…,XnX_1,X_2,…,X_nX1,X2,…,Xn定义新过程Y1,Y2,…,YnY_1,Y_2,…,Y_nY1,Y2,…,Yn，其中每个YiY_iYi服从p(yi∣xi)p(y_i|x_i)p(yi∣xi)，且条件独立于其他所有的XjX_jXj，j≠ij≠ij=i，即
p(xn,yn)=p(x1)∏i=1n−1p(xi+1∣xi)∏i=1np(yi∣xi)p\left(x^{n}, y^{n}\right)=p\left(x_{1}\right) \prod_{i=1}^{n-1} p\left(x_{i+1} \mid x_{i}\right) \prod_{i=1}^{n} p\left(y_{i} \mid x_{i}\right) p(xn,yn)=p(x1)i=1∏n−1p(xi+1∣xi)i=1∏np(yi∣xi)
这样的过程称为隐马尔可夫模型(HMM)。
4. 数据压缩
4.1 编码的基本概念
贝尔实验室的Shannon 和 MIT 的 Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。算术编码是部分匹配预测（PPM）技术的变体
定义4.1.1关于随机变量XXX的信源编码CCC是从XXX的取值空间到D∗D^\astD∗的一个映射，其中D∗D^\astD∗表示字母表DDD上有限长度的字符串所构成的集合。用C(x)C(x)C(x)表示xxx的码字，并用l(x)l(x)l(x)表示C(x)C(x)C(x)的长度。
定义4.1.2设随机变量X∼p(x)X\sim p(x)X∼p(x)，信源编码C(x)C(x)C(x)的期望长度为
L(c)=∑x∈Xp(x)l(x)L(c) = \sum_{x\in \mathcal{X}}p(x)l(x) L(c)=x∈X∑p(x)l(x)
其中l(x)l(x)l(x)表示对应于xxx的码字长度。
定义4.1.3如果编码将XXX的取值空间中的每个元素映射成D∗D^\astD∗中不同的字符串，即x≠x′⇒C(x)≠C′(x)x \neq x^\prime \Rightarrow C(x) \neq C^\prime(x)x=x′⇒C(x)=C′(x)则称这个编码是非奇异的。
定义4.1.4编码CCC的扩展C∗C^\astC∗是从XXX上的有限长字符串到DDD上的有限长字符串的映射，定义为
C(x1,x2,...,xn)=C(x1)C(x2)...C(xn)C(x_1,x_2,...,x_n)=C(x_1)C(x_2)...C(x_n) C(x1,x2,...,xn)=C(x1)C(x2)...C(xn)
C(xi)C(x_i)C(xi))表示相应码字的串联。
定义4.1.5如果一个编码的扩展码是非奇异码，则称该编码是唯一可译的。信息序列与码字序列一一对应。
定义4.1.6若码中无任何码字是其它码字的前缀，则称该码为前缀码。
每一码字传输完毕，即可译码，称为即时码。
4.2 Kraft不等式
定理4.2.1（Kraft不等式，前缀码存在定理）含有DDD个码字的编码系统，当且仅当各个码字长度l1,l2,...,lml_1,l_2,...,l_ml1,l2,...,lm满足Kraft不等式
∑k=1mD−lk⩽1\sum_{k=1}^m D^{-l_k} \leqslant 1 k=1∑mD−lk⩽1
时，存在前缀码。
定理4.2.2（推广Kraft不等式）含有DDD个码字的编码系统，对任意构成前缀码的可数无限码字集，当且仅当个码字长度l1,l2,...,l∞l_1,l_2,...,l_\inftyl1,l2,...,l∞满足Kraft不等式
∑k=1mD−lk⩽1\sum_{k=1}^m D^{-l_k} \leqslant 1 k=1∑mD−lk⩽1
时，存在前缀码。
4.3 最优码
定理4.3.1随机变量XXX的任一DDD元即时码的期望长度必定大于或等于熵HD(X)H_D(X)HD(X)，即L⩾HD(X)L\geqslant H_D(X)L⩾HD(X)，当且仅当pi=D−lip_i = D^{-l_i}pi=D−li时等号成立。
定义4.3.1对于某个nnn，如果概率分布的每一个概率值均等于D−nD^{-n}D−n，则称这个概率分布是DDD进制的。当且仅当XXX的分布是DDD进制的，上述定理等号成立。
定理4.3.2（最优码长的界）设l1,l2,…,lml_1, l_2,…, l_ml1,l2,…,lm是关于信源分布ppp和一个DDD元字母表的一组最优码长，LLL为最优码的期望长度，则
HD(X)⩽L⩽HD(X)+1H_D(X) \leqslant L \leqslant H_D(X)+1 HD(X)⩽L⩽HD(X)+1
设 LnL_nLn为每个输入字符的平均码长，即
Ln=12El(x1,x2,...,xn)L_n = \frac{1}{2}El(x_1,x_2,...,x_n) Ln=21El(x1,x2,...,xn)
有增加分组长度，可逼近最优编码。
定理4.3.3（平稳随机过程的编码界）每字符最小期望码字长满足
H(X1,X2,⋯,Xn)n≤Ln∗≤H(X1,X2,⋯,Xn)n+1n\frac{H\left(X_{1}, X_{2}, \cdots, X_{n}\right)}{n} \leq L_{n}^{*} \leq \frac{H\left(X_{1}, X_{2}, \cdots, X_{n}\right)}{n}+\frac{1}{n} nH(X1,X2,⋯,Xn)≤Ln∗≤nH(X1,X2,⋯,Xn)+n1
进一步，若X1,X2,…,XnX_1,X_2,…,X_nX1,X2,…,Xn是平稳随机过程，有Ln∗→H(X)L_n^\ast \to H(\mathcal{X})Ln∗→H(X)。其中$ H(\mathcal{X})$为随机过程的熵率。
编码偏差：编码的分布与信源的真实分布存在偏差时，可用D(p∣∣q)D(p||q)D(p∣∣q)描述编码增加的复杂度。
定理4.3.4（偏码）码字长度分配关于p(x)的期望满足l(x)=−⌈logq(x)⌉l(x)=-\lceil\log q(x)\rceill(x)=−⌈logq(x)⌉关于p(x)的期望满足
H(p)+D(p∣∣q)⩽Epl(x)<H(p)+D(p∣∣q)+1H(p) + D(p || q) \leqslant E_pl(x)< H(p)+D(p || q)+1 H(p)+D(p∣∣q)⩽Epl(x)<H(p)+D(p∣∣q)+1
结论：若真实分布为p(x)p(x)p(x)，而编码使用的分布为q(x)q(x)q(x)，则平均码长增加D(p∣∣q)D(p||q)D(p∣∣q)。
定理4.3.5 （唯一可译码的Kraft不等式）含有DDD个码字的编码系统，其任意唯一可译码的平均码长满足Kraft不等式
∑k=1mD−lk⩽1\sum_{k=1}^m D^{-l_k} \leqslant 1 k=1∑mD−lk⩽1
反之，若给定满足上述不等式的一组码字长度，则可以构造出具有同样码字长度的唯一可译码。
4.4 Haffman编码
缩减信源：指由原信源缩减得到的信源：K→K−1K\to K-1K→K−1。其概率变化如下：[X′P′(x)]=[a1a2⋯aK−2aK−1′p(a1)p(a2)⋯p(aK−2)p′(aK−1)]\left[\begin{array}{c} X^{\prime} \\ P^{\prime}(x) \end{array}\right]=\left[\begin{array}{ccccc} a_{1} & a_{2} & \cdots & a_{K-2} & a_{K-1}^{\prime} \\ p\left(a_{1}\right) & p\left(a_{2}\right) & \cdots & p\left(a_{K-2}\right) & p^{\prime}\left(a_{K-1}\right) \end{array}\right] [X′P′(x)]=[a1p(a1)a2p(a2)⋯⋯aK−2p(aK−2)aK−1′p′(aK−1)]
也就是有p′(aK−1)=p(aK−1)+p(aK)p^\prime(a_{K-1}) = p(a_{K-1})+p(a_K)p′(aK−1)=p(aK−1)+p(aK)。
编码方法：设C′C^\primeC′为某信源经缩减后所得的最优前缀码，将C′C^\primeC′中由原信源中的两个最小概率的两个字母缩减得到的字母所对应的码字各加0和1，作为原信源的两个最小概率的源码的码字，而其余码字不变，则这样得到的码CCC为原信源的最优前缀码。
最小化∑pili\sum p_il_i∑pili的哈夫曼算法对任意一组pi⩾0p_i\geqslant 0pi⩾0都是成立的，而无需考虑∑pi\sum p_i∑pi的大小。此时，赫夫曼编码算法最小化的是码长加权和∑ωili\sum \omega_il_i∑ωili ，而非平均码长。
对于某个特定的字符，使用码长为−⌈logq(x)⌉-\lceil\log q(x)\rceil−⌈logq(x)⌉的编码（称为香农码）可能比最优码更差。
费诺编码：是次优编码，类似于切片码。先将概率值以递减次序排列，然后选取k使
∣∑i=1klogpi−∑i=k+1mlogpi∣\left|\sum_{i=1}^{k} \log p_{i}-\sum_{i=k+1}^{m} \log p_{i}\right| ∣∣∣∣∣i=1∑klogpi−i=k+1∑mlogpi∣∣∣∣∣
达到最小值。
定理4.4.1Huffman码是最优的，即如果CCC是Huffman码而C′C^\primeC′是其它码，则L(C∗)⩽L(C’)L(C^*)\leqslant L(C’)L(C∗)⩽L(C’)。利用归纳法可以证明二元赫夫曼码是最优的。
4.5 算术编码
适合的场合： 小字母表、概率分布不均衡、建模与编码分开。
将源码序列的概率与[0,1)[0,1)[0,1)中的一个实数相对应，实数的二进制表示即为源码序列的算术码。
定理4.5.1（算术码的存在性）定义aka_kak的修正累积概率Fˉ(ak)=∑ai>akp(ai)+p(ak)/2\bar{F}\left(a_{k}\right)=\sum_{a_{i}>a_{k}} p\left(a_{i}\right)+p\left(a_{k}\right) / 2Fˉ(ak)=∑ai>akp(ai)+p(ak)/2由修正概率可以推出源字母，而后将修正概率用二进制表示，取二进制小数后lKl_KlK位，使其能与aKa_KaK一一对应。可以证明，取lk=⌈logp(ak)−1⌉+1l_{k}=\left\lceil\log p\left(a_{k}\right)^{-1}\right\rceil+1lk=⌈logp(ak)−1⌉+1位即可唯一确定aka_kak；此时平均码长lˉ<H(X)+2\bar{l}<H(X)+2lˉ<H(X)+2。
性质：与Huffman相比二者的渐近性质相同。扩展的Huffman要求巨大数量的存储和编码mnm^nmn。增益为字母表大小和分布的函数。不均衡的分布更适合算术编码，很容易将算术编码扩展到多个编码器，很容易将算术编码适应到统计变化模型（自适应模型、上下文模型）
自适应算术编码：统计编码技术需要利用信源符号的概率，获得这个概率的过程称为建模。建模的方式包括静态建模和自适应动态建模。
QM编码器：将输入符号(一个bit)分为大概率符号（More Probable Symbol，MPS）或小概率符号（Less Probable Symbol，LPS）在输入下一位之前，编码器先利用一个统计模型预测MPS是0还是1，然后再输入该位并按其实际值分类输出流为MPS或LPS的流，MPS和LPS的概率动态更新，为算术编码器所用。
5. 信道容量
信道描述：（1 ）输入容许字母集合及统计特征；（2）输出容许字母集合；（3）输入输出的转移概率分布 离散信道：{X,p(y∣x),Y}\{X,p(y|x),Y\}{X,p(y∣x),Y}。如果输出概率仅依赖于输入符号，与以前的输入、输出均无关，这种信道称为无记忆信道。5.1 基本概念
定义5.1.1：离散无记忆信道信道容量定义为C=maxp(x)I(X;Y)C = \max_{p(x)}I(X;Y)C=maxp(x)I(X;Y)。将信道容量定义为信道的最高码率。在此码率下，信息能够以任意小的差错概率传输。（香农第二定理）
信道例子：无噪声二元信道、无重叠输出的有噪声信道、有噪声的打字机信道；
二元对称信道（BSC）。该二元信道的输入字符以概率ppp互补。其信道容量为C=1−H(p)C = 1-H(p)C=1−H(p)。二元删除信道（BEC）。该二元信道的输入字符以概率ααα被删除。在接收端收到e，不能确定发送端比特。其信道容量为C=1−αC = 1-\alphaC=1−α。
译码：W^=g(Yn)\hat{W}=g(Y^n)W^=g(Yn)猜测消息WWW。
定义5.1.2（离散信道）：用(X,p(y∣x),Y)(X,p(y|x),Y)(X,p(y∣x),Y)表示的离散信道由两个有限集XXX和YYY以及一簇概率密度函数p(y∣x)p(y|x)p(y∣x)构成，其中对任意x,yx,yx,y有p(y∣x)⩾0p(y|x)\geqslant 0p(y∣x)⩾0，以及对任意的xxx，有∑p(y∣x)=1\sum p(y|x) = 1∑p(y∣x)=1而xxx和yyy分别看作信道的输入与输出。
定义5.1.3（扩展信道）： 离散无记忆信道（DMC）的nnn次扩展是指信道(Xn,p(yn∣xn),Yn)(X^n,p(y^n|x^n),Y^n)(Xn,p(yn∣xn),Yn)，其中p(yk∣xk,yk−1)=p(yk∣xk)p(y_k|x^k,y^{k-1}) = p(y_k | x_k)p(yk∣xk,yk−1)=p(yk∣xk)。
定义5.1.4（编码）：信道(X,p(y∣x),Y)(X,p(y|x),Y)(X,p(y∣x),Y)的(M,n)(M,n)(M,n)码由以下部分构成：（1）下标集{1,2,…,M}\{1,2,…,M\}{1,2,…,M} ；（2）编码函数为Xn:{1,2,…,M}→XnX^n: \{1,2,…,M\}\to X^nXn:{1,2,…,M}→Xn上的映射，生成码字xn(1),xn(2),…,xn(M)x_n(1), x_n(2),…, x_n(M)xn(1),xn(2),…,xn(M)。码字集合称为码书；（3）译码函数g:Yn→{1,2,…,M}g: Y_n\to \{1,2,…,M\}g:Yn→{1,2,…,M}。为一确定规则，对接收码字进行译码。
定义5.1.5（条件误差概率）： 设λi=Pr(g(Yn)≠i∣Xn=xn(i))\lambda_i = Pr(g(Y^n)\neq i | X^n = x^n(i))λi=Pr(g(Yn)=i∣Xn=xn(i))为已知下标iii被发送的条件下的条件误差概率，其中I(⋅)I(·)I(⋅)为示性函数。
最大误差概率定义为λ(n)=maxi∈{1,2,...,M}λi\lambda^{(n)} = \max_{i\in \{1,2,...,M\}}\lambda_iλ(n)=maxi∈{1,2,...,M}λi。
定义5.1.6（平均误差概率）：Pe(n)=1M∑i=1MλiP_e^{(n)} = \frac{1}{M} \sum_{i=1}^M \lambda_iPe(n)=M1∑i=1Mλi。
定义5.1.7(M,n)(M,n)(M,n)的码率定义为R=(logM)/nR=(\log M)/nR=(logM)/n 比特
定义5.1.8（可达）：如果存在一个(⌈2nR⌉,n)\left(\lceil2^{nR}\rceil,n\right)(⌈2nR⌉,n)码序列，满足n→∞n\to \inftyn→∞时，最大误差概率λ(n)→0\lambda (n)\to 0λ(n)→0，则称码率RRR是可达的。
定义5.1.9（信道容量）：所有可达码率的上确界。
简单推论：对于充分大的分组长度，小于信道容量的码率对应的误差概率可以任意小。
5.2 对称信道
对称信道的信道容量：设rrr表示转移矩阵的一行：I(X;Y)=H(Y)−H(r)⩽log∣Y∣−H(r)I(X;Y)=H(Y)-H(r)\leqslant \log|Y| -H(r)I(X;Y)=H(Y)−H(r)⩽log∣Y∣−H(r).当YYY等概分布时，等号成立。
定义5.2.1（对称信道）：如果信道转移矩阵p(y∣x)p(y|x)p(y∣x)的任何两行互相置换；任何两列也互相置换，那么称该信道是对称的。如果转移矩阵的每一行p(⋅∣x)p(·|x)p(⋅∣x)都是其他每行的置换，而所有列的元素和∑p(y∣x)\sum p(y|x)∑p(y∣x)相等，则称这个信道是弱对称的。
定理7.2.1对于弱对称信道，C=log∣Y∣−H(r)C = \log|Y| - H(r)C=log∣Y∣−H(r)。
信道容量的性质：
a. C⩾0C\geqslant 0C⩾0
b. C⩽log∣X∣C \leqslant \log|X|C⩽log∣X∣
c. C⩽log∣Y∣C \leqslant \log | Y|C⩽log∣Y∣
d. I(X;Y)I(X;Y)I(X;Y)是p(x)p(x)p(x)的上凸函数，其最大值即为信道容量。
5.3 信道编码定理
联合典型：输入典型n长序列，有约2nH(Y∣X)2^{nH(Y|X)}2nH(Y∣X) 个可能的Y序列与之对应，且所有序列等概。
定理5.3.1（信道编码定理，香农第二定理）：对于离散无记忆信道，小于信道容量CCC的所有码率都是可达的。具体来说，对任意码率R<CR<CR<C，存在一个(2nR,n)(2^{nR},n)(2nR,n)码序列，它的最大误差概率为λ(n)→0\lambda^{(n)}\to 0λ(n)→0。反之，任何满足的λ(n)→0\lambda^{(n)}\to 0λ(n)→0的码(2nR,n)(2^{nR},n)(2nR,n)序列必定有R⩽CR\leqslant CR⩽C。
5.4 联合典型序列
定义5.4.1： 服从分布p(x,y)p(x,y)p(x,y)的联合典型序列{(xn,yn)}\{(x^n,y^n)\}{(xn,yn)}所构成的集合Aε(n)A_ε ^{(n)}Aε(n)是指其经验熵与真实熵“ε\varepsilonε-*接近”的nnn长序列构成的集合，即A(n)={(xn,yn)∈Xn×Yn:∣−(logp(xa))/n−H(X)∣<ε∣−(logp(yn))/n−H(Y)∣<ε∣−(logp(xn,yn))/n=H(X,Y)∣<ε}\begin{array}{l} A^{(n)}=\left\{\left(x^{n}, y^{n}\right) \in X^{n} \times Y^{n}:\right. \\ \left|-\left(\log p\left(x^{a}\right)\right) / n-H(X)\right|<\varepsilon \\ \left|-\left(\log p\left(y^{n}\right)\right) / n-H(Y)\right|<\varepsilon \\ \left.\left|-\left(\log p\left(x^{n}, y^{n}\right)\right) / n=H(X, Y)\right|<\varepsilon\right\} \end{array} A(n)={(xn,yn)∈Xn×Yn:∣−(logp(xa))/n−H(X)∣<ε∣−(logp(yn))/n−H(Y)∣<ε∣−(logp(xn,yn))/n=H(X,Y)∣<ε}
定理5.4.1（联合AEP）： 设(Xn,Yn)(X^n,Y^n)(Xn,Yn)为服从p(xn,yn)=∏i=1np(xi,yi)p(x^n,y^n) = \prod_{i=1}^n p (x_i,y_i)p(xn,yn)=∏i=1np(xi,yi)的i.i.d.的nnn长序列则
1、当n→∞n\to \inftyn→∞时，Pr((Xn,Yn)∈Aε(n))→1Pr((X^n,Y^n)\in A_\varepsilon^{(n)})\to 1Pr((Xn,Yn)∈Aε(n))→1 。
2、 ∣Aε(n)∣⩽2nH(X,Y)+ε|A_\varepsilon^{(n)}|\leqslant 2^{nH(X,Y)+\varepsilon}∣Aε(n)∣⩽2nH(X,Y)+ε。
3、如果 X~n\tilde{X}^nX~n与Y~n\tilde{Y}^nY~n 是独立的，且与p(xn,yn)p(x^n,y^n)p(xn,yn)有相同的边缘分布，那么
Pr((X~n,Y~∗n)∈Ac(n))≤2−n(I(X;Y)−3ε)\operatorname{Pr}\left(\left(\tilde{X}^{n}, \tilde{Y}^{*n}\right) \in A_{c}^{(n)}\right) \leq 2^{-n(I(X ; Y)-3 \varepsilon)} Pr((X~n,Y~∗n)∈Ac(n))≤2−n(I(X;Y)−3ε)
而且，对于充分大的nnn
Pr((X~n,Y~n)∈Ae(n))≥(1−ε)2−n(I(X;Y)+3ε)\operatorname{Pr}\left(\left(\tilde{X}^{n}, \tilde{Y}^{n}\right) \in A_{e}^{(n)}\right) \geq(1-\varepsilon) 2^{-n\left(I(X;Y)+3\varepsilon\right)} Pr((X~n,Y~n)∈Ae(n))≥(1−ε)2−n(I(X;Y)+3ε)
5.5 汉明码
汉明码是1950年由汉明首先构造， 用以纠正单个错误的线性分组码。
奇偶校验矩阵性质：矩阵HHH对任意码字ccc均有HcT=0Hc^T=0HcT=0。
差错向量：设eie_iei是第iii个位置为1其余位置为0的向量。
接收向量：若码字第iii个位置出错，则接收到的向量为r=c+eir=c+e_ir=c+ei。
校验： HrT=H(c+ei)T=HcT+HeiT=HeiTHr^T=H(c+e_i)T=Hc^T+He_i^T=He_i^THrT=H(c+ei)T=HcT+HeiT=HeiT可指示错误位置。
系统码：对于一般情形，将线性码进行修改，可以使得映射更加明显：让码字中的前kkk个比特代表消息，而后面n−kn-kn−k个比特留作奇偶校验位。这样得到的编码称作系统码。
卷积码：每个输出组不仅依赖于当前的输入组，而且依赖于过去的一些输入组。这种码的一个高级结构化的形式称作卷积码。
5.6 反馈容量
定义5.6.1 （反馈码）：(2nR,n)(2^{nR},n)(2nR,n) 的一个映射序列xi(W,Yi−1)x_i(W,Y^{i-1})xi(W,Yi−1)和一个译码函数序列g:Yn→{1,2,…,2nR}g:Y^n\to \{1,2,…,2^{nR}\}g:Yn→{1,2,…,2nR}，其中xix_ixi 是消息W∈{1,2,…,2nR}W\in \{1,2,…,2^{nR}\}W∈{1,2,…,2nR}和先前接收到的值Y1,Y2,…,Yi−1Y_1,Y_2,…,Y_{i-1}Y1,Y2,…,Yi−1的函数。
差错概率：WWW服从{1,2,…,2nR}\{1,2,…,2^{nR}\}{1,2,…,2nR}均匀分布时，有
Pe(n)=Pr{g(Yn)≠W}P_e^{(n)} = Pr\{g(Y^n) \neq W\}Pe(n)=Pr{g(Yn)=W}
定义5.6.2 （反馈容量）：离散无记忆信道的反馈容量定义为反馈码可以达到的所有码率的上确界。
定理5.6.1（反馈容量）：信道反馈容量等于信道容量。
CFB=C=maxp(x)I(X;Y)C_{FB} = C = \max_{p(x)}I(X;Y)CFB=C=p(x)maxI(X;Y)
定理5.6.2：采用联合信源信道编码与分离编码一样有效。
定理5.6.3（信源信道编码定理）：如果V1,V2,…,VnV_1,V_2,…,V_nV1,V2,…,Vn为有限字母表上满足AEP和H(V)<CH(V)<CH(V)<C的随机过程，则存在一个信源信道编码使得误差概率Pr(Vˉn≠Vn)→0Pr(\bar{V}^n \neq V^n)\to 0Pr(Vˉn=Vn)→0 。反之，对任意平稳随机过程，如果H(V)>CH(V)>CH(V)>C，那么误差概率远离0，从而不可能以任意低的误差概率通过信道发送这个过程。能够通过信道传输平稳遍历信源当且仅当它的熵率小于信道容量。
6. 微分熵
6.1 定义
定义6.1.1设XXX是一个随机变量，其累计分布函数为F(x)=Pr(X⩽x)F(x)=Pr(X\leqslant x)F(x)=Pr(X⩽x) 。如果F(x)F(x)F(x)连续，则称该随机变量连续。另外，使f(x)>0f(x)>0f(x)>0 的所有xxx构成的集合称为XXX的支撑集。
定义6.1.2(微分熵)一个以f(x)f(x)f(x)为密度函数的连续型随机变量XXX的微分熵h(X)h(X)h(X)定义为
h(X)=−∫Sf(x)logf(x)dxh(X) = - \int_S f(x)\log f(x)dx h(X)=−∫Sf(x)logf(x)dx
其中SSS是这个随机变量的支撑集。离散的熵
HΔx(X)=−∑i=−∞∞f(xiΔx)log(f(xi)Δx)H_{\Delta x}(X) = -\sum_{i=-\infty}^\infty f(x_i\Delta x)\log (f(x_i)\Delta x) HΔx(X)=−i=−∞∑∞f(xiΔx)log(f(xi)Δx)
定义微分熵的目的：微分熵差具有信息度量的意义、连续信源的微分熵与离散信源的熵在形式上统一。
6.2 连续随机变量的AEP
定理 6.2.1设X1,X2,...,XnX_1,X_2,...,X_nX1,X2,...,Xn是概率密度函数为p(x)p(x)p(x)的i.i.d随机序列，那么下面的极限依概率收敛−1nlogp(X1,X2,...,Xn)→h(X)-\frac{1}{n}\log p(X_1,X_2,...,X_n)\to h(X)−n1logp(X1,X2,...,Xn)→h(X)
定义6.2.1（体积）集合A⊂RnA\sub R^nA⊂Rn的体积Vol(A)Vol(A)Vol(A)定义为：Vol(A)=∫Sdx1dx2...dxnVol(A) = \int_S dx_1 dx_2 ... dx_nVol(A)=∫Sdx1dx2...dxn。
定理6.2.2典型集Aε(n)A_\varepsilon^{(n)}Aε(n)有如下性质：
a. 当nnn充分大时，Pr{Aε(n)}>1−εPr\{A_\varepsilon^{(n)}\}>1-\varepsilonPr{Aε(n)}>1−ε；
b. 对于所有nnn，Vol(Aε(n))⩽2n(h(X)+ε)Vol(A_\varepsilon^{(n)})\leqslant 2^{n(h(X)+\varepsilon)}Vol(Aε(n))⩽2n(h(X)+ε)；
c. 当nnn充分大时，Vol(Aε(n))⩾(1−ε)2n(h(X)−ε)Vol(A_\varepsilon^{(n)})\geqslant (1-\varepsilon)2^{n(h(X)-\varepsilon)}Vol(Aε(n))⩾(1−ε)2n(h(X)−ε)。
定理8.2.3在一阶指数意义下， 在所有概率P⩾1−εP\geqslant 1-εP⩾1−ε的集合中，Aε(n)A_\varepsilon^{(n)}Aε(n)是体积最小者。
微分熵解释：熵就是拥有大部分概率的最小集的边长的对数值。因此， 较低的熵意味着随机变量被限于一个狭小的有效正方体内，而较高的熵意味着该随机变量是高度分散的。
6.3 微分熵与离散的关系
定理6.3.1如果随机变量XXX的密度函数f(x)f(x)f(x)是黎曼可积的，那么
HΔx(X)+logΔx→h(f)=h(X),Δx→0H_{\Delta x}(X)+\log \Delta x \to h(f) = h (X),\Delta x\to 0 HΔx(X)+logΔx→h(f)=h(X),Δx→0
于是，连续随机变量XXX经过nnn比特量化处理(分割的小区间长度1/2n1/2^n1/2n后的熵大约为h(X)+nh(X)+nh(X)+n。
6.4 联合微分熵与条件微分熵
定义6.4.1 (联合微分熵)联合密度函数为f(x1,x2,...,xn)f(x_1, x_2, ..., x_n)f(x1,x2,...,xn)的一组随机变量X1,X2,...,XnX_1, X_2, ..., X_nX1,X2,...,Xn的联合微分熵定义为
h(X1,X2,...,Xn)=−∫f(xn)logf(xn)dxnh(X_1,X_2,...,X_n) = -\int f(x^n)\log f(x^n)dx^n h(X1,X2,...,Xn)=−∫f(xn)logf(xn)dxn
定义6.4.2 (条件微分熵)联合密度函数为f(x,y)f(x, y)f(x,y)，条件微分熵定义为
h(X∣Y)=−∫f(x,y)logf(x∣y)dxdyh(X|Y) = -\int f(x,y)\log f(x|y)dxdy h(X∣Y)=−∫f(x,y)logf(x∣y)dxdy
定理6.4.1 (多元正态分布的熵)设X1,X2,...,XnX_1, X_2, ..., X_nX1,X2,...,Xn服从均值为μμμ，协方差矩阵为KKK的多元正态分布则
h(X1,X2,...,Xn)=h(N(μ,K))=12log((2πe)n∣K∣)h(X_1,X_2,...,X_n) = h(N(\mu,K)) = \frac{1}{2}\log((2\pi e)^n|K|) h(X1,X2,...,Xn)=h(N(μ,K))=21log((2πe)n∣K∣)
6.5 相对熵与互信息
互信息的一般形式：
可从随机变量的值域的有限分割的角度来定义互信息。设χ\chiχ为随机变量XXX的值域，P\mathcal{P}P为χ\chiχ的一个分割是指存在有限个不相交的集合PiP_iPi使得⋃iPi=x\bigcup_iP_i = x⋃iPi=x。XXX关于PPP的量化记为[X]P[X]_{\mathcal{P}}[X]P是定义如下的离散随机变量：
Pr([X]P=i)=Pr(X∈Pi)=∫PidF(x)Pr([X]_P = i) = Pr(X \in P_i) = \int_{P_i}dF(x) Pr([X]P=i)=Pr(X∈Pi)=∫PidF(x)
任何随机变量XXX与YYY间的互信息如下
I(X;Y)=supP,QI([X]P;[Y]Q)I(X;Y) = \sup_{P,Q}I([X]_P;[Y]_Q) I(X;Y)=P,QsupI([X]P;[Y]Q)
6.6 微分熵、相对熵以及互信息的性质
定理6.6.1（相对熵非负）：D(f∣∣g)⩾0D(f||g)\geqslant 0D(f∣∣g)⩾0，当且仅当∗f∗=∗g∗*f*=*g*∗f∗=∗g∗，几乎处处等号成立。
定理6.6.2 （微分熵的链式规则）：h(X1,X2,...,Xn)=∑i=1nh(Xi∣X1,X2,...,Xi−1)h(X_1,X_2,...,X_n) = \sum_{i=1}^n h(X_i | X_1,X_2,...,X_{i-1})h(X1,X2,...,Xn)=∑i=1nh(Xi∣X1,X2,...,Xi−1)。
定理6.6.3 （微分熵的平移不变性）：h(X+c)=h(X)h(X+c) = h(X)h(X+c)=h(X)。
定理6.6.4 （微分熵的倍加性）： h(aX)=h(X)+log∣a∣h(aX)=h(X)+log|a|h(aX)=h(X)+log∣a∣。
定理6.6.5 （随机向量微分熵的上界）：设随机向量x∈Rnx\in R^nx∈Rn的均值为零，协方差矩阵为K=EXXTK=EXX^TK=EXXT则
h(X)⩽12log((2πe)n∣K∣)h(X)\leqslant \frac{1}{2}\log((2\pi e)^n|K|) h(X)⩽21log((2πe)n∣K∣)
当且仅当X∼N(0,K)X\sim N(0,K)X∼N(0,K)等号成立。
定理6.6.6 （估计误差与微分熵）：对任意随机变量X及其估计X^\hat{X}X^，
E(X−X^)2⩾12πee2h(X)E(X-\hat{X})^2\geqslant \frac{1}{2\pi e}e^{2h(X)} E(X−X^)2⩾2πe1e2h(X)
，其中等号成立的充分必要条件是X为高斯分布而X^\hat{X}X^为其均值。
7. 高斯信道
高斯信道：噪声是独立同分布的高斯分布。
接收信号：噪声与发送信号之和。数学表示：Yi=Xi+ZiZi∼N(0,N)Y_i = X_i + Z_i\quad Z_i \sim N(0,N)Yi=Xi+ZiZi∼N(0,N)
高斯噪声假设：大量的小随机事件的累积效果渐近于正态分布。
平均误码概率Pe=1−Φ((P/N))P_e = 1-\Phi(\sqrt{(P/N)})Pe=1−Φ((P/N))
7.1 定义
功率限制为P的高斯信道的信息容量为C=maxp(x):EX2⩽PI(X;Y)C = \max_{p(x):EX^2\leqslant P }I(X;Y)C=maxp(x):EX2⩽PI(X;Y)
参数1噪声熵Z(0,N)Z~(0,N)Z(0,N)则h(Z)=(log2πeN)/2h(Z) = (\log 2\pi eN)/2h(Z)=(log2πeN)/2
参数2接收信号功率界：XXX与ZZZ独立且E[Z]=0E[Z]=0E[Z]=0，有E[Y2]=P+NE[Y^2] = P+NE[Y2]=P+N。接收信号熵上界：(log2πe(P+N))/2(\log 2\pi e(P+N))/2(log2πe(P+N))/2。互信息上界：I(X;Y)=(log(1+P/N))/2I(X;Y) = (\log (1+P/N))/2I(X;Y)=(log(1+P/N))/2。
可以证明：高斯信道的容量即是所有可达码率的上确界。
定理7.1.1一个 功率限制为∗P∗*P*∗P∗且噪声方差为∗N∗*N*∗N∗的高斯信道的容量为
C=12log(1+PN)C = \frac{1}{2}\log \left(1 + \frac{P}{N}\right) C=21log(1+NP)
定理7.1.2（逆定理）: 对于功率限制为PPP的高斯信道中的任一个(2nR,n)(2^{nR},n)(2nR,n)序列（编码），当Pε(n)→0P_{\varepsilon}^{(n)} \to 0Pε(n)→0时，则R⩽C=12log(1+PN)R\leqslant C = \frac{1}{2}\log \left(1 + \frac{P}{N}\right)R⩽C=21log(1+NP)。
7.2 带宽有限信道
输出为Y(t)=(X(t)+Z(t))∗h(t)Y(t) = (X(t)+Z(t))*h(t)Y(t)=(X(t)+Z(t))∗h(t)。h(t)h(t)h(t)是一个理想低通滤波器的冲击响应，它的作用是将大于WWW的所有频率过滤掉
定理7.2.1假定信号f(t)f(t)f(t)的最大截频为WWW，那么该信号可由间隔为1/2W1/2W1/2W秒的采样序列完全决定。
每个样本信息量为C=12log(1+PN0W)C = \frac{1}{2}\log \left(1 + \frac{P}{N_0W}\right)C=21log(1+N0WP)
信道容量：W→∞W \to \inftyW→∞时有C=PN0log2eC = \frac{P}{N_0}\log_2 eC=N0Plog2e。
7.3 并联高斯信道容量
模型：Yj=Xj+ZjY_j = X_j + Z_jYj=Xj+Zj，噪声在信道与信道之间相互独立。使用的总功率方面存在一个公共的功率限制，即E∑j=1kXj2⩽PE\sum_{j=1}^k X_j^2 \leqslant PE∑j=1kXj2⩽P。
信道容量为
C=maxf(x1,x2,...,xk):∑EXI2⩽PI(X1,X2,...,Xk;Y1,Y2,...,Yk)=∑i12log(1+PiNi)C = \max_{f(x_1,x_2,...,x_k):\sum EX_I^2 \leqslant P} I(X_1,X_2,...,X_k;Y_1,Y_2,...,Y_k)=\sum_i\frac{1}{2}\log \left(1+\frac{P_i}{N_i}\right) C=f(x1,x2,...,xk):∑EXI2⩽PmaxI(X1,X2,...,Xk;Y1,Y2,...,Yk)=i∑21log(1+NiPi)
8. 率失真理论
离散信源的有损压缩：信道描述Q=(q(bj∣aK))K×JQ=(q(b_j | a_K))_{K\times J}Q=(q(bj∣aK))K×J。连续信源：输出消息在时间和取值上都连续的信源。8.1 量化
量化分类：标量量化和矢量量化。
标量量化：每个信源输出分别量化。标量量化划分：均匀量化（量化区域等长）和非均匀量化（量化区域可以不等长）。矢量量化：对信源输出组合进行整体量化。
定义8.1.1（标量量化）：仅考虑一个采样点的量化问题。将一个连续幅度值转变成离散幅度值（有限个值）x^=Q(x)\hat{x}=Q(x)x^=Q(x)。Δi=di−di−1\Delta i = d_i - d_{i-1}Δi=di−di−1△i=di-di-1称为量化步长。
最优（Max-Lloyd）量化器：信源XXX的概率密度为p(x)p(x)p(x)，x→x^x\to \hat{x}x→x^，量化均方误差为
D=E[(x−x^)2]=∫(x−x^)2p(x)dx=∑k=1K∫dk−1dkp(x)dxD = E[(x-\hat{x})^2] = \int (x-\hat{x})^2p(x)dx = \sum_{k=1}^K\int_{d_{k-1}}^{d_k}p(x)dx D=E[(x−x^)2]=∫(x−x^)2p(x)dx=k=1∑K∫dk−1dkp(x)dx
为使DDD最小，可得
dk=12(rk+rk+1),rk=(∫dk−1dkxp(x)dx)/(∫dk−1dkp(x)dx)d_k = \frac{1}{2}(r_k+r_{k+1}),r_k = (\int_{d_{k-1}}^{d_k}xp(x)dx)/(\int_{d_{k-1}}^{d_k}p(x)dx) dk=21(rk+rk+1),rk=(∫dk−1dkxp(x)dx)/(∫dk−1dkp(x)dx)
代表值rkr_krk实际上是输入的概率密度函数在区间[dk−1,dk][d_{k-1}, d_k][dk−1,dk]上的中心矩；
均匀量化器：假设信源的概率密度函数关于Y轴对称，仅考虑x>0x>0x>0的部分，量化间隔相等。量化值rk=((2k−1)/2)dr_k = ((2k-1)/2)drk=((2k−1)/2)d。目标：对给定概率密度函数p(x)p(x)p(x)和量化分层数KKK，可以确定ddd，使失真最小。
均匀量化失真：
D=2∑k=1K/2−1∫(k−1)dkd(2k−12d−x)2p(x)dx+2∫(K/2−1)d∞(K−12d−x)2p(x)dxD=2 \sum_{k=1}^{K / 2-1} \int_{(k-1) d}^{k d}\left(\frac{2 k-1}{2} d-x\right)^{2} p(x) \mathrm{d} x+ 2 \int_{(K / 2-1) d}^{\infty}\left(\frac{K-1}{2} d-x\right)^{2} p(x) \mathrm{d} x D=2k=1∑K/2−1∫(k−1)dkd(22k−1d−x)2p(x)dx+2∫(K/2−1)d∞(2K−1d−x)2p(x)dx性质：当信源在[∗d∗0,∗d∗K][*d*0,*d*K][∗d∗0,∗d∗K]上均匀分布时，最优量化与均匀量化等价，且Δ=(dK−d0)/K,Dmin=Δ2/12\Delta = (d_K-d_0)/K,D_{min} = \Delta^2/12Δ=(dK−d0)/K,Dmin=Δ2/12。
正态信源量化：x∼N(0,σ2)x\sim N(0,\sigma^2)x∼N(0,σ2)量化值计算：
X^(X)={2/πσ当x≥0−2/πσ当x<0\hat{X}(X)=\left\{\begin{array}{ll} \sqrt{2 / \pi} \sigma & \text { 当 } x \geq 0 \\ -\sqrt{2 / \pi} \sigma & \text { 当 } x<0 \end{array}\right. X^(X)={2/πσ−2/πσ当x≥0当x<0
当代表点集合{X^(ω)}\{\hat{X}(\omega)\}{X^(ω)} 给定时，可通过将信源随机变量XXX映射为代表点中最接近于它的表示X^(ω)\hat{X}(\omega)X^(ω)，使失真最小化。该映射定义一个X的区域构成的集合，称为由代表点定义的Voronoi 划分或狄利克雷划分。代表点应该在各自划分到的区域上使条件期望失真最小化。
满足这两个性质的量化就是Max-Lloyd量化器。
定义8.1.2（矢量量化）：将nnn个连续的采样值构成一个数据块或矢量x=[x1,x2,…,xn]Tx=[x_1,x_2,…,x_n]^Tx=[x1,x2,…,xn]T，用有限个代表矢量{X^1,X^2,...,X^K}\{\hat{X}_1,\hat{X}_2,...,\hat{X}_K\}{X^1,X^2,...,X^K}中的一个来逼近连续矢量xxx，代表矢量中的任一个矢量X^k={x^k1,x^k2,...,x^kn}\hat{X}_k=\{\hat{x}_{k1},\hat{x}_{k2},...,\hat{x}_{kn}\}X^k={x^k1,x^k2,...,x^kn}都是与xxx相同维数的矢量。代表矢量的集合称为码本，码本中的一个矢量称为码字。对一个给定的矢量xxx，从码本中找到一个码字来尽可能逼近xxx。
8.2 定义
失真度量：信源字母表与重建字母表的乘积空间到非负实数集上的映射。 失真矩阵(d(k,j))K×J=[d(a1,b1)d(a1,b2)⋯d(a1,bJ)d(a2,b1)d(a2,b2)⋯d(a2,bJ)⋮d(aK,b1)d(aK,b2)⋯d(aK,bJ)](d(k, j))_{K \times J}=\left[\begin{array}{c} d\left(a_{1}, b_{1}\right) d\left(a_{1}, b_{2}\right) \cdots d\left(a_{1}, b_{J}\right) \\ d\left(a_{2}, b_{1}\right) d\left(a_{2}, b_{2}\right) \cdots d\left(a_{2}, b_{J}\right) \\ \vdots \\ d\left(a_{K}, b_{1}\right) d\left(a_{K}, b_{2}\right) \cdots d\left(a_{K}, b_{J}\right) \end{array}\right] (d(k,j))K×J=⎣⎢⎢⎢⎡d(a1,b1)d(a1,b2)⋯d(a1,bJ)d(a2,b1)d(a2,b2)⋯d(a2,bJ)⋮d(aK,b1)d(aK,b2)⋯d(aK,bJ)⎦⎥⎥⎥⎤
平均失真：
Dˉ=∑k=1K∑j=1Jp(ak,bj)d(ak,bj)=∑k=1K∑j=1Jp(ak)p(bj/ak)d(ak,bj)\bar{D} = \sum_{k=1}^K\sum_{j=1}^Jp(a_k,b_j)d(a_k,b_j) = \sum_{k=1}^K\sum_{j=1}^Jp(a_k)p(b_j/a_k)d(a_k,b_j) Dˉ=k=1∑Kj=1∑Jp(ak,bj)d(ak,bj)=k=1∑Kj=1∑Jp(ak)p(bj/ak)d(ak,bj)
平均失真度是信道传输质量的一种度量。在信源和编码器给定的情况下，平均失真度是编码器（信道概率矩阵）的函数。
定义8.2.1一个(2nR,n)(2^{nR},n)(2nR,n)率失真码(rate distortion code)包括一个编码函数fn:Xn→{1,2,...,2nR}f_n:X^n\to \{1,2,...,2^{nR}\}fn:Xn→{1,2,...,2nR}和一个译码函数gn:{1,2,...,2nR}→X^ng_n:\{1,2,...,2^{nR}\}\to\hat{\mathcal{X}}^ngn:{1,2,...,2nR}→X^n，关于这个(2nR,n)(2^{nR},n)(2nR,n)码的失真定义为D=Ed(Xn,gn(fn(Xn)))D=Ed(X^n,g_n(f_n(X^n)))D=Ed(Xn,gn(fn(Xn))).
定义8.2.2称率失真对(R,D)(R,D)(R,D)是可达的，若存在一个 (2nR,n)(2^{nR},n)(2nR,n)率失真码序列(fn,gn)(f_n,g_n)(fn,gn) ， 满足
limn→∞Ed(Xn,gn(fn(Xn)))⩽D\lim_{n\to \infty}Ed(X^n,g_n(f_n(X^n)))\leqslant D n→∞limEd(Xn,gn(fn(Xn)))⩽D
定义8.2.3全体可达率失真对(R,D)(R,D)(R,D)所成的集合闭包称为信源的率失真区域。
信道传输的观点：给定信源统计特性p(ak)p(a_k)p(ak)，允许的最大平均失真度∗D∗*D*∗D∗，信道传输率是前向转移概率的下凸函数，信道传输的最低信息量是DDD的函数，即
R(D)=minQ{I(X;Y),E[D(X,Y)]⩽D}R(D) = \min_Q \{I(X;Y),E[D(X,Y)]\leqslant D\} R(D)=Qmin{I(X;Y),E[D(X,Y)]⩽D}
率失真函数直观意义：给定失真度，对固定信源，在满足失真度要求E{d(X,Y)}⩽DE\{d(X,Y)\}\leqslant DE{d(X,Y)}⩽D下，为重建信源所必须获得的最小平均信息量I(X,Y)I(X,Y)I(X,Y)，也就是信源通过该信道必须传输给接收端的最小信息率。
性质：
a.R(D)R(D)R(D)的定义域为(Dmin,Dmax)(D_{min},D_{max})(Dmin,Dmax)，其中Dmin=∑k=1Kp(ak)[minjd(ak,bj)]D_{min} = \sum_{k=1}^Kp(a_k)[\min_jd(a_k,b_j)]Dmin=∑k=1Kp(ak)[minjd(ak,bj)]
b.R(D)R(D)R(D)的定义域DDD上的下凸函数。
c.R(D)R(D)R(D)的定义域DDD上的连续函数；
d.R(D)R(D)R(D)的定义域DDD上的单减函数。
定理8.2.1（率失真编码定理，香农第三定理）：设R(D)R(D)R(D)为某离散无记忆信源的率失真函数，对任意允许失真度D⩾DminD\geqslant D_{min}D⩾Dmin和任意小的正数ε\varepsilonε，以及足够长的分组长度nnn，则必存在一种信源编码WWW，其码字个数M⩽2n[R(D)+ε]M\leqslant 2^{n[R(D)+\varepsilon]}M⩽2n[R(D)+ε]，编码后的平均失真度满足Dˉ(W)⩽D+ε\bar{D}(W) \leqslant D +\varepsilonDˉ(W)⩽D+ε
综上所述，如果不等式C>R1⩾R(D)C>R_1\geqslant R(D)C>R1⩾R(D)成立，通过定理3（率失真编码）、定理1（冗余编码）和定理2（抗干扰信道编码），总能得到既有效、又可靠的通信系统；反之，不等式不成立，则在信宿端失真或错误不可避免。
8.3 率失真函数的计算
**定理8.3.1 （二元信道）**Bernoulli(p)信源在汉明失真度量下的率失真函数为
R(D)={H(p)−H(D),0≤D≤min{p,1−p}0,D>min{p,1−p}R(D)=\left\{\begin{array}{ll} H(p)-H(D), & 0 \leq D \leq \min \{p, 1-p\} \\ 0, & D>\min \{p, 1-p\} \end{array}\right. R(D)={H(p)−H(D),0,0≤D≤min{p,1−p}D>min{p,1−p}
**定理8.3.2 （高斯信道）**一个N∼(0,σ2)N\sim(0,σ^2)N∼(0,σ2)信源在均方误差失真度量下的率失真函数为
R(D)={12logσ2D,0≤D≤σ20,D>σ2R(D)=\left\{\begin{array}{ll} \frac{1}{2} \log \frac{\sigma^{2}}{D}, & 0 \leq D \leq \sigma^{2} \\ 0, & D>\sigma^{2} \end{array}\right. R(D)={21logDσ2,0,0≤D≤σ2D>σ2
定理8.3.3 （并联高斯信源的率失真）设Xi∼N(0,σi2)X_i\sim N(0,σ_i^2)Xi∼N(0,σi2) 为独立的高斯随机变量，假定失真度量为d(xm,ym)=∑i=1m(xi−yi)2d(x_m,y_m) = \sum_{i=1}^m(x_i-y_i)^2d(xm,ym)=∑i=1m(xi−yi)2。则率失真函数为
R(D)=∑i=1m{12logσi2Di}R(D)=\sum_{i=1}^{m}\left\{\frac{1}{2} \log \frac{\sigma_{i}^{2}}{D_{i}}\right\} R(D)=i=1∑m{21logDiσi2}
其中D1=min{λ,σi2}D_1 = \min \{\lambda,\sigma_i^2\}D1=min{λ,σi2}，且∑i=1mDi=D\sum_{i=1}^mD_i = D∑i=1mDi=D。
率失真函数表达式：将最小化改写为双重最小化
R(D)=minr(x^)minq(x^∣x):∑p(x)q(x^∣x)d(x,x^)⩽D∑x∑x^p(x)q(x^∣x)logq(x^∣x)r(x^)R(D) = \min_{r(\hat{x})}\min_{q(\hat{x}|x):\sum p(x)q(\hat{x}|x)d(x,\hat{x})\leqslant D}\sum_x\sum_{\hat{x}}p(x)q(\hat{x}|x)\log \frac{q(\hat{x}|x)}{r(\hat{x})} R(D)=r(x^)minq(x^∣x):∑p(x)q(x^∣x)d(x,x^)⩽Dminx∑x^∑p(x)q(x^∣x)logr(x^)q(x^∣x)
若AAA为其边际分布p(x)p(x)p(x)满足失真限制的所有联合分布构成的集合，BBB为乘积分布P(x)r(x^)P(x)r(\hat{x})P(x)r(x^)全体构成的集合，其中r(x^)r(\hat{x})r(x^)为任意， 则
R(D)=minq∈Bminp∈AD(p∣∣q)R(D) = \min_{q\in B}\min_{p \in A}D(p||q) R(D)=q∈Bminp∈AminD(p∣∣q)
可应用交替最小化算法。
9. 最大熵
正问题：根据系统所受的外界作用估计系统产生的结果。逆问题：根据系统产生的结果估计外界所用和过程。过定：条件过多。欠定：条件不足。适定问题：解存在、惟一、连续依赖于初边值条件。9.1 最大熵分布
约束条件：f(x)⩾0f(x)\geqslant 0f(x)⩾0当xxx在支撑集SSS的外部时等号成立。∫Sf(d)dx=1\int_S f(d)dx = 1∫Sf(d)dx=1，∫Sf(x)ri(x)dx=αi\int_Sf(x)r_i(x)dx = \alpha_i∫Sf(x)ri(x)dx=αi。
信息不等式：若密度函数ggg满足约束条件，而f∗f^\astf∗是解，则
0⩽D(g∣∣f∗)⩽−h(g)+h(f∗)0\leqslant D(g||f^\ast)\leqslant -h(g)+h(f^\ast) 0⩽D(g∣∣f∗)⩽−h(g)+h(f∗)
从而，对任何满足约束条件的密度函数ggg，均有h(g)⩽h(f∗)h(g)\leqslant h(f^\ast)h(g)⩽h(f∗)。
定理9.1.1 （最大熵分布）设
f∗(x)=exp(λ0+∑i=1mλiri)f^\ast(x) = \exp(\lambda_0 + \sum_{i=1}^m\lambda_ir_i) f∗(x)=exp(λ0+i=1∑mλiri)
其中λi\lambda_iλi是使fff满足约束条件的待定系数。则f∗f^\astf∗是所有满足约束条件的概率密度函数中唯一能够使得h(f)h(f)h(f)最大化的概率密度函数。
奇异：∫−∞∞f(x)dx=∞\int_{-\infty}^\infty f(x)dx = \infty∫−∞∞f(x)dx=∞从而密度函数不能标准化。扰动位置选择：通过适当选择扰动位置，可在新的分布的熵没有明显减少(相对正态分布的熵)的情形下，高阶矩可取到任意值。最大熵只能是εεε可达。
9.2 谱估计
功率谱：假设{Xi}\{X_i\}{Xi}是一个0均值的平稳随机过程，自相关函数为R(k)=EXiXi+kR(k)=EX_iX_{i+k}R(k)=EXiXi+k，0均值过程的自相关函数的傅里叶变换是该过程的功率谱密度函数S(λ)S(\lambda)S(λ):S(λ)=∑m=−∞∞R(m)e−imλS(\lambda) = \sum_{m = -\infty}^\infty R(m) e^{-im\lambda} S(λ)=m=−∞∑∞R(m)e−imλ
周期图估计：通过取长度为nnn的样本数据的样本平均来估计自相关函数，
R^(k)=1n−k∑i=1n−kXiXi+k\hat{R}(k) = \frac{1}{n-k}\sum_{i=1}^{n-k}X_iX_{i+k} R^(k)=n−k1i=1∑n−kXiXi+k
估计方法的改进：加窗处理方案平滑突变。Burg改进：在某些应用中，可假定一个基本自回归模型作为数据的过程，该方法已被证明在确定模型的参数时很有用。
9.3 高斯过程的熵率
实值随机过程熵率：设{Xi}\{X_i\}{Xi}, Xi∈RX_i\in RXi∈R为一个随机过程，如果下面极限存在，那么该过程的微分熵率定义为h(X)=limx→∞1nh(X1,X2,...,Xn)h(X) = \lim_{x \to \infty} \frac{1}{n}h(X_1,X_2,...,X_n) h(X)=x→∞limn1h(X1,X2,...,Xn)
高斯过程：协方差矩阵K(n)K^{(n)}K(n)是第一行元素为R(0),R(1),…,R(n−1)R(0),R(1),…, R(n-1)R(0),R(1),…,R(n−1)的特普利兹矩阵。于是Kij(n)=R(∣i−j∣)=E(Xi−EXi)E(Xj−EXj)K_{ij}^{(n)}=R(|i-j|)=E(X_i-EX_i)E(X_j-EX_j)Kij(n)=R(∣i−j∣)=E(Xi−EXi)E(Xj−EXj)。当n→∞n\to \inftyn→∞时，该协方差矩阵的特征
值的包络存在且为该随机过程的功率谱密度函数。熵率表达式：科尔莫戈罗夫证明平稳高斯随机过程的熵率可表示为
h(X)=12log(2πe)+14π∫−ππlogS(λ)dλh(X) = \frac{1}{2}\log(2\pi e) + \frac{1}{4\pi}\int_{-\pi}^\pi\log S(\lambda)d\lambda h(X)=21log(2πe)+4π1∫−ππlogS(λ)dλ
其条件熵率为12log(2πeσ∞2)\frac{1}{2}\log(2\pi e\sigma_\infty^2)21log(2πeσ∞2)，其中σ∞2\sigma_\infty^2σ∞2 是在已知无穷过去的条件下对Xn的最佳估计的误差的方差。σ∞2=12πe22h(X)\sigma_\infty^2 = \frac{1}{2\pi e}2^{2h(X)}σ∞2=2πe122h(X)。熵率对应着该过程的一个样本的最佳估计的最小均方差。
9.4 Burg最大熵定理
定理9.4.1 （Burg最大熵定理）：满足约束条件EXiXi+k=αkEX_iX_{i+k}=\alpha_kEXiXi+k=αk 的最大熵率随机过程{Xi}\{X_i\}{Xi}必是如下形式的ppp阶高斯马尔可夫过程：Xi=−∑k=1pakXi−k+ZiX_i = -\sum_{k=1}^pa_kX_{i-k}+Z_i Xi=−k=1∑pakXi−k+Zi
其中Zi∼N(0,σ2)i.i.dZ_i\sim N(0, \sigma^2) i.i.dZi∼N(0,σ2)i.i.d。
最大熵过程的功率谱密度为
S(λ)=−∑m=−∞∞R(m)e−imλ=σ2∣1+∑k=1pake−ikλ∣2S(\lambda) = -\sum_{m = -\infty}^\infty R(m)e^{-im\lambda}=\frac{\sigma^2}{|1+\sum_{k=1}^p a_ke^{-ik\lambda}|^2} S(λ)=−m=−∞∑∞R(m)e−imλ=∣1+∑k=1pake−ikλ∣2σ2
马尔科夫过程熵率公式：如果仅求ppp阶高斯马尔科夫过程的熵率，可以不计算所有aia_iai而直接得到它。令KpK_pKp为该过程的自相关矩阵。对于该过程，熵率等于
h∗=h(Xp∣Xp−1,⋯,X0)=h(X0,⋯,Xp)−h(X0,⋯,Xp−1)=12log((2πe)p⋅t∣Kp∣)−12log((2πe)p∣Kp−1∣)=12log((2πe)∣Kp∣∣Kp−1∣)\begin{aligned} &h^{*}=h\left(X_{p} \mid X_{p-1}, \cdots, X_{0}\right)=h\left(X_{0}, \cdots, X_{p}\right)-h\left(X_{0}, \cdots, X_{p-1}\right)\\ &=\frac{1}{2} \log \left((2 \pi \mathrm{e})^{\mathrm{p} \cdot \mathrm{t}}\left|\boldsymbol{K}_{\mathrm{p}}\right|\right)-\frac{1}{2} \log \left((2 \pi \mathrm{e})^{\mathrm{p}}\left|\boldsymbol{K}_{\mathrm{p}-1}\right|\right)=\frac{1}{2} \log \left((2 \pi \mathrm{e}) \frac{\left|\boldsymbol{K}_{p}\right|}{\left|\boldsymbol{K}_{\mathrm{p}-1}\right|}\right) \end{aligned} h∗=h(Xp∣Xp−1,⋯,X0)=h(X0,⋯,Xp)−h(X0,⋯,Xp−1)=21log((2πe)p⋅t∣Kp∣)−21log((2πe)p∣Kp−1∣)=21log((2πe)∣Kp−1∣∣Kp∣)
10. 通用信源编码
10.1 通用码与信道容量
冗余度：如果使用的码的码长为l(x)l(x)l(x)，并假设该码通过Huffman编码所得，相应的概率为q(x)=2−l(x)q(x)=2-l(x)q(x)=2−l(x)， 定义码的冗余度为编码的期望长度与期望长度的下界之差：R(pθ,q)=Epθ[l(X)]−(−Epθ[logpθ(X)])=D(pθ∣∣q)R(p_\theta,q) = E_{p_\theta}[l(X)] - (-E_{p_\theta}[\log p_\theta(X)]) = D(p_\theta || q) R(pθ,q)=Epθ[l(X)]−(−Epθ[logpθ(X)])=D(pθ∣∣q)
其中q(x)=2−l(x)q(x) = 2^{-l(x)}q(x)=2−l(x)为对应码字长度l(x)l(x)l(x)的分布。
编码目标：无论真实分布pθp_θpθ如何，总希望找到一个编码，能始终表现得很好。
最小最大冗余度：定义为
R∗=minqmaxpθR(pθ,q)=minqmaxpθD(pθ∣∣q)R^\ast = \min_q \max_{p_\theta}R(p_\theta,q) = \min_q\max_{p_\theta}D(p_\theta ||q) R∗=qminpθmaxR(pθ,q)=qminpθmaxD(pθ∣∣q)
编码器：为求得分布qqq，使它在相时熵意义下尽可能与所有可能的pθp_θpθ 接近，对于信道{θ,pθ(x),X}\{θ, p_θ(x), X\}{θ,pθ(x),X}的转移矩阵，它的行等于信源的可能分布pθp_θpθ 。
结论：最小最大冗余度R∗R^\astR∗等于该信道的容量，且达到信道容量时的输入分布导出该信道的输出分布，即是此时的最优码分布。信道容量为
C=maxπ(θ)∑θπ(θ)pθ(x)logpθ(x)qπ(x)C = \max_{\pi(\theta)}\sum_\theta \pi(\theta)p_\theta(x)\log\frac{p_\theta(x)}{q_\pi(x)} C=π(θ)maxθ∑π(θ)pθ(x)logqπ(x)pθ(x)
其中
qπ(x)=∑θπ(θ)pθ(x)q_\pi(x) = \sum_\theta\pi(\theta)p_\theta(x) qπ(x)=θ∑π(θ)pθ(x)
定理10.1.1：设信道p(x∣θ)p(x|θ)p(x∣θ)的各行分别为p1,p2,…,pmp_1, p_2,…, p_mp1,p2,…,pm，则它的容量为
C=R∗=minqmaxpθD(pθ∣∣q)C = R^\ast =\min_q\max_{p_\theta}D(p_\theta ||q)C=R∗=qminpθmaxD(pθ∣∣q)
其中，最小值时的分布qqq为达到信道容量时的输入分布π(θ)π(θ)π(θ)的所导出的输出分布
q∗(x)=qπ∗(x)=∑θπ∗(θ)pθ(x)q^\ast(x) = q_{\pi^\ast}(x) =\sum_\theta\pi^\ast(\theta)p_\theta(x) q∗(x)=qπ∗(x)=θ∑π∗(θ)pθ(x)
10.2 二元序列的通用编码
脱机算法描述：计算0、1比例，算法为两阶段描述：
获得1的数目kkk；（编码比特数：⌈log(n+1)⌉\lceil \log(n+1) \rceil⌈log(n+1)⌉）给所有kkk个1的上面序列一个确定的下标⌈logCnk⌉\lceil \log C_n^k \rceil⌈logCnk⌉。
两阶段编码长度估计：总长度为
l(xn)⩽log(n+1)+logCnk+2⩽nH(kn)+12logn−12log(πk(n−k)n2)+3l(x^n)\leqslant \log(n+1) + \log C_n^k +2 \leqslant nH(\frac{k}{n})+\frac{1}{2}\log n - \frac{1}{2}\log(\pi\frac{k(n-k)}{n^2})+3 l(xn)⩽log(n+1)+logCnk+2⩽nH(nk)+21logn−21log(πn2k(n−k))+3
结论：编码序列的代价大约等于(logn)/2(\log n)/2(logn)/2比特，与对应于(k/n)(k/n)(k/n)的伯努利分布的香农码的最优代价相比，上述描述的代价更大。两阶段编码缺陷：压缩器需要耐心等待到看完整个序列。
另一种编码方法：编码时使用总体上达到上述相同结果的混合分布。
编码分布：q(x1,x2,...,xn)=2−l(x1,x2,...,xn)q(x_1,x_2,...,x_n) = 2^{-l(x_1,x_2,...,x_n)}q(x1,x2,...,xn)=2−l(x1,x2,...,xn)。为x1,x2,…,xnx_1, x_2,…,x_nx1,x2,…,xn上所有Bernoulli(θ)分布的混合分布。性质：
a.序列混合概率p(x1,x2,...,xn)=∫01θk(1−θ)n−kdθ=A(n,k)p(x_1,x_2,...,x_n) = \int_0^1 \theta^k(1-\theta)^{n-k}d\theta = A(n,k)p(x1,x2,...,xn)=∫01θk(1−θ)n−kdθ=A(n,k)
b.概率递归公式：A(n,k)=n−kk+1A(n,k+1)A(n,k) = \frac{n-k}{k+1}A(n,k+1)A(n,k)=k+1n−kA(n,k+1)
c.初值A(n,n)=1n+1A(n,n) = \frac{1}{n+1}A(n,n)=n+11
d.编码码字长度估计：log1q(xn)⩽log(n+1)+logCnk+1\log\frac{1}{q(x^n)} \leqslant \log(n+1) + \log C_n^k +1logq(xn)1⩽log(n+1)+logCnk+1。
结论：与上述的两阶段锚述相比，长度相差在1 比待之内。与最优编码器的差距：若实际信源服从Bernoulli(θ)，则最优码的码长需要nH(k/n)nH(k/n)nH(k/n)，但对于没有任何假设的信源分布而言，上述混合分布达到的码字长度与之相比超出的代价在(logn)/2(\log n)/2(logn)/2比特之间。
10.3 算术编码
字符序列的编码是一个区间，它的长度随着增加更多的字符到序列中而减少。
给定任意长度nnn和概率密度函数q(x1,x2,…,xn)q(x_1, x_2,…, x_n)q(x1,x2,…,xn)，算术编码程序能够以长度−log(q(x1,x2,…,xn))+2-\log(q(x_1, x_2,…, x_n))+2−log(q(x1,x2,…,xn))+2比特编码序列x1,x2,…,xnx_1, x_2,…, x_nx1,x2,…,xn。
如果信源为i.i.d.，并假定分布qqq等于数据的真实分布ppp，这个程序能达到的平均分组长度与熵相比超出的部分在2比持之内。
尽管对固定的分组长度，此程序不一定是最优的，但这个程序是增量式的，而且对任意分组长度都适用。
10.4 Lempel-Ziv编码
自适应字典式压缩算法。LZ77或滑动窗Lempel-Ziv算法与LZ78或树结构Lempel-Ziv算法。Lempel-Ziv编码：设Rn(Xn)R_n(X^n)Rn(Xn)表示我们在过去观察到nnn长字符组XnX^nXn的最近时刻，则(logRn)/n→H(X)(\log R_n)/n\to H(X)(logRn)/n→H(X)，且描述再现时间的编码是渐进最优的。如果序列可以解析为此前未出现过的最短词组，l(xn)l(x^n)l(xn)为解析序列的描述长度，则对任意平稳遍历过程{Xi}\{X_i\}{Xi}，均有limsup1nl(Xn)⩽H(X)a.s.\lim \sup \frac{1}{n} l(X^n) \leqslant H(X)\quad a.s. limsupn1l(Xn)⩽H(X)a.s.
