信息论与编码

1 引论

1.1 信息论的基本概念

信息论：研究（概率）信息的传输、存储和处理

要素：信源、编码器、信道、译码器、信宿、干扰源

信息表征客体变化、客体之间的差异和关系，表征客体的行为和能力而不是客体本身

概率信息（香农信息）：从事件的不确定度和概率测度出发

信息（包含在消息中）、消息（具体的但不是物理的）、信号（消息的载荷者）

经典信息论（香农信息论）、工程信息论（一般信息论）、广义信息论（信息科学）

* 1.2 信息论与编码的发展简史

* 1.3 香农与经典信息论

2 信源编码-唯一可译码

2.1 信源的数学模型

离散信源：每隔定长时间发出随机变量$X_1,X_2,X_3,...$

假设每个X~n~都是取值在有限集合$S=\{s_1,s_2,...,s_q\}$上的离散随机变量
S称为信源字母表

离散无记忆信源：随机变量$X_1,X_2,X_3,...$彼此统计独立

离散无记忆简单信源：随机变量$X_1,X_2,X_3,...$具有相同概率分布的离散无记忆信源

2.2 信源编码

r-元编码：

$S=\{s_1,s_2,...,s_q\}$，信源字母表
$T=\{t_1,t_2,...,t_r\}$，信道的基本符号组合
$C=\{w_1,w_2,...,w_q\}$，输出的码字集合

T中的一个字（word）w是由T中字母组成的有限序列，字的长度即为序列中字母的个数。

$T^n=T\times T...\times T$
$\varepsilon$：空字
$T^*=\bigcup_{n\geq 0}T^n$：所有字集合
$T^+=\bigcup_{n>0} T^n$：所有非空字集合

信源编码：$C:S\rightarrow T^+$，$C=\{w_1,w_2,....,w_q\}$

信源序列编码：$C^*:S^*\rightarrow T^*$，$C^*=\{w_{i1},w_{i2},...,w_{in}|w_{ij}\in C,n\geq 0\}$

平均码字长度：$L(C)=\sum_{k=1}^{K}p_kl_k$

信源编码最主要目的：易于实现、平均码长最短（编码效率尽可能大）

2.3 唯一可译码

定义【唯一可译码】：$C:S^*\rightarrow T^*$是唯一可译码，若对$\forall t\in T^*$，至多存在一个$s\in S^*$与之对应。即$C:S^*\rightarrow T^*$是一一对应的。

定理：若C中每个码字w~i~具有相同长度，则C是唯一可译码

若C中码字长度都相同，则称之为长度为L的分组码

定义：定义C~0~C~1~...为非空字集合$C_n\subseteq T^+$，特别地，定义C~0~=C，且$C_n=\{w\in T^*|uw=v,其中u\in C,v\in C_{n-1} 或 u\in C_{n-1},v\in C \},n\geq 1$；$C_{\infty}=\bigcup_{n=1}^{\infty}C_n$；

定理【唯一可译码的充要条件】：码C为唯一可译码的充要条件为$C\bigcap C_{\infty}=\empty$

反证法可证明

定义【即时码】：如果对每个码字序列$w_{i1},w_{i2},...,w_{in}...$，每个以$w_{i1},w_{i2},...,w_{in}...$开头的马子序列t都唯一地被译为$s_{i1},s_{i2},...,s_{in}...$，无论t中后续字母是什么

定义【前缀码】：如果每个码字都不是其他码字的前缀

定理：一个码C为即时码的充要条件为C是前缀码

逗点码（延长码）：每个码字的开头都是相同的字母串，且这个字母串只出现在码字的开头

2.4 信源编码的分类

码

奇异码
非奇异码
- 非唯一可译码
- 唯一可译码
  - 等长码
  - 变长码
    - 前缀码/即时码
    - 逗点码/延长码

3 信源编码-即时码的构造

3.1 图论的观点：码树

一个码C可看作树$T^*$中一些顶点的有限集合

码字$w_i$是$w_j$的前缀当且仅当存在一条从$w_i$到$w_j$的路径

码C是即时码当且仅当每个码字都不受其他码字支配

3.2 Kraft不等式

定理：设信源消息集合为$S={s_1,s_2,...s_q}$，信道基本符号的种类为r，码字集合为$C={w_1,w_2,...,w_q}$，对应的码长集合为$b={l_1,l_2,...,l_q}$，则存在即时码的充要条件为下列不等式：$\sum_{i=1}^{q}r^{-l_i}\leq 1$

Kraft不等式为前缀码约束条件
适用于即时码的存在性问题，但不能给出具体的码
能判定不是即时码，但不能判定是即时码

3.3 McMillan's不等式

定理：任意唯一可译码的码长必然满足Kraft不等式$\sum_{i=1}^{q}r^{-l_i}$

引理：存在码长为$l_1,l_2,...,l_q$的即时码，当且仅当存在码长为$l_1,l_2,...,l_q$的唯一可译码

3.4 即时码的最小期望长度

期望的码字长度：$L^*=-\sum{p_ilog_r p_i}$

最佳码长原则：大概率对应短码长，小概率对应长码长

4 信源编码-Huffman编码

4.1 最优码

定义【最优码】：给定信道的符号个数r以及概率分布$p_i$，期望码长最小的即时码称为最优码

定理：若$p_j>p_k$，则$l_j<l_k$

引理：给定信源S和整数r，{L(C),C为对信源S的唯一可译码}={L(C),C为对信源S的即时码}。{L(C),C为对信源S的即时码}下界为0，记L~min~(S)为集合下确界，则一个r元即时码C为最优码满足L(C)=L~min~(S)

定理：对于任意信源，总存在r元最优码（$r\geq2$）

4.2 二元Huffman编码

缩减信源：对信源S的信源符号重新编号，使之对应的概率从大到小排序。将两个概率最小的信源符号合并为一个新符号，并将两个信源符号的概率之和作为新符号的概率，得到包含q-1个信源符号的缩减信源S'

引理：若C'使即时码，则C也是即时码

构建方法：q个字母的信源S的二元即时码C可由q-1个字母的信源S'的二元即时码得到。以此类推：

$S \rightarrow S'\rightarrow S'',...,\rightarrow S^{q-1}$，$C \leftarrow C'\leftarrow C'',...,\leftarrow C^{q-1},$C即为信源S的Huffman编码

注意：Huffman编码不唯一，在各次缩减信源中保持码元分配的一致性。码元分配不同，具体的码字也不同，但码长不变

定义【码长的方差】：码字长度的方差$\sigma^2=E[(l_i-L(C))^2]=\sum_{i=1}^{q}p_i(l_i-L(C))^2$

在Huffman编码中，对缩减信源符号按概率由大到小的顺序重新排列，应使合并后的新符号尽可能排在靠前的位置，这样能够使合并后的新符号重复编码次数减少，使短码得到充分利用。

4.3 二元Huffman编码的平均码长

信源S对应码字集合为C，其一次缩减信源S'对应码字集合为C'，则有:

$L(C)-L(C')=(l+1)p_q+(l+1)p_{q-1}-l(p_q+p_{q-1})=p_{q-1}+p_q=p'$

利用$L(C^{(q-1)})=|\varepsilon|=0$，迭代可得：$L(C)-L(C^{(q-1)})=L(C)=p'+p''+...+p^{(q-1)}$

计算每次缩减信源产生的新概率之和即可得到平均码长

4.4 二元Huffman编码的最优性

定义【兄弟】：若两个二元码字$w_1$和$w_2$是同一个字$x$的孩子，即形式为$x0$和$x1$，则它们互称为兄弟

引理：对于任意信源S，总存在一个二元最优即时码，其最长的两个码字为兄弟

定理：对于任意信源S，若C是与之对应的二元Huffman编码，则C是信源S的最优码

5 信息量

5.1 非平均互信息量

输入空间、输出空间、联合空间：

输入空间：$X=\{x_k,k=1,2,...,K\}$，概率记为$Q(x_k)$
输出空间：$Y=\{y_j,j=1,2,...,K\}$，概率记为$\Omega(y_j)$
联合空间：$XY=\{x_ky_j;k=1,2,...,K;j=1,2,...,J\}$，概率为$P(x_ky_j)$
$P(x_ky_j)=P(k_k|y_j)\Omega(y_j)=P(y_j|x_k)Q(x_k)$
先验概率$Q(x_k)$，后验概率$P(x_k|y_j)$

信息量只与后验概率和先验概率有关。先验概率越大，得到的信息量越小，反之信息量越大。

定义【非平均互信息量】：二维离散型随机变量$\{(X,Y),(x_k,y_j),P(x_K,y_j),k=1\sim K;j=1\sim J\}$。因此给定了两个离散型随机变量$\{X,x_k,Q_k,k=1\sim K\}$，$\{Y,y_j,\Omega_j,j=1\sim J\}$。事件$x_k$与$y_j$的互信息定义为$I(x_k;y_j)=\log\frac{P(x_k|y_j)}{Q(x_k)}=\log\frac{P(y_j|x_k)}{\Omega(y_j)}=I(y_j;x_k)$

底数为2时，互信息量的单位为比特bit；底数为e时互信息量的单位为奈特nat

非平均互信息=收信者收到$y_j$前后，对信源发$x_k$的不确定性的消除。

性质【非平均互信息量】：

对称性：$I(x_k;y_j)=I(y_j;x_k)$
$P(x_k,y_j)=Q_k\Omega_j$，则$I(x_k;y_j)=0$（X与Y独立时成立）
$P(x_k,y_j)>Q_k\Omega_j$，则$I(x_k;y_j)>0$
$P(x_k,y_j)<Q_k\Omega_j$，则$I(x_k;y_j)<0$
当$y_j$的出现有助于肯定事件$x_k$的出现，即$P(x_k|y_j)>Q_k$，则$I(x_k;y_j)>0$；否则$I(x_k;y_j)<0$

三个事件集的条件互信息：$I(u_1;u_2|u_3)=\log\frac{P(u_1|u_2,u_3)}{P(u_1|u_3)}=\log\frac{P(u_1,u_2|u_3)}{P(u_1|u_3)P(u_2|u_3)}$。

可加性：$I(u_1;u_2,u_3)=I(u_1;u_2)+I(u_1;u_3|u_2)=I(u_1;u_3)+I(u_1;u_2|u_3)$。

$(u_2,u_3)$联合给出的关于$u_1$的信息量等于$u_2$给出的关于$u_1$的信息量与$u_2$已知条件下$u_3$给出的关于$u_1$的信息量之和。

5.2 非平均自信息量

定义【非平均自信息量】：给定一个离散型随机变量${X,x_k,Q_k,k=1\sim K}$，事件$x_k\in X$的自信息量定义为：$I(x_k)=\log_a {\frac{1}{Q_k}}$，其中a是大于1的常数。

性质【非平均自信息量】：

非负性：$I(x_k)\geq 0$
单调性：$Q_k$越小，$I(x_k)$越大
$I(x_k;y_j)\leq \min\{I(x_k),I(y_j)\}$，即互信息量不超过各自的自信息量

非平均自信息量的物理意义：

当$x_i$发生前，表示该事件发生的不确定性
当$x_i$发生后，表示该事件所提供的信息量

定义【条件的非平均自信息量】：给定二位离散型随机变量$\{(X,Y),(x_k,y_j),P(x_k,y_j),k=1\sim K;j=1\sim J\}$。在事件$y_j$发生的条件下,事件$x_k$的条件自信息量定义为：$I(x_k|y_j)=\log_a{\frac{1}{P(x_k|y_j)}}=\log_a\frac{P(y_j)}{P(x_k,y_j)}$

性质【条件的非平均自信息量】：$I(x_k;y_j)=I(x_k)-I(x_k|y_j)$

定义【联合的非平均自信息量】：给定一个二维离散型随机变量$\{(X,Y),(x_k,y_j),P(x_k,y_j),k=1\sim K;j=1\sim J\}$。事件$(x_k,y_j)\in (X,Y)$的自信息量定义为$I(x_k,y_j)=\log_a{\frac{1}{P(x_k,y_j)}}$。

性质【联合的非平均自信息量】：$\begin{aligned}I(x_k,y_j)&=I(x_k)+I(y_j|x_k)\\&=I(x_k)+I(y_j)-I(x_k;y_j)\end{aligned}$

6 熵

6.1 离散集的平均自信息量-熵

定义【平均自信息量-熵】：离散型随机变量$\{X,x_k,Q_k,k=1\sim K\}$的平均自信息量，即熵定义为：

$H(X)=E[I(X)]=\sum_{k=1}^{K}p(x_k)I(x_k)=-\sum_{k=1}^{K}Q_k\log_a Q_k$

约定：$0\log0=0$，信息熵单位与自信息单位相同Bit、Nat、Det

集X的平均自信息量表示集X中事件出现的平均不确定性：

观测前，集X中每出现一个事件平均所需的信息量
观测后，集X中每出现一个事件平均给出的信息量

定义【条件平均自信息量-条件熵】：给定一个二维离散型随机变量$\{(X,Y),(x_k,y_j),P(x_k,y_j),k=1\sim K;j=1\sim J\}$，则X相对于Y的条件熵定义如下：$H(X|Y)=-\sum_{k=1}^{K}\sum_{j=1}^{J}p(x_k,y_j)\log p(x_k|y_j)$

定义【联合熵】：给定一个二维离散型随机变量$\{(X,Y),(x_k,y_j),P(x_k,y_j),k=1\sim K;j=1\sim J\}$，则X与Y的联合熵为：

$H(X,Y)=-\sum_{k=1}^{K}\sum_{j=1}^{J}p(x_k,y_j)\log p(x_k,y_j)$

性质：熵、条件熵、联合熵的关系

$H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)$
当X与Y独立时，$H(X,Y)=H(X)+H(Y)$，$H(X|Y)=H(X),H(Y|X)=H(Y)$

定义【相对熵】：两个概率密度函数p(x)与q(x)之间的相对熵定义为：$D(p||q)=\sum_{x\in X}p(x)\log \frac{p(x)}{q(x)}=E_{p(x)}\log \frac{p(x)}{q(x)}$

约定：$0\log\frac{0}{q}=0$，$p\log \frac{p}{0}=\infty$

性质【相对熵】：

相对熵总是非负的
条件相对熵$D(p(y|x)||q(y|x))=E_{p(x,y)}\log \frac{p(Y|X)}{q(Y|X)}$
链式法则：$D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))$

6.2 离散集的平均互信息量

$I(X;y_i)=\sum_{i=1}^{N}p(x_i|y_j)I(x_i;y_j)=\sum_{x}p(x|y_i)I(x;y_j)$【从y~i~中获取关于输入符号的平均信息量应该在条件概率空间中做统计平均】

定义【平均互信息量】：$I(X;Y)=\sum_x\sum_yp(x,y)\log\frac{p(x,y)}{p(x)p(y)}=D(p(x,y)||p(x)p(y))=I(Y;X)$

性质【平均互信息量】：

对称性：$I(X;Y)=I(Y;X)$
各种熵的关系：$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y)$

注意：联合熵、条件熵、平均互信息都是对联合概率平均

物理意义：

条件熵H(X|Y)：给定Y之后X剩余的不确定度的度量
联合熵H(X,Y)：X和Y一起出现时的不确定度的度量
互信息I(X;Y)：给定Y后X不确定度减少的程度

推广【条件互信息】：

$I(X;Y|Z)=\sum_x\sum_y\sum_z\log\frac{p(x|yz)}{p(x|z)}$
$I(X;Y|Z)=H(X|Z)-H(X|YZ)$

信道环境中，H(X|Y)称为疑义度，H(Y|X)称为噪声熵，H(X,Y)称为共熵。

熵的链式法则：$H(X_1,X_2,...,X_n)=\sum_{i=1}^{n}H(X_i|X_{i-1},...,X_1)$

互信息的链式法则：$I(X_1,X_2,...X_n;Y)=\sum_{i=1}^{n}I(X_i;Y|X_{i-1},...,X_1)$

熵的性质：

非负性：$H(X)\geq0$，$H(X|Y)\geq0$，$H(Y|X)\geq0$，$H(X,Y)\geq0$
确定性：当一个概率分量为1时，H(X)=0
可忽略性：当某个随机变量发生某个事件概率很小时，该事件对熵的贡献可以忽略不计
可加性：$H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)$
极值性：$H(X)\leq\log_aK$，当且仅当$q_1=q_2=...=q_k=1/K$，等号成立。

7 信息不等式

7.1 信息不等式

定义【凸函数】：$f(\theta\alpha+(1-\theta)\beta)\leq\theta f(\alpha)+(1-\theta)f(\beta)$

性质【凸函数】：

如果f(a)是凸的，则-f(a)是凹的
如果函数f总是位于任意一条弦的下面，则是凸的
若$f_1(\alpha),...,f_L(\alpha)$都是凹函数且$c_1,...,c_L$都是正数，则$c_1f_1(\alpha)+...+c_Lf_L(\alpha)$也是凹函数
如果函数f存在处处非负的二阶导数，则f为凸函数

定理【K-T条件】：（K-T条件是确定某个点为极值点的必要条件，==若目标函数为凸函数，则是充分必要条件==）$f(\alpha)$是定义域R上的凹函数，a是概率矢量，偏导数$\frac{\partial f(a)}{\partial a_k}$存在且连续，$f(a)$在R上为极大的充分必要条件是$\begin{aligned}&\frac{\partial f(a)}{\partial a_k}=\lambda,a_k\neq 0\\ &\frac{\partial f(a)}{\partial a_k}\leq\lambda,a_k=0\end{aligned}$

定理【基础不等式】：$\ln x\leq x-1$

定理【Jensen不等式】：如果f为凹函数，X为随机变量，则$E[f(X)]\geq f(EX)$

若函数是严格凸的，则不等式严格成立。
X是个常数，即X=EX时等号成立
若f为凹函数，则不等式反向

定理【信息散度不等式】：$D(p||q)\geq0$，等号成立当且仅当$p(x)=q(x)$对任意x成立

定理【互信息不等式】：

$I(X;Y)=D(p(x,y)||p(x)p(y)) \geq 0$，等号成立当且仅当$p(x,y)=p(x)p(y)$
$I(X;Y|Z)\geq0$，所有Shannon信息度量都可以看做I(X;Y|Z)的特例
若Z退化为常数，则：$I(X;Y|c)=I(X;Y),I(X;X|c)=H(X),I(X;X|Z)=H(X|Z)$

7.2 相对熵、熵和互信息量的凸性

定理【最大离散熵定理】：设|X|是X中的元素数目，则$H(X)\leq\log|X|$，当等概分布时等号成立。

定理【条件降低熵】：$H(X|Y)\leq H(X)$，X与Y独立时等号成立；$H(X_1,X_2,...,X_n)\leq \sum_{i=1}^{n}H(X_i)$

条件作用使上减小仅在平均意义下成立，某个特定的H(X|Y=y)可能比H(X)大或小

定理【对数和不等式】：对非负数$a_1,a_2,...,a_n$和$b_1,b_2,...,b_n$，有：$\sum_{i=1}^{n}a_i\log\frac{a_i}{b_i}\geq(\sum_{i=1}^{n}a_i)\log\frac{\sum_{i=1}^{n}a_i}{\sum_{i=1}^{n}b_i}$，当且仅当$a_i/b_i$为常数时等号成立。

推论：
- $D(p||q)$是(p,q)的凸函数
- $H(p)$是p的凹函数（$H(p)=\log|X|-D(p||u)$）

定理【互信息量的凹凸性】：已知联合概率分布$(X,Y)\sim p(x,y)=p(x)p(y|x)$，其互信息量为$I(X;Y)=\sum_{x}\sum_{y}p(y|x)p(x)\log\frac{p(y|x)}{\sum_{x}p(y|x)p(x)}$

若$p(y|x)$给定，则$I(X;Y)$是关于$p(x)$的凹函数
若$p(x)$给定，则$I(X;Y)$是关于$P(y|x)$的凸函数

定理【半平均互信息量】：$I(X;Y)=\sum_{k=1}^{K}q_kI(X=k;Y)$

定理【马尔可夫链】：对于3个随机变量空间XYZ，如果Z的条件分布只取决于Y而与X无关，则称XYZ构成了马尔可夫链。特别地，若$P(X,Y,Z)=P(X)P(Y|X)P(Z|Y)$，则称随机变量XYZ构成了马氏链，即$X\rightarrow Y\rightarrow Z$。

马尔可夫链蕴含独立性：$p(xz|y)=p(x|y)p(z|y)$

定理【信息处理定理】：若存在马氏链$X \rightarrow Y \rightarrow Z$，则

$I(X;Y)\geq I(X;Z)$【找不到对Y的处理过程使得Y包含X的信息量增加】
- $I(X;Y,Z)=I(X;Z)+I(X;Y|Z)=I(X;Y)+I(X;Z|Y)$，$I(X;Z|Y)=0$
$I(X;Y)\geq I(X;Y|Z)$【通过观察顺流的随机变量Z，X与Y的依赖性有所降低】
- 如果XYZ不构成马氏链，则可能$I(X;Y|Z)>I(X;Y)$

定理【Fano不等式】：设$P_e=Pr\{\hat X\neq X\}$，则$H(P_e)+P_e\log(|X|-1)\geq H(X|Y)$。

减弱形式：$1+P_e\log|X| \geq H(X|Y)$或$P_e \geq \frac{H(X|Y)-1}{\log|X|}$

8 渐进均分性

8.1 渐进均分性定理AEP

定理【弱大数定律】：设$X=\{x_1,x_2,...,x_n,...\}$为相互独立的随机变量序列，并服从相同的分布，且数学期望为$EX_i=a$，则$\frac{1}{n}\sum_{i=0}^{n-1}X_i$以概率收敛到a，即对任意$\varepsilon>0$有$\lim_{n\rightarrow\infty}Pr\{|\frac{1}{n}\sum_{i=0}^{n-1}X_i-a|<\varepsilon\}=1$

定理【AEP】：对无记忆独立同分布信源$\{X_k,k\geq1\}$：$-\frac{1}{n}\log p(X^n)$依概率收敛到$H(X)$

i.i.d：独立同分布

性质【AEP】：

若$(x_1,x_2,...,x_n)\in A_\varepsilon^{(n)}$，则$H(X)-\varepsilon\leq -\frac{1}{n}\log p(x_1,x_2,...,x_n)\leq H(X)+\varepsilon$
当n充分大时，$Pr\{A_\varepsilon^{(n)}\}>1-\varepsilon$
$|A_\varepsilon^{(n)}|\leq 2^{n(H(X)+\varepsilon)}$
当n充分大时，$|A_{\varepsilon}^{(n)}\geq(1-\varepsilon)2^{n(H(X)-\varepsilon)}|$

* 8.2 AEP的结果应用：数据压缩

* 8.3 高概率与典型集

9 熵界和几种典型信源编码

9.1 熵与平均码长

定理【熵与平均码长】：若C时信源S的一个r元唯一可译码，则有$L(C)\geq H_r(S)$

$H_r(S)\leq L(C)+\log_r K\leq L(C),K=\sum_{i=1}^{q}r^{-l_i}$

推论【熵与平均码长】：给定信源S的概率分布$p_i$，则存在一个r元唯一可译码C，其平均码长$L(C)=H_r(S)$的充分必要条件为：$\log_r p_i$对每个i都是一个整数，即$p_i=r^{-l_i}$，$l_i$为非负整数

定义【熵界】：信源S的任意一个r元即时码的平均码长必须大于等于熵$H_r(S)$，其中等号成立当且仅当$p_i=r^{-l_i}$

定义【编码效率】：$\eta=\frac{H_r(S)}{L(C)}$

定义【冗余度】：$\bar\eta=1-\eta$

几种典型的信源编码：

Shannon-Fano编码
Shannon-Fano-Elias编码
算数编码

10 香农第一定理

对于给定信源空间$\{X,P(X)\}$的离散信源，其熵$H(X)$时确定的数值，如果信道的基本符号也是确定的话，则下界值也确定了，这就意味着如果不改变信源的统计特性，减小平均码长的潜力，到了$H_r(S)$也就到了极限。因此，如果要进一步提高编码效率，必须对信源本身进行研究，例如改变信源的统计特性。

10.1 信源的扩张

定义【扩展信源】：设信源字母表$S=\{s_1,s_2,...,s_q\}$，则S的n次扩展信源的消息集合为：

$S^n=\{s_{1_1},...,s_{1_n},...,s_{q_1},...,s_{q_n}\}$

信源S的扩展信源$S^{n}$即为n个S的乘积

定义：设信源S和T的消息集合分别为$\{s_i\}$和$\{t_j\}$，对应的概率为$\{p_i\}$和$\{q_j\}$，定义S和T的积$S \times T$为信源，消息集合为$\{(s_i,t_j)\}$，对应概率为$Pr(s_it_j)$

定理【$S \times T$】：设信源S与T相互独立，则$H_r(S\times T)=H_r(S)+H_r(T)$

10.2 香农第一定理

定理【香农第一定理】：又称为Shannon信源编码定理、可变长无失真信源编码定理。通过对n足够大的$S^{n}$进行编码，总可以找到信源S的一个r元即时码，其对应于S的平均码长$\frac{L_n}{n}$可以与熵$H_r(S)$任意接近。

$\frac{L_n}{n}$表示n重符号序列中每个符号对应的平均码元数，随着n的增加，编码效率也会增加，在极限情况下达到最高
但是提高编码效率是以增加编码的复杂性作为代价的
揭示了：无失真信源编码的结果，在无噪离散信道中传输的有效性是有一定限度的，其极限值就是信源熵。

注意：香农第一定理成立的条件是$n \rightarrow\infty$，但是在实际中，只要$\frac{1}{n}\ll H(X)$，香农第一定理就能成立

注意：香农第一定理仅是一个存在性定理，并没有给出构造编码的方法。

* 10.3 LZ编码

11 信道

11.1信道分类

定义【信道】：信道是传输信息的媒质或通道

定义【输入事件与输出事件】：

信道输入事件的概率空间为$[A \ P]$
信道输出事件的概率空间为$[B \ Q]$

信道相当于一个数学交换，可以用条件概率描述

信道的分类：

根据输入输出事件的时间特性和输入输出事件集合的特点进行分类：
- 离散信道：AB都是离散事件集合
- 连续信道：AB都是连续事件集合
- 半连续信道：AB一个是离散事件集合，一个是连续事件集合
- 时间离散的连续信道：信道输入和输出取值于连续集合的序列
- 波形信道：信道输入和输出是随机过程
根据输入和输出个数进行分类：
- 两端信道：输入和输出只有一个事件集合，称为单用户信道
- 多端信道：输入和输出至少有一端有两个以上的事件集合，称为多用户信道
根据信道的统计特性进行分类：
- 恒参信道：信道统计特性不随时间变化
- 随参信道：信道统计特性随时间变化
根据信道的记忆特性进行分类：
- 无记忆信道：信道输出集合B仅与当前输入集合A有关
- 有记忆信道：信道输出集合B与当前和以前若干输入集合有关
根据信道是否有固定的传播线路进行分类：
- 有线信道
- 无线信道
根据信道是否有噪声进行分类：
- 无噪信道
- 有噪信道
根据信道发送消息是否有丢失进行划分：
- 有损信道
- 无损信道

注意：无噪信道既是无损信道又是确定信道；无用信道是从输入不能得到有关输出的任何信息的信道

定义【信道输入输出事件】：

信道输入事件的概率空间为$[A=\{a_1,...,a_r\} \ P=\{p_i=p(a=a_i)\}]$
信道输出事件的概率空间为$[B=\{b_1,...,b_s\} \ Q=\{Q_j=p(b=b_j)\}]$
信道相当于一个数学交换，可以用条件概率描述：$p_{ij}=p(b=b_j|a=a_i)=p(b_j|a_i)$
$\sum_{j=1}^sp_{ij}=1$

定义【离散无记忆信道DMC】：若离散信道的转移概率满足：$p(y|x)=p(y_1y_2...y_N|x_1x_2...x_N)=\prod_{i=1}^{N}p(y_i|x_i)$，则称之为离散无记忆信道，记作$[X \ p(y_i|x_i) \ Y]$

定义【平稳信道】：若DMC对于任意给定的n和m有$p(y_n=b_j|x_n=a_i)=p(y_m=b_j|x_m=a_i)$，则称为平稳信道，即信道转移概率不随时间变化。

离散信道分类：

无噪信道：$y_n=f(x_n)$，$p(y_n|x_n)=\begin{cases}1 & y_n=f(x_n)\\ 0 & y_n \neq f(x_n)\end{cases}$
离散无记忆信道：$y_n\neq f(x_n)$，$p(y|x)=p(y_1y_2...y_N|x_1x_2...x_N)=\prod_{i=1}^{N}p(y_i|x_i)$
离散有记忆信道：$y_n\neq f(x_n)$，$p(y|x)=p(y_1y_2...y_N|x_1x_2...x_N)\neq \prod_{i=1}^{N}p(y_i|x_i)$

定义【单符号离散无记忆信道】：假设信道输入随机变量为X，取值为x，$x\in A=\{a_1,a_2,...,a_r\}$；输出随机变量为Y，取值为y，$y\in B\{b_1,b_2,...,b_s\}$，信道传递概率为$p(y|x)=p(Y=b_j|X=a_i)=p(b_j|a_i)$

$\sum_{j=1}^sp(b_j|a_i)=1$

定义【信道矩阵】：$P=\begin{bmatrix}p(y_1|x_1)&p(y_2|x_1) & \cdots & p(y_s|x_1)\\ p(y_1|x_2)&p(y_2|x_2)&\cdots&p(y_2|x_2)\\ \vdots&\vdots&\ddots&\vdots\\p(y_1|x_r)&p(y_2|x_r)&\cdots&p(y_s|x_r)\end{bmatrix}=\begin{bmatrix}p_{11}&p_{12} & \cdots & p_{1s}\\ p_{21}&p_{22}&\cdots&p_{2s}\\ \vdots&\vdots&\ddots&\vdots\\p_{r1}&p_{r2}&\cdots&p_{rs}\end{bmatrix}$

特点：
- 每个元素均大于0
- 每行元素之和为1

定义【二进制对称信道BSC】：$\varepsilon$为交叉传输概率。如果交叉传输概率相等，则称此二进制信道为二进制对称信道BSC。

$P=\begin{bmatrix}1-\varepsilon&\varepsilon\\\varepsilon&1-\varepsilon\end{bmatrix}$

定义【对称信道】：信道矩阵的行元素集合相同、列元素集合也相同的信道，称为对称信道

所有行/列都是第一行/列的置换

定义【二进制删除信道】：如果对积分器输出的判决不能明显地决定是0还是1，则将其作为信道输入的符号E。

$P=\begin{bmatrix}1-\varepsilon_1-\varepsilon_2&\varepsilon_1&\varepsilon_2\\\varepsilon_2&\varepsilon_1&1-\varepsilon_1-\varepsilon_2\end{bmatrix}$

二进制对称BSC可以看作r=s=2且转移概率矩阵对称的DMC。

11.2 公式和定义

定义

【先验概率】：$p_i=p(a_i)=p(X=a_i)$
【信道传递概率（前向概率）】：$p_{ij}=p(b_j|a_i)=p(Y=b_j|X=a_i)$
- $\sum_{j=1}^{s}p(b_j|a_i)=1$
【联合概率】：$R_{ij}=p(a_ib_j)=p(X=a_i,Y=b_j)=p(a_i)p(b_j|a_i)$
【输出符号概率】：$p(b_j)=p(Y=b_j)=\sum_{i=1}^{r}p(a_i)p(b_j|a_i)$
【后验概率（后向概率）】：$Q_{ij}=p(a_i|b_j)=\frac{p(a_i)p(b_j|a_i)}{\sum_{k=1}^r p(a_k)p(b_j|a_k)}$

定义【信道疑义度】：$H(X|Y)=E[H(X|b_j)]=\sum_{j=1}^{s}\sum_{i=1}^{r}p(a_ib_j)\log p(a_i|b_j)$

信宿收到全部Y后，对输入符号上存在的平均不确定程度——损失熵
无损信道：$H(X|Y)=0$

定义【后验熵】：$H(X|b_j)=\sum_{x}p(x|b_j)\log \frac{1}{p(x|b_j)}$

$I(X;Y)=\sum_{x}\sum_{y}p(x)p(y|x)\log\frac{p(y|x)}{p(x)p(y|x)}$，是信源分布$p(x)$和信道转移概率$p(y|x)$的函数

定理：对于给定的信道，$I(X;Y)$是信源分布$p(x)$的凹函数

对于给定信道，至少存在一个信源，当通过这个信道传递时，能够获得最大的平均互信息
【信道容量】

定理：对于给定的信源，$I(X;Y)$是信道传递函数$p(y|x)$的凸函数

对于给定的信源，至少存在一个信道，当这个信源通过时，可以获得最小的平均互信息
【限失真信源压缩、率失真函数】

简介【信息率失真函数】：研究信道，将信源压缩过程看成通过一个信道，寻找保真度准则下的最小平均互信息

定义【离散N次无记忆扩展信道】：假设离散信道为$[X,p(y|x),Y]$，输入符号集合为$A=\{a_1,a_2,...,a_r\}$，输出符号集合为$B=\{b_1,b_2,...,b_s\}$，xy取值集合分别为AB，将输入输出N次扩展后得到$X=(X_1X_2...X_N)$和$Y=(Y_1Y_2...Y_N)$。

若$p(y|x)=p(y_1y_2...y_N|x_1x_2...x_N)=\prod_{i=1}^{N}p(y_i|x_i)$，则称为$[X,p(y|x),Y]$的N次无记忆扩展信道，记作$[X^N,p(y^N|x^N),Y^N]$
若$p(y|x)=p(y_1y_2...y_N|x_1x_2...x_N)\neq\prod_{i=1}^{N}p(y_i|x_i)$，则称为$[X,p(y|x),Y]$的N次有记忆扩展信道

性质【离散信道N次无记忆扩展信道】：

输入集合：$A^N=\{a_1,a_2,...,a_{r^N}\}$
输出集合：$B^N=\{b_1,b_2,...,b_{s^N}\}$
传递概率：$p(y^N|x^N)=\prod_{i=1}^{N}p(b_{h_i}|a_{k_i})$
平均互信息：$I(X^N;Y^N)=H(X^N)-H(X^N|Y^N)\leq NI(X;Y)$
- 等号成立充要条件为：信道输入无记忆扩展信源

* 11.3 香农第一定理的推广

12 信道容量

12.1 信道容量的定义

定义【信道容量】：信道容量C定义为平均互信息量的最大值$C=max_{p(x)}\{I(X;Y)\}$

表征信道传输信息的最大能力，信道实际传输的信息量不大于信道容量
$I(X;Y)$是关于$p(x)$的凹函数，对于给定信道，存在$p(x)$使得$I(X;Y)$最大——该信源称之为最佳信源分布
关于信道$p(y|x)$的函数，与$p(x)$无关
平均互信息量与信源分布和信道特性两者都有关，而信道容量仅与信道特性有关，即在各种可能的信源分布$p(x)$中，一定能找到一个分布，使得$I(X;Y)$达到最大值，此值即信道容量

性质【信道容量】：

$C\geq 0$
$C\leq \log |X|$，$C\leq\log|Y|$
$I(X;Y)$与$p(x)、p(y|x)$
- 固定$p(y|x)$，$I(X;Y)$是关于$p(x)$的凹函数
- 固定$p(x)$，$I(X;Y)$是关于$p(y|x)$的凸函数

实例：

【无噪、无损信道】：输入X与输出Y具有确定的一一对应的函数关系
- $p(y_j|x_i)=p(x_i|y_j)=\begin{cases} 0 & i\neq j\\ 1 & i=j \end{cases}$
- 每行每列都只有一个非零元素，且为1
- $H(Y|X)=H(X|Y)=0$，$I(X;Y)=H(X)=H(Y)$
- $C=\max_{p(x)}\{I(X;Y)\}=\max_{p(x)}\{H(X)\}=\max_{p(x)}\{H(Y)\}=\log r=\log s$
  
  当输入等概分布时，信道传输的互信息量达到信道容量
【无噪、有损信道】：输入X与输出Y具有确定的多个输入对应一个输出的函数关系
- $p=\begin{bmatrix}1&0\\0&1\\0&1\\1&0\end{bmatrix}$
- 每行只有一个非零元素
- $r>s$，$H(Y|X)=0$，$H(X|Y)\neq0$，$H(X)\geq H(Y)$，$I(X;Y)=H(Y)$
- $C=\max_{p(x)}\{I(X;Y)\}=\log s<\log r$
【有噪、无损信道】：输入X与输出Y具有一个输入对用多个不确定的输出的函数关系
- $p=\begin{bmatrix}p_{11}&p_{12}&p_{13}&0&0&0\\0&0&0&p_{24}&p_{25}&p_{26}\end{bmatrix}$
- 每列只有一个非零元素
- $r<s$，$H(Y|X)\neq0$，$H(X|Y)=0$，$H(x)\leq H(Y)$，$I(X;Y)=H(X)$
- $C=\max_{p(x)}\{I(X;Y)\}=\log r<\log s$
【二进制对称信道BSC】：输入和输出都只有0和1两种符号，且发送0收到1或发送1收到0的概率相同
- $I(X;Y)=H(Y)-H(Y|X)=H(Y)-\sum p(x)H(Y|X=x)=H(Y)-\sum p(x)H(p)=H(Y)-H(p)<1-H(p)=C_{BSC}$
  - 当输入均匀分布时等号成立，信道传输的互信息量达到信道容量
【对称DMC（对称离散无记忆信道）】：
- 特点：
  - 离散：输入集和输出集都是离散集
  - 无记忆：任意时刻的输出只依赖于该时刻输入
  - 输入对称：转移概率矩阵每行都是第一行的置换
  - 输出对称：转移概率矩阵每列都是第一列的置换
- 输入对称：$H(Y|X_i)$与i无关，$H(Y|X)=H(Y|X_i)$
- 输入符号均匀分布$\to$输出符号均匀分布，反之也成立
- $C=\max\{I(X;Y)\}=\max\{H(Y)-H(Y|X)\}=\max\{H(Y)\}-H(Y|X)=\max\{H(Y)\}-\sum_{j=1}^{s}p(y_j|x_i)\log p(y_j|x_i)$
  - 当输出符号均匀分布时$H(Y)$最大：$C=\log s-\sum_{j=1}^{s}p(y_j|x_i)\log p(y_j|x_i)$
- 【强对称信道】：输入和输出符号个数均为n，正确的传输概率为$1-\varepsilon$，错误的传输概率均为$\frac{\varepsilon}{n-1}$
【二进制删除信道BEC】：输入只有0和1，输出有0、1和e。设0$\to$e概率为$\alpha$，$Pr(X=1)=\pi$
- $I(X;Y)=H(Y)-H(Y|X)=H(Y)-H(\alpha)=(1-\alpha)H(\pi)$，$H(Y|X)=H(\alpha)$，$H(X|Y)=\alpha H(\pi)$
- $C=\max\{I(X;Y)\}=\max\{(1-\alpha)H(\pi)\}=1-\alpha$
  - 由于比例为$\alpha$的字节在信道中丢失，因此可以恢复比例为$1-\alpha$的字节，则容量至多为$1-\alpha$
【有噪打字机信道】：信道输入以概率1/2在输出端精确接收，或以1/2概率转变为下一个字母
- $C=\max\{I(X;Y)\}=\max\{H(Y)-H(Y|X)\}=\max\{H(Y)\}-1=\log13$
- 如果在26个符号中间隔输入13个符号，则每次可以无差地传输13个符号
- 香农第二定理的直观解释：世界上任何一个信道均可以看成有噪声的打字机信道

12.2 信道容量的计算

由于$I(X;Y)$是有界闭区域上的凹函数，所以局部最大值也是整体最大值。

约束条件：$\begin{cases}\sum_{i=1}^{M}p(x_i)=1\\p(x_i)\geq0\end{cases}$

定理【K-T条件】：$f(\alpha)$是定义域n维无穷凸集R上的凹函数，$a=(a_1,a_2,...,a_n)$是概率矢量，偏导数$\frac{\partial f(a)}{\partial a_k}$存在且连续，$f(a)$在$a^*$上为极大的充分必要条件是$\begin{aligned}&\frac{\partial f(a)}{\partial a_k}|_{a=a^*}=\lambda,a^*> 0\\ &\frac{\partial f(a)}{\partial a_k}|_{a=a^*}\leq\lambda,a^*=0\end{aligned}$

DMC是最简单、最本质的信道：

对任意x，都有$\sum_{y=0}^{J-1}p(y|x)=1$
对任意y，都有$w(y)=\sum_{x=0}^{K-1}q(x)p(y|x)$

设输出x概率分布为$\{x,q(x),x\in\{0,1,...,K-1\}\}$，输出分布为$\{y,w(y),y\in\{0,1,...,J-1\}\}$，转移矩阵为$P=[p(y|x),x\in\{0,1,...,K-1\},y\in\{0,1,...,J-1\}]$

$[w(0),w(1),...,w(J-1)]=[q(0),q(1),...,q(K-1)]\times P$

\[
    \begin{aligned}
    I(X;Y)
    &=\sum_{x=0}^{K-1}\sum_{y=0}^{J-1}p(x,y)\log\frac{p(y|x)}{w(y)}\\
    &=\sum_{x=0}^{K-1}\sum_{y=0}^{J-1}q(x)p(y|x)\log\frac{p(y|x)}{\sum_{z=0}^{K-1}q(z)p(y|z)}\\
    &=\sum_{x=0}^{K-1}q(x)\sum_{y=0}^{J-1}p(y|x)\log\frac{p(y|x)}{\sum_{z=0}^{K-1}q(z)p(y|z)}\\
    \end{aligned}
    \]

定理【DMC的最佳输入分布】：输入概率分布$\{x,q(x),x\in\{0,1,...,K-1\}\}$是最佳输入分布的充要条件是：对任何满足$q(k)>0$的k，$I(X=k;Y)=\sum_{y=0}^{J-1}p(y|k)\log\frac{p(y|k)}{\sum_{z=0}^{K-1}q(z)p(y|z)}=C$；对任何满足$q(k)=0$的k，$I(X=k;Y)\leq C$

定义【准对称DMC】：如果DMC的转移概率矩阵P的全体可分为若干个列子集，若每个列子集所对应的P的子阵都满足“任一行是第一行的置换”、“任一列是第一列的置换”，则称为准对称DMC信道

如果列子集只有一个，则为对称DMC

结论【DMC】：

如果DMC关于输出对称，则当输入等概分布时，输出也等概分布
准对称DMC关于输入对称，不一定关于输出对称
对称DMC不仅关于输入对称，也关于输出对称
对称DMC当输入分布等概时，输出分布也等概
准对称DMC当输入分布等概时，输出分布局部等概
对称DMC未必有J=K，即输入输出的符号数目不一定相等

定理【准对称DMC的最佳输入分布】：对于准对称DMC，达到信道容量的最佳输入分布为等概分布，$C=\sum_{y=0}^{J-1}p(y|k)\log\frac{p(y|k)}{w(y)}=I(X=k;Y)$

当信道为对称信道时，$C=\log J+\sum_{y=0}^{J-1}p(y|k)\log p(y|k)$

定理【k元对称信道】：（强对称信道/均匀信道）达到信道容量的最佳输入分布为等概分布，$C=H(X=k;Y)=\log K-p\log (K-1)-H(p)$

信道容量是转移概率矩阵任何一行对应的半平均互信息量

定义【模K加性噪声信道】：引入噪声$Z=\{0,1,...,K-1\}$，且$Y=(X+Z)\mod K$

模K加性噪声信道是对称DMC，信道容量为$C=\log K-H(Z)$

* 13 信道组合

13.1 积信道（并联信道）

定义【积信道】：信道1的输入事件为x，共K个；输出事件为y，共J个。信道2的输入事件为u，有N个；输出事件为v，共M个。现有一信道，输入事件为(x,u)，共KN个；输出事件为(y,v)，共JM个，其转移概率矩阵为$[p((y,v)|(x,u))]_{(KN)\times (JM)}$，其中$p((y,v)|(x,u))=p_1(y|x)p_2(v|u)$，则称该信道为信道1与信道2的积信道/独立并联信道。

性质【积信道】：设信道1转移概率矩阵为$[p_1(y|x)]_{K\times J}$，信道容量$C_1$，最佳输入分布$\{x,q_1(x)\}$；信道1转移概率矩阵为$[p_1(y|x)]_{K\times J}$，信道容量$C_1$，最佳输入分布$\{x,q_1(x)\}$。

【最佳输入分布】：$p(x_1x_2,...,x_N)=\prod_{i=1}^N p(x_i)$
【联合平均互信息量】：$I(X;Y)\leq \sum_{i=1}^{N}I(X_i;Y_i)$
【信道容量】：$C=\sum_{i=1}^{N}C_i$

13.2 和信道（合信道）

定义【和信道】：信道1的输入事件为x，共K个；输出事件为y，共J个。信道2的输入事件为u，有N个；输出事件为v，共M个。现有一信道，输入事件为$\{x\}\cup\{u\}$且$\{x\}$与$\{u\}$不相交，共K+N个；输出事件为$\{y\}\cup\{v\}$且$\{y\}$与$\{v\}$不相交，共J+M个，其转移概率矩阵为$\begin{bmatrix}p_1(y|x)_{K\times J} &0\\0&p_2(v|u)_{N\times M}\end{bmatrix}_{(K+N)\times (J+M)}$，则称该信道为信道1与信道2的和信道/合信道。

性质【和信道】：

【信道容量】：$C=\log(2^{C_1}+2^{C_2})$
【最佳输入分布】：$\{x,\frac{2^{C_1}}{2^{C_1}+2^{C_2}}q_1(x)\}$，$\{u,\frac{2^{C_2}}{2^{C_1}+2^{C_2}}q_2(u)\}$

13.3 级联信道（串联信道）

定义【级联信道】：将信道1的输出作为信道2的输入，信道1的输入作为组合信道的输入集，信道2的输出就是组和信道的输出集，这样的信道称为级联信道/串联信道

性质【级联信道】：

【一般级联信道】：$I(X,Y;Z)\geq I(Y;Z)$，$I(X,Y;Z)\geq I(X;Z)$
- 第1个不等式等号成立条件：当且仅当XYZ构成马尔可夫链
【具有马尔可夫性的级联信道】：$p(z|xy)=p(z|y)$，$p(z|x)=\sum_{y}p(y|x)p(z|xy)$
- 转移概率矩阵为$[p(z|x)]_{r\times m}=[p(y|x)]_{r \times s}[p(z|y)]_{s\times m}$
- $\begin{cases}I(X;Z)\leq I(X;Y)\\I(X;Z)\leq I(Y;Z)\end{cases}$，等号成立条件分别为$\begin{cases}p(x|z)=p(x|y)\\p(z|x)=p(z|y)\end{cases}$
【信道容量】：$C\leq \min\{C_1,C_2\}$

14 译码规则与联合AEP

14.1 译码规则

信道编码的作用：从信道输入符号集合X中选出M个作为信源输出的M个消息序列的码字，使得编码后信道输出符号集S'与输入符号集S的差错尽可能小。

定义【译码规则】：设信道输入符号集为$X=\{x_1,x_2,...,x_r\}$，输出符号集为$Y=\{y_1,y_2,...,y_s\}$，若对每一个输出符号$y_j$都有一个确定的函数$\Delta(y_i)$，使$y_i$对应于唯一的一个输入符号$x_i$，则成这样的一族函数为译码规则，即$\Delta:Y\to X,\Delta(y_i)=x_i$

对于r输入、s输出的信道而言，按上述定义得到的译码规则共有$r^s$种

定义【译码错误概率】：确定译码规则$\Delta(y_I)=x_i$后，若信道输出端接收符号$y_j$，则译成$x_i$：

如果发送端发送的是$x_i$，则译码正确，正确的概率为$p[\Delta(y_j)|y_j]=p(x_i|y_j)$
如果发送端发送的是$x_k，i\neq k$，则译码错误，译码错误的概率$p_E(y_j)=1-p[\Delta(y_j)|y_j]=1-p(x_i|y_j)$

译码规则不同，译码错误概率也不同。

定义【平均译码错误概率】：给定译码错误规则$\Delta(y_j)=x^*$后，信道输出端接收到某个特定符号$y_j$的译码错误概率$p_E=1-p(x^*|y_j)$，信道接收端收到一个符号的平均译码错误概率$p_E=\sum_{j=1}^{s}p(y_j)p_E(y_j)=\sum_{x(x\neq x*)}\sum_{y}p(x,y)$

译码规则的矩阵表示：

【联合概率矩阵】矩阵中所有元素之和为1，红色表示译码规则对应关系
【传递概率矩阵】矩阵中所有元素之和为r，红色表示译码规则对应关系

定义【最佳译码规则】：平均译码错误概率最小

定理【最大后验概率准则】：对于收到的符号$y_j$，选择译码规则$\Delta(y_j)=x^*$，使之满足条件$p(x^*|y_j)\geq p(x_i|y_j)$

也称为理想观测者准则
所有译码规则中，最大后验概率准则的$p_E$最小

定理【极大似然译码准则】：对于收到的符号$y_j$，选择译码规则$\Delta(y_j)=x^*$，使之满足条件$p(y_j|x^*)p(x^*)\geq p(y_j|x_i)p(x_i)$

极大似然译码准则与最大后验概率等价
输入等概时，极大似然译码准则变为$p(y_j|x^*)\geq p(y_j|x_i)$，平均译码错误概率为$p_E=\frac{1}{r}\sum_{x(x\neq x^*)}\sum_{y}p(y|x)$

定理【Fano不等式】：译码错误概率$p_E$与信道疑义度$H(X|Y)$之间满足关系：$H(X|Y)\leq H(p_E)+p_E\log(r-1)$

$H(p_E)$：接收到Y后判断是否发生错误的不确定性
$p_E\log(r-1)$：当判断是错误的，错误概率为$p_E$，确定由r-1个符号种哪一个引起错误的不确定性

14.2 编码方法和错误概率

影响平均译码错误概率的因素：

译码规则
信道统计特性

改变信道传递概率减少$p_E$：

物理上更换信道
数学上信道编码

定义【信息传输率】：$R=\frac{\log M}{n}$，M为信源输出消息序列个数，n为信道编码码字长度

定义【n次重复编码】：随着重复编码次数n增大，$p_E$下降，但是R也减少；随着M的增大，R增大，但是$p_E$也增大。

定义【(5,2)线性码】：对于$a_i=a_{i_1}a_{i_2}a_{i_3}a_{i_4}a_{i_5}$，$\begin{cases}a_{i_1}a_{i_2}=\{00,01,10,11\}\\a_{i_3}=a_{i_1}\bigoplus a_{i_2}\\a_{i_4}=a_{i_1}\\a_{i_5}=a_{i_1}\bigoplus a_{i_2}\end{cases}$

M=4，n=5
采用极大似然译码规则，正确译码概率为$\bar {p_E}=\bar p^5+5\bar p^4p+2\bar p^3p^2$

只要码率小于信道的信道容量，则存在错误概率任意小的信道编码。

14.3 联合典型序列与联合AEP

联合典型序列是典型序列在涉及两个随机序列是的自然扩展，是信道编码的基础

信源序列的渐进均分性质是弱大数定列车在信息论中的应用

$A_\varepsilon^{(n)}$称为典型集，$A_\varepsilon^{(n)}$中的序列称为$\varepsilon-$典型序列
典型集的概率近似为1，典型集中所有元素几乎是等可能的，典型集的元素个数近似等于$2^{nH}$

定义【联合典型序列】：设$x=(x_1,x_2,...,x_n)\in X^n$，$y=(y_1,y_2,...,y_n)\in Y^n$。x为典型序列，即对任意小的正数$\varepsilon$，存在n使得$|-\frac{1}{n}\log p(x)-H(X)|<\varepsilon$。y为典型序列，即对任意小的正数$\varepsilon$，存在n使得$|-\frac{1}{n}\log p(y)-H(Y)|<\varepsilon$。xy是典型序列，即对任意小的正数$\varepsilon$，存在n使得$|-\frac{1}{n}\log p(x,y)-H(X,Y)|<\varepsilon$

$A_\varepsilon^{(n)}=\{(x^n,y^n)\in X^n\times Y^n:\\|-\frac{1}{n}\log p(x^n)-H(X)|<\varepsilon\\|-\frac{1}{n}\log p(y^n)-H(Y)|<\varepsilon\\|-\frac{1}{n}\log p(x^n,y^n)-H(X,Y)|<\varepsilon\}$

定义【联合AEP】：设$(x^n,y^n)$是服从$p(x^n,y^n)=\prod_{i=1}^{n}p(x_i,y_i)$的独立同分布的n长序列，则：

当$n\to \infty$时，$Pr[(x^n,y^n)\in A_\varepsilon^{(n)}]\to 1$
$|A_\varepsilon^{(n)}|\leq 2^{n(H(X)+\varepsilon)}$
如果$(\widetilde X^n,\widetilde Y^n)\sim p(x^n)p(y^n)$，即$\widetilde X^n$与$\widetilde Y^n$独立且与$p(x^n,y^n)$有相同边缘分布，则：$Pr[(\widetilde X^n,\widetilde Y^n)\in A_\varepsilon^{(n)}]\leq 2^{-n(I(X;Y)-3\varepsilon)}$，并且对于充分大的n，有$Pr[(\widetilde X^n,\widetilde Y^n)\in A_\varepsilon^{(n)}]\geq (1-\varepsilon)2^{-n(I(X;Y)+3\varepsilon)}$

性质：

联合分布中，大约有$2^{nH(X)}$个典型X序列和$2^{nH(Y)}$个典型Y序列。组合有$2^{n(H(X)+H(Y))}$种，但是联合典型只有$2^{nH(X,Y)}$个。随机选择出现联合典型序列的概率为$2^{-nI(X;Y)}$

15 信道编码定理

定义【信道包含的要素】：对于信道$\{X,p(y|x),Y\}$的信道编码包含以下要素：

输入符号集合$\{1,2,...,M\}$
编码函数$f:\{1,2,...,M\}\to X^n$。该函数为每一个输入符号产生了相应的信道编码码字，这些码字构成的集合称为码簿
解码函数$g:Y^n\to \{1,2,...,M\}$，该函数为一个确定性判决函数，将每一个可能的接收向量映射到一个输入符号
这样的信道编码称为(M,n)码

定义【条件错误概率】：输入符号为$\omega$时的条件错误概率为$\lambda_\omega=\sum_{y\in Y^n;g(y)\neq \omega}Pr\{Y^{(n)}=y|X^{(n)}=f(\omega)\}$

定义【最大错误概率】：(M,n)码最大错误概率为$\lambda^{(n)}=\max_{\omega\in \{1,2,...,M\}}\lambda_\omega$

定义【算术平均错误概率】：$P_e^{(n)}=\frac{1}{M}\sum_{i=1}^M \lambda_i$

若输入等概，则算术平均错误概率等于译码错误概率；算术平均错误概率小于等于最大错误概率

定义【码率】：$R=\frac{\log M}{n}$比特/传输

信道码的每个码字母所能携带的最大信息量
$(2^{nR},n)$

定义【】：一个信道的容量是该信道上所有可达码率的上确界，即$C=\sup R$

小于信道容量的码率能够获得任意小的差错概率

定理【信道编码定理】：对于离散无记忆信道，小于其容量C的所有码率是可达的，即对于任意$R<C$，可以找到一个信道编码方案$(2^{nR},n)$，使得最大错误概率$\lambda^{(n)}\to0$。反之，对于任意编码方案$(2^{nR},n)$，若$\lambda^{(n)}\to0$，则必有$R\leq C$

16 汉明码与线性码

* 16.1 Hamming与汉明码

16.2 汉明码

汉明码的构造：

考虑长度为n=7的二进制信道编码，构造以下矩阵：$H=\begin{bmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{bmatrix}$
- 矩阵的秩为3，因此其零空间是4维的，其所有$2^4$个向量为: $$ \begin{bmatrix} 0000000&0100101&1000011&1100110\ 0001111&0101010&1001100&1101001\ 0010110&0110011&1010101&1110000\ 0011001&0111100&1011010&1111111 \end{bmatrix} $$
- 假设码字为$(x_1,x_2,x_3,x_4,r_1,r_2,r_3)$，则有$\begin{cases}x_4+r_1+r_2+r_3=0\\x_2+x_3+r_1+r_2=0\\x_1+x_3+r_1+r_3=0\end{cases}$，从而得到$\begin{cases}r_1=x_2+x_3+x_4\\r_2=x_1+x_3+x_4\\r_3=x_1+x_2+x_4\end{cases}$
定义【权重、汉明距离】：二进制序列中1的个数称为权重，两个二进制序列中对应位不相等的个数称为两个序列的汉明距离
定义【奇偶校验矩阵】：H为奇偶校验矩阵=>$\begin{cases}Hc^T=0\\Hr^T=H(c^T+e_i^T)=He_i^T\end{cases}$
- $e_i$为第i位为1，其余位为0的向量，$He_i^T$即为H的第i列向量

汉明码的译码：

将奇偶校验矩阵H根据二进制表示从1到n排列
设由信道接收到消息x，计算$S(x)=xH^T$
- 如果$S(x)=0$，则没有错误发生
- 如果$S(x)\neq0$，则有一个错误发生，$S(x)$即为错误位置的二进制表示，将错误位置改正即可

定义【系统码】：一般地，前k个比特代表消息，后面n-k个比特留作奇偶校验位，这样得到的码称为系统码。该码由分组长度n、信息比特数k以及最小距离d三个参数确定

上述汉明码又称[7,4,3]汉明码

二元汉明码的参数：

码长：$n=2^r-1$
校验位个数：r
信息位个数：$k=n-r=2^r-1-r$
码字最小距离：3
纠错能力：1

结论【汉明距离】：

$d_H(u,u)=0$
$d_H(u,v)=d_H(v,u)$
$d_H(u,v)\leq d_H(u,w)+d_H(v,w)$