第一章 绪论
第二章 离散信源及信息测度
第三章 离散信道及其信道容量
第四章 连续信源和波形信道
第五章 无失真信源编码定理
第六章 有噪信道编码
第七章 限失真信源编码
第八章 无失真信源编码
第九章 纠错编码
第二章 离散信源及其信息测度
2.1 信源的数学模型及分类
信源的分类
- 在时间和取值上分类：离散信源、连续信源。
- 根据信源发出的信息序列之间是否有统计依赖性：有记忆信源、无记忆信源。
- 根据信源发出消息序列中的消息：平稳信源、非平稳信源。
本章重点研究对象：记忆长度有限的有记忆信源——马尔可夫信源。
信源的数学模型
- 信源的描述方法：随机变量、随机矢量、随机过程。
-
用随机变量描述信源输出的消息
信源输出的消息有限或可数，且每次指数处其中一个消息，可以用一个离散随机变量来描述：
\begin{bmatrix}X\\P(X)\end{bmatrix}=\begin{bmatrix}x_1&&x_2&&...&&x_q\\P(x_1)&&p(x_2)&&...&&p(x_q)\end{bmatrix}
\begin{gathered} 0\leq p(x_{_i})\leq1 ,~~~~~~\sum\limits_{i=1}^{q}p(x_{_i})=1 \end{gathered}
信源输出单个符号的消息，但消息的取值是连续的，可以用连续随机变量来描述：
\begin{bmatrix} X\\P \end{bmatrix}=\begin{bmatrix} (a,b)\\p(x) \end{bmatrix}~p(x)>0,~\int^b_ap(x)\mathrm dx=1
-
用随机矢量来描述信源输出的消息
如果信源输出的消息是由一系列符号组成，例如图像、视频，可以用N维随机矢量（随机序列）来描述信源：
\pmb{X}=X_1X_2\cdots X_N
-
用随机过程描述信源输出的消息
信源输出的消息常常是时间和取值都是连续的，例如语音信号、模拟电视图像信号。可以用随机过程\{x(t)\}来描述，这一类信源称为波形信源。
直接研究时间上连续的随机过程很困难，对时间离散化可以得到随机序列，再对随机序列通过采样、量化转换为离散信源处理。
不同信源的特性
- 离散平稳信源：信源输出的随机序列中每个随机变量都是离散型随机变量，且随机矢量的各维概率分布都与时间起点无关。
- 连续平稳信源：信源输出的随机序列中每个随机变量都是连续性随机变量，且随机矢量的各维概率密度函数都与时间起点无关。对连续平稳信源可通过量化，把连续的取值转换成离散值。
- 离散无记忆信源：信源先后发出的符号彼此统计独立。
- 离散有记忆信源：符号间彼此依存，互不独立，可用联合概率分布或条件概率分布来描述这种关联性。实际信源发出的消息符号往往只和前面若干符号依赖性较强，抓中信源称为有限记忆信源。
2.2 离散信源的信息熵
自信息
-
定义：时间x_i本身所包含的信息量：
I(x_i)=-\log p(x)=\log \frac{1}{p(x_i)}
自信息量的单位与所用对数的底的关系：
- 以2为底，单位为比特（bit）
- 以e为底，单位为奈特（nat）
- 以10为底，单位为哈特（Hat）
一般我们使用比特作为单位。
-
含义：
对于事件发生前：描述该时间发生的不确定性的大小；
对于事件发生后：表示该事件所含有/提供的信息量
在理想信道中：等于收信者接受到该信息后所获取的信息量。
联合自信息和条件自信息
-
联合自信息：二维联合空间XY中的事件(x_iy_j)的联合自信息定义为：
I(x_iy_j)=-\log p(x_iy_j)
-
条件自信息：在联合空间XY中，在事件y_j给定的条件下事件x_i的条件自信息的定义为：
I(x_i|y_j)=-\log p(x_i|y_j)
-
联合自信息和条件自信息的关系：
\begin{aligned} I(x_iy_j)=-\log p(x_i)p(y_j\mid x_i)=I(x_i)+I(y_j\mid x_i) \\ =-\log p(y_j)p(x_i\mid y_j)=I(y_j)+I(x_i\mid y_j) \end{aligned}
平均自信息
平均自信息可以定义整个信源的不确定度。平均自信息还可称为信息熵、香农熵。
随机变量X的平均自信息：每个消息包含的信息量的统计平均值。
假设随机变量X的概率空间为：
\begin{bmatrix}X\\P(X)\end{bmatrix}=\begin{bmatrix}x_1&&x_2&&...&&x_q\\P(x_1)&&p(x_2)&&...&&p(x_q)\end{bmatrix}
\begin{gathered} 0\leq p(x_{_i})\leq1 ,~~~~~~\sum\limits_{i=1}^{q}p(x_{_i})=1 \end{gathered}
则随机变量X的平均自信息为：
\begin{aligned} H(X)& \triangleq E[I(x_i)] \\ &=E[-\log p(x_i)]=-\sum\limits_{i=1}^q p(x_i)\log p(x_i) \end{aligned}
-
信息熵的单位
- 以2为底，单位为比特/符号；
- 以e为底，单位为奈特/符号；
- 以10为底，单位为哈特/符号。
-
信息熵的意义
信源的信息熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体特征的。对于某特定的信源，其信息熵只有一个。不同的信源因统计特性不同，其信息熵也不同。
-
信息熵的物理含义
H(X)在信源输出前表示信源的平均不确定性；
H(X)在信源输出后表示每个消息（符号）所提供的平均信息量；
H(X)表征变量X的随机性。
2.3 信息熵的基本性质
熵函数
离散随机变量X的概率空间为：
\begin{bmatrix}X\\P(X)\end{bmatrix}=\begin{bmatrix}x_1&&x_2&&...&&x_q\\P(x_1)&&p(x_2)&&...&&p(x_q)\end{bmatrix}
\begin{gathered} 0\leq p(x_{_i})\leq1 ,~~~~~~\sum\limits_{i=1}^{q}p(x_{_i})=1 \end{gathered}
记p_i=p(x_i)，则：
H(X)=-\sum_{i=1}^q p_i\log p_i=H{(p_1,p_2,...,p_n)}=H(\pmb p)
当n=2时，H(\pmb p)=H(p,1-p)=H(p)
对称性
当\pmb p=(p_1,p_2,...,p_n)中各分量的次序任意变更时，熵函数的值不变。
非负性
H(\pmb p)=H(p_1,p_2,...,p_q)\ge0
- 只有当随机变量是一确知量时，熵H(X)=0；
- 离散信源的熵满足非负性，而连续信源的熵可能为负。
确定性
在概率空间中，只要有一个事件为必然事件，那么其他事件必然是不可能事件，因此信源没有不确定性，H(X)=0。
扩展性
\lim\limits_{\epsilon\to0}H_{q+1}(p_1,p_2,\ldots,p_q,-\epsilon,\epsilon)=H_{q}(p_1,p_2,\ldots,p_q)
- 拓展性说明，增加一个概率接近于零的事件，信源熵保持不变。
- 虽然小概率事件出现后，给予收信者较多的信息，但从总体来考虑时，因为这种概率很小的事件几乎不会出现，所以它对于离散集的熵的贡献可以忽略不计。这也是熵的总体平均性的一种体现。
强可加性
设有两个相互关联的信源X和Y:
\begin{bmatrix}X\\P(X)\end{bmatrix}=\begin{bmatrix}x_1&&x_2&&...&&x_n\\P(x_1)&&p(x_2)&&...&&p(x_n)\end{bmatrix}
\begin{gathered} 0\leq p(x_{_i})\leq1 ,~~~~~~\sum\limits_{i=1}^{n}p(x_{_i})=1 \end{gathered}
\begin{bmatrix}Y\\P(Y)\end{bmatrix}=\begin{bmatrix}y_1&&y_2&&...&&y_m\\P(y_1)&&p(y_2)&&...&&p(y_m)\end{bmatrix}
\begin{gathered} 0\leq p(y_{_i})\leq1 ,~~~~~~\sum\limits_{i=1}^{m}p(y_{_i})=1 \end{gathered}
$$ \begin{aligned} H(XY)&=H(X)+\sum_ip(x_i)H(Y|x_i) \&=H(X)+H(Y|X)
\end{aligned} $$
-
联合熵的物理意义
表明在X和Y相关联的情况下，信源(XY)每发一个符号所提供的平均信息量等于信源X每发一个符号所能提供的平均信息量，再加上在X已知的条件下，信源Y再发一个符号所提供的平均信息量。
-
当XY相互独立时：H(XY)=H(X)+H(Y)
极值性和上凸性
-
上凸性：熵函数的极值点就是最值点
-
极值性：离散无记忆信源输出n个不同信息符号，当且仅当各个符号出现概率相等时（即p_i=\frac1n），熵最大，即：
H(p_1,p_2,...,p_n)\le H(\frac{1}{n},\frac{1}{n},...,\frac{1}{n})=\log n
各种熵之间的关系
-
性质1
H(XY)=H(X)+H(Y|X)
H(XY)=H(Y)+H(X|Y)
当X、Y相互独立时：
H(XY)=H(X)+H(Y)
对于多个随机变量：
$$
H\left(X_{1}X{2}\cdots X{N}\right) =H\left(X_1\right)+H\left(\begin{matrix}X_2\mid X_1\end{matrix}\right)+\cdots +H\left(X_N\mid X_1X_2\cdots X{_{N-1}}\right) $$
如果这N个随机变量相互独立，则：
H(X_1X_2...X_n)=H(X_1)+H(X_2)+...+H(X_N)
-
性质2
H(XY)\le H(X)+H(Y)
-
性质3
H(X|Y)\le H(X)
2.5 离散无记忆的扩展信源
-
离散单符号信源：输出离散取值的单个符号。
-
离散无记忆信源的扩展信源：实际的信源输出为符号序列，符号序列中前后符号出现彼此无关，概率空间相同。用随机矢量来描述：
\pmb X=X_1X_2X_3...\\ \begin{bmatrix} X_i\\P(X_i) \end{bmatrix}= \begin{bmatrix} X_i=x_1&X_i=x_2&...&X_i=x_q\\ p(x_1)&p(x_2)&...&p(x_q) \end{bmatrix}
以二进制信源为例：
- 未扩展二进制信源：a_1=0,a_2=1；
- 二次拓展信源：a_1=00,a_2=01,a_3=10,a_4=11；
- 三次拓展信源：a_1=000,a_2=001,a_3=010,a_4=011,a_1=100,a_2=101,a_3=110,a_4=111；
- N次拓展信源：2^N项。
N次扩展信源的数学模型
\begin{bmatrix}X^N\\P(X^N)\end{bmatrix}=\begin{bmatrix}\alpha_1&\cdots&\alpha_i&\cdots&\alpha_{q^N}\\p(\alpha_1)&\cdots&p(\alpha_i)&\cdots&p(\alpha_{q^N})\end{bmatrix}
- \alpha_i是由N个\alpha_i组成的一个符号序列；
- p(\alpha_i)是对应N个\alpha_i组成的序列的乘积。
N次扩展信源的熵
\begin{aligned} H(\pmb{X})=H(X^N)&=-\sum_{i=1}^{q^N}p(\alpha_i)\log p(\alpha_i) \\ &=NH(X) \end{aligned}
2.6 离散平稳信源
极限熵
随机变量序列中，对前N个随机变量的联合熵求平均称为平均符号熵：
H_N(\pmb X)=\frac 1NH(X_1X_2...X_N)
如果当N\rightarrow\infty时上式存在。则\lim\limits_{N\rightarrow\infty}H_N(\pmb X)被称为熵律，或极限熵，记为：
H_\infty=\lim\limits_{N\rightarrow\infty}H_N(\pmb X)
如果H_1(X)<\infty，则H_\infty存在，并且：
H_\infty=\lim\limits_{N\rightarrow\infty}H_N(\pmb X)=\lim\limits_{N\rightarrow\infty}H(X_N|X_1X_2...X_{N-1})
极限熵代表了离散平稳有记忆信源平均每发一个符号提供的信息量，极限熵才能确切表达多符号离散平稳有记忆信源平均每发一个符号提供的信息量。
2.7 马尔可夫信源
- 实际信源都是有记忆信源，符号间的相关性可以追溯到很远，使得极限熵的计算比较复杂。
- 解决实际问题时，限制其记忆长度可以有效简化问题。因此我们引出马尔科夫链及马尔可夫信源。
- 马尔可夫信源是一类相对简单的有记忆信源。信源在某一时刻发出某一符号的概率，除与该符号有关外，只与此前发出的有限个符号有关。
马尔可夫链
-
定义
马尔科夫链是一种特殊的时间离散、状态离散的随机过程。
设\left\{X_n,n\in N^+\right\}为一个随机序列，时间参数集N^+=\{0,1,2,...\}，状态空间S=\{S_1,S_2,...,S_J\}，若对于所有n\in N^+，有
\begin{aligned} &{P}\Bigl\{X_n=S_{i_n}\mid X_{n-1}=S_{i_{n-1}},X_{n-2}=S_{i_{n-1}},\cdots,X_1=S_{i_1},X_0=S_{i_0}\Bigr\} \\ =&P\bigl\{X_n=S_{i_n}|X_{n-1}=S_{i_{n-1}}\bigr\} \end{aligned}
则称\left\{X_n,n\in N^+\right\}为马尔科夫链。
-
意义
随机序列\{X_n\}的“将来”只通过“现在”与“过去”发生联系，一旦“现在”已知，则“将来”只决定于“现在”，而与“过去”无关。
-
状态转移概率
p_{ij}(m,n)=p\left\{X_n=S_j\mid X_m=S_i\right\}=p\left\{X_n=j\mid X_m=i\right\}
- 性质：
- 0\leq p_{_{ij}}(m,n)\leq1
- \sum\limits_{j\in S}p_{_{ij}}(m,n)\text{=}1
- 一步转移概率：p_{ij}(m,m+1)\Rightarrow p_{ij}(m)
- k步转移概率：p_{ij}^{(k)}(m)=p\left\{X_{m+k}=j|X_m=i\right\}
-
齐次性
如果马尔科夫链的状态转移概率与起始时刻无关，即对任意m，有
p_{ij}({m})=p(X_{m+1}=S_j\mid X_{m}=S_i)=p_{ij}
则称这类马尔科夫链为实齐（齐次）马尔科夫链。也称为转移概率平稳的马尔科夫链。
-
转移矩阵与状态转移图
齐次马氏链可以用状态转移矩阵或状态转移图来描述。一步转移概率p_{ij}的转移矩阵如下：
P=\begin{bmatrix}p_{11}&p_{12}&\cdots&p_{1J}\\ p_{21}&p_{22}&\cdots&p_{2J}\\ \cdots&\cdots&\cdots&\cdots\\ p_{J1}&p_{J2}&\cdots&p_{JJ}\end{bmatrix}
\begin{aligned} &0\leq p_{_{ij}}(m,n)&& \leq1 \\ &\sum\limits_{j\in S}p_{ij}(m,n)&& =1 \\ &n= m+1 \end{aligned}
-
切普曼-柯尔莫阁罗夫方程
P^{(k)}=P^{(l)}\cdot P^{(n)}
由切普曼-柯尔莫阁罗夫方程可得k步转移概率矩阵：
P^{(k)}=P\cdot P^{(k-1)}=P\cdot P\cdot P^{(k-2)}=\cdots=P^k
-
判断马尔科夫链的稳态分布是否存在方法：
设一时齐马氏链，状态有限，并且是不可约闭集和非周期态，若当n\rightarrow\infty时：
\lim\limits_{n\to\infty}p_j^{(n)}=W_j\quad j\in E
存在，则称该马氏链具有遍历性（各态历经性）。
对于时齐、有限状态的马氏链，若存在正整数r，使转移矩阵P^{(r)}中任意元素都大于0，则此马氏链具有各态历经性，或称遍历马氏链。
-
求解马氏链的极限分布
定理表明，当n\rightarrow\infty，经过n步转移后处于状态j的概率已与初始处于什么状态无关。
\lim\limits_{n\to\infty}P(X_n=S_j)=\lim\limits_{n\to\infty}\sum_i p_{0i}p_j^n=\lim\limits_{n\to\infty}\sum_j p_{0i}W_j=W_j
称\{W_j\}为极限分布，而且W_J满足：
\begin{cases}WP=W\\ \sum\limits_j W_j=1\end{cases}
其中
W=\begin{bmatrix}W_1&W_2&\cdots&W_J\end{bmatrix}，通过该方程组即可求解极限分布。
马尔可夫信源
-
m阶马尔可夫信源
信源在某一时刻发出某一符号的概率，除与该信号有关外，只与此前发出的m个符号有关。即：
p\left(x_i\mid x_{i-1},x_{i-2},\cdots,x_{i-m},\cdots\right)=p\left(x_i\mid x_{i-1},x_{i-2},\cdots,x_{i-m}\right)
-
若条件概率p\big(x_i|x_{i-1},x_{i-2},...,x_{i-m}\big)与时间起点i无关，则这样的信源叫作齐次马尔可夫信源。
将马尔可夫信源看作马尔可夫链的方式是：把时刻i_1到i_m的m个变量组成的符号序列看成一个状态。
-
平稳性：
马尔可夫信源在起始的有限时间内，信源不是平稳和各态历经性的，状态的概率有一段渐变过程。经过足够长时间之后，信源处于某个状态的概率与初始状态无关，这时每种状态的概率与初始状态无关。
一般的马尔可夫信源都不是平稳信源。但当齐次遍历的马尔可夫信源达到稳定后，这时就可以看作是平稳信源。
-
熵：
对于m阶马尔可夫信源，当其满足平稳性条件时，极限熵存在，且：
H_\infty=H_{m+1}=\sum\limits_ip(s_i)H(X|s_i)
- 实际信源常常是非平稳、有记忆的信源，为了便于分析，常常做如下近似：
- 在一个较短的时间窗内，可进似为平稳。
- 实际信源的记忆长度可追溯到起始时刻，但是通常相隔较远的两个符号，相关性已变的很弱，因此可以限制其记忆长度。
- 在做了上述假定之后，即可把实际信源当作马尔可夫信源进行研究。
- 实际信源常常是非平稳、有记忆的信源，为了便于分析，常常做如下近似：
2.8 信源冗余度与自然语言的熵
信源的相关性
对于同一信源，采用不同的模型，计算得到熵的关系是：
H_0\geq H_1\geq H_2\geq\cdots\geq H_{m+1}\geq\cdots\geq H_n
结论得：符号的相关性越大、信源熵越小。
英语信源的熵
-
如果将英语看作是离散无记忆等该分布信源，则英语信源的最大熵：
H_0=\log_227=4.76~(bit/sym)
-
如果将实际英文文章进行概率统计，得到字母的概率分布，把英文信源建模为离散无记忆非等概分布信源，得到：
H_1=-\sum\limits^{27}_{i=1}p_i\log_2p_i=4.03~(bit/sym)
-
进一步考虑到前后字母间的依赖关系，对实际英文文章进行统计，得到英文字母的一阶条件概率，把英文信源建模为一阶马尔可夫信源得：
H_2=3.32~(bit/sym)
-
实际上，当前字母不仅和前一个字母有依赖关系，和更前面的字母也有依赖关系，统计这种依赖关系，得到更多阶的条件概率分布，于是可以把英文信源建模为更高阶的马尔可夫信源：
H_\infty=1.4~(bit/sym)
信源的冗余度
-
信源的冗余度：
R=1-\frac{H_\infty}{H_0}
-
熵的相对率：
\eta=\frac{H_\infty}{H_0}\\R=1-\eta
经过计算英语信源的冗余度为0.71，因此写英语文章时，71%都是由语言结构定好的，只有29%时写文字的人可以自由选择的。100页的书，大约只传输29页就可以了，其余71页可以压缩掉。信息的冗余度表示信源可以压缩的程度。
从提高传输效率的观点出发，总是希望减少或去掉冗余度。单冗余度大的信息抗干扰能力强。通过前后符号的关联关系纠正错误。
习题
-
答案
判断对错：
- 信源可以分为离散信源和连续信源两种类型。（对/错）
- 根据信源发出的信息序列之间是否有统计依赖性，信源可以分为有记忆信源和无记忆信源两种类型。（对/错）
- 马可夫信源是记忆长度无限的有记忆信源。（对/错）
- 离散无记忆信源指信源先后发出的符号彼此统计独立。（对/错）
- 平均自信息和信息熵是同一个概念。（对/错）
- 熵的单位是比特。（对/错）
- 遍历马氏链表示马尔可夫过程中可能到达的所有状态。（对/错）
- 实际信源一般都是无记忆信源。（对/错）
- 一段长文本的最大熵是常数，不随文本内容的改变而改变。（对/错）
- 信源分为时间和取值上的分类，离散信源是指在时间和取值两个维度上都是离散的。（对/错）
- 平稳信源指不管何时开始观察，信源的统计规律都不会改变。（对/错）
- 可以用比特和字节来表示熵的单位。（对/错）
信源发出消息序列中的消息一般都是连续的。（对/错）具有二次拓展性的信源熵可以通过乘以拓展次数来得到。（对/错）- 马氏链的一步转移概率表示从一个状态转移到另一个状态的概率。（对/错）
- 信源熵越小，信源的不确定性就越小。（对/错）
- 为计算熵，需要知道每个符号发生的概率和每个符号所提供的信息量。（对/错）
- 估计信源熵的方法一般都要用到大量的样本数据。（对/错）
- 马尔可夫信源只与此前发出的有限个符号有关，不需要考虑更远的符号。（对/错）
- 信源的熵是随机序列中每个消息提供的平均信息量。（对/错）
-
答案
（答案：1-对，2-对，3-错，4-对，5-错，6-对，7-对，8-错，9-对，10-对，11-对，12-对，13-错，14-对，15-对，16-对，17-对，18-对，19-对，20-对）
-
答案
评论区