【通信原理二】第七章信源和信源编码

本文主要是介绍【通信原理二】第七章信源和信源编码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在通原I中，我们知道通信需要信源、信道以及信宿，本章节主要讲述了信源、信息论的基本概念以及信源编码的相关知识。

一、信源

1. 信源的概念及分类

信源是产生信息的源头，为了方便分析和描述，我们将信源分为两大类：模拟信源和数字信源。模拟信源也被成为连续信源，其输出可建模为模拟基带信号m(t)，对于模拟基带信号，我们的处理方式主要是数字化。而数字信源是离散信源，是我们重点讨论的部分，其输出建模为随机符号序列{𝑋1, 𝑋2,𝑋3, … ,𝑋𝐿}，对于随机符号序列，我们的处理主要是信源压缩，这就牵扯到我们在后面介绍的信源编码定理以及大数定律。不论是哪种信源，我们的最终信源的存储或传输端接收到的都是比特序列。

2. 数字信源的概率描述

下面，我们将重点讨论数字信源，数字信源的输出是符号序列，具体来说是字符取自某个字典（字符集）的字符串。如果字符集中不同的字符个数为n个—— $X\epsilon \left \{a_{1},a_{2},...,a_{n} \right \}$ ，那么字符为n进制字符，信源为n进制信源，具体输出为 $X_{1}X_{2}...X_{L}\epsilon \left \{a_{1},a_{2},...,a_{n} \right \}$ 。

由于数字信源的输出是随机符号序列，我们就需要研究其概率分布，首先，单个符号 $X\epsilon \left \{a_{1},a_{2},...,a_{n} \right \}$ 的概率分布为

其中，X可以表示任何含义，重点不是X本身，而是X的概率分布。

有了单个符号的概率分布，我们可以进行一对符号概率分布的研究，一对符号可视为一个更大的符号，例如， $X\epsilon \left \{a_{1},a_{2},...,a_{n} \right \}$ 与 $Y\epsilon \left \{b_{1},b_{2},...,b_{n} \right \}$ 可等价看成 $(X,Y)\epsilon \left \{(a_{1},b_{1}),(a_{2},b_{2}),...,(a_{n},b_{n}) \right \}$ 。

以此类推，我们可以得出三个符号构成一个大符号，例如将硬币独立掷3次得到 $Z = (X_{1}X_{2}X_{3})$ ，整体是一个8进制符号，其样本空间是 $\left \{ z_{1}z_{2}...z_{8} \right \}=\left \{ 000,001,...,111 \right \}$ ；若X是非均匀硬币的话，对应的 $X\epsilon \left \{ 0,1 \right \}$ 的概率分布是 $\left \{ p,1-p \right \}$ ，则可逐一算出Z的各种可能结果的出现概率，如 $P(Z=001)=P(X_{1}=0, X_{2}=0, X_{3}=1)=p^{2}(1-p)$ ，其概率分布为：

同样n个符号也可以构成一个大符号，这时候我们将其称为——符号序列

二、信息论的基本概念

在这部分我们主要介绍熵和信息量的概念，我们知道传统通信的方式是语法通信，即通信符号如何保证正确传输。对于通信符号的衡量，我们用信息量来表示。

1. 信息量

（1）信息量

首先信息是如何传输的呢？信息的传输可以归结为整数的传输，收发建立信息库，只需要告诉id号，所以任何形式的信源都可以建模为从一个库中选取了一个 $X\epsilon \left \{e_{1},e_{2},...,e_{n} \right \}$ 。也就是说，我们的信息库是确定的，我们知道所传输的信息库中的内容，但是我们不知道具体传输的是什么。

信息量的概念就是指的对库中信息进行整数编号所需的最少位数（digit），描述了我们信息传输的不确定性和自由度。具体我们可以用bit，Nat以及Det单位进行表述。例如，n位二进制密码锁的信息量为n bit，这时候我们的单个符号对应的信息库就是{0，1}，多个符号就是{0...0, ...., 1....1}

$1bit = 0.693Nat = 0.301Det$

我们还可以从哪个角度来理解比特呢？以比特为单位的信息量是样本空间的最大二分次数，也就是指的最多能二分多少次，比如一个Yes/No的问题，代表1bit信息，我们回答多少次能得到最终的答案，也就是多少bit信息。下面我们举一个掷硬币的例子：

某信源输出是掷一个硬币的结果，信息量是1比特；某信源输出是两个独立的掷硬币的结果，信息量是2比特；某信源输出是10万个独立的掷硬币的结果，信息量是100000比特；某信源输出是10万个独立的掷硬币的结果，每个硬币正面出现概率是0.1，信息量是？这时候我们就需要用到加权平均的思想：

平均掷一次硬币的信息量：

总信息量：

同时我们还可以把掷一次硬币的信息量看作是二元熵函数（与上述思想类似）：

除此之外，我们可以看成排列组合的问题，100000个硬币里面有10000个正面，有多少种可能：

大数定律（Law of Large Number）

从上述的公式结果我们可以看出，当不等概的时候，可能性比等概时少；这说明当不等概的时候，存在冗余，我们可以用更少的比特来表示同样的信息。

（2）自信息self-information

自信息实际是在用事件发生的概率来刻画一个事件的信息量，也就是我们在上面提到的掷一次硬币的信息量。若事件 $A$ 出现的概率是 $P(A)$ ，其自信息是 $-logP(A)$ 。一个Y/N问题可以获得1bit信息，自信息为问出A需要几个问题。自信息反应该事件出现的意外程度或不确定度。

（3）互信息mutual information

我们可以用一个图来清晰地看出互信息的含义：

其公式可以写为：

$I(X;Y)=I(X)-I(X|Y)$

$I(X;Y)=I(Y)-I(X|Y)$

$I(X;Y)=I(X)+I(Y)-I(X,Y)$

条件熵H(X|Y)我们可以理解为：得知Y后，我对X还有多无知；互信息I(X;Y)我们可以理解为：得知Y使我对X知道了多少。

互信息有许多性质，如：对称性 $I(Y;X)=I(X;Y)$ 、非负性 $I(X;Y)\geq 0$ 以及互信息不超过无条件熵 $I(X;Y)\leq H(X), I(X;Y)\leq H(Y)$ 。

2. 信息熵 H(x)

（1）熵

信息量度量的是一个具体事件发生所带来的信息，而熵则是在结果出来之前对可能产生的信息量的期望——考虑该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望，所以信息熵时信源输出的平均信息量（自信息为概率的负对数）。

熵的具体含义可以表述为以下几种：

反应无限长序列实际可能的个数。
当信息等概的时候，我们知道n进制符号序列X1, X2, X3…XL的可能个数为 $n^{L}$ ，此时信息量为 $I(X_{1}...X_{L})=-log\frac{1}{n^{L}}=logn^{L}=Llogn$ ，将信息量的单位默认为比特，我们可以得到信息量为 $Llog_{2}n$ ，那序列的可能次数即为 $2^{Llog_{2}n}=n^{L}$ ；但是当不等概的时候，我们就需要用到信息熵来进行衡量：假设我们使用比特来作为信息量的单位，信息量这时候为 $I(X_{1}...X_{L})=LH(X)$ ，那序列的可能次数为 $2^{LH(X)}$ ，其中H（X）是平均每符号的熵bit。
不确定性或无知程度的定量化。
自信息的数学期望。

熵和信息量一样，有许多性质，例如：

熵非负：H(X)≥0
M进制符号的熵最大为logM，H(X)≤logM：
等概分布时熵最大
条件熵小于等于无条件熵 H(X|Y)≤X(X)
独立符号的联合熵时各自熵之和
条件熵=联合熵-条件自身的熵
联合熵小于等于各自熵之和
条件熵非负
联合熵大于任何一个边缘熵
若X，Y独立，则条件熵与条件无关

讨论完熵的具体含义和性质之后，我们给出熵的具体表达式：

随机符号的熵：

二元函数熵：

（2）两个符号的联合熵

讨论完单个符号的熵之后，我们考虑两个符号的联合熵，由于两个符号整体是一个更大的符号，我们可以得到联合熵的公式

其中，两个符号之间的关系有独立或者不独立，首先是两个独立符号的联合熵，两个独立符号的联合熵是各自熵的和，证明如下：

然后是两个不独立符号的联合熵，两个不独立符号的联合熵不超过各自熵之和，即

从上述的表述，我们可以知道两个符号独立等概时联合熵最大：每个符号等概时各自的熵最大，两个符号独立时联合熵最大。

最后，我们推广到符号序列的熵：

（3）条件熵

条件熵时条件概率的负对数的数学期望 $H(X|Y) = E[-logP(X|Y)]$ ，其中， $W=-log P(X|Y)$ 是从(X, Y)映射到实数，我们的概率值为联合概率而自信息中的概率为条件概率：

注意，条件熵时所有可能条件下，熵的数学期望：

（4）微分熵（差分熵）

我们知道，离散符号的熵是概率的负对数的数学期望，而对连续随机变量，定义概率密度的负对数的数学期望为微分熵：

$E=\left [ -logp(x) \right ]=-\int p(x)logp(x)dx$

同时，在功率限定时，零均值高斯熵最大，即高斯噪声的随机性最大（高斯噪声是最糟糕的噪声，而白高斯噪声是更糟糕的噪声）。这时候，我们假设X的分布为 $X\sim N(0,\sigma^{2})$ ， $p(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{x^{2}}{2\sigma^{2}}}$ ，由于存在e的指数项，我们对p(x)进行取以e为底的对数，可以得到 $-lnp(X)=ln\sqrt{2\pi\sigma^{2}}+\frac{X^{2}}{2\sigma^{2}}$ ，然后对其取均值，前一项为常数，后一项根据均方值和方均值的关系 $V=E(X^{2})-E^{2}(X)$ 可以得到， $h(X)=ln\sqrt{2\pi \sigma^{2}}-\frac{\sigma^{2}}{2\sigma^{2}}=ln\sqrt{2\pi e\sigma^{2}}$ 。

三、简单的信源编码

讨论完信源以及信息论的基本概念之后，下面，我们讨论对数字信源的处理方式——信源压缩，也就是信源编码。

1. 无失真离散信源编码

（1）概念

信源编码（压缩编码）的输入是L个n进制符号，编码器将其压缩为K个m进制符号。压缩编码后，平均每信源符号的编码长度是 $\frac{K}{L}$ 。

无失真编码指的是对每个具体的x=x1,x2,…,xL，译码器收到编码输出s=(s1,s2,…,sK)后，能还原出x，即通过S能恢复出x。在上图中，我们讨论了当信源独立等概的时候，不能做信源编码，故只有不等概的时候才可以进行信源编码，其中我们具体压缩的是大数定律中肯定不会出现的情况。

（2）典型序列

当L→∞时（足够长的时候才满足大数定律），x的实现将分化为两类。一类是符合大数定律的，称为典型序列（只对于典型序列做编码），另一类是不符合的，称为非典型序列。 Ω𝑥相应也分成两部分，典型序列（可能实现的）集合 Ω1 与非典型序列（不可能实现的）集合 Ω2 。

一般情况下，设L个符号 $x=(x_{1},x_{2},x_{3},...,x_{L})$ 的熵 $H(x_{1},x_{2},x_{3},...,x_{L})$ 平均到每个符号是 $H(X)=\frac{H(x_{1},x_{2},x_{3},...,x_{L})}{L}bit/symbol$ ，则当L→∞时，元素的个数为 $2^{LH(X)}$ 个，且这些元素等概出现。

与此同时，当L→∞时， $x=(x_{1},x_{2},x_{3},...,x_{L})$ 的实现为非典型序列的概率趋于零，即 $P(x\epsilon \Omega _{2})\rightarrow 0$ ；为典型序列的概率是1，即 $P(x\epsilon \Omega _{1})\rightarrow 1$ 。也就是说，当L→∞时不符合大数定律的非典型序列基本不会出现。

所以我们只对典型序列进行编码，若信源编码器认定非典型序列不会出现，只将典型序列集合 $\Omega _{1}$ 中的 $2^{LH(X)}$ 个元素逐一映射为K个m进制符号 $s_{1},s_{2},s_{3},...,s_{k}$ ，则 $m^{K}\geq 2^{LH(X)}$ 。平均每信源符号在编码后的码长是 $\frac{K}{L}\geq \frac{H(X)}{log_{2}m}$ ，即进来的符号的信息量比平均每个符号所承载的信息量。

（3）信源编码定理

对于信源编码，我们分为等长信源编码以及变长信源编码。其中等长信源编码定理为对于任意给定的充分小正数 $\varepsilon, \delta$ ，只要 $\frac{K}{L}log_{2}m\geq H(X)+\varepsilon$ ，则当L足够大时，必可使译码差错率小于 $\delta$ 。反之，当 $\frac{K}{L}log_{2}m\leq H(X)-2\varepsilon$ 时，译码差错一定是个有限值，而当L足够大时，译码几乎必定出错。关于式子，我们可以理解为，熵是一切信源压缩的极限，即最少用几比特来表示信源。