b10c...eb5d

也许是比特币网络上最酷的一笔交易

信息论与编码

引论

信息论的基本概念

• 信息论：一门应用概率论和数理统计的方法研究概率信息的传输、存储和处理的学科

graph LR
A[信源]-->|消息|B[编码器]
B-->|信号|C[信道]
C-->|信号|D[译码器]
D-->|消息|E[信宿]
F[干扰源]-->|干扰|C

• 信息

  • 通俗的信息：信息是一种消息

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

  • 概率信息：又称香农信息、狭义信息，从事件的不确定性和概率测度出发定义信息

• 信息、消息和信号

  • 信息：抽象，包含在消息中
  • 消息：具体，但不是物理的，可以包含多个信息
    • 构成条件：能被通信双方理解；可以传递
  • 信号：消息的载荷者

信源编码：唯一可译码

信源的数学模型

• （离散）信源：信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列 $X_1,X_2,X_3,\dots$

  • 假设每个 $X_n$ 都是一个取值在有限集合 $S=\{s_1,s_2,s_3,\dots\}$ 上的离散型随机变量

    • $S$ 称为信源字母表

  • 实际中认为信源序列有限，但是出于理论证明的目的，也会考虑无限长序列

  • 分类

    • 离散无记忆信源：随机变量 $X_1,X_2,X_3,\dots$ 彼此统计独立
    • 离散无记忆简单信源（教程主要信源）：随机变量 $X_1,X_2,X_3,\dots$ 具有相同的概率分布

信源编码

• r-元编码

  • 假设每个 $X_n$ 都是一个取值在信源字母表 $S=\{s_1,s_2,s_3,\dots,s_q\}$ 上的离散型随机变量
  • 设有一个含 $r$ 字母的字母表 $T=\{t_1,t_2,t_3,\dots\,t_r\}$， 对于 $(X_1,X_2,X_3,\dots)$ 的每一个事件，都用一个字母串来表示，这种表示方法称为 r-元编码；
  • e.g：r=2，ASCII；r=3，Morse code

• 字：$T$ 中的一个字 $w$ 是由 $T$ 中字母组成的有限序列，字的长度即为序列中字母的个数

  • $T^n=T\times T\times T\times \dots\times T$：长度为 $n$ 的字的集合
  • $\varepsilon$：长度为 0 的空字
  • $T^*=\bigcup_{n\ge0}T^n$：所有字（包括空字）的集合
  • $T^+=\bigcup_{n> 0}T^n$：所有非空字的集合

• 信源编码：$C:S\rightarrow T^+$，简记 $C=\{\omega_1,\omega_2,\dots,\omega_q\}$

• 信源序列编码：$C^*:S^*\rightarrow T^*$，简记 $C^*=\{\omega_{i1},\omega_{i2},\dots,\omega_{in}\in T^*|\omega_{ij}\in C,n\ge0\}$

• 平均码字长度：设信源随机变量 $X$ 的概率分布为 $\{a_k,p(a_k),k=1,\cdots ,K\}$ ，事件 $a_k$ 对应的码字长度为 $l_k$，则平均码字长度为 $L(C)=\sum^K_{k=1}p(a_k)l_k=\sum^K_{k=1}p_kl_k$

  • 信源编码的主要目的在于易于实现和码字的平均长度最短

• 唯一可译性：对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列

唯一可译码

• 定义

• $C: S^*\rightarrow T^*$ 是唯一可译码，若对 $\forall t \in T^*$，至多存在一个 $s \in S^*$ 与之对应。换言之，$C:S^*\rightarrow T^*$ 是一对一的。

• 性质

  • $C: S^*\rightarrow T^*$ 是唯一可译码，若有 $u_1\cdots u_m=v_1\cdots v_n$，其中 $u_i,v_j\in C$，则有 $m=n$，且 $u_i=v_i$
    • 即：每个码字序列可以被唯一分解

• 定理

• 若 $C$ 中的每个码字具有相同的长度，则 $C$ 是一个唯一可译码

• 证明

  • 定义 $C_{0} C_{1},\cdots,$ 为非空字集合 （即 $C_{n} \subseteq T^{+}$）；

    特别地 $,$ 定义 $C_{0}=C,$ 且 $C_{n}=\left\{\omega \in T^{*} \mid u \omega=v,\right.$ 其中 $u \in C, v \in C_{n-1}$ 或 $\left.u \in C_{n-1}, v \in C\right\}, n \geq 1$

    $C_{\infty}=\bigcup_{n=1}^{\infty} C_{n} \quad \quad \quad C_{1}=\left\{\omega \in T^{+} \mid u \omega=v,\right.$ 其中 $\left.u v \in C\right\}$

  • 一个码C为唯一可译码的充分必要条件是 C\cap C_\infin=\O

即时码

• 延时译码：等到序列全部接收完毕后才能开始译码

• 即时码：若对每个码字序列 $w_{i_{1}}, w_{i_{2},} \cdots w_{i_{n}}$，每个以 $w_{i_{1}}, w_{i_{2},} \cdots w_{i_{n}}$ 开头的码字序列 $t$ 都
  唯一地被译为 $s=s_{i_1}s_{i_2} ⋯ s_{i_n} ⋯$，无论 $t$ 中后续字母是什么。该码称为即时码。

• 前缀码：若每个码字 $w_i$ 都不是其他码字 $w_j$ ,的前缀，即 $w_{j} \neq w_{i} w, w \epsilon T^{*},$ 等价地， $C_{1}=\emptyset$

• 一个码 $C$ 为即时码的充分必要条件是 $C$ 为前缀码

唯一可译性的两种解决方法

• 逗点码
  1. 事件与码字一一对应；
  2. 每个码字的开头部分都是一个相同的字母串；
  3. 这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现
     在两个码字的结合部。
• 即时码
  1. 事件与码字一一对应；
  2. 每个码字都不是另一个码字的开头部分（字头）

信源编码的分类

graph TD
A(码)-->B1(奇异码)
A-->B2(非奇异码)
 B2-->C2(非唯一可译码)
 B2-->C1(唯一可译码)
  C1-->D1(等长码)
     C1-->D2(变长码)
   D2-->E1(前缀码)
   D2-->E2(逗点码)

即时码的构造

码树

1. 一个码 $C$ 可以看做是树 $T^*$ 中一些顶点的有限集合
2. 一个码字 $w_{\mathrm{i}}$ 是 $w_{\mathrm{j}}$ 的前缀当目仅当存在一条从 $w_{\mathrm{i}}$ 到 $w_{\mathrm{j}}$ 的向上的路( $w_{\mathrm{i}}$ 被 $w_{\mathrm{j}}$ 支配 $)$
3. 一个码 $C$ 是即时码当目仅当对每个码字 $w_{\mathrm{i}}$ 都不受其他码字 $w_{j}(i \neq j )$ 支配

Kraft 不等式

• 定理 : 设信源消息集合为 $S=\left\{s_{1}, s_{2}, \ldots, s_{q}\right\},$ 信道基本符号的种类为 $r,$ 码字集合为 $C=\left\{w_{1}, w_{2}, \ldots, w_{q}\right\},$ 对应的码长集合为 $b=\left\{l_{1}, l_{2}, \ldots, l_{q}\right\},$ 则存在即时码的充分必要条件是：$r$ 、 $q$ 和码长 $l_{i}$ 应满足如下不等式

$\sum_{i=1}^{q} r^{-l_{i}} \leq 1$

​ 上式称为 Kraft 不等式

※：Kraft不等式只涉及即时码的存在性问题，可以用来判断一组码不是即时码，而不能判断一组码是即时码

McMillan’s不等式

• 定理：任意唯一可译码的长度必然满足Kraft不等式
  • 说明：从码字长度集合的角来考虑 ，唯一可译码不能提供比即时码更优的选择 。对唯一可译码和即时码而言 ，其码字长度集合的可行条件是一样的
  • 所以目标是：构造平均长度最小的即时码

即时码的最小期望长度问题

• 即时码的最小期望长度问题是一个最优化问题 ：

  在所有整数 $l_{1}, l_{2}, \ldots, l_{q}$ 上，最优化

$L(\mathcal{C})=\sum_{i=1}^{N} p_{i} l_{i}$

​ 其约束条件为 $\sum_{i=1}^{q} r^{-l_{i}} \leq \mathbf{1}$

• 方法：取消对整数的限制 ，利用 Lagrange 乘子法
• 从理论推导可知：最佳码长原则满足：大概率对应短码长，小概率对应长码长

Huffman编码

最优码

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

  • 交换性质：若 $p_j<p_k$，则 $l_j>l_k$

• 对任意信源 𝑆，总存在 $r$ 元最优码 （$r\ge2$）

二元 Huffman 编码

• 原理

  1. 对信源 $S$ 的信源符号 $s_{1}, s_{2}, \cdots, s_{q}$ 重新编号,使其对应的概率满足 $p_{1} \geq p_{2} \geq \cdots \geq p_{q}($ 从大到小的顺序柳列 $)$
  2. 将两个概率最小的信源符号 $s_{q-1}$ 和s $_{q}$ 合并成一个新符号s’，并用这两个最小的概率之和作为新符号 $s'$ 的概率 $p'$，得到一个只包含 $q-1$ 个信源符号的新信源称为原信源的缩减信源，用 $S'$ 表示
  3. 设信源 $S'$ 的二元码为 $C'$，则可构造信源 $S$ 的二元码 $C$

• 算法

  • 进行霍夫曼编码前，我们先创建一个霍夫曼树。
    1. 将每个字符依照出现频率由小排到大，最小在左
    2. 每个字符都代表一个叶节点，比较每个字符的出现频率，将最小的两个字符频率相加合成一个新的节点。将新的节点替代这两个最小字母频率节点加入到叶节点中，再重复上述操作。
  3. 最后产生的树状图就是霍夫曼树。
  • 进行编码
    1. 给霍夫曼树的所有左链接 ‘0’ 与右链接 ‘1’ 。
    2. 从树根至树叶依序记录所有字母的编码。

• Huffman 编码并不唯一，但是平均码长是相同的

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

• 对于特定的最优码，概率方差越大，平均码长通常会变小

二元 Huffman 编码的平均码长

• 将信源 $S$ 缩减为 $S^{(q-1)}$ 时产生的 “新”概率之和 $p'+p''+\cdots+p^{(q-1)}$ 即 为编码 $C$ 的平均码长

二元 Huffman 编码的最优性

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

信息量

非平均互信息量

输入、输出空间定义

• 输入空间 $X=\left\{x_{k}, k=1,2, \ldots, K\right\}$，概率记为 $Q\left(x_{k}\right)$，称为先验概率
• 输出空间Y $=\left\{y_{j}, j=1,2, \ldots, J\right\}$，概率记为 $\Omega\left(y_{j}\right)$
• 联合空间 $\mathrm{XY}=\left\{x_{k} y_{j} ; k=1,2, \ldots, K ; j=1,2, \ldots, J\right\}$，概率为 $P\left(x_{k} y_{j}\right)$

$P\left(x_{k} y_{j}\right)=P\left(x_{k} \mid y_{j}\right) \Omega\left(y_{j}\right)=P\left(y_{j} \mid x_{k}\right) Q\left(x_{k}\right)$

• $P(x_k|y_j)$ 称为后验概率

非平均互信息量认识

• 先验概率越大 ，得到的信息量越小 ，反之信息量越大

• 在一个系统中我们所关心的输入是哪个消息的问题 ，只与事件出现的先验概率和经过观察后事件出现的后验概率有关

• 非平均互信息量：给定一个二维离散型随机变量

  $\left\{(X, Y),\left(x_{k}, y_{j}\right), P\left(x_{k}, y_{j}\right), k=1 \sim K ; j=1 \sim J\right\}$

  因此就给定了两个离散型随机变量 $\left\{X, x_{k}, Q_{k}, k=1 \sim K\right\}$ 和 $\left\{Y, y_{j}, \Omega_{j}, j=1 \sim J\right\}$
  事件 $x_{k} \in X$ 与事件 $y_{j} \in Y$ 的互信息量定义为 $I\left(x_{k} ; y_{j}\right)$

$\begin{aligned} I\left(x_{k} ; y_{j}\right) &=\log _{a} \frac{P\left(x_{k} \mid y_{j}\right)}{Q\left(x_{k}\right)} \\ &=\log _{a} \frac{P\left(y_{j} \mid x_{k}\right)}{\Omega\left(y_{j}\right)}=I\left(y_{j} ; x_{k}\right) \end{aligned}$

• 其中底数a是大于1的常数，常用a=2或a=e

  • 当 a=2 时互信息量的单位，为 bit
  • 当 a=e 时互信息量的单位，为 nat

• 另一种理解：

  $I\left(x_{i} ; y_{j}\right)=$ [收到 $y_{j}$ 前 $,$ 收信者对信源发 $x_{i}$ 的不确定性]$-$[收到 $y_{j}$ 后，收信者对信源发 $x_{i}$ 仍然存在的不确定性]$=$ 收信者收到 $y_{j}$ 前后，收信者对信源发 $x_{i}$ 的不确定性的消除

• 当事件 $y_{j}$ 的出现有助于肯定事件 $x_{k}$ 的出现，即

  $P\left(x_{k} \mid y_{j}\right)>Q\left(x_{k}\right), \text { 则 } I\left(x_{k} ; y_{j}\right)>0$

  当事件 $y_{j}$ 的出现告诉我们事件 $x_{k}$ 的出现可能性减少 , 即

  $P\left(x_{k} \mid y_{j}\right)<Q\left(x_{k}\right), \text { 则 } I\left(x_{k} ; y_{j}\right)<0$

• 三个事件集的条件互信息定义为
  $I\left(u_{1} ; u_{2} \mid u_{3}\right)=\log \frac{p\left(u_{1} \mid u_{2}, u_{3}\right)}{p\left(u_{1} \mid u_{3}\right)}=\log \frac{p\left(u_{1}, u_{2} \mid u_{3}\right)}{p\left(u_{1} \mid u_{3}\right) p\left(u_{2} \mid u_{3}\right)}$​

• $\left(u_2, u_{3}\right)$ 联合给出的关于 $u_{1}$ 的信息量等于 $u_{2}$ 给出的关于 $u_{1}$ 的信息量与 $u_{2}$ 已知条件下 $u_{3}$ 给出的关于 $u_{1}$ 的信息量之和。$\begin{aligned} I\left(u_{1} ; u_{2}, u_{3}\right) &=I\left(u_{1} ; u_{2}\right)+I\left(u_{1} ; u_{3} \mid u_{2}\right) \\ &=I\left(u_{1} ; u_{3}\right)+I\left(u_{1} ; u_{2} \mid u_{3}\right) \end{aligned}$

非平均自信息量

• 给定一个离散型随机变量 $\left\{X, x_{k}, Q_{k}, k=1 \sim K\right\}$
  事件 $x_{k} \in X$ 的自信息量定义为

  $I\left(x_{k}\right)=\log _{a} \frac{1}{Q_{k}}$

  其中底数 $a$ 是大于 1 的常数。

• 非平均自信息量的性质：

  1. 非负性：$I\left(x_{k}\right) \geq 0$
  2. 单调性： $Q _k$ 越小，$I (x_k)$ 越大
  3. $I\left(x_{k} ; y_{j}\right) \leq \min \left\{I\left(x_{k}\right), I\left(y_{j}\right)\right\}$，即互信息量不超过各自的自信息量。

• 非平均自信息量 $I\left(x_{i}\right)$ 的物理意义

  • 当事件 $x_{i}$ 发生前，表示该事件发生的不确定性
  • 当事件 $x_{i}$ 发生后 , 表示该事件所提供的信息量

条件的非平均自信息量

• 在事件 $y_{j}$ 发生的条件下事件 $x_{k}$ 的条件自信息量定义

$\begin{aligned} I\left(x_{k} \mid y_{j}\right) &=\log _{a} \frac{1}{P\left(x=x_{k} \mid Y=y_{j}\right)} \\ &=\log _{a} \frac{\Omega_{j}}{P\left(x_d, y_{j}\right)} \end{aligned}$

• 性质：$I\left(x_k \mid y_j\right)=I\left(x_k\right)-I\left(x_k;y_j\right)$

联合的平均自信息量

• $I\left(x_{k} ,y_{j}\right)=\log _{a} \frac{1}{P\left(x_{k} ,y_{j}\right)}$

• 性质：

  $\begin{aligned} I\left(x_{k}, y_{j}\right) &=I\left(y_{j}\right)+I\left(x_{k} \mid y_{j}\right) \\ &=I\left(x_{k}\right)+I\left(y_{j} \mid x_{k}\right) \\ I\left(x_{k}, y_{j}\right) &=I\left(x_{k}\right)+I\left(y_{j}\right)-I\left(x_{k} ; y_{j}\right) \end{aligned}$

• 联合的非平均自信息量实际上是非平均自信息量的简单推广 ——将 $(X,Y)$ 看成一维变量

熵

离散集的平均自信息量——熵

• 熵：$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$
  • $a>1$
  • 定义 𝟎𝒍𝒐𝒈𝟎=𝟎
  • 信息熵单位与自信息量单位相同：Bit，Nat，Det
  • 表示了 $X$ 中事件出现的平均不确定性

条件熵、联合熵

• 条件熵：$H(X|Y)=-\sum_{k=1}^K\sum_{j=1}^Jp(x_k,y_j)\log{p(x_k|y_k)}$

• 联合熵：$H(X,Y)=-\sum_{k=1}^K\sum_{j=1}^Jp(x_k,y_j)\log{p(x_k,y_k)}$

• 联合熵条件熵的关系

  1. $H(X, Y)=H(X)+H(Y \mid X)=H(Y)+H(X \mid Y)$
  2. 当 $X$ 与 $Y$ 相互独立时，

  $H(Y \mid X)=H(Y), H(X \mid Y)=H(X)$

  ​ 此时也有 $H(X, Y)=H(X)+H(Y)$

相对熵

• 相对熵：两个随机分布之间的距离

  • 两个概率密度函数 $p(x)$ 和 $q(x)$ 之间的相对嫡，或 Kullback-Leibler 距离定义为 :

    $\begin{aligned} D(p \| q) &=\sum_{x \in X} p(x) \log \frac{p(x)}{q(x)} \\ &=E_{p(x)} \log \frac{p(x)}{q(x)} \end{aligned}$

  • 约定：$0\log {\frac{0}{q}=0},p\log {\frac{p}{0}=\infin}$

  • $D(p\|q)\neq D(q\|p)$

• 相对熵的意义：量度当真实分布为 $p$ 而假设分布是 $q$ 时的无效性

• 性质：

  1. 相对熵总是非负的 ( 信息散度不等式 )

  $\begin{aligned} -D(p \| q)=&-\sum_{x \in A} p(x) \log \frac{p(x)}{q(x)}=\sum_{x \in A} p(x) \log \frac{q(x)}{p(x)} \leq \log \sum_{x \in A} p(x) \frac{q(x)}{p(x)} \\ &=\log \sum_{x \in A} q(x) \leq \log \sum_{x \in X} q(x)=\log 1=0 \end{aligned}$

  2. 条件相对熵

  $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)}$

  3. 链式法则
     $D(p(x, y) \| q(x, y))=D(p(x) \| q(x))+D(p(y \mid x) \| q(y \mid x))$

离散集的平均互信息量

• $I(X;Y)=\sum_{XY}P(XY)I(x;y)=I(Y;X)=D(p(x,y)\|p(x)p(y))$

• 性质：

  1. $\begin{aligned} I(X ; Y) &=H(X)-H(X \mid Y)=H(Y)-H(Y \mid X) \\ &=H(X)+H(Y)-H(X, Y) \\ \end{aligned}$
  2. $I(X ; X) =H(X)-H(X \mid X)=H(X)$
  3. $I(x;y)\leq min\left\{H(X),H(Y)\right\}$

• 熵是随机变量不确定度的量度

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

• 链式法则：

  1. 熵：$H\left(X_{1}, X_{2}, \ldots, X_n\right)=\sum_{i=1}^{n} H\left(X_{i} \mid X_{i-1}, \ldots, X_{1}\right)$
  2. 互信息：$I\left(X_{1}, X_{2}, \ldots, X_n;Y\right)=\sum_{i=1}^{n} I\left(X_{i};Y \mid X_{i-1}, \ldots, X_{1}\right)$

熵的宏观理解

• 熵与事件的具体形式无关，仅取决于其概率分布

• 熵必定不小于0

• 如果概率向量中某个分量为 1，说明该事件确定，熵为 0

• 可忽略性：当 $q_{k} \rightarrow 0$ 时 $q_{k} \log _{a}\left(\frac{1}{q_{k}}\right) \rightarrow 0$

• 极值性：$H(x) \leq \log _{a} k$ 当 $q_{1}=q_{2}=\cdots=q_k=1 / k$ 时，才有

$H(X)=\log_{a} K$

信息不等式

信息不等式

• 凸函数：$f(\theta\alpha+(1-\theta)\beta)\leq \theta f(\alpha)$
  • 凸函数的线性组合还是凸函数
  • 函数 $f$ 总是位于任意一条弦下面
  • 凸函数的二阶导数非负（恒正为严格凸函数）
• 概率矢量：矢量的所有分量和为 1
• 基础不等式：$ln x\leq x-1$
• Jensen 不等式
  • 若 $f$ 是凸函数，X为随机变量 , 则 $E[f(X)] \geq f[E(X)]$
  • 若 $f$ 是严格凸的，则不等式严格成立 $;$ 除非 $X$ 是个常数 $,$ 即 $X=E X$ 时等号成立
  • 若 $f$ 是凹函数，则不等式反向
• 信息散度不等式：$D(p\| q)\geq 0$，等号成立当且仅当 $p(x)=q(x)$ 恒成立
• 互信息不等式：$I(X;Y)\geq 0$
  • 所有的 Shannon 信息度量都可以看成 $I(X;Y\mid Z)$ 的特例

相对熵，熵，互信息的凸性

• 最大离散熵定理

  设 $|X|$ 是 $X$ 中的元素数目，则 $H(X) \leq \log |X|$ ，当等概率时等号成立

• 条件降低熵

  $H(X \mid Y) \leq H(X)$，$X$ 与 $Y$ 独立时等号成立

  ※：条件作用使熵减小仅在平均意义下成立，某个特定的 $H(X\mid Y=y)$ 可能比 $H(X)$ 大

• 对数和不等式
  对非负数 $a_{1}, a_{2}, \ldots, a_{n}$ 和 $b_{1}, b_{2}, \ldots, b_{n},$ 有

  $\sum_{i=1}^{n} a_{i} \log \frac{a_{i}}{b_{i}} \geq\left(\sum_{i=1}^{n} a_{i}\right) \log \frac{\sum_{i=1}^{n} a_{i}}{\sum_{i=1}^{n} b_{i}}$

  当且仅当 $\frac{a_{i}}{b_{i}}$ 为常数时等号成立

  • 应用：$D(p \| q)$ 是 $(p, q)$ 的凸函数

• 马尔科夫链：$P(X,Y,Z)=P(X)P(Y\mid X)P(Z|Y)$

• 数据处理不等式：若存在马尔科夫链 $X\rightarrow Y\rightarrow Z$，则 $I(X;Y)\geq I(X;Z)$

• 找不到一个对 $Y$ 进行确定性或随机的处理过程 ，使得 $Y$ 包含 $X$ 的信息量增加

• Fano 不等式

  设已知随机变量 $Y$, 需要估计和 $Y$ 相关的随机变量X的值，Fano不等式将猜测随机变量 $X$ 的错误概率与条件熵 $H(X \mid Y)$ 联系起来

  • $P_{e}=\operatorname{Pr}\{\widehat{X} \neq X\}=0$ 当且仅当 $H(X \mid Y)=0$
  • 不等式：$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\mid Y)-1}{\log |X|}$

• 互信息量的凹凸性

  1. 若 $p(y \mid x)$ 给定 $,$ 则 $I(X ; Y)$ 是关于 $p(x)$ 的凹函数
  2. 若 $p(x)$ 给定 $,$ 则 $I(X ; Y)$ 是关于 $p(y \mid x)$ 的凸函数

渐进均分性

渐进均分性定理

• 弱大数定律：设 $X=\left\{x_{1}, x_{2}, \ldots, x_{n}, \ldots\right\}$ 为相互独立的随机变量序列
  并服从相同的分布，且有有限数学期望 $E X_{i}=a,$ 则 $\frac{1}{n} \sum_{i=0}^{n-1} X_{i}$ 以概 率收敛到 $a$

• 渐进均分性定理 (AEP : Asymptotic Equipartition Property)：
  "几乎所有的事件都等概率出现"
  对无记忆独立同分布信源 $\left\{X_{k}, k \geq 1\right\}$ 有 $-\frac{1}{n} \log p\left(X^{n}\right)$ 依概率收敛到 $H(X)$

• 典型集 $A_{\varepsilon}^{(n)}$：满足 $2^{-n(H(X)+\varepsilon)}\leq p(X^n)\leq2^{-n(H(X)-\varepsilon)}$

• 性质：

  1. 若 $\left(x_{1}, x_{2}, \ldots, x_{n}\right) \in A_{\varepsilon}^{(n)},$ 则

  $H(X)-\varepsilon \leq-\frac{1}{n} \log p\left(x_{1}, x_{2}, \ldots, x_{n}\right) \leq H(X)+\varepsilon$

  2. 当 $n$ 充分大时，$Pr\left\{A_{\varepsilon}^{(n)}\right\}>1-\varepsilon$
  3. $|A_{\varepsilon}^{(n)}|\leq2^{n(H(X))+\varepsilon}$
  4. 当 $n$ 充分大时，$|A_{\varepsilon}^{(n)}|\geq (1-\varepsilon)2^{n(H(X))-\varepsilon}$

AEP 的结果应用：数据压缩

• 编码方案：

  1. 将每个集合中的所有元素按某种顺序 ( 如字典序 ) 进行排列。然后通过给予每个序列一 个下标，就可以表示 $A_{\varepsilon}^{(n)}$ 中的每一个序列。 由于 $A_{\varepsilon}^{(n)}$ 中的序列个数 $\leq 2^{n(H(X)+\varepsilon)},$ 则这些下标不超过 $n(H+\varepsilon)+1$ 比特。在所有的 这些序列前加 0，表示 $A_{\varepsilon}^{(n)}$ 中的每一个序列需要的总长度 $\leq n(H+\varepsilon)+2$ 比特。
  2. 对不属于 $A_{\varepsilon}^{(n)}$ 中的每个序列给出下标，所需的字节数不超过 $n\log|X|+1$ 比特。在这些序列前加 1，就获得了一个关于 $X^{n}$ 中所有序列的编码方案。

• 用 $x^{n}$ 表示序列 $x_{1}, x_{2}, \ldots, x_{n},$ 设 $l\left(x^{n}\right)$ 是对应于 $x^{n}$ 的码字长度。

• 定理: 设 $X^{n}$ 为独立同分布序列且服从 $p(x), \quad \varepsilon>0,$ 则存在一个将 长度为n的序列 $x^{n}$ 映射到二进制串的编码，使得编码是 “one-to-one” 的(因而可逆 )，且当n充分大时，有

$E\left[\frac{1}{n} l\left(X^{n}\right)\right] \leq H(X)+\varepsilon$

• 从平均意义上讲，用 $nH(X)$ 比特就可以表示序列 $X^{n}$

熵界

熵和平均码长

• 熵界：信源 $S$ 的任一 $r$ 元即时码的平均码长必大于等于熵 $H_{r}(X)$, 其中等号成立当且仅当 $p_{i}=r^{-l_{i}}$
  • 解释 : 信源 $s$ 发射的每个符号平均携带 $H_{r}(S)$ 个信息单元 ; 如果要在不丢失任何信息的情况下对 $S$ 进行编码，则码 $C$ 必须是唯一可译码 ; 每个码字符号传达一个信息单元 , 因此平均每个码字必须至少包含 $H_{r}(S)$ 个码字符号，也就是说 $L(C) \geq H_{r}(S)$
• 编码效率：$\eta=\frac{H_{r}(S)}{L(C)}$
• 冗余度： $\bar{\eta}=1-\eta$

几种典型的信源编码

Shannon-Fano 编码

• Shannon-Fano 编码：由 Kraft 不等式，存在的满足码长条件的即时码 $C$
  • 可以估算平均码长（Huffman 不行）
  • $H_r(S)\leq L(C)< 1+H_r(S)$
  • 不知道如何构造

Shannon-Fano-Elias 编码

• 思路：利用累积分布函数来分配码字
  • 设字母集 $X$，假设对 $x\in X$,$p(x)>0$
  • 累积分布函数：$F(x)=\sum_{x\geq a}p(x)$
  • 修正的累计分布函数 $\bar F( x)=\sum_{x\geq a}p(a)+\frac{1}{2}p(x)$
  • 设 $\bar F(x)=0.a_1a_2a_3\dots a_{l(x)}a_{l(x)+1}\dots$
    • 码长 $l(x)=[\log\frac{1}{p(x)}]+1$，用 $[\bar F(x)]_{l(x)}$ 表示小数点后 $l(x)$ 位，则码字为 $[\bar F(x)]_{l(x)}$
    • 平均码长：$\bar L<H(x)+2$，只比最优值多了 2 bit

算术编码方法

• 上述编码都是建立在信源符号于码字一一对应的基础上的，被称为块码，而要对序列进行编码，则需要从整个序列出发，采用递推形式进行编码
• 基本方法：
  • 寻找一个计算 $x^n$ 的概率分布 $p(x^n)$ 和累积分布函数 $F(x^n)$ 的快速算法
  • 利用 Shannon-Fano-Elias 方法进行编码：用 $[F(x^n)-p(x^n),F(x^n)]$ 中的一个二进制数表示 $x^n$ 码字
• 以二元序列为例
  • 编码：$F(x^n)=\sum_{y^n\leq x^n}p(y^n)=\sum_{T \text{子树在} x^n \text{的左侧}} p(T)+p(x^n)$，码长为 $[\log \frac{1}{p(x^n)}]$
  • 译码：从收到的码字计算相应的 $F(x^n)$,从根节点开始比较 $F(x^n) 和 p(0)$
    • 如果 $F(x^n)>p(0)$，则从 0 往下的子树在 $x^n$ 的左边，第一位是 1，反之是 0
    • 如果已经译出 $x_1=0$，则继续比较 $F(x^n)$ 和 $p(00)$，以此类推
• 优点
  • 编码效率高：当序列很长时，$\eta$ 接近 1
  • 需要参数少，编码译码简单，没有哈夫曼那样的大码表
• 实际使用时，如果编码使用的是非真实分布，平均长度会增加 $D(p\|q)$

香农第一定理

信源的扩张

• 扩展信源：$S=\left\{s_1,\dots,s_q\right\}$ 的 n 次扩展信源的消息集合为 $S^n=\left\{s_{1_1},\dots,s_{1_n},s_{q_1},\dots,s_{q_n}\right\}$
  • 可以看作是 n 个 $S$ 的乘积
    • 乘积：对于消息集合 $S,T$，$S\times T=\left\{s_i,t_j\right\}$
    • 如果 $S,T$ 独立，则 $H_r(S,T)=H_r(S)+H_r(T)$
  • 单位消息的平均码长随着信源扩张不断降低

香农第一定理

• Shannon 信源编码定理、可变长无失真信源编码定理：通过对 $n$ 足够大的 $S^n$ 进行编码，总可以找到信源 $S$ 的一个 $r$ 元即时码，其对应 $S$ 的平均码长可以与 $H_r(S)$ 任意接近
• 是一个存在性定理

LZ 编码

• 比 Huffman 编码更高效，比算术编码更快捷的算法

LZ78

• 是一种分段编码算法，编码是将输入信源序列分段：

  • 首先，取一个符号作为第一段
  • 然后继续分段，若有符号与前面符号相同时，就再取紧跟后面的一个符号一起组成一个段，使之与前面的段不同
  • 当字典达到一定大小，再分段就应查看是否与字典中已有符号相同，若有重复就添加符号后查看，直至与字典中短语不同为止

• 分段规则：尽可能取最少个相连的信源符号，并保证各段都不相同

• 设信源符号集 $A=\left\{a_1,a_2,\dots,a_k\right\}$ ，输入信源符号序列为 $u=(u_1,u_2,\dots,u_L)$，其中 $u_i\in A$，编码时 $u$ 按照规则进行分段

• 设分段结果为 $\left\{y_1,y_2\cdots,y_c\right\}$ 构成字典，则 $y_j\in A$ 或有 $y_j=y_ia_r(i<j)$，所以编码码字可以用段号 $i$ 和符号序号 $r$ 组成

  • 仅包含单符号的短语段号为 0，非单字符短语的为除最后一个符号外字典中相同短语的段号

• 编码码字为 $N_j=i*k+r$

  • 段号所需码长 $[\log c]$，符号序号所需码长为 $[\log K]$
  • 总码长 $c([\log c]+[\log K])$，平均码长 $\frac{c([\log c]+[\log K])}{L}$

• 定理：随着输入序列增长，LZ 的编码效率提高，平均码长会逼近信源熵

信道

信道

• 信道：传输信息的媒介

graph TD
A[信源A]--输入端-->B[信道]
B--输出端-->C[信宿B]
D[干扰]-->B

信道分类

根据输入输出时间的时间特性和输入分类

• 离散信道：A 和 B 都是离散事件集合
• 连续信道：A 和 B 都是连续事件集合
• 半连续信道：A 和 B 一个是离散事件集合，一个是连续事件集合
• 时间离散的连续信道：信道的输入和输出是取决于连续集合的序列
• 波形信道：信道输入和输出是随机过程

根据输入和输出个数

• 两端信道：输入输出只有一个事件集合
• 多端信道：输入和输出至少有一段有两个以上的事件集合

根据统计特性

• 恒参信道：信道的统计特性不随时间变化
• 随参信道：信道统计随时间变化

根据记忆特性

• 无记忆信道：输出集仅取决当前输入集
• 有记忆信道：输出集与当前和以前若干个输入集有关

传播路线

• 有线信道
• 无线信道

有无噪声

• 无噪信道：无损信道+确定信道

  • 信道的输入和输出集存在确定的函数关系

    $\begin{cases} p(y_n|x_n)=1 &y_n=f(x_n)\\ \\ p(y_n|x_n)=0 &y_n\neq f(x_n) \end{cases}$

• 有噪信道

有无损

• 无损信道
• 有损信道

离散信道模型

1. 信道输入事件的概率空间为

$\left[\mathbf{A}=\left\{a_{1}, \ldots, a_{r}\right\} \quad \mathbf{P}=\left\{\boldsymbol{p}_{i}=\boldsymbol{p}\left(\boldsymbol{a}=\boldsymbol{a}_{i}\right)\right\}\right]$

2. 信道输出事件的概率空间为

$\left[\mathbf{B}=\left\{\boldsymbol{b}_{1}, \ldots, \boldsymbol{b}_{s}\right\} \quad \mathbf{Q}=\left\{\boldsymbol{q}_{j}=\boldsymbol{p}\left(\boldsymbol{b}=\boldsymbol{b}_{\boldsymbol{j}}\right)\right\}\right]$

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

$\boldsymbol{p}_{i j}=\boldsymbol{p}\left(\boldsymbol{b}=\boldsymbol{b}_{j} \mid \boldsymbol{a}=\boldsymbol{a}_{i}\right)=\boldsymbol{p}\left(\boldsymbol{b}_{\boldsymbol{j}} \mid \boldsymbol{a}_{\boldsymbol{i}}\right)$

离散无记忆信道 DMC

• 若离散信道的转移概率满足

$p(y \mid x)=p\left(y_{1} y_{2} \ldots y_{N} \mid x_{1} x_{2} \ldots x_{N}\right)=\prod_{i=1}^{N} p\left(y_{i} \mid x_{i}\right)$

​ 则称其为离散无记忆信道，记作 $\left[X p\left(y_{i} \mid x_{i}\right) Y\right]$

平稳信道(恒参信道)

• 若 DMC 对于任意给定的 $n$ 和 $m$ 有

$p\left(y_{n}=b_{j} \mid x_{n}=a_{i}\right)=p\left(y_{m}=b_{j} \mid x_{m}=a_{i}\right)$

​ 则称为平稳信道，即信道转移概率不随时间变化

信道矩阵

• 信道矩阵：可以表示信道传递概率
  • 每个元素不小于 0
  • 每行元素和等于 1

几种典型有扰离散信道

二进制对称信道

• BSC
  • $P=\begin{bmatrix}1-\varepsilon &\varepsilon \\\varepsilon&1-\varepsilon \end{bmatrix}$
  • 对称信道：所有行/列都是第一行/列的置换

二进制删除信道（BEC）

• 输出结果除了 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}$

  • 准对称信道：每个子集行元素集合相同

公式和定义

• 先验概率，前向（信道传递）概率，后向（后验）概率，联合概率，输出符号概率

• 信道疑义度：信源收到全部符号 $Y$ 后，对输入符号 $X$ 的平均不确定程度 $H(X|Y)$

• 平均互信息：消除的不确定性

  • 对于给定信道，$I(X;Y)$ 是信源分布 $p(x)$ 的凹函数——至少存在一个信源通过该信道传递时，可以获得最大平均互信息（信道容量）
  • 对于给定信道，$I(X;Y)$ 是信道传递函数 $p(y|x)$ 的凸函数——至少存在一个信道，当信源通过时，获得最小平均互信息（限失真信源压缩-率失真函数）

香农第一定理的推广

• 给定信道输出 $B$ 的知识下，对信道输入 $A$ 的唯一可译码的平均码长下界为 $H(A|B)$

信道容量的定义与计算

• 信道容量：$c\overset{def}{=}\underset{p(x)}{\max}{I(X:Y)}$

  • 表征信道传输信息的最大能力
  • 寻找一个信源分布 $p(x)$

• 特殊的信道

• 有噪打字机

• DMC 的最佳输入分布

  • 输入概率分布 $\{x, q(x), x \in\{0,1, \ldots, K-1\}\}$ 是最佳输入分布的充分必要条件为：
    对任何满足 $q(k)>0$ 的 $k$,

    $I(X=k ; Y)=\sum_{y=0}^{J-1} p(y \mid k) \log \frac{p(y \mid k)}{\sum_{z=0}^{K-1} q(z) p(y \mid z)}=C$

    对任何满足 $q(k)=0$ 的 $k, I(X=k ; Y) \leq C$
    $C$ 恰好就是DMC的信道容量

• 准对称 DMC

  • 当输入分布等概时，输出分布局部等概

  • 达到信道容量的最佳输入分布为等概分布

  • 信道容量
    $C=\sum_{y=0}^{J-1} p(y \mid k) \log \frac{p(y \mid k)}{w(y)}=I(X=k ; Y)$ 对任意 $k \in\{0,1, \ldots, K-1\}$ 都成立

信道组合

积信道（并联信道）

• 两个以上信道并行使用

• 信道容量 $C=C_1+C_2$

• 最佳输入分布

  $\left\{(x,u),q_1(x)q_2(u)\right\}$

和信道（合信道）

• 两个以上信道交替使用

• 信道容量 $C=\log (2^{C_1}+2^{C_2})$

• 最佳输入分布

  $\left\{x, \frac{2^{C_{1}}}{2^{C_{1}}+2^{C_{2}}} q_{1}(x)\right\}$
  $\left\{u, \frac{2^{C_{2}}}{2^{C_{1}}+2^{C_{2}}} q_{2}(u)\right\}$

级联信道（串联信道）

• 两个以上信道串联使用
• 信道容量 $C\leq \max\left\{C_1,C_2\right\}$

译码规则和联合 AEP

译码规则

• 信道容量描述了一个信道单位时间可以传输的最大信息量，但是未保证信息传输的无差错性
• 译码规则：对每一个输出符号 $y_i$ 都有一个确定函数 $\Delta(y_i)$ ，使 $y_i$ 对应唯一的一个输入符号 $x_i$，这样的一族函数，称为译码规则
  • 对于有 $r$ 个输入，$s$ 个输出的信道而言，译码规则有 $r^s$ 种
• 译码错误概率：在确定 $\Delta(y_i)=x_i$ 后，若信道输出端接收到符号 $y_i$，则译为 $x_i$
  • 如果发送端发送的就是 $x_i$，译码正确，正确概率为 $p(x_i|y_i)$
  • 如果发送端发送的不是 $x_i$，译码错误，错误概率为 $1-p(x_i|y_i)$
  • ※：注意是 $y_i$ 下的条件概率，所以往往需要使用贝叶斯公式
• 平均译码错误概率：$P_E=\sum_Yp(y_j)p_E(y_j)$
• 最优译码规则：平均译码错误概率最小的译码规则
• 最大后验概率准则（理想观测者准则）：对于收到的的符号 $y_j$，译码规则 $\Delta(y_j)=x^*$，使之满足条件 $p(x^*|y_j)\geq p(x_i|y_j)\quad(i=1,2,\dots,r)$
  • 所有译码规则中，最大后验概率准则的 $P_E$ 最小
• 极大似然译码准则（大数逻辑译码准则）：对于收到的的符号 $y_j$，译码规则 $\Delta(y_j)=x^*$，使之满足条件 $p(y_j|x^*)p(x^*)\geq p(y_j|x_i)p(x_i)\quad(i=1,2,\dots,r)$
  • 与最大后验概率准则等价，但是更加方便计算

编码方法和错误概率

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

  • 译码规则：数学上通过信道编码改变
  • 信道转移概率：物理上通过更换信道改变

• n 次简单重复编码：从 $n$ 次编码可供选择的 $2^n$ 的码字中，选取 $M$ 个进行传输，输入概率等概率，则

  • 随着 $n$ 增大，平均错误概率下降，信息传输率也减少
  • 随着 $M$ 增大，平均错误概率增大，信息传输率增大

• (5,2) 线性码

  • 特点：适当增加 $M$ 和 $n$，得到较低平均错误概率和较好信息传输率的信道编码
  • 选择海明距离小的译成同一码字

汉明码和线性码

• 信道编码定理仅给出了码的存在性，没有说明如何获得工程上的好码，这是几十年努力的目标：码长尽量短；码字具有规律

汉明码

• 码重：二进制序列中 1 的个数
• 汉明距离：两个二进制序列中对应位不相等的个数
• 二元汉明码 Ham $(r, 2)$ 的译码方式
  1. 根据二进制表示的列向量从 $1$ 到 $n=2^r-1$ 排列得到奇偶校验矩阵 $H$
  2. 设由信道接收到消息 $x,$ 计算 $S(x)=x H^{T}$
  3. 如果 $S(x)=x H^{T}=0$， 则没有错误发生
  4. 否则，则有一个错误发生 $, S(x)$ 即为错误位置的二进制表示，将错误位置 上的值改变即可
• 一般地 : 前 $k$ 个比特代表消息，后面 $n-k$ 个比特留作奇偶校验位，这样得到的码通常称为系统码
  • 码由分组长度 $n,$ 信息比特数 $k$ 以及 最小距离 $d$ 三个参数确定
• 二元汉明码 Ham $(r, 2)$ 的译码参数
  • 码长：$n=2^r-1$
  • 校验位个数：$r$
  • 信息位个数：$k=n-r=2^r-1-r$
  • 最小码字长度：$d=W(C)$
  • 纠错能力：$t=[\frac{t-1}{2}]$

线性码

• 定理： $q$ 元汉明码Ham $(r, q)$ 是 $q$ 元 $(n, n-r, 3)$ 线性码，其中
  $n=\left(q^{r}-1\right) /(q-1)$

• 现考虑 $F$ 上码长为 n 的码，则这种码的码字集合是 $F^{n}$ 的一个子集，注意是 $F$ 上 的 n 维向量空间

  如果码 $C$ 的码字集合构成 $F^{n}$ 的一个线性子空间，设此线性空间维数为 $k,$ 此时将码 $C$ 记作 $(n, k)$ 线代码

• 如果线性码 $C$ 的生成矩阵 $G$ 的标准形式为 $G=\left(I_{k} \mid P\right)$, 则 $C$ 的一个校验矩阵形如 $H=\left(-P^{T} \mid I_{n-k}\right)$

• 线性码的编码方式：设G为 $q$ 元 $(n, k)$ 线性码 $C$ 的生成矩阵 $,$ 如果信源消息 $x$ 为 $F^{k}$ 的一个向量 $,$ 则对 任意 $x \in F^{k},$ 将其编码为 $x G$

• 线性码的译码方式：

  • 列表法：按如下方式构造列表
    1. 表的第1行为 $L$ 中所有码字，且 0 排在第1位 $(0+L)$
    2. 对第 i 行，首先选取不在先前 $i-1$ 行中出现且重量最小的 $v_{i} \in F^{n},$ 令第 i 行 的所有元素为 $v_{i}+L,$ 且其余元素按照第1行中非零码字的排列顺序进行排列，使得每行元素互不相交
    3. 重复以上步骤，直到排完 $F^{n}$ 的所有元素 $,$ 最终该表共有 $\frac{q^{n}}{q^{k}}=q^{n-k}$ 行，称作标准阵 $\left(v_{i}\right.$ 为陪集头 $)$
    4. 设线性码的最小距离为 $d,$ 则令 $t=\left\lfloor\frac{d-1}{2}\right]$ 为码的纠错个数，在重量为 $w t\left(v_{i}\right) \leq t$ 的最后一行后划一条横线作为标记
  • 利用伴随式进行解码
    1. 将列表简化，仅保留两列：陪集头及其伴随式
    2. 设接收到 $v$, 则计算其伴随式 $v H^{T}$ ，在上述伴随式表中寻找伴随式与 $x H^{T}$ 相的陪集头 $v_{i}$
    3. 将v译为 $v-v_{i}$

译码错误概率和不可检错误概率