信息论与编码

狭义信息论是一门应用数理统计方法来研究信息处理和信息传递的科学。它研究存在于通讯和控制系统中普遍存在着的信息传递的共同规律，以及如何提高各信息传输系统的有效性和可靠性的一门通讯理论。
一般信息论主要是研究通讯问题，但还包括噪声理论、信号滤波与预测、调制与信息处理等问题。
广义信息论不仅包括狭义信息论和一般信息论的问题，而且还包括所有与信息有关的领域，如心理学、语言学、神经心理学、语义学等。
信源：产生消息的来源- 信宿：消息传送的终点- 信道：信号传输的媒介
信号：消息的载体
消息：信息的载体（具有不确定性）
信息：信息的内涵，即消息中包含的有意义的内容
通信系统的目的：消除或部分消除不确定性，从而获得信息
信源编码：压缩信源冗余度，提高信息传输效率，提高通信系统的有效性
信道编码：增加冗余，提高了纠错检错能力，提高通信系统的可靠性
信息的度量：概率空间，先验概率，自信息，互信息等。 ${I \left( x\mathop{{}}\nolimits_{{i}} \left) \triangleq -log\;p \left( x\mathop{{}}\nolimits_{{i}} \right) \right. \right. }$
自信息：该事件发生的概率对数负值
$I(x_i;y_j) =I(x_i)-I(x_i|y_j)\qquad(I=1,2...n;j=1,2...m) \\ = \log \;\frac{p(x_i|y_j)}{p(x_i)}$
互信息：表示 $y_j$ 出现前后关于事件 $x_i$ 的不确定性减少的量；事件 $y_j$ 出现以后信宿获得的关于事件 $x_i$ 的信息量。
- 性质：互信息的对称性；互信息可为正值、负值、或为0；任何两个事件之间的互信息不可能大于其中任一事件的自信息。
平均自信息：（信息熵、信源熵、香农熵、无条件熵、熵函数、熵），单位：比特/符号。
$H(X) \triangleq E[I(x _i)]=- \sum^{n}_{i=1} p(x_i)log\;p(x_i)$
- 含义：（1）通信前，信源符号的平均不确定性。
  （2）通信后，信号平均每个符号提供的信息量。
- 性质：（1）非负性（离散信源熵）
  （2）极值性：离散无记忆源输出n个不同的信息符号，当且仅当各符号出现概率相等时熵最大。
  （3）强可加性： $H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y)$
  推广： $H(X_1X_2...X_N)=H(X_1)+H(X_2|X_1)+H(X_3|X_1X_2)+...H(X_N|X_1X_2...X_{N-1})$
联合熵：随机变量X和Y的联合分布为 $P(x_i y_j)$ $H(XY)=- \sum^{n}_{i=1}\sum^{m}_{j=1}\;log\;p(x_i y_j)$ \
条件熵:随机变量X和Y的条件熵定义为噪声熵： $H(X|Y)=-\sum_i \sum_j p(x_i y_j)log\;p(x_i|y_j)$
损失熵： $H(Y|X)=-\sum_i \sum_j p(x_i y_j)log\;p(y_j|x_i)$
条件熵表示已知一个随机变量，对另一个随机变量的平均不确定性。
平均互信息
$I(X;Y)=H(X)-H(X|Y) \\ =H(Y)-H(Y|X) \\ =H(X)+H(Y)-H(XY)$

\tiny 随机序列=\left\{ \begin{aligned} 非平稳信源\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\平稳信源\left\{ \begin{aligned}连续平稳信源\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\离散平稳信源\qquad\left\{ \begin{aligned} 离散无记忆信源\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\离散有记忆信源\qquad\left\{ \begin{aligned} 记忆长度无限长\qquad\qquad\qquad\qquad\\记忆长度有点长（马尔可夫信源）\qquad\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.

平稳信源：各维度联合概率分布与时间起点无关。
信源无记忆：前后符号间独立。
平均符号熵：
$H_N(X)=\frac{1}{N}(X_1X_2...X_N)$
N趋于无穷时： $H_\infty=\lim\limits_{x\rightarrow\infty}H_N(X)$ （极限熵）
扩展信源：把信源输出N长符号序列看成是一个新信源，即N次扩展信源。离散平稳无记忆信源的N次扩展信源的熵等于离散单符号信源熵的N倍：
$H ( X ) = H ( X ^ { N } ) = N H ( X )$
离散平稳无记忆信源的熵率
$H _ { \infty } = \lim \limits_ { N \rightarrow \infty } H _ { N } ( X ) \\= \lim\limits _ { N \rightarrow \infty } \frac { 1 } { N } \cdot N H ( X ) \\= H ( X )$
离散平稳有记忆信源：设信源输出N长的符号序列，用N维随机矢量 $X = X _ { 1 } X _ { 2 } \cdots X _ { n }$ 来表示信源
N维随机矢量的联合熵为：
$H ( X ) = H ( X _ { 1 } X _ { 2 } \cdots X _ { N } )\\= H ( X _ { 1 } ) + H ( X _ { 2 } | X _ { 1 } ) + H ( X _ { 3 } | X _ { 1 } X _ { 2 } ) + \cdots H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N } )$ (熵函数链规则)
- 条件概率阶数：m，记忆长度m+1
- 定理： (1)条件熵 $H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )$ 随N的增加而减小。
  (2)N给定时平均符号熵大于等于条件熵： $H _ { N } ( X ) \geqslant H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )$
  (3)平均符号熵随N的增加是递减的。
  (4)对于离散平稳信源，如果 $H _ { 1 } ( X ) <\infty$ ，则有
  $H _ { \infty } = \lim\limits _ { N \rightarrow \infty } H _ { N } ( x ) \\= \lim\limits _ { N \rightarrow \infty } \frac { 1 } { N } H( X _ { 1 } X _ { 2 } \cdots X _ { N } )\\= \lim\limits _ { N \rightarrow \infty } H ( X_ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )$
M阶马尔可夫信源：信源在某时刻发出的符号仅与在此之前发出的m个符号有关。熵率：
$H _ { \infty } = \lim\limits _ { N \rightarrow \infty } H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )\\= \lim \limits_ { N\rightarrow \infty}H ( X _ { N } | X _ { N - m} X _ { N-m + 1 } \cdot \cdot \cdot X _ { N })\\= H ( X _ { M + 1 }| X _ { 1 } X _ { 2 } \cdots X _ { m } )\\= H _ { m + 1 }$
齐次马尔可夫链 定义：马氏链状态转移概率与起始时刻无关，随机变量状态仅与上一时刻所处状态有关联，与再之前的状态无关联。
状态转移概率：（描述马氏链最重要的参数）
$P _ { i j } ( m , n ) = P \{ { X _ { n } =S _ { j } | X _ { m } = S _ { i } }\}\\= P \{{ X _ { n } = j | X _ { m } = i }\}$
马氏链平稳 (稳态)分布定义：时齐、有限马尔科夫链满足各态历经性，转移步长足够长，最终各状态绝对概率分布达到稳态。
稳态分布存在条件：设P为马氏链的状态转移矩阵，则该马氏链平稳分布存在的充要条件是存在一个正整数N,使矩阵P^N^中的所有元素均大于零。
稳态分布求解：求解前必须验证稳态分布是否存在！若Wj为平稳分布，Wj是满足方程组WP=W和WJ≥0， $\sum_{i=1}^J W_J=1$ 的唯一解。
符号间相关性越大，熵越小。熵的相对率:
$\eta = \frac { H _ { \infty } } { H _ { 0 }}$
信源的剩余度
$\gamma = 1 - \eta = 1 - \frac { H _ { \infty} } { H _ { 0 } } = 1 - \frac { H _ { \infty } } { \log q }$
信道定义：信号的传输媒介，传送信息的物理通道。
- 按输入/输出信号的幅度和时间特性划分：

幅度	时间	信道分类名称
离散	离散	离散信道/数字信道（例如：数字电话）
连续	离散	连续信道
连续	连续	模拟信道/波形信道（例如：模拟电话）
离散	连续	(理论和实用价值均很小)

- 按输入/输出之间的记忆性来划分：无记忆信道：信道在某时刻的输出只与信道该时刻的输入有关而与信道其他时刻的输入、输出无关。有记忆信道：信道在某时刻的输出与其他时刻的输入输出有关。
- 根据信道的输入/输出是否是确定关系可分为：有噪声信道、无噪声信道
- 根据信道的统计特性是否随时间改变可分为：平稳信道（恒参信道、时不变信道）非平稳信道（变参信道、时变信道）
- 根据输入/输出的个数可分为：单用户信道：一个输入一个输出单向通信。多用户信道：双向通信或三个或更多个用户之间相互通信的情况。

$i = 1 , 2 , \cdots , r;j= 1 , 2 , \cdots , s \\ 满足：0 \leqslant p ( y _ { j } | x _ { i } ) \leqslant 1 ( i = 1 , 2 \cdots r ; j = 1 , 2 \cdots s)\\ \sum _ { j = 1 } ^ { s } p ( y _j | x _ { i } ) = 1 ( i = 1 , 2 , \cdots r )$

二元对称信道（BSC：binary symmetric channel) 输出符号集 $A = \{ 0 , 1\}$ ,输出符号集 $B = \{ 0 ,1\}$ ，r=s=2.
传递概率： $p( 0 | 0 ) = \overline { p }\\p(0|1)=p → \begin{bmatrix} \overline { p } & p \\ p & \overline { p } \\ \end{bmatrix} \\ p(1|0)=p\\ p( 1 | 1 ) = \overline { p }$
二元删除信道输入符号集 $A = \{ 0 , 1 \}$ ，符号输出集 $B = \{ 0 , ? ,1\},r=2,s=3$ 信道矩阵为 $p=\begin{bmatrix} p & 1-p & 0 \\ 0 & 1-q & q \\ \end{bmatrix}$
信息传输率R:信道中平均每个符号所传送的信息量。
平均互信息 $I(X;Y)$ :是接收到符号Y后平均获得的关于X的信息量。
信道的信息传输率本质就是平均互信息： $R=I(X;Y)$ (比特/符号)
信道每秒钟平均传输的信息量为：信息传输速率 $R_t$ $R_t=I(X;Y)$ (比特/秒)
最大的信息传输率为信道容量： $C=max_{p(x)}{I(X;Y)}$ (比特/符号) 相应的输入概率分布被称为最佳输入分布。
信道容量性质：
- 与信源的概率分布无关。
- 描述信道特性的参量；
- 信道能够传输的最大信息量。
无噪无损信道：输入、输出之间有确定的一一对应关系 $P ( y _j| x_i ) = \left\{ \begin{aligned} 1 ; y _ { j } = f ( x _ { i } ) \\ 0; y _ { j } \neq f ( x _ { i } ) \end{aligned} \right.\\I ( X ; Y ) = H ( X ) = H ( Y )\\C = max_{p(x)} I ( X ; Y ) = m a x_{p(x)} H ( X ) = \log r$
行对称信道：信道矩阵P中每行都是第一行的排列。
对称信道：信道矩阵中每行都是第一行的排列，每列都是第一列的排
强对称信道：
- 特征：行列对称。信道输入与输出消息（符号）数相等， $r=s$ 。错误分布是均匀的：信道矩阵中正确传输概率都相等，且错误传输概率均匀地分配到 $r-1$ 个符号上

\begin{bmatrix} \overline { p } & \frac { p } { r-1 } &{\cdots}&\frac { p } { r-1 } \\ \frac { p } { r-1 } &\overline { p }&{\cdots}&\frac { p } { r-1 } \\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ \frac { p } { r-1 } &\frac { p } { r-1 } &{\cdots}&\overline { p }\\ \end{bmatrix}

重要引理：对于对称信道，当信道输入概率分布为等概分布时，输出概率分布必为等概分布。此时到达信道容量。 $C = \log s - H ( p _ { 1 }^ { \prime } , p _ { 2 } ^ { \prime } \cdots p _ { s } ^ { \prime } )$ 其中 $p _ { 1 }^ { \prime } , p _ { 2 }^ { \prime } \cdots p _ { s } ^ { \prime }$ 是信道矩阵中的任意一行中的元素。
信源编码目的：使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息。在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。
信源编码作用：以提高通信有效性为目的。通常通过压缩信源的冗余度来实现。码字 $w _ { i } = x _ { i _1} x _ { i_2 } \cdots x _ { i _i}$ 将信源符号集中的符号Si(或者长为N的信源符号序列)映射成由码符号（码元)xi组成的长度为li的一一对应的码符号序列wi
分组码与非分组码：将信源符号集中的每个信源符号 $S _ { i }$ ,固定的映射成某一个码字 $w_ { i }$ ,这样的码称为分组码
奇异码与非奇异码：分组码中所有码字不同，则为非奇异码。
唯一可译码与非唯一可译码：码符号序列被唯一地译为对应的信源符号序列，则称为唯一可译码。
即时码与非即时码：若某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码，则称此码为即时码。

定理：即时码的充要条件：任何一个码字都不是其它码字的前缀。

码=\left\{ \begin{aligned} 非分组码\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\分组码\left\{ \begin{aligned}奇异码\qquad\qquad\qquad\qquad\qquad\qquad\\非奇异码\left\{ \begin{aligned} 非唯一可译码\qquad\qquad\\唯一可译码\left\{ \begin{aligned} 即时码\\非即时码\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.

对于定长码，非奇异码一定是唯一可译码。设信源符号集中共有q个符号， $s =\{s_1,s_2 …s_q\}$ 码符号集中共有r种码元， $x=\{x_1,x_2…x_r\}$ 定长码码长为1，则要满足非奇异性必然有: $q≤r^l$ 如果对N次扩展信源进行S^N^定长编码，要满足非奇异性，须满足条件 $q^N≤r^l$

Kraft定理:即时码存在的充要条件是 $\sum_{i=1}^qr^{-l_i}\leq1$
McMillan定理:唯一可译码存在的充要条件是 $\sum_{i=1}^qr^{-l_i}\leq1$ 说明: 当满足Kraft(或McMillan)不等式时，必然可以构造出即时码(或唯一可译码)，否则不能构造出即时码(或唯一可译码)。该定理不能作为判断一种码是否是即时码(或唯一可译码)的判断依据。
平均码长 $\overline L=\sum_{i=1}^qp(s_i)l_i$ 码符号/信源符号对于给定的信源和码符号集，若有一个唯一可译码，其平均长度小于所有其他唯一可译码，则称这种码为紧致码或最佳码。
平均码长界限定理设离散无记忆信源的熵为H(S)，用r个码符号进行编码，则总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足: $\frac{H(S)}{\log r}\leq \overline L < \frac{H(S)}{\log r}+1$ 平均码长=下限值: $p(s_i)=r^{-l_i}\;(i= 1,2...q)$ 结论:变长编码过程中，大概率消息用较短的码字表示，小概率消息用较长的码字表示，通过概率匹配可降低平均码长。
香农第一定律设离散无记忆信源的熵为H(S)，它的N次扩展信源为S^N^，对扩展信源S^N^进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足 $\frac{H(S)}{\log r}\leq \frac{\overline L_N}{N} < \frac{H(S)}{\log r}+\frac1N$ 当 $N→\infty$ 时，有 $\lim\limits_{ N \rightarrow \infty }\frac{\overline L_N}{N}=H_r(S)$ 信息传输率(码率): $R=H(X)=\frac{H(S)}{\overline L}\;\;\;\;\overline L=\frac{\overline L_N}{N}$
编码效率： $\eta =\frac{R}{\log r}=\frac{H(S)/\overline L}{\log r}$ 平均码长压缩下限与信源熵有关。
费诺码
- 编码步骤如下: 将概率按从大到小的顺序排列，令 $p(s_1) ≥ p(s_2) ≥ ... ≥p(s_q)$ 将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。给每一组分配一位码元“0”或“1”。将每一分组再按同样方法划分，重复步骤2和3，直至概率不再可分为止费诺码比较适合分组概率相等或者接近的信源编码
Huffman码
- 编码步骤: 将信源符号按概率从大到小的顺序排列，令 $p(s_1) ≥ p(s_2) ≥ …. ≥p(s_q)$ 将概率最小的信源符号S~~n-1~~和Sn合并成一个新符号并分配一个码元“0”和“1”，用两个最小的概率之和作为新符号的概率，得到一个只包含(n一1)个信源符号的新信源。将缩减信源概率从大到小顺序排列，重复步骤2，得到只含(n一2)个符号的缩减信源。重复步骤，直至信源只剩两个符号，从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
- 二元Huffman编码特点: 码长与概率是相匹配的是紧致码、最佳码，平均码长最短，编码效率高。平均码长未必打到编码定理的下界。(条件: $P_i=2^{-l_i}$ ) 霍夫曼码需要信源统计特性才能编码。需要进行差错检测(会降低信息传输有效性)。
信道编码概述
- 目标: 提高通信的可靠性:信道传输错误率最低，信息传输率最高。错误概率与信道统计特性、译码规则有关。
- 方法: 按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列。信道译码，就是按与信道编码器相同的数学规律去掉接收到的码符号序列中的冗余符号。
- 存在问题: 增加的冗余符号越多，检错和纠错能力就越强。但是，增加的冗余符号越多，传输效率就越低。
两种重要的译码规则
- 最大后验概率(最小错误概率、最优)译码规则(MAP):步骤: (转移概率矩阵每行乘以P(x)得到联合概率分布矩阵; 每列矩阵最大概率对应的输入概率X作为译码规则。所有译码结果对应联合概率之和为正确概率，矩阵其余元素之和为错误概率。
- 极大似然译码规则(ML)步骤: 以转移概率矩阵每列中最大的元素对应的xi作为译码规则。所有译码规则对应转移概率之和乘以一作为正确概率。

说明:当输入符号等概分布时，采用极大似然译码准则等价于最大后验概率准则，平均译码错误概率最小。

汉明距离 概念: 设 $X_i=x_{i1}x_{i2}…x_{in}$ 和 $Y_j=y_{j1}y_{j2}…y_{jn}$ 表示两个长度为n的码符号序列，定义: $D(x_i,y_j)=\sum_{k=1}^n x_{ik} \bigoplus y_{jk}$ 称D(xi,yj)为码字xi和yj之间的汉明距离。(两序列符号相异的个数)
- 最小汉明距离译码准则: 最小码距D~~min~~越大，则平均错误概率PE越小，在选择编码规则时，应使码字之间的距离D~~min~~越大越好，这样的准则即为最小距离译码准则编码可纠正u个以内错误充要条件: $D_{min}=2u+1$ 编码可检测t个以内错误充要条件: $D_{min}=t+1$
香农第二定理
- 内容:对于离散无记忆平稳信源。信道容量为c若编码速率R<C若码长足够大，至少存在一种编码使得译码错误概率任意小，反之，若编码速率R>C，则码长无论多长，也找不到使得译码错误概率任意小的编码。
- 说明: 高可靠性:译码错误概率任意小。高效率:信息传输速率接近信道容量。存在这中编码必要条件R<C
- 与香农第一定理的对比: 信源编码部分介绍香农第一定理:实现无失真信源编码时平均码长压缩下限为信源熵。信道编码部分介绍香农第二定理:实现高可靠性信道编码的信息率极限是信道容量。