基础信息论复习
课程复习指引：
-
分清了解，理解，掌握
了解： 知道
理解：可辩析，可论述
掌握：可辩析可论述，可计算 -
课程学习目标：
- 掌握通信系统中信息测度，信道容量和率失真函数得基本概念和计算方法
- 掌握部分信源编码方法及信道编码得基本理论
（重要：二元信道，面向考试的话，注意重要得信道，不会考很难的信道）
-
重点和难点：
（调制解调要了解，可能会出简答题，画出通信模型等等）
清楚各个物理概念，理解记忆并表述
离散熵比连续熵更重要 -
各个章的重点内容：
-
第二章一定会出计算题，重点中的重点
重视 ：离散，平稳信源！马尔可夫信源！(可能提高考察) 香农第一定理(自己推导一遍) -
第三章：
重视单符号离散信道容量的计算，重视几种特殊信道的信道容量的计算！重视香农公式的推到，物理意义，应用！
-
第四章 率失真函数：一般会考察定义，定义域，值域，参量表达式等
-
第五章 信源编码方法：
主要理解唯一可译码的条件，必要性，付出代价，以及掌握码数方法等。
聚焦到香农编码和费诺编码 -
第六章 信道编码方法
聚焦到奇偶效验码和线性分组码两个方法!
而且要掌握译码准则：最大后验概率译码规则和极大似然译码规则等等！ -
推荐作业：
-
第2章 信息熵
一. 信息量
-
自信息量
一个随机事件发生某一结果后所带来的信息量称为 自信息量\(I(a_i) = -log_2p(a_i)\)
--当log底数为 2时：单位为bit
--当log底数为e时：单位为奈特(nat)
--当log底数为10时：单位为笛特(Det)或哈特(Hart)\(I(a_i)\)的性质：
- 为非负值
- \(p(a_i)\)为1的时候， 为 0
- \(p(a_i)\)为0的时候，为 \(\infin\)
- \(I(a_i)\)时\(p(a_i)\)的单调递减函数
即：概率越大的事件，提供的自信息量越少
-
联合自信息量
\(I(a_ib_j)=-log_2p(a_ib_j)\)
当X与Y相互独立的时候，有公式：
\(I(a_ib_j) = I(a_i)+I(b_j)\) -
条件自信息量
设\(b_j\)条件下，发生\(a_i\)的条件概率为\(p(a_i/b_j)\) 。
则它的条件自信息量为：
\(I(a_i/b_j)=-log_2p(a_i/b_j)\)
表示特定条件下随机事件发生\(a_i\)所带来的信息量
二. 互信息量与条件互信息量
-
互信息量
设两个随机事件X和Y，X取值于信源发出的离散消息集合，Y取值于信宿收到的离散消息集合。
一般而言，由于信道中总存在着噪音和干扰，所以：- 先验概率： \(p(a_i)\)
- 后验概率： \(p(a_i/b_j)\)
则，互信息量定义为：
\(I(a_i;b_j)=log_2\frac{p(a_i/b_j)}{p(a_i)}\)
将上式展开：
\(I(a_i; b_j)=I(a_i)-I(a_i/b_j)\)
即：
互信息量等于自信息量减去条件信息量。互信息量等于先验不确定度-后验不确定度
可以这样理解：自信息量就是对\(b_j\)一无所知的情况下，\(a_i\)的不确定度，条件自信息量就是在数量上等于已知\(b_j\)的条件下，\(a_i\)仍然存在的不确定度。再者：可以从宏观角度观察问题：
可以认为输入随机变量X和输出随机变量Y之间没有任何关联关系。即X和Y统计独立
则根据概率的性质，和先验不确定度和后验不确定度的公式得到：
\(I(a_i; b_j)=I(a_i)+I(b_j)-I(a_ib_j)=log_2\frac{p(a_ib_j)}{p(a_i)(b_j)}\) -
互信息的性质
- 对称性
\(p(a_i;b_j)=p(b_j;a_i)\)
互信息的对称性表明了两个随机事件及时间的可能结果\(a_i\)和\(b_j\) 之间的统计约束程度 - 当X和Y相互独立时，互信息为 0
- 互信息量可为正值或负值。
取决于先验概率和后验概率的大小关系
- 对称性
-
条件互信息量
条件互信息量的含义是给定 \(c_k\)的条件下，\(a_i\)和\(b_j\)之间的互信息量。用 \(I(a_i; b_j / c_k)\)表示
定义式为： \(I(a_i; b_jc_k)=I(a_i; c_k)+I(a_i;b_j/c_k)\)
三. 信源熵
-
信源熵
定义各个离散消息的自信息量的数学期望，即概率加权的统计平均值，为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或者香农熵，有时称为无条件熵或熵函数。记为H(X)
\(H(X)=E[(I(a_i)]=-\sum^n_{i=1}p(a_i)log_2p(a_i)\)信源熵的三种物理含义：
- 表示信源输出后，平均每个离散消息所提供的信息量
- 表示信源输出前，信源的平均不确定度
- 反映了变量X的随机性
-
条件熵（损失熵）（噪声熵）
（当已知X时，Y跟着完全确定的时候，噪声熵为 0！）
条件熵是在联合符号集合XY上的条件自信息量的数学期望。 \(H(X/Y)=\sum^m_{j=1}\sum^n_{i=1}p(a_ib_j)I(a_i/b_j) = -\sum^m_{j=1}\sum^n_{i=1}p(a_ib_j)log_2(a_i/b_j)\)
计算方法
- 先根据条件求出 \(p(a_i)\)
- 再求出 \(p(a_i/b_j)\)
- 最后根据公式求得 H(X/Y)
（当H(X/Y) = H(Y/X) = 0时，要求是一一对应信道，也就是无噪无损信道）
-
联合熵
也叫共熵
是联合离散符号集合XY上的每个元素\(a_ib_j\)的联合自信息量的数学期望。用 H(XY)表示
即：
\(H(XY)=\sum_{i=1}^n\sum_{j=1}^mp(a_ib_j)I(a_ib_j)=-\sum_{i=1}^n\sum_{j=1}^mp(a_ib_j)log_2p(a_ib_j)\) -
信源熵的基本定理和性质
-
非负性
因为自信息有非负性 -
对称性
-
最大离散熵定理
定理：信源X中包含n个不同离散消息时，信源熵H(X)有
\(H(X)\le{log_2n}\)
当且仅当X中各个消息出现的概率全相等时，上去取等号即：最大离散熵为 \(log_2n\)
-
扩展性
-
确定性
-
可加性
\(H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y)\) -
极值性
\(H_n[p(a_1),p(a_2),...,p(a_n)]\le-\sum_{i=1}^np(a_i)log_2p(b_i)\)
由极值性可以证明 条件熵小于信源熵
\(H(X/Y)\le{H(X)}\) -
上凸性
\(H(\alpha X+(1-\alpha)Y\ge\alpha H(X)+(1-\alpha)H(Y)\)
-
-
平均互信息量
互信息量只反映了某一对输入输出消息间信息的流通。我们更希望从平均意义上来衡量信源，信宿间的信息流通
定义式：
\(I(X; Y)=\sum_{i=1}^n\sum^m_{j=1}p(x_iy_j)log\frac{p(x_i/y_j)}{p(x_i)}=\sum_{i=1}^n\sum^m_{j=1}p(x_iy_j)I(a_i;b_j)\)\(I(X; Y)=H(X)-H(X/Y)=H(X)+H(Y)-H(XY)\)
通信前对X的平均不确定度 - 通信后，已知Y，对X的平均不确定度
性质：
-
对称性
-
非负性
-
极值性
\(I(X;Y)\le H(X)\)
\(I(X;Y)\le H(Y)\)
当X与Y独立的时候 ，为 0！ -
凸函数性
信道固定时：为\(p(x_i)\)的上凸函数
信道固定时：为\(p(y_j/x_i)\)下凸函数
-
5. 与各类熵的关系
四. 离散平稳信源
-
离散性。平稳性
-
序列信息的熵(离散平稳无记忆信源)
可以证明：离散平稳无记忆信源X的N次扩展信源的熵就是离散信源X的熵的N倍。
即\(H(X^N)=NH(X)\) -
离散平稳信源的信源熵和极限熵
离散平稳信源一般是有记忆信源。-
信源熵：
\(H(X)=H(X_1X_2)=H(X_1)+H(X_2/X_1)\)
可以看出：二位离散平稳有记忆信源的熵\(\le\)二维离散平稳无记忆信源的熵
上式是二维离散信源。还可以推广到N维：
就是X起始时刻随机变量X1的熵与各阶条件熵之和 -
平均符号熵和极限熵
-
信源的矢量熵(联合熵)
\(H(X_1X_2...X_N)\)
信源平均每发出一个消息所提供的信息量 -
平均符号熵
\(H_N=\frac{H(X_1X_2...X_n)}{N}\)
-
极限熵
当分组长度N趋于无穷大时的平均符号熵
研究实际信源，必须求出信源的极限熵，能表示多符号离散平稳有记忆信源平均每发一个符号的信息量
-
-
五. 马尔可夫信源与冗余度
-
定义：
某一时刻信源输出的符号的概率只与当前所处状态有关，而与以前的状态无关
信源的下一个状态由当前状态和下一刻的输出唯一确定 -
马尔可夫信源的极限熵
m阶马尔可夫信源的极限熵等于m阶条件熵
\(H∞=H_{m+1}=-\sum_i\sum_jp(e_i)p(e_j|e_i)logp(e_j|e_i)\)
$p(e_j)$：信源的平稳分布
注：极限熵并非一定存在
计算常用全概率公式
\(p(s_j)=\sum_ip(s_i)p(s_j/s_i)\)
- m阶马尔可夫与一般有记忆信源的区别
信源冗余度
对实际信源，其所提供的信息量应该用 H∞ 衡量
但涉及到求解无穷维联合概率分布的问题
将实际信源近似为 多符号信源 或 m阶马尔可夫信源
* 冗余度定义：
$\xi=1-\frac{H_\infty}{H_0}$
表示信息中，$\xi$的内容都是多余的
* 冗余度与传输效率
冗余度越低，通信有效性越好
冗余度过低，会带来通信可靠性方面的问题
* 常用公式：
$H_\infty=\frac{log(字的个数)}{每个字包含的平均字符数}$
六. 连续信源
- 连续信源的熵
连续信源的熵为无穷大！所以不确定性也是无穷大
丢掉无穷大项后，
定义连续信源的熵为：\(H_c(X)=-\int_{-\infty}^{+\infty}p(x)logp(x)dx\)
(因为应用中常常关心的是熵之间的差值，故无穷项可以相互抵消)
所以定义中的熵不会影响讨论所关心的交互信息量，信息容量和率失真函数
-
几种特殊连续信源的熵
- 一维均匀分布
- 一维高斯分布(仅与方差有关)
- 指数分布
-
连续熵的性质及最大连续熵定理
-
连续熵可为负值
-
可加性
\(H_c(XY)=H_c(X)+H_c(Y/X)\)
\(H_c(XY)=H_c(Y)+H_c(X/Y)\) -
平均互信息量的非负性，对称性
\(I_c(X;Y)=H_c(X)-H_c(Y/X)\)
\(I_c(X;Y)=H_c(Y)-H_c(X/Y)\)
\(I_c(X;Y)=[H_c(X)+H_C(Y)]-H_c(XY)\)
\(I_c(X;Y)=I_c(Y;X)\) -
最大熵
-
当峰值功率受限时
均匀分布的熵最大 log(b-a)
-
平均功率受限时：（均值为0，方差受限的随机变量）
正态分布的熵最大 \(\frac12log2\pi eP_{avg}\) -
输出信号幅度受限
- 定理：对于服从均匀分布的随机变量
- 定理：对于服从均值为m，方差为\(\sigma_2\)的高斯分布的随机变量具有最大输出熵
-
-
七. 熵功率
-
离散信源的信息变差：
\(I_{0\infty}=H_0 - H_{\infty}\)
两者差值越大，代表信源的绝对冗余度越大！ -
连续信源的信息变差
\(I_{p,q}=H_c[p(x), X]-H_c[q(x),X]\)
最大熵- 实际熵 -
限定条件不同的时候，信息变差的值并不相同：
仅讨论均值为0，平均功率受限的连续信源：
\(I_{p,q}=H_c[p(x), X]-H_c[q(x),X]=\frac12log2\pi e P_{avg}-\frac12log2\pi e \overline{P_{avg}}\)
即：
\(I_{p,q}=\frac12log\frac{P_{avg}}{\overline{P_{avg}}}\)
八. 香农第一定理(离散无失真信源编码定理)
-
定长编码定理
易推导，对于平稳无记忆信源，由平均符号熵为\(\frac{Klog_2m}L\)
只要：\(L\ge\frac{\sigma^2[I(a_i)]}{\epsilon^2\delta}\)译码差错率一定小于任意正数\(\delta\)
- 解题思路：
用所给信源模型求出H(X), \(\sigma^2[I(a_i)]\).
编码效率=\(\frac{H(X)}{H(X)+\varepsilon}\)
计算出\(\varepsilon\)
然后由\(L\ge\frac{\sigma^2[I(a_i)]}{\epsilon^2\delta}\)
得到L的取值范围
- 解题思路：
-
变长编码定理
计算公式：
编码效率的下界：
\(\eta=\frac{H(X)}R\gt\frac{H(X)}{H(X)+\frac{log_2m}{L}}\)
第三章 信道容量
一. 单符号离散信道
用信道转移概率矩阵来表示信道特征。
\(I(X;Y)\)理解为信道的信息传输率。(或信息率)
易知\(R=I(X;Y)\le H(X)\)
由凸函数性质可知：一定有一种概率分布可以使信道所能传送的信息率为最大。
我们把这个最大的信息传输率定义为信道容量，记为C
若信道平均传输一个符号要t秒。则单位时间的信道容量为 \(C_t=\frac1tmaxI(X;Y)\)
-
几种特殊离散信道的信道容量
-
离散无噪信道的信道容量
由无躁的概念分为3种情况：-
具有一一对应关系(输入n = 输出m)
易知H(X/Y) = 0。 即 I(X;Y) = H(X) = H(Y)
信道矩阵为单位矩阵 -
具有可扩展性能的无噪信道（输入n < 输出m）
（例如，一对多）
已知Y后，X不再具有任何不确定度：即H(X/Y) = 0, 故 I(X;Y) = H(X)
此时\(C = log_2n\)注意：此信道的输入端符号熵小于输出端符号熵H(X) < H(Y)
最佳输入：\(p(x_i)=\frac1n\) -
具有归并性能的无噪信道(输入n > 输出m)
（例如，多对一）
类似：H(Y/X) = 0. 故 I(X;Y) = H(Y)H(X) > H(Y)
此时\(C = log_2m\)
最佳输入：使\(p(y_j)=\frac1m的p(x_i)\)注意！此时最佳输入概率分布并不唯一！
-
可知：无噪信道的信道容量C 只取决于 信道的输入符号数n或输出符号数m，与信源无关
-
强对称离散信道的信道容量
信道矩阵特点
- 对角线元素都为\(\overline{p}\)(正确传递概率)
- 其余元素都为 \(\frac{p}{n-1}\)(错误传递概率)
- 每行之和为1
每列之和也为1 - 矩阵为对称阵
计算：用I(X;Y) = H(Y) - H(Y/X) 因为\(p(y_j/x_i)\)已知
推导后可得： \(I(X;Y)=H(X)-H(Y/X)=H(Y)-H(行矢量)\)
故：C = max[H(Y)] - H(行矢量) = \(logn + \overline{p}log\overline{p}+plog\frac{p}{n-1}\)
max[H(Y)] = log n可以推导出最佳信源分布为：等概分布
- 特例：二进制对称信道！
当p = 0.5时，为无用信道，强噪声信道。
-
对称离散信道的信道容量
定义：行可排列，列可排列，矩阵可排列-
推导公式：
\(H(Y/X)=H(行矢量)\)
\(C = max_{p(x_i)}[H(Y)]- H(行矢量)\)可以推出 -> \(p(x_i)=\frac1n\) 就能推出 \(p(y_j)\)为常量
即： 最佳输入为\(p(x_i)=\frac1n\) .
C = log m - H(行矢量)
-
-
准对称离散信道的信道容量
定义：行可排列， 列不可排列。但矩阵中的m列 可分成s 个不相交的子集。每个子集对应的子矩阵具有可排列性
达到最佳输入分布也是等概率分布信道容量计算公式为：\(C = log n - \sum_{k=1}^sN_klog M_k -H (q_1,q_2,...,q_m)\)
n为输入符号集的个数。\(N_k\)为第k个子矩阵中的行元素之和(常数)。\(M_k\)是第k个子矩阵的列元素之和(常数)。s是子矩阵的个数。\(q_1, q_2,...q_m\)为整个信道矩阵中的行元素(常数)
可得
推导过程中：
\(H(Y/X)=H(q_1,q_2,...,q_m)\)
H(Y)的前一部分 = log n
H(Y)的后一部分 = \(-\sum_{k=1}^sN_klog M_k\)
再由C = H(Y) - H(Y/X) 得到最终公式$C = log n - \sum_{k=1}^sN_klog M_k -H (q_1,q_2,...,q_m)
-
二. 单变量连续信道与香农公式
-
香农公式！
加性连续信道：噪声N与信号X统计独立。噪声对信号的干扰表现为和输入线性叠加-
对于加性连续信道，其信道转移特性为噪声的概率密度。p(y/x) = p(n)
-
\(H_c(Y/X)=H(N)\) \(C = max_{p(x)}\{H_c(Y)\}-H_c(N)\)
-
最大连续熵：常见限定条件：
-
峰值功率受限：均匀分布
-
均值受限： 指数分布
-
平均功率受限：正态分布
容易计算出\(H_c(N)=\frac12log(2\pi e P_N)=\frac12log(2\pi e \sigma^2)\)
可以证明：当平均功率受限的条件下，Y满足高斯分布的时候，\(H_c(Y)\)达到最大！
当在X也服从零均值的高斯分布的时候，Y=X+N,也服从高斯分布。且E(Y)=E(X)+E(N)=0.
\(P_Y = \sigma_Y^2=\sigma_X^2+\sigma^2_N=P_X+P_N\)代入之前的公式得到：\(C=\frac12log(1+\frac{P_X}{P_N})\) 单位：bit/sig
上式就是香农公式的第一种形式！！！
-
采样定理：信道的频带为(0, W) ,则每秒需要进行2W 次采样，在接收端才能无失真的恢复出原始信号。
可以计算出：
香农公式的第二种形式：\(C_t=Wlog(1+\frac{P_X}{P_N})\) 单位：bit /s
公式中：功率信噪比：\(\frac{P_x}{P_N}(dB)=10*log_{10}^{\frac{P_x}{P_N}}\)
即：\(\frac{P_x}{P_N}=10^{\frac{\frac{P_x}{P_N}dB}{10}}\) -
由高斯白噪声的概念：高斯白噪声就是指功率谱密度为常数(\(N_0 / 2\)) ，而在一个频带为(0, W)的信道中，噪声平均功率是：\(P_N = \frac{N_0}2*2W=N_0W\)
可以带入第二种形式得到：
香农公式的第三种形式：\(C_t = Wlog(1+\frac{P_X}{N_0W})\) 单位 bit / s
从第三种形式可以看出，信噪比和带宽是成反比的！
-
-
-
对于非高斯信道，用香农公式算出的信道容量是其理论上的下限值
-
- 带宽一定，提高信噪比可以提高信道容量
- 倍数相同，增加带宽通常比提高信噪更有效！
- 无噪连续信道的信道容量为无穷大。
- 当增加信道带宽，并不能使信道容量无限增加！无限接近\(\frac{P_X}{N_0}*log e\)
- 当所需要传输的总信息量一定时，则带宽W，传输时间T，信噪比\(P_X/P_N\)三者可以进行相互转换
三. 信道编码定理
数学描述： 若有一离散无记忆平稳信道，容量C，输入序列长度为L，只要待传送的信息率R<C，总可以找到一种编码，当L足够长，对任意正数\(\varepsilon\) ，总可以找到一种编码，使得译码差错概率\(P_e < \varepsilon_0\) 反之，当R<C时，任何编码的\(P_e\)必大于0，当L->∞，\(P_e-> 1\)
当\(R\le C\)，理论上就可以实现近乎无失真地传输。具体方法就是，通过编码得方法，增加信道符号序列的长度。
四. 噪声
主要研究加性噪声。
-
二进制信道模型
IN=0/1 -> binary channel -> OUT = 0/1
-
计算BER(Binary Error Rate)
BER 约等于 错误的比特数 / 匹配的比特数
第四章 信息率失真函数
一. 基本概念
信号传输允许一定程度的失真
-
失真函数
\(d(x_i, y_j)\)
可以人为规定-
\[d(x_i,y_j)=\begin{cases}0, i=j\\a,a\ge0.i\ne j\end{cases} \]
当a=1时，失真函数称为汉明失真函数
-
\(d(x_i,y_j)=(y_j-x_i)^2\)
平方误差失真函数。一半用于表示由于幅度变化引起的失真。多用于连续信源
-
-
失真函数的定义推广到适量传输
比如离散序列矢量信源的N长符号序列。\(d_N(X,Y)=\sum_{i=1}^Nd(X_i,Y_i)\)
对应的失真矩阵有\(n^N *m^N\)个元素 -
平均失真度
限失真的失真值。只能用它的数学期望或统计平均值，将失真函数的数学期望称为平均失真度\(\overline{D}=\sum_{i=1}^n\sum_{j=1}^mp(x_iy_j)*d(x_i,y_j)\)
平均失真度的意义：
在平均意义上衡量信道每传递一个符号所引起的失真的大小-
矢量传输的平均失真意义：
\(\overline{D_N}=E[D_N]=\sum^N_{i=1}\overline{D_i}\)
其中，\(\overline{D_i}\)时第i个位置上的符号的平均失真 -
如果信源时离散无记忆N次扩展信源，且信道是离散无记忆N次扩展信道。
则，每个位置上的符号的平均失真\(\overline{D_i}\)相等，且等于矢量平均失真。
\(\overline{D_N}=N\overline{D_i}, i=1,2,...,\)
-
-
信息率失真函数
-
保真度准则：
$\overline{D}\le D $（预先规定的限定失真度，是允许失真的上界）
信息压缩后的平均失真度，若信源和失真度一定，就只是信道统计特性 的函数。传递概率不同，平均失真度随之改变 -
D 失真许可信道
满足保真度准则的所有信道。 -
信息率失真函数的定义
在D允许信道\(P_D\)中，寻找一个信道p（Y|X），使给定的信源经过此信道传输时，其信道传输率 \(I(X,Y)\)最小。
\(R(D)=\min_{p(y|x)∈P_D}I(X,Y)\)
-
* 信息率失真函数的物理意义：
对于某给定信源而言，任何限失真编译码方法，必须保证系统的平均互信息量 $I(X;Y)\ge R(D)$,才有可能满足失真条件$\overline{D}\le D$。否则一定有$\overline{D} > D$
- 求信息率失真函数的方法：
* 求解方法对比：
-
信息率失真函数的性质
- 定义域： R(D) 的定义域 (0, Dmax)
- R（D）是关于D的下凸函数
- R(D) 在区间 (0, Dmax)上是严格递减函数
最小平均失真度\(D_{min}\)的求法：
在失真矩阵的每一行找出一个最小的\(d(x_i,y_j)\)，各行的最小值都不同。对这些所有的最小值求数学期望，就是信源的最小平均失真度
当每一行都有0存在的时候，最小平均失真度为0，此时，信源不允许任何失真存在。
而且信息率至少等于信源输出的平均信息量，即R(0) = H(X)
最大平均失真度\(D_{max}\)的求法：
必须传输的信息率R越小，容忍的失真D就越大。当R(D)等于 0 的时候，对应的平均失真最大。也就是函数R(D) 定义域的上界值\(D_{max}\)
-
计算\(D_{max}\)的值
\(D_{max}=\min_{p(y|x)∈P_0}E[d(x,y)]=min_{p(y_j)}\sum_jp(y_j)D_j\)
R(D)函数就是压缩程度的衡量。
二. 离散信源的信息率失真函数
1. 离散信源信息率失真函数的参量表达式
- 参量表示法
2. 二元及等概率离散信源的信息率失真函数
-
二元对称信源的信息率失真函数R(D)
给定平均失真度D：- 信源分布越均匀，(p值越接近1/2)，R(D)越大，即可压缩性越小
- 信源分布越不均匀，R(D)就越小，即可压缩性越大
-
等概率离散信源的信息率失真函数
公式分析：
* 第一项log n 是等概率信源的熵，即无失真传送信源所必须的信息率，后两项则是由于容忍到一定失真可以压缩的信息率。
* 对同一失真度D，n越大，R(D)越大，压缩率越小。
* 对同一失真度D，n越小，R(D)越小，压缩率越大。
* 当n=2，$\alpha=1$时，$R(D) = H(p)-H(D)=log 2 - H(D) = 1 - H(D)$
三. 连续信源的信息率失真函数
1. 连续信源信息率失真函数的参量表达式
-
平均失真度定义：
\(\overline{D}=E\{d(X,Y)\}=\int^{\infty}_{-\infty}\int^{\infty}_{-\infty}p(xy)d(x,y)dxdy\)
\(=\int^{\infty}_{-\infty}\int^{\infty}_{-\infty}p_X(x)p(x|y)d(x,y)dxdy\)
式子中的p(y|x)为信道特征。满足\(\int^{\infty}_{-\infty}p(y|x)dy=1\) -
连续信源的信息率失真函数相关定义
\(R(D)=\inf_{p(y|x∈P_D)}I(X,Y)\)
其中，inf表示下界。试验集合为\(P_D:\{p(y|x),\overline{D}\le D\}\)连续信源的信息率失真函数具有离散信源的信息率失真函数的性质
2. 高斯信源的信息率失真函数
接着用反向信道的方法推导：
当信源均值不为0时，仍有这个结果，因为高斯信源的熵只与随机变量的方差有关，与均值无关
3. 信道容量与率失真函数的比较(对偶问题)
第五章
一. 信源编码定理
1. 信源编码相关概念
-
- 分组码： 将信源的输出符号序列，分组处理的编码
- 非奇异码：若分组码中所有码字不相同，称为非奇异码，否则称为奇异码
- 如果一个码的任何一个码字都不是其他码字的前缀，则称该码为前缀码，异前置码，异字头码，逗点码，也称即时码。
- 同价码：每个码符号所占的传输时间都相同
码的分类：
2. 定长编码定理：
-
唯一可译码要求：码的任意有限次扩展码为 非奇异码
定长码：只要是定长码为非奇异码，则必为 唯一可译码对一个简单信源X进行定长编码，信源X存在唯一可译定长码的条件是：
\(n \le m^K\)
其中，n为信源X的符号个数 ，m是码符号数，K是定长码的码长 -
L次扩展信源的定长码：
对L次扩展信源进行定长编码，若要编得定长码是唯一可译码，则必须满足：
\(n^L\le m^K\)
化简可以得到： \(\frac KL \ge log_mn\) 这个公式效率不高！ -
定长编码定理：
- 正定理：
一个熵为H(X)的离散无记忆信源，若对长度为L的信源符号序列进行等长编码，设码字是从m个码符号集中选取的K个码元组成。对任意的和 \(\varepsilon > 0, 1>\delta>0\) > 只要满足：
\(\frac{K*logm}L\ge H(X)+\varepsilon\)
则当L足够长，必可以使得译码差错小于\(\delta\)
这个公式可以提高编码效率！ - 逆定理
反之，当\(\frac{K*logm}L \le H(X)-2\varepsilon\), 译码差错一定大于\(\delta\) .
当L -> ∞，译码差错趋近于1
- 正定理：
-
编码信息率
编码后平均每个信源符号能载荷的最大信息量\(R\'=\frac{K*logm(K长码字的最大信息量)}{L(信源符号的序列长度)}=\overline{K}*log\ m\) 单位：比特/信源
-
编码效率：
编码效率 = (要求平均每个信源符号携带的实际信息量) / (编码后平均每个信源符号的最大可能载信息量) = 最小可能码长 / 编码后实际码长对于等长编码：
\(\eta=\frac{H(X)}{R\'}=\frac{H(X)}{H(X)+\varepsilon}\) -
编码效率与扩展次数L的关系：
当L足够大的时候，必须使译码差错小于\(\delta\) ,编码效率才能趋于1
当允许的错误概率\(P_E\)小于\(\delta\)的时候信源序列长度L必须有：
\(L\ge \frac{\sigma^2(x)}{\varepsilon^2\delta}\)注意： \(\sigma^2(x)\) 就是信源的方差！
-
定长编码定理扩展
可以推广到有记忆信源上：
只需要将H(X) 换成\(H_\infty(X)\)
3. 变长编码定理(香农第一定理)
-
变长编码付出的代价和条件：
代价：- 译码需要同步
- 可能遇到译码延迟
条件：
- 变长码必须是非奇异码，而且任意有限长L次扩展码也应该是非奇异码
- 为了能即时译码，变长码必须是即时码（任何一个码字都不是其他码字的前缀）
Kraft不等式
（描述了信源符号数和码字长度之间满足了什么条件才能构成即时码）
m元长度为\(k_i(i=1,2,...,n)\)的即时码存在的充要条件是
\(\sum_{i=1}^nm^{-k_i}\le 1\)
这个式子称为克拉夫特不等式
（即时码一定满足Kraft不等式，反之不一定！）
- 平均码长：
\(\overline{K}=\sum^n_{i=1}p(x_i)*k_i\) 单位：码符号/信源符号 - 紧致码：对于给定的信源和码符号集，若存在一个唯一可译码，其平均码长小于所有其他唯一可译码的平均码长，则称为紧致码(最佳码)
- 信息传输率：经过信源编码后，平均每个码符号所携带的信息量
单位：比特/ 码符号
\(\frac{H(X)}{\overline{K}}=R\) - 信息传输速率：单位时间传输的信息量
\(R_t = \frac{H(X)}{\overline{K}t}\) = R/ t 比特/秒
单符号信源的变长编码定理
无记忆信源L次扩展信源的变长编码定理
编码效率
同样：虽然是无记忆信源，但也可以扩展到有记忆信源：
只要将H(X)变换为无穷熵就行。
变长编码的信息传输率等概念
-
变长编码的编码信息率R\'
\(R\'\triangleq \frac{\overline{K_L}}{Llog \ m}\)表示编码后平均每个信源符号能载荷的最大信息量
-
香农第一定理又可以表示为：
若 \(H(X)\le R\' <H(X)+\varepsilon\) ,就存在唯一可译的变长编码
若R\'大于H(X)。则不存在唯一可译的变长编码，不能实现无失真的信源编码 -
信息传输率 R
\(R=\frac{H(X)}{\overline{K}}\) 比特/ 符号
由\(\overline{K}=\frac{\overline{K_L}}{log\ m}\)
所以 \(R\le log \ m\) -
编码效率和剩余度
\(\eta=\frac{H(X)}{R\'}=\frac{H(X)}{\overline{K}log\ m}\)定义剩余度为：
\(\gamma=1-\eta=1-\frac{H_m(X)}{\overline{L}}\)
4. 香农第三定理
二. 信源编码方法
1. 香农编码
-
编码步骤
-
将信源符号按概率从大到小依次排列。
-
令\(p(x_0)=0\). 并用\(p_a(x_j)\)表示第j个码字之前的累加概率
即： \(p_a(x_j)=\sum^{j-1}_{i=0}p(x_i), j=1,...,n\) -
确定满足下列不等式的整数\(k_j\). 并令\(k_j\)为第j个码字的长度
\(-log\ p(x_j)\le k_j\ < 1-log\ p(x_j)\) -
将累加概率\(p_a(x_j)\)用二进制表示，去除小数点，根据码长并取小数点后共\(k_j\)位作为\(x_j\)的编码
-
计算编码效率。\(\eta\)= 要求平均每个信源符号传递的信息量/ 折算后，平均每个信源符号的最大可能载信量。
\(\eta = \frac{H(X)}{\frac{\overline{L}*log\ m}{N}}\)\(\overline{L}\) 计算： 用概率*码长累加（感觉就是平均码长）
-
2. 费诺编码
-
编码步骤：
-
将信源符号按概率从大到小依次排列，设排序后的消息分别记为：x1,x2,...,xn
-
将信源符号按概率分为若干组。使得每组的概率的和尽量接近或者相等。若编二元码就分为两组，编m元码就分成 m 组
-
给每组分配一位码元，码元的分配可以是任意的
-
对每一分组按上述原则继续分组，直到概率不可分
-
检验是否为即使码。并计算编码效率：
\[\eta = \frac{H(X)}{\frac{\overline{L}*log\ m}{N}} \]
-
例子：
3. 霍夫曼编码
- 二元码的编码步骤如下：
- 将信源符号按概率从大到小依次排列，设排序后的消息分别记为：x1,x2,...,xn
- 给两个概率最小的信源符号\(p(x_{n-1})\)和\(p(x_n)\)各分配一个码符号0 和 1.将这两个信源符号合并成一个新符号，并用\(p(x_{n-1})+p(x_n)\) 作为新符号的概率，结果得到一个只包含n - 1个信源符号的新信源。将该信源称为第一次缩减信源，用\(S_1\)表示
- 将缩减信源\(S_1\)的符号仍按概率从大到小的顺序排列，重复步骤2，得到只含n-2个符号的缩减信源\(S_2\)
- 重复上述步骤，直到缩减信源只剩下两个符号为止。此时所剩的两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字
第六章
香农第二定理
- 内容：
加噪信道具有信道容量C， 即可以传输有用信息的最大速率。
对于任何数据速率 R < C，都存在一种对数据进行编码的方法，使错误概率任意小。
信道编码
以提高通信可靠性为主要目的。
它是对信源编码器输出的最佳码再进行一次编码。以提高其抗干扰能力的一种编码形式
-
信道编码算法/规则
方法：按一定的规则给数字序列M增加一些多余的码元，使不具有规律性的信息序列M变换为具有某种规则性的数字序列C基本思想： 根据相关性来检测和纠正传输过程中产生的差错。提高通信可靠性
-
译码规则：
X方有 r个 x, Y方有 s个y。则共有\(r^S\)种译码规则 -
平均错误译码概率：
\(P_E=\sum^s_{j=1}p(y_j)p(e|y_j)=\sum^s_{j=1}\{1-p[F(y_j)|y_j]\}\)
译码准则：
最大后验概率译码规则：
最大似然准则
极大似然译码规则：
\(p(y_j|x^*)\ge p(y_j|x_i)\)
对每一列选择最大的传递概率。对应的输入符号，即为该输出符号的译码函数
汉明距离
两个码字之间的汉明距离是对应位不同的数量。
测量将一个码字转换为另一个码字所需的误码数量
-
最小汉明距离确定接收器可以检测或者纠正的最大误码位数
若最小汉明距离是d。则接收器可以：
- 对每个码字检错但不纠错最多d-1位
- 检错并纠错 (d - 1) / 2
校验位编码方法
基于奇偶校验位编码
(k+1, k, 2)码
- 给定k比特的信息， 可以通过添加1 比特来创建 (k+1, k, 2)分组码
- 选择该位 以使码字中的 (k + 1) 位之和为偶数
- 同样，如果k 个消息位的总和为 奇数， 则该位为 1， 否则为 0
- 该位称为奇偶校验位
- 生成的码字具有偶校验性
这样可以检测到单比特错误
(8, 4, 3)码
向矩阵的每一行或每一列都添加一个奇偶校验位Pi。
再重新排列这些比特形成最终的码字
- 校正位：
校正位Si在接收到的码字中检查，Si = 1表示违反了奇偶校验位Pi的条件
(9, 4, 4)码
