首先，老规矩：

未经允许禁止转载(防止某些人乱转，转着转着就到蛮牛之类的地方去了)

B站:Heskey0

Part 1 公式

第二章信息量与信息熵

信息的特征是不确定性
自信息量：度量某一事件，信源某一具体符号的不确定性 $（机器学习）信息论与编码基础 - 图1$ %3D-%5Clog%20p(x_i)%0A#card=math&code=I%28x_i%29%3D-%5Clog%20p%28x_i%29%0A)

信息熵：信源的平均不确定度 $（机器学习）信息论与编码基础 - 图2$ %3DE%5BI(X)%5D%3D-%5Csum_ip(x_i)%5Clog%20p(x_i)%0A#card=math&code=H%28X%29%3DE%5BI%28X%29%5D%3D-%5Csum_ip%28x_i%29%5Clog%20p%28x_i%29%0A)

条件熵：已知 X 后，关于 Y 的平均不确定度 $（机器学习）信息论与编码基础 - 图3$ %3D-%5Csum%7Bij%7Dp(x_i%2Cy_j)%5Clog%20p(y_j%7Cx_i)%3D%5Csum_ip(x_i)H(Y%7Cx_i)%0A#card=math&code=H%28Y%7CX%29%3D-%5Csum%7Bij%7Dp%28x_i%2Cy_j%29%5Clog%20p%28y_j%7Cx_i%29%3D%5Csum_ip%28x_i%29H%28Y%7Cx_i%29%0A)

联合熵：表示 X 和 Y 同时发生的不确定度 $（机器学习）信息论与编码基础 - 图4$ %3D-%5Csum%7Bij%7Dp(x_i%2Cy_j)%5Clog%20p(x_i%2Cy_j)%5C%5C%0AH(X%2CY)%3DH(X)%2BH(Y%7CX)%5C%5C%0AXY%E7%8B%AC%E7%AB%8B%E6%97%B6%EF%BC%8CH(X%2CY)%3DH(X)%2BH(Y)%0A#card=math&code=H%28X%2CY%29%3D-%5Csum%7Bij%7Dp%28x_i%2Cy_j%29%5Clog%20p%28x_i%2Cy_j%29%5C%5C%0AH%28X%2CY%29%3DH%28X%29%2BH%28Y%7CX%29%5C%5C%0AXY%E7%8B%AC%E7%AB%8B%E6%97%B6%EF%BC%8CH%28X%2CY%29%3DH%28X%29%2BH%28Y%29%0A)

互信息量：已知某一条件 Y，使得对 X 的不确定度减少了。衡量条件 Y 提供了多少关于 X 的信息量

$（机器学习）信息论与编码基础 - 图5$ %3D%5Clog%5Cfrac%7Bp(x_i%7Cy_j)%7D%7Bp(x_i)%7D%3D%5Clog%5Cfrac%7B%E5%90%8E%E9%AA%8C%E6%A6%82%E7%8E%87%7D%7B%E5%85%88%E9%AA%8C%E6%A6%82%E7%8E%87%7D%0A#card=math&code=I%28x_i%3By_j%29%3D%5Clog%5Cfrac%7Bp%28x_i%7Cy_j%29%7D%7Bp%28x_i%29%7D%3D%5Clog%5Cfrac%7B%E5%90%8E%E9%AA%8C%E6%A6%82%E7%8E%87%7D%7B%E5%85%88%E9%AA%8C%E6%A6%82%E7%8E%87%7D%0A)

平均互信息量：平均意义上的互信息量

$（机器学习）信息论与编码基础 - 图6$ %3D%5Csum%7Bi%2Cj%7Dp(x_i%2Cy_j)%5Clog%5Cfrac%7Bp(x_i%7Cy_j)%7D%7Bp(x_i)%7D%0A#card=math&code=%20%20I%28X%3BY%29%3D%5Csum%7Bi%2Cj%7Dp%28x_i%2Cy_j%29%5Clog%5Cfrac%7Bp%28x_i%7Cy_j%29%7D%7Bp%28x_i%29%7D%0A)

$（机器学习）信息论与编码基础 - 图7$ %3DH(X)-H(X%7CY)%0A#card=math&code=%20%20I%28X%3BY%29%3DH%28X%29-H%28X%7CY%29%0A)

不等关系：

$（机器学习）信息论与编码基础 - 图8$ %5Cle%20H(X)#card=math&code=H%28X%7CY%29%5Cle%20H%28X%29)
$（机器学习）信息论与编码基础 - 图9$ %5Cle%20H(X)%2BH(Y)#card=math&code=H%28XY%29%5Cle%20H%28X%29%2BH%28Y%29)

关系：

$（机器学习）信息论与编码基础 - 图10$ %3DH(X)%2BH(Y%7CX)#card=math&code=H%28X%2CY%29%3DH%28X%29%2BH%28Y%7CX%29)
$（机器学习）信息论与编码基础 - 图11$ %3DH(X)-H(X%7CY)#card=math&code=I%28X%3BY%29%3DH%28X%29-H%28X%7CY%29)
$（机器学习）信息论与编码基础 - 图12$ %3DI(X%3BY)#card=math&code=I%28Y%3BX%29%3DI%28X%3BY%29)
$（机器学习）信息论与编码基础 - 图13$ %3DH(X)%2BH(Y)-H(X%2CY)#card=math&code=I%28X%3BY%29%3DH%28X%29%2BH%28Y%29-H%28X%2CY%29)

通信模型：

信源：发出的信息量 $（机器学习）信息论与编码基础 - 图14$ #card=math&code=H%28X%29)
信道：信道中损失的信息量 $（机器学习）信息论与编码基础 - 图15$ #card=math&code=H%28X%7CY%29)
信宿：接收端获得的信息量 $（机器学习）信息论与编码基础 - 图16$ #card=math&code=I%28X%3BY%29)

衍生概念：

$（机器学习）信息论与编码基础 - 图17$ #card=math&code=H%28X%7CY%29)：疑义度，表示由于信道上存在干扰和噪声而损失掉的平均信息量
$（机器学习）信息论与编码基础 - 图18$ #card=math&code=H%28Y%7CX%29)：噪声熵
全损信道：干扰很大，难以从 Y 中提取 X 的有效信息，信源发出的所有信息都损失在信道中
- $（机器学习）信息论与编码基础 - 图19$ %3D0#card=math&code=I%28X%3BY%29%3D0)
- 例如：加密编码
无损信道：没有干扰，接收端能完全收到信源发出的信息
- $（机器学习）信息论与编码基础 - 图20$ %3DH(X)#card=math&code=I%28X%3BY%29%3DH%28X%29)

第三章信道容量

信道容量：信道所能传送的最大信息量

$（机器学习）信息论与编码基础 - 图21$ %7DI(X%3BY)%0A#card=math&code=%20%20C%3D%5Cmax_%7Bp%28x_i%29%7DI%28X%3BY%29%0A)

单位时间的信道容量：单位时间内信道所能传送的最大信息量

$（机器学习）信息论与编码基础 - 图22$ %7DI(X%3BY)%0A#card=math&code=%20%20Ct%3D%5Cfrac1t%5Cmax%7Bp%28x_i%29%7DI%28X%3BY%29%0A)

对称DMC信道
- 如果概率转移矩阵 P 的每一行都是第一行的置换(即包含相同元素)，称该矩阵是输入对称的
- 如果概率转移矩阵 P 的每一列都是第一列的置换(即包含相同元素)，称该矩阵是输出对称的
- DMC信道：输入输出都对称的离散无记忆信道
- 信道容量：

$（机器学习）信息论与编码基础 - 图23$ %3D%5Clog%20m%2B%5Csum%5Em%7Bj%3D1%7Dp%7Bij%7D%5Clog%20p%7Bij%7D%0A#card=math&code=%20%20%20%20C%3D%5Clog%20m-H%28Y%7Cx_i%29%3D%5Clog%20m%2B%5Csum%5Em%7Bj%3D1%7Dp%7Bij%7D%5Clog%20p%7Bij%7D%0A)

$（机器学习）信息论与编码基础 - 图24$ 指转移矩阵的列数

BSC信道（二进制对称DMC信道）
- 信道容量： $（机器学习）信息论与编码基础 - 图25$ %3D1-H(%5Cepsilon)%0A#card=math&code=C%3D%5Clog2-H%28%5Cepsilon%2C1-%5Cepsilon%29%3D1-H%28%5Cepsilon%29%0A)

香农公式：计算 AWGN 信道的信道容量 $（机器学习）信息论与编码基础 - 图26$ %3DW%5Clog(1%2B%5Cfrac%7BP_S%7D%7BN_0W%7D)%0A#card=math&code=C%3DW%5Clog%281%2BSNR%29%3DW%5Clog%281%2B%5Cfrac%7BP_S%7D%7BN_0W%7D%29%0A)

$（机器学习）信息论与编码基础 - 图27$ ：信道频带宽度，简称带宽，单位 Hz

$（机器学习）信息论与编码基础 - 图28$ ：signal to noise ratio，信噪比，是信号功率（单位为W）与噪声功率（单位为W）的比值

$（机器学习）信息论与编码基础 - 图29$ ：信号发射功率

$（机器学习）信息论与编码基础 - 图30$ ：高斯白噪声的单边功率谱密度

提升信道容量的方式
- 提升信道带宽
- 提升信噪比
  - 提升发射功率
  - 降低信道噪声
香农限：当带宽不受限制时，传送1比特信息，信噪比最低只需 -1.6dB

第五章信源编码

目的：提升通信系统的有效性

define:

$（机器学习）信息论与编码基础 - 图31$ : 输入编码器的信息位长度
$（机器学习）信息论与编码基础 - 图32$ : 进制数
$（机器学习）信息论与编码基础 - 图33$ : 编码后的码字长度
- 定长编码中， $（机器学习）信息论与编码基础 - 图34$ 是定值
- 变长编码中， $（机器学习）信息论与编码基础 - 图35$ 是码字平均长度
$（机器学习）信息论与编码基础 - 图36$ : 编码前后的信息量比值
平均码长 $（机器学习）信息论与编码基础 - 图37$ : 每一个信息位用几位编码来表示
- $（机器学习）信息论与编码基础 - 图38$ ，二进制的情况下， $（机器学习）信息论与编码基础 - 图39$

定长编码：

无失真条件 $（机器学习）信息论与编码基础 - 图40$ #card=math&code=R%5Cge%20H%28X%29)
输出信息率 $（机器学习）信息论与编码基础 - 图41$
编码效率 $（机器学习）信息论与编码基础 - 图42$ %7D%7BR%7D#card=math&code=%5Cmu%3D%5Cfrac%7BH%28X%29%7D%7BR%7D)

变长编码：

无失真条件 $（机器学习）信息论与编码基础 - 图43$ %5Cle%5Cbar%20R%3CH(X)%2B%5Cfrac%7B%5Clog%20m%7D%7BL%7D#card=math&code=H%28X%29%5Cle%5Cbar%20R%3CH%28X%29%2B%5Cfrac%7B%5Clog%20m%7D%7BL%7D)
平均输出信息率 $（机器学习）信息论与编码基础 - 图44$
编码效率 $（机器学习）信息论与编码基础 - 图45$ %7D%7B%5Cbar%20R%7D#card=math&code=%5Cmu%3D%5Cfrac%7BH%28X%29%7D%7B%5Cbar%20R%7D)
码字平均长度 $（机器学习）信息论与编码基础 - 图46$ K_i#card=math&code=%5Cbar%20K_L%3D%5Csum_ip%28x_i%29K_i)
平均码长 $（机器学习）信息论与编码基础 - 图47$

常见编码方法：哈夫曼编码，算数编码

第六章信道编码

信源编码目的：提高数字通信系统的有效性

信道编码目的：提高数字通信系统的可靠性

差错控制系统：

前向纠错：发送端信息经过纠错编码后实行传送，而接收端通过独立的纠错编码，自动纠正传递过程的差错
自动反馈重传：接收端若发现接收码字有错，则通过反向信道通知发送端重新发送该码字，如此反复，直到接收端认为接收正确为止
混合纠错：前向纠错和反馈重传的结合，兼有检错和纠错两种能力

有扰离散信道编码定理

信道编码器的码率 $（机器学习）信息论与编码基础 - 图48$ 信道容量 $（机器学习）信息论与编码基础 - 图49$ 时，一定存在一种信道编码方式可以实现无差错传输

汉明距离：两个（相同长度）码字对应位不同的数量

对两个码字进行异或云打算，并统计结果为1的个数

汉明重量：码字对应于相同长度的零字符串的汉明距离，也就是码字中非零元素的个数

常见的信道编码方法：

线性分组码
- 汉明码
- 循环码
- CRC校验码
卷积码

Part 2 理论

第二章离散信源及其信息测度

1. 自信息

信息量的计算要带单位，是物理量，有物理意义

一般采用以2为底的对数，常省略2不写

单位与对数的底有关，底为2时，单位为比特

自信息具有非负性 | 自信息的物理意义： | | —- |

事件发生前，描述该事件发生的的不确定性大小
事件发生后，该事件所含有的信息量

2. 信息熵

熵函数的重要性质：

可加性： $（机器学习）信息论与编码基础 - 图50$ %3DH(X)%2BH(Y%7CX)#card=math&code=H%28XY%29%3DH%28X%29%2BH%28Y%7CX%29)
上凸性： $（机器学习）信息论与编码基础 - 图51$ #card=math&code=H%28p_1%2C…p_n%29) 是概率分布 $（机器学习）信息论与编码基础 - 图52$ #card=math&code=%28p_1%2C…p_n%29) 的严格上凸函数
极值性：当且仅当符号概率都相等即 $（机器学习）信息论与编码基础 - 图53$ ，熵最大
- $（机器学习）信息论与编码基础 - 图54$ %5Cle%20H(%5Cfrac1n%2C…%5Cfrac1n)%3D%5Clog%20n#card=math&code=H%28p_1%2C…p_n%29%5Cle%20H%28%5Cfrac1n%2C…%5Cfrac1n%29%3D%5Clog%20n) | 信息熵的物理意义： | | —- |

信源输出前，描述信源的平均不确定性（自信息的数学期望）
信源输出后，每个消息(符号)给出的平均信息量
变量X随机性的大小
变量X的最小描述复杂度

3. 信源的分类

离散无记忆信源：

符号序列中生成每个符号的互相独立，且概率分布相同
符号序列中前后符号的出现彼此无关

离散有记忆信源：

符号序列中生成每个符号之间存在依赖关系

扩展信源：多符号信源

例如

$（机器学习）信息论与编码基础 - 图55$ %3Dp(1)p(0)p(0)#card=math&code=p%28100%29%3Dp%281%29p%280%29p%280%29)

N次扩展信源 $（机器学习）信息论与编码基础 - 图56$ ：把N个符号组成的N长序列看做一个整体 $（机器学习）信息论与编码基础 - 图57$

平均符号熵：

$（机器学习）信息论与编码基础 - 图58$ %3D%5Cfrac1NH(X_1X_2…X_N)#card=math&code=H_N%28%5Cvec%20X%29%3D%5Cfrac1NH%28X_1X_2…X_N%29)

N次扩展信源 $（机器学习）信息论与编码基础 - 图59$ 的熵：

$（机器学习）信息论与编码基础 - 图60$ %3DNH(X)#card=math&code=H%28X%5EN%29%3DNH%28X%29)

离散平稳信源：不同时刻消息的概率分布相同

N维平稳信源：N次扩展信源+离散平稳信源

N维平稳必然N-1维平稳

离散平稳有记忆信源，考虑记忆长度无穷，则平稳信源极限熵（熵率）：

$（机器学习）信息论与编码基础 - 图61$ %3D%5Clim%7BN%5Crightarrow%5Cinfin%7DH(X_N%7CX_1…X%7BN-1%7D)#card=math&code=H%5Cinfin%3D%5Clim%7BN%5Crightarrow%5Cinfin%7DHN%28%5Cvec%20X%29%3D%5Clim%7BN%5Crightarrow%5Cinfin%7DH%28XN%7CX_1…X%7BN-1%7D%29)

极限熵的求法：条件熵

平稳有限记忆长度为m+1的信源（ m+1 维平稳信源）极限熵，就等于m阶的条件熵
$（机器学习）信息论与编码基础 - 图62$ %3DH%7Bm%2B1%7D#card=math&code=H%5Cinfin%3DH%28X%7Bm%2B1%7D%7CX_1…X_m%29%3DH%7Bm%2B1%7D)

式子中 $（机器学习）信息论与编码基础 - 图63$ 为记忆长度

如：二维平稳信源(极限)熵： $（机器学习）信息论与编码基础 - 图64$ #card=math&code=H_2%28X_3%7CX_2%29)
如：三维平稳信源(极限)熵： $（机器学习）信息论与编码基础 - 图65$ #card=math&code=H_3%3DH%28X_3%7CX_1X_2%29)

4. 马尔可夫信源

M阶马尔可夫信源定义：

一类非平稳离散有记忆信源
在某一时刻发出某一符号的概率，只与此前发出的m个符号有关（用条件概率表示，条件长度为m）
熵 $（机器学习）信息论与编码基础 - 图66$ #card=math&code=H%7Bm%2B1%7D%3DH%28X%7Bm%2B1%7D%7CX_1X_2…X_m%29)

状态转移：

k步转移概率： $（机器学习）信息论与编码基础 - 图67$ %7D%7Bij%7D%3DP%5C%7BX%7Bm%2Bk%7D%3Dj%7CXm%3Di%5C%7D#card=math&code=p%5E%7B%28k%29%7D%7Bij%7D%3DP%5C%7BX_%7Bm%2Bk%7D%3Dj%7CX_m%3Di%5C%7D)
转移概率（条件概率）与起始时刻 $（机器学习）信息论与编码基础 - 图68$ ，转移的步数 $（机器学习）信息论与编码基础 - 图69$ 以及所处的状态 $（机器学习）信息论与编码基础 - 图70$ 和 $（机器学习）信息论与编码基础 - 图71$ 都有关

时齐(齐次)马尔可夫链：

时齐马尔可夫链的状态转移概率与时刻无关（平稳转移概率）
齐次马氏链可以用转移概率矩阵来描述。

$（机器学习）信息论与编码基础 - 图72$

矩阵中每个元素非负，并且每一行之和为1。

各态历经性：

对于时齐，有限状态的马氏链，若存在正整数，使转移矩阵 $（机器学习）信息论与编码基础 - 图73$ %7D#card=math&code=P%5E%7B%28r%29%7D) 中任意元素都大于0 ，则马氏链具有遍历性（各态历经性），即存在

$（机器学习）信息论与编码基础 - 图74$ %7D%3DWj%0A#card=math&code=%5Clim%7Bn%5Crightarrow%5Cinfin%7Dp_%7Bij%7D%5E%7B%28n%29%7D%3DW_j%0A)

极限分布/稳态分布：

向量 $（机器学习）信息论与编码基础 - 图75$
$（机器学习）信息论与编码基础 - 图76$
若转移概率矩阵或其矩阵乘积，每个元素都大于0，则稳态分布存在
计算极限分布之前，一定要先验证其极限分布存在

$（机器学习）信息论与编码基础 - 图77$ 时，状态的稳态分布和符号的稳态分布不同

符号稳态分布：通过状态稳态分布 $（机器学习）信息论与编码基础 - 图78$ ，符号条件矩阵 $（机器学习）信息论与编码基础 - 图79$ 计算

$（机器学习）信息论与编码基础 - 图80$

求状态极限分布：解线性方程组

$（机器学习）信息论与编码基础 - 图81$

马尔可夫信源的熵：可以用平稳信源的熵性质计算

$（机器学习）信息论与编码基础 - 图82$ %5C%5C%0A%26%3DH(X%7Bm%2B1%7D%7CS)%5C%5C%0A%26%3D%5Csum_ip(s_i)H(X%7Cs_i)%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AH%5Cinfin%3DH%7Bm%2B1%7D%26%3DH%28X%7Bm%2B1%7D%7CX1X_2…X_m%29%5C%5C%0A%26%3DH%28X%7Bm%2B1%7D%7CS%29%5C%5C%0A%26%3D%5Csum_ip%28s_i%29H%28X%7Cs_i%29%0A%5Cend%7Baligned%7D%0A)

极限熵计算使用符号条件概率矩阵，而不是状态转移矩阵

总结：

对于时齐马尔可夫链来说，一步转移概率完全决定了k步转移概率。
转移概率仅仅是条件概率，不包含初始概率分布。
由初始分布及各时刻的一步转移概率才能完整描述马尔可夫链的统计特性。
由初始分布及一步转移概率就能完整描述齐次马尔可夫链的统计特性。

对同一信源，采用不同的模型计算得到的熵的关系为：

$（机器学习）信息论与编码基础 - 图83$

信源的剩余度：存在剩余度的原因是分布不等概

$（机器学习）信息论与编码基础 - 图84$

其中 $（机器学习）信息论与编码基础 - 图85$ 为等概分布的熵，即 $（机器学习）信息论与编码基础 - 图86$

熵的相对率：

$（机器学习）信息论与编码基础 - 图87$

第三章离散信道及其信道容量

1. 离散信道

随机干扰：存在于输入和输出之间的关系

信道传递概率：

用 $（机器学习）信息论与编码基础 - 图88$ #card=math&code=P%28%5Cvec%20Y%7C%5Cvec%20X%29) 表示
离散无记忆信道（DMC），满足 $（机器学习）信息论与编码基础 - 图89$ %3D%5Cprod%7Bn%3D1%7D%5ENp(Y_n%7CX_n)%0A#card=math&code=p%28%5Cvec%20Y%7C%5Cvec%20X%29%3D%5Cprod%7Bn%3D1%7D%5ENp%28Y_n%7CX_n%29%0A)

$（机器学习）信息论与编码基础 - 图90$ %3Dp(0%7C1)p(1%7C0)p(0%7C0)%0A#card=math&code=p%28010%7C100%29%3Dp%280%7C1%29p%281%7C0%29p%280%7C0%29%0A)

离散无记忆恒参（平稳）信道，满足 $（机器学习）信息论与编码基础 - 图91$ %3Dp(Y_m%3Dj%7CX_m%3Di)%0A#card=math&code=p%28Y_n%3Dj%7CX_n%3Di%29%3Dp%28Y_m%3Dj%7CX_m%3Di%29%0A)

一般，不加说明，离散无记忆信道都看做是离散无记忆恒参信道

因此，离散无记忆信道的研究只需研究单个符号的传输即可，所以也叫单符号离散信道

单符号离散信道：

信道转移概率： $（机器学习）信息论与编码基础 - 图92$ %3DP(Y%3Db_j%7CX%3Da_i)%0A#card=math&code=p%28b_j%7Ca_i%29%3DP%28Y%3Db_j%7CX%3Da_i%29%0A)

可以用信道矩阵 $（机器学习）信息论与编码基础 - 图93$ 表示， $（机器学习）信息论与编码基础 - 图94$ ， $（机器学习）信息论与编码基础 - 图95$

2. 平均互信息

信道疑义度：

表示接收端收到信道输出的一个符号之后对信道输入的符号仍然存在的平均不确定性。
$（机器学习）信息论与编码基础 - 图96$ %3D%5Csumjp(y_j)H(X%7Cy_j)%3D-%5Csum%7Bi%7D%5Csum%7Bj%7Dp(x_iy_j)%5Clog%20p(x_i%7Cy_j)%0A#card=math&code=H%28X%7CY%29%3D%5Csum_jp%28y_j%29H%28X%7Cy_j%29%3D-%5Csum%7Bi%7D%5Csum_%7Bj%7Dp%28x_iy_j%29%5Clog%20p%28x_i%7Cy_j%29%0A)

其中 $（机器学习）信息论与编码基础 - 图97$ #card=math&code=H%28X%7Cy_j%29) 表示接收输出符号 $（机器学习）信息论与编码基础 - 图98$ 后关于 $（机器学习）信息论与编码基础 - 图99$ 的后验熵

互信息量：

收到 $（机器学习）信息论与编码基础 - 图100$ 后获取的关于发送符号 $（机器学习）信息论与编码基础 - 图101$ 的信息量
$（机器学习）信息论与编码基础 - 图102$ %3DI(x_i)-I(x_i%7Cy_j)%3D%5Clog%5Cfrac%7Bp(x_i%7Cy_j)%7D%7Bp(x_i)%7D%3D%5Clog%5Cfrac%7B%E5%90%8E%E9%AA%8C%E6%A6%82%E7%8E%87%7D%7B%E5%85%88%E9%AA%8C%E6%A6%82%E7%8E%87%7D%0A#card=math&code=I%28x_i%3By_j%29%3DI%28x_i%29-I%28x_i%7Cy_j%29%3D%5Clog%5Cfrac%7Bp%28x_i%7Cy_j%29%7D%7Bp%28x_i%29%7D%3D%5Clog%5Cfrac%7B%E5%90%8E%E9%AA%8C%E6%A6%82%E7%8E%87%7D%7B%E5%85%88%E9%AA%8C%E6%A6%82%E7%8E%87%7D%0A)

互信息量的物理意义：

$（机器学习）信息论与编码基础 - 图103$ #card=math&code=I%28x_i%3By_j%29) 表示事件 $（机器学习）信息论与编码基础 - 图104$ 出现后关于事件 $（机器学习）信息论与编码基础 - 图105$ 的不确定性减少的量
$（机器学习）信息论与编码基础 - 图106$ #card=math&code=I%28x_i%7Cy_j%29) 表示事件 $（机器学习）信息论与编码基础 - 图107$ 出现后关于事件 $（机器学习）信息论与编码基础 - 图108$ 仍然存在的信息量
事件 $（机器学习）信息论与编码基础 - 图109$ 出现以后信宿获得的关于事件 $（机器学习）信息论与编码基础 - 图110$ 的信息量

互信息量的性质：

互易性： $（机器学习）信息论与编码基础 - 图111$ %3DI(y_j%3Bx_i)#card=math&code=I%28x_i%3By_j%29%3DI%28y_j%3Bx_i%29)
可为0（ $（机器学习）信息论与编码基础 - 图112$ 相互独立），可正可负
任何两个事件之间的互信息不可能大于其中任一事件的自信息 $（机器学习）信息论与编码基础 - 图113$ %5Cle%20I(x_i)%5C%5C%0AI(x_i%3By_j)%5Cle%20I(y_i)%0A#card=math&code=I%28x_i%3By_j%29%5Cle%20I%28x_i%29%5C%5C%0AI%28x_i%3By_j%29%5Cle%20I%28y_i%29%0A)

平均互信息：

互信息 $（机器学习）信息论与编码基础 - 图114$ #card=math&code=I%28x_i%3By_j%29) 在联合概率空间 $（机器学习）信息论与编码基础 - 图115$ #card=math&code=P%28XY%29) 中的统计平均值 $（机器学习）信息论与编码基础 - 图116$ %26%3DE%5BI(x_i%3By_j)%5D%5C%5C%0A%26%3DH(X)-H(X%7CY)%5C%5C%0A%26%3DH(Y)-H(Y%7CX)%5C%5C%0A%26%3DH(X)%2BH(Y)-H(XY)%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AI%28X%3BY%29%26%3DE%5BI%28x_i%3By_j%29%5D%5C%5C%0A%26%3DH%28X%29-H%28X%7CY%29%5C%5C%0A%26%3DH%28Y%29-H%28Y%7CX%29%5C%5C%0A%26%3DH%28X%29%2BH%28Y%29-H%28XY%29%0A%5Cend%7Baligned%7D%0A)

平均互信息量的物理意义：

表示接收到Y以后，平均每个符号获得的关于输入变量X的信息量，是信道实际传输信息的数量（从 $（机器学习）信息论与编码基础 - 图117$ 获得的关于 $（机器学习）信息论与编码基础 - 图118$ 的平均信息量）
$（机器学习）信息论与编码基础 - 图119$ #card=math&code=H%28X%29) 是信源输出的信息量，而真正被接收者收到的信息量则是 $（机器学习）信息论与编码基础 - 图120$ #card=math&code=I%28X%3BY%29)

维拉图：可以用图判断公式对不对

$（机器学习）信息论与编码基础 - 图121$ 等价于 $（机器学习）信息论与编码基础 - 图122$
- $（机器学习）信息论与编码基础 - 图123$ %3DH(X)%2BH(Y%7CX)#card=math&code=H%28X%2CY%29%3DH%28X%29%2BH%28Y%7CX%29)
$（机器学习）信息论与编码基础 - 图124$ 等价于 $（机器学习）信息论与编码基础 - 图125$
- $（机器学习）信息论与编码基础 - 图126$ %3DH(X)-H(X%7CY)%3DH(X)%2BX(Y)-H(XY)#card=math&code=I%28X%3BY%29%3DH%28X%29-H%28X%7CY%29%3DH%28X%29%2BX%28Y%29-H%28XY%29)
$（机器学习）信息论与编码基础 - 图127$ 等价于 $（机器学习）信息论与编码基础 - 图128$
- $（机器学习）信息论与编码基础 - 图129$ %3DI(X%3BY_1Y_2)-I(X%3BY_2)#card=math&code=I%28X%3BY_1%7CY_2%29%3DI%28X%3BY_1Y_2%29-I%28X%3BY_2%29)

平均互信息的性质：

非负性
互易性
是信源概率分布 $（机器学习）信息论与编码基础 - 图130$ #card=math&code=P%28X%29) 的上凸函数
极值性 $（机器学习）信息论与编码基础 - 图131$ %5Cle%20H(X)%5C%5C%0AH(X%3BY)%5Cle%20H(Y)%0A#card=math&code=H%28X%3BY%29%5Cle%20H%28X%29%5C%5C%0AH%28X%3BY%29%5Cle%20H%28Y%29%0A)

计算题：

一：平均互信息的计算： $（机器学习）信息论与编码基础 - 图132$ #card=math&code=H%28X%3BY%29)

先求概率分布（矩阵）：条件分布 $（机器学习）信息论与编码基础 - 图133$ 和边缘分布 $（机器学习）信息论与编码基础 - 图134$
求联合概率： $（机器学习）信息论与编码基础 - 图135$ %3Dp(x_i)p(y_j%7Cx_i)#card=math&code=p%28x_i%2Cy_j%29%3Dp%28x_i%29p%28y_j%7Cx_i%29) 矩阵中元素相乘
$（机器学习）信息论与编码基础 - 图136$ %3D%5Csum%20p(x_i%2Cy_j)%5Clog%20p(y_j%7Cx_i)#card=math&code=H%28Y%7CX%29%3D%5Csum%20p%28x_i%2Cy_j%29%5Clog%20p%28y_j%7Cx_i%29)
$（机器学习）信息论与编码基础 - 图137$ %3DH(Y)-H(Y%7CX)#card=math&code=H%28X%3BY%29%3DH%28Y%29-H%28Y%7CX%29)

3. 信道容量

信息传输率： $（机器学习）信息论与编码基础 - 图138$

信道中平均每个符号所传送的信息量。 $（机器学习）信息论与编码基础 - 图139$ %3DH(X)-H(X%7CY)%0A#card=math&code=R%3DI%28X%3BY%29%3DH%28X%29-H%28X%7CY%29%0A)

信道容量： $（机器学习）信息论与编码基础 - 图140$

最大的信息传输率 $（机器学习）信息论与编码基础 - 图141$ %5C%7D#card=math&code=C%3D%5Cmax%5C%7BI%28X%3BY%29%5C%7D) ，相应的输入概率分布被称为最佳输入分布
与信源的概率分布无关，是完全描述信道特性的参量
是信道能够传输的最大信息量

求解信道容量：

无噪无损信道
- 无噪无损信道矩阵为单位阵（r=s）
- $（机器学习）信息论与编码基础 - 图142$ %3D0%2CH(X%7CY)%3D0#card=math&code=H%28Y%7CX%29%3D0%2CH%28X%7CY%29%3D0) 得 $（机器学习）信息论与编码基础 - 图143$ %3DH(X)%3DH(Y)#card=math&code=I%28X%3BY%29%3DH%28X%29%3DH%28Y%29)
- 则 $（机器学习）信息论与编码基础 - 图144$ %7DH(X)%3D%5Clog%20r%3D%5Clog%20s#card=math&code=C%3D%5Cmax_%7Bp%28x%29%7DH%28X%29%3D%5Clog%20r%3D%5Clog%20s)
有噪无损信道
- $（机器学习）信息论与编码基础 - 图145$ ，最佳输入：等概分布
无噪有损信道
- $（机器学习）信息论与编码基础 - 图146$ ，最佳输入：不唯一，使输出等概分布

无记忆扩展信道：

输入和输出是一个随机变量序列
每一个随机变量均取值于同一输入或输出符号集

4. 对称信道

离散输入对称信道：

信道矩阵每一行都是相同元素的排列组合

离散输出对称信道：

信道矩阵每一列都是相同元素的排列

对称信道：

输入对称+输出对称

准对称信道：

信道矩阵可以按列分为一些对称的子阵
划分子集只有一个时，就是对称信道

准对称信道和对称信道容量的最佳输入分布都是等概分布。

5. 信道组合

级联信道：串联

信道一： $（机器学习）信息论与编码基础 - 图147$ #card=math&code=P%28Y%7CX%29) ，输入 $（机器学习）信息论与编码基础 - 图148$ ，输出 $（机器学习）信息论与编码基础 - 图149$
信道二： $（机器学习）信息论与编码基础 - 图150$ #card=math&code=P%28Z%7CXY%29) ，输入 $（机器学习）信息论与编码基础 - 图151$ ，输出 $（机器学习）信息论与编码基础 - 图152$
$（机器学习）信息论与编码基础 - 图153$ %5Cge%20I(Y%3BZ)#card=math&code=I%28XY%3BZ%29%5Cge%20I%28Y%3BZ%29)

一般来说，串联信道中，随机变量序列（ XYZ ）可构成马氏链，即， Z与X没有直接的依赖关系

$（机器学习）信息论与编码基础 - 图154$ %5Cle%20I(X%3BY)#card=math&code=I%28X%3BZ%29%5Cle%20I%28X%3BY%29)：信息不增（一般总是丢失信息的）

信源与信道匹配：

当信源与信道连接时，若信息传输率达到了信道容量，则称此信源与信道达到匹配。否则，认为信道有剩余

信道的剩余度：

$（机器学习）信息论与编码基础 - 图155$ #card=math&code=C-I%28X%3BY%29)

第四章波形信源和波形信道

1. 连续信源熵

微分熵：也叫差熵，可以为负

$（机器学习）信息论与编码基础 - 图156$ %3D-%5Cint_a%5Ebp(x)%5Clog%20p(x)dx#card=math&code=h%28X%29%3D-%5Cint_a%5Ebp%28x%29%5Clog%20p%28x%29dx)

最大熵：

即输出幅度受限的情况下，服从均匀分布的随机变量具有最大熵
对于平均功率受限的连续随机变量，当服从高斯分布时具有最大熵

熵功率：

设限定的平均功率为P，某连续信源的实际熵为h(X)，则与它具有相同熵的高斯信源的平均功率被定义为熵功率 $（机器学习）信息论与编码基础 - 图157$ %7D%0A#card=math&code=%5Cbar%20P%3D%5Cfrac1%7B2%5Cpi%20e%7De%5E%7B2h%28X%29%7D%0A)

剩余度：

平均功率和熵功率之差 $（机器学习）信息论与编码基础 - 图158$

2. 香农公式

会用公式算就行

对于连续信源，

当幅度（峰值功率）受限时，均匀分布具有最大熵；
当平均功率受限时，高斯分布具有最大熵

编码：多做几个题就行

第五章无失真信源编码

1. 码的分类

信源符号集： $（机器学习）信息论与编码基础 - 图159$

码字：编码器的输出

码符号集：用来组成码字的符号的集

定长码：码字等长

分组码：信源符号集和码符号集为一对一或多对一（不能一对多），分类：

非奇异码：信源符号和码字一一对应，不一定是唯一可译码
奇异码：信源符号和码字不是一一对应，一定不是唯一可译码

信源编码目的：提高数字通信系统的有效性

信道编码目的：提高数字通信系统的可靠性

唯一可译码：任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列（看PPT的例子）

唯一可译码的充要条件：编码的任意次扩展均为非奇异码

定长非奇异码一定是唯一可译码，但非充要条件（有可能是非定长即时码）

唯一可译码可分为两类：

即时码：某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码
- 充要条件：码组中任一码字都不是其它码字的前缀
非即时码

平均码长：

假设信源的分布： $（机器学习）信息论与编码基础 - 图160$ #card=math&code=s_i%5Csim%20p%28s_i%29) ，码字对应长度 $（机器学习）信息论与编码基础 - 图161$
则平均码长： $（机器学习）信息论与编码基础 - 图162$ li%0A#card=math&code=%5Cbar%20L%3D%5Csum%7Bi%3D1%7D%5Eqp%28s_i%29l_i%0A)

紧致码/最佳码：平均码长最小的唯一可译码

2. 定长编码定理

定理1：如果对 $（机器学习）信息论与编码基础 - 图163$ 次扩展信源 $（机器学习）信息论与编码基础 - 图164$ 进行定长编码，要满足非奇异性，需满足 $（机器学习）信息论与编码基础 - 图165$

定长信源编码定理：设离散平稳无记忆信源的熵为H(S), 若对N次扩展信源进行 $（机器学习）信息论与编码基础 - 图166$ 定长编码(r个编码符号)，则对于任意 $（机器学习）信息论与编码基础 - 图167$ ，只要满足

$（机器学习）信息论与编码基础 - 图168$ %2B%5Cepsilon%7D%7B%5Clog%20r%7D%0A#card=math&code=%5Cfrac%7Bl%7D%7BN%7D%5Cge%5Cfrac%7BH%28S%29%2B%5Cepsilon%7D%7B%5Clog%20r%7D%0A)

则当N足够大时，可实现几乎无失真编码，即译码错误概率 $（机器学习）信息论与编码基础 - 图169$ 为任意小

反之，如果：

$（机器学习）信息论与编码基础 - 图170$ -2%5Cepsilon%7D%7B%5Clog%20r%7D%0A#card=math&code=%5Cfrac%7Bl%7D%7BN%7D%5Cle%5Cfrac%7BH%28S%29-2%5Cepsilon%7D%7B%5Clog%20r%7D%0A)

则不可能实现无失真编码，当N足够大时，译码错误概率 $（机器学习）信息论与编码基础 - 图171$ 为1

3. 变长码

设：

信源符号集 $（机器学习）信息论与编码基础 - 图172$
码符号集 $（机器学习）信息论与编码基础 - 图173$
码字 $（机器学习）信息论与编码基础 - 图174$
其码长分别为 $（机器学习）信息论与编码基础 - 图175$

Kraft不等式：即时码、唯一可译码存在的充分必要条件

$（机器学习）信息论与编码基础 - 图176$

注意:

该定理可以作为判断一种码不是即时码（或唯一可译码）的判断依据。
该定理不能作为判断一种码是即时码（或唯一可译码）的判断依据

唯一可译码判别准则：看PPT或者B站搜

编码信息率：R

$（机器学习）信息论与编码基础 - 图177$ %7D%7B%5Cbar%20L%7D%0A#card=math&code=R%3D%5Cfrac%7BH%28S%29%7D%7B%5Cbar%20L%7D%0A)

香农第一定理：

对扩展信源 $（机器学习）信息论与编码基础 - 图178$ 编码，总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足：

$（机器学习）信息论与编码基础 - 图179$ %7D%7B%5Clog%20r%7D%5Cle%20%5Cfrac%7B%5Cbar%20L_N%7D%7BN%7D%3C%5Cfrac%7BH(S)%7D%7B%5Clog%20r%7D%2B%5Cfrac1N%0A#card=math&code=%5Cfrac%7BH%28S%29%7D%7B%5Clog%20r%7D%5Cle%20%5Cfrac%7B%5Cbar%20L_N%7D%7BN%7D%3C%5Cfrac%7BH%28S%29%7D%7B%5Clog%20r%7D%2B%5Cfrac1N%0A)

编码下界记作：

$（机器学习）信息论与编码基础 - 图180$ %3D%5Cfrac%7BH(S)%7D%7B%5Clog%20r%7D%0A#card=math&code=H_r%28S%29%3D%5Cfrac%7BH%28S%29%7D%7B%5Clog%20r%7D%0A)

编码效率：

$（机器学习）信息论与编码基础 - 图181$

Huffman码：哈夫曼码的构造过程建议看B站/PPT

第六章有噪信道编码

信道编码：

按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列

信道译码：

接收到码符号序列后，按照与信道编码器相同的数学规律，去掉符号序列中的冗余符号

1. 译码规则/错误概率

设：

输入符号集 $（机器学习）信息论与编码基础 - 图182$
输出符号集 $（机器学习）信息论与编码基础 - 图183$

译码规则：

函数 $（机器学习）信息论与编码基础 - 图184$ #card=math&code=F%28y_j%29)，输出为 $（机器学习）信息论与编码基础 - 图185$

错误概率：

设译码规则为 $（机器学习）信息论与编码基础 - 图186$ %3Dx_i%5E%5Cstar#card=math&code=F%28y_j%29%3Dx_i%5E%5Cstar)
当输入符号是 $（机器学习）信息论与编码基础 - 图187$ 时，译码正确
- 正确译码的概率： $（机器学习）信息论与编码基础 - 图188$ %7Cy_j%5D%3Dp(x_i%5E%5Cstar%7Cy_j)%0A#card=math&code=p%5BF%28y_j%29%7Cy_j%5D%3Dp%28x_i%5E%5Cstar%7Cy_j%29%0A)

  - 平均正确译码概率：

$（机器学习）信息论与编码基础 - 图189$ %0A#card=math&code=%5Cbar%20PE%3D%5Csum%5ES%7Bj%3D1%7Dp%28x%5E%5Cstar%20y_j%29%0A)

当输入符号是除 $（机器学习）信息论与编码基础 - 图190$ 以外的 $（机器学习）信息论与编码基础 - 图191$ #card=math&code=%28r-1%29) 种符号时，译码错误
- 错误译码的概率

$（机器学习）信息论与编码基础 - 图192$ %26%3D%5Csum%7Bk%5Cne%20i%7Dp(x_k%7Cy_j)%5C%5C%0A%26%3D1-p(x_i%5E%5Cstar%7Cy_j)%3D1-p%5BF(y_j)%7Cy_j%5D%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0Ap%28e%7Cy_j%29%26%3D%5Csum%7Bk%5Cne%20i%7Dp%28x_k%7Cy_j%29%5C%5C%0A%26%3D1-p%28x_i%5E%5Cstar%7Cy_j%29%3D1-p%5BF%28y_j%29%7Cy_j%5D%0A%5Cend%7Baligned%7D%0A)

平均错误译码概率： $（机器学习）信息论与编码基础 - 图193$ p(e%7Cyj)%3D1-%5Csum%5ES%7Bj%3D1%7Dp(xi%5E%5Cstar%20y_j)%0A#card=math&code=P_E%3D%5Csum%5ES%7Bj%3D1%7Dp%28yj%29p%28e%7Cy_j%29%3D1-%5Csum%5ES%7Bj%3D1%7Dp%28x_i%5E%5Cstar%20y_j%29%0A)

错误概率的影响因素：
- 信道统计特性：信源概率分布和信道转移概率分布
- 译码准则： $（机器学习）信息论与编码基础 - 图194$ %3Dx_i%5E%5Cstar#card=math&code=F%28y_j%29%3Dx_i%5E%5Cstar) ，这里 $（机器学习）信息论与编码基础 - 图195$ 即目标 $（机器学习）信息论与编码基础 - 图196$

常用的两个重要译码规则：

最大后验概率规则(最佳译码准则，也称最小错误概率译码准则)-MAP
- 令， $（机器学习）信息论与编码基础 - 图197$ %3Dx%5E%5Cstar#card=math&code=F%28y_j%29%3Dx%5E%5Cstar)，若 $（机器学习）信息论与编码基础 - 图198$ %5Cge%20p(x_i%7Cy_j)#card=math&code=p%28x%5E%5Cstar%7Cy_j%29%5Cge%20p%28x_i%7Cy_j%29)，即 $（机器学习）信息论与编码基础 - 图199$ %5Cge%20p(x_iy_j)#card=math&code=p%28x%5E%5Cstar%20y_j%29%5Cge%20p%28x_iy_j%29)
- 则译码规则为MAP准则
- $（机器学习）信息论与编码基础 - 图200$ %3D1-%5Csum%7BY%2CX%5E%5Cstar%7Dp(x_i)p(y_j%7Cx_i)%0A#card=math&code=P_E%3D1-%5Csum%7BY%2CX%5E%5Cstar%7Dp%28xiy_j%29%3D1-%5Csum%7BY%2CX%5E%5Cstar%7Dp%28x_i%29p%28y_j%7Cx_i%29%0A)

具体使用：看PPT，有例题，懒得抄
- 取的每一列的最大，加起来之后得到
  - 极大似然译码规则-ML
在MAP的基础上，输入符号等概分布，则 $（机器学习）信息论与编码基础 - 图204$ %5Cge%20p(y_j%7Cx_i)#card=math&code=p%28y_j%7Cx%5E%5Cstar%29%5Cge%20p%28y_j%7Cx_i%29)
$（机器学习）信息论与编码基础 - 图205$ %0A#card=math&code=PE%3D1-%5Cfrac1r%5Csum%7BY%2CX%5E%5Cstar%7D%20p%28y_j%7Cx_i%29%0A)

具体使用：看PPT，懒得抄
- 取信道矩阵 $（机器学习）信息论与编码基础 - 图206$ 的每一列的最大，加起来 $（机器学习）信息论与编码基础 - 图207$ 之后得到 $（机器学习）信息论与编码基础 - 图208$

Fano不等式：说明了信道疑义度和 $（机器学习）信息论与编码基础 - 图209$ 之间的关系

$（机器学习）信息论与编码基础 - 图210$ %5Cle%20H(P_E)%2BP_E%5Clog(r-1)%0A#card=math&code=H%28X%7CY%29%5Cle%20H%28P_E%29%2BP_E%5Clog%28r-1%29%0A)

其中 $（机器学习）信息论与编码基础 - 图211$ #card=math&code=H%28X%7CY%29) 是信道疑义度

PPT上有一个Fano不等式的图像

Fano不等式的物理意义：当信源、信道给定，信道疑义度就给定了译码错误概率的下限

2. 编码方法

加强输入符号序列间的相关性，降低信道疑义度 $（机器学习）信息论与编码基础 - 图212$ #card=math&code=H%28X%7CY%29)，从而给 $（机器学习）信息论与编码基础 - 图213$ 减小创造前提

汉明距离：

设两个长度为 $（机器学习）信息论与编码基础 - 图214$ 的码符号序列：
- $（机器学习）信息论与编码基础 - 图215$
- $（机器学习）信息论与编码基础 - 图216$
它们之间的汉明距离：（异或运算：同0异1）
- $（机器学习）信息论与编码基础 - 图217$ %3D%5Csum%7Bk%3D1%7D%5Enx%7Bik%7D%5Coplus%20y%7Bjk%7D%0A#card=math&code=D%28%5Calpha_i%2C%5Cbeta_j%29%3D%5Csum%7Bk%3D1%7D%5Enx%7Bi_k%7D%5Coplus%20y%7Bj_k%7D%0A)

性质：
- 非负性
- 对称性
- 三角不等式

最小汉明距离：在二元码C中，任意两个码字之间的汉明距离的最小值

最小汉明译码准则-MD：

最大似然译码准则用汉明距离的概念可表述为：收到 $（机器学习）信息论与编码基础 - 图218$ 后译成与之距离最小的输入码符号序列 $（机器学习）信息论与编码基础 - 图219$
汉明距离越小表示两个码符号序列越相似，这就是“最大似然”的含意

3. 有噪信道编码定理

联合 $（机器学习）信息论与编码基础 - 图220$ 典型序列：

联合 $（机器学习）信息论与编码基础 - 图221$ 典型序列是那些平均联合自信息以 $（机器学习）信息论与编码基础 - 图222$ 任意小地接近联合熵的 $（机器学习）信息论与编码基础 - 图223$ 长序列对的集合

联合渐进等分割性：

香农第二定理：
设有一离散无记忆平稳信道，其信道容量为 $（机器学习）信息论与编码基础 - 图224$ ，只要信道编码信息率 $（机器学习）信息论与编码基础 - 图225$ ，当码长 $（机器学习）信息论与编码基础 - 图226$ 足够大时，则至少存在一种编码，使译码错误概率任意小
香农第二定理指出了“高效率、高可靠性”的信道编码存在性，
- （1）“高效率”的含义是信息传输率接近信道容量;
- （2）“高可靠性” 的含义是译码差错任意小;
- （3）存在这种信道编码的必要条件是 $（机器学习）信息论与编码基础 - 图227$
只要码率小于信道容量，一个离散无记忆平稳信道的错误概率便可以做到想多小就多小

第七章限失真信源编码

失真函数：

非负函数 $（机器学习）信息论与编码基础 - 图228$ #card=math&code=d%28x_i%2Cy_j%29)
- 失真矩阵： $（机器学习）信息论与编码基础 - 图229$ %5D#card=math&code=D%3D%5Bd%28x_i%2Cy_j%29%5D)
函数形式可根据需要定义
- 常用失真函数有：见PPT
- 汉明失真
- 平方误差失真
- 绝对失真
- 相对失真
定量描述发出符号与接收符号之间的差异（失真）

平均失真度：

$（机器学习）信息论与编码基础 - 图230$ d(xi%2Cy_j)%0A#card=math&code=D%3D%5Csum%7Bi%3D1%7D%5En%5Csum_%7Bj%3D1%7D%5Emp%28x_iy_j%29d%28x_i%2Cy_j%29%0A)

矢量传输的失真度：

输入N长符号序列 $（机器学习）信息论与编码基础 - 图231$
输出N长符号序列 $（机器学习）信息论与编码基础 - 图232$
则
失真函数： $（机器学习）信息论与编码基础 - 图233$ %3D%5Csum%5EN%7Bi%3D1%7Dd(X_i%2CY_i)%0A#card=math&code=d%28%5Calpha%2C%5Cbeta%29%3D%5Csum%5EN%7Bi%3D1%7Dd%28X_i%2CY_i%29%0A)

N长信源序列的平均失真度 $（机器学习）信息论与编码基础 - 图234$ %0A#card=math&code=D_N%3D%5Cfrac1ND%28N%29%0A)

信源序列第 $（机器学习）信息论与编码基础 - 图235$ 个分量的平均失真度： $（机器学习）信息论与编码基础 - 图236$
则
如果是平稳信源： $（机器学习）信息论与编码基础 - 图237$

当信源和信道均为无记忆时 $（机器学习）信息论与编码基础 - 图238$ %3D%5Csum%5EN%7Bi%3D1%7DD_i%0A#card=math&code=D%28N%29%3D%5Csum%5EN%7Bi%3D1%7DD_i%0A)

保真度准则：

设预先规定的平均失真度为 $（机器学习）信息论与编码基础 - 图239$ ，压缩后的失真度为 $（机器学习）信息论与编码基础 - 图240$
保真度准则： $（机器学习）信息论与编码基础 - 图241$
$（机器学习）信息论与编码基础 - 图242$ 允许的试验信道：满足保真度准则的所有信道

率失真函数：

性质：
- $（机器学习）信息论与编码基础 - 图243$ #card=math&code=R%28D%29) 是关于 $（机器学习）信息论与编码基础 - 图244$ 的下凸函数
- 在定义区间是严格递减函数

香农第三定理：

只要满足 $（机器学习）信息论与编码基础 - 图245$ #card=math&code=R%3ER%28D%29)
当信源序列长度N足够大时，一定存在一种编码方法，使译码失真 $（机器学习）信息论与编码基础 - 图246$ ，其中 $（机器学习）信息论与编码基础 - 图247$ 是任意小的正数

第九章纠错编码

1. 基本概念

反馈重传（ARQ）：

发送端经编码后发出能够发现错误的码，接收端收到后经检验，如果发现传输中有错误，则通过反馈系统把这一判断结果反馈回发端，然后发送端把前面发出的信息重新传送一次，直到接收端认为正确地收到信息为止

前向纠错（FEC）：

发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译码器可以自动纠正错误
特点：
- 无需反馈
- 延迟小，实时性好

混合纠错（HEC）：

错误不严重时，自动纠错
错误严重时，反馈重传

纠错码分类：看PPT

按功能分
- 检错码：仅能检测误码
- 纠错码：可纠正误码
- 纠删码
按信息码元与监督码元之间的检验关系分：
- 线性码：满足线性关系，满足一组线性方程
- 非线性码
按信息码元与监督码元之间的约束方式不同分：
- 分组码：本码组的监督码元仅和本码组的信息元相关
- 卷积码
按信息码元在编码后是否保持原形式不变：
- 系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变
- 非系统码：信息位打乱，与编码前不同

2. 线性分组码

(n,k)分组码：

信息码组由 $（机器学习）信息论与编码基础 - 图248$ 个信息码元组成，共有 $（机器学习）信息论与编码基础 - 图249$ 个不同的信息码组, 即能表示 $（机器学习）信息论与编码基础 - 图250$ 个消息, 即码字的数目共有 $（机器学习）信息论与编码基础 - 图251$ ，这 $（机器学习）信息论与编码基础 - 图252$ 个码字的集合称为 (n,k) 分组码
编码器输出长度为 $（机器学习）信息论与编码基础 - 图253$ 的码字
附加了 $（机器学习）信息论与编码基础 - 图254$ 个校验码元

线性分组码分类：

汉明码
循环码
BCH码，RS码等

线性分组码一定满足封闭性：线性分组码中任意两个码字之和仍然是该码的码字

校验矩阵，生成矩阵：

以(7,3)线性分组码为例
- 码字为 $（机器学习）信息论与编码基础 - 图255$
- 其中 $（机器学习）信息论与编码基础 - 图256$ 为信息元， $（机器学习）信息论与编码基础 - 图257$ 为校验元
- 校验元可由下面方程组计算得到： $（机器学习）信息论与编码基础 - 图258$

即（因为二进制没有-， $（机器学习）信息论与编码基础 - 图259$ ，所以 $（机器学习）信息论与编码基础 - 图260$ 前没有负号） $（机器学习）信息论与编码基础 - 图261$

校验矩阵/监督矩阵： $（机器学习）信息论与编码基础 - 图262$ 上面方程组对应的矩阵（有几个校验位，校验矩阵就有几行）（ $（机器学习）信息论与编码基础 - 图263$ 为单位矩阵） $（机器学习）信息论与编码基础 - 图264$

对(n,k)线性分组码，校验矩阵为 $（机器学习）信息论与编码基础 - 图265$ %5Ctimes%20n#card=math&code=%28n-k%29%5Ctimes%20n) 维矩阵

生成矩阵： $（机器学习）信息论与编码基础 - 图266$ ( 信息位在前，校验位在后 )（ $（机器学习）信息论与编码基础 - 图267$ 为单位矩阵）
在上面方程组的基础上增加： $（机器学习）信息论与编码基础 - 图268$ ， $（机器学习）信息论与编码基础 - 图269$ ， $（机器学习）信息论与编码基础 - 图270$ $（机器学习）信息论与编码基础 - 图271$

生成矩阵为 $（机器学习）信息论与编码基础 - 图272$ 维

监督矩阵和生成矩阵的关系：

$（机器学习）信息论与编码基础 - 图273$
线性系统码的 $（机器学习）信息论与编码基础 - 图274$ 和 $（机器学习）信息论与编码基础 - 图275$ 之间可以直接互换： $（机器学习）信息论与编码基础 - 图276$ （ $（机器学习）信息论与编码基础 - 图277$ ， $（机器学习）信息论与编码基础 - 图278$ ）

线性分组码的伴随式：又称监督子、校验子

伴随接收码字的n-k维向量，反映“信道对码字造成的干扰”
设发送码字为 $（机器学习）信息论与编码基础 - 图279$ ，接收到的码元序列为 $（机器学习）信息论与编码基础 - 图280$ ，令伴随式 $（机器学习）信息论与编码基础 - 图281$ 或 $（机器学习）信息论与编码基础 - 图282$
- $（机器学习）信息论与编码基础 - 图283$ 时，说明 $（机器学习）信息论与编码基础 - 图284$ 是一个码字，传输过程没有产生误码
对于已给线性分组码，一个伴随式对应一种错误图样，即可纠正对应的错误。则n-k位的伴随式有 $（机器学习）信息论与编码基础 - 图285$ 种，其与可纠正错误数目u的关系
纠错步骤：
1. 确定校验矩阵 $（机器学习）信息论与编码基础 - 图286$
2. 求解伴随式： $（机器学习）信息论与编码基础 - 图287$
3. 根据伴随式，推断出错码元位置，求解错误图样 $（机器学习）信息论与编码基础 - 图288$
4. 纠错 $（机器学习）信息论与编码基础 - 图289$

完备码：

$（机器学习）信息论与编码基础 - 图290$

伴随式个数与错误图样个数相同的码，被称为完备码
上式等号成立则为完备码

线性分组码最小汉明距离的判定方法1

设 $（机器学习）信息论与编码基础 - 图291$ 为线性分组码的最小汉明距离
该码具备纠正 $（机器学习）信息论与编码基础 - 图292$ 个以内错误的充分必要条件是 $（机器学习）信息论与编码基础 - 图293$ ，看PPT上的图
该码具备检测 $（机器学习）信息论与编码基础 - 图294$ 个以内错误的充分必要条件是 $（机器学习）信息论与编码基础 - 图295$
该码具备纠正 $（机器学习）信息论与编码基础 - 图296$ 个错误，同时可以发现 $（机器学习）信息论与编码基础 - 图297$ #card=math&code=l%28l%3Et%29) 个错误的充分必要条件是 $（机器学习）信息论与编码基础 - 图298$

线性分组码最小汉明距离的判定方法2

若H中的任意 t 列线性无关，而存在 t +1 列线性相关，则该码的最小汉明距离 $（机器学习）信息论与编码基础 - 图299$ 为 $（机器学习）信息论与编码基础 - 图300$

3. 汉明码

汉明码：

是一种能够纠正单个错误的线性分组码
最小码距： $（机器学习）信息论与编码基础 - 图301$
设监督码共有 $（机器学习）信息论与编码基础 - 图302$ 位，则汉明码长必为 $（机器学习）信息论与编码基础 - 图303$
设计汉明码：看PPT例题：设计一个r=4的汉明码

4. 循环码

循环码：

循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组

码多项式：

设循环码码字 $（机器学习）信息论与编码基础 - 图304$
则码多项式： $（机器学习）信息论与编码基础 - 图305$ %3Dc_1x%5E%7Bn-1%7D%2Bc_2x%5E%7Bn-2%7D…%2Bc_n#card=math&code=C%28x%29%3Dc_1x%5E%7Bn-1%7D%2Bc_2x%5E%7Bn-2%7D…%2Bc_n) （ x仅是码元位置的标记，并无取值的含义）

生成多项式：

从码中取出一个前面 $（机器学习）信息论与编码基础 - 图306$ 位都是0的码字，定义这个码字的码多项式为生成多项式 $（机器学习）信息论与编码基础 - 图307$ #card=math&code=g%28x%29) （该多项式的次数为 $（机器学习）信息论与编码基础 - 图308$ ，即监督码元的位数）
所有码多项式必定为 $（机器学习）信息论与编码基础 - 图309$ #card=math&code=g%28x%29) 的倍式
为了保证构成的生成矩阵G的各行线性不相关，通常用 $（机器学习）信息论与编码基础 - 图310$ #card=math&code=g%28x%29) 来构造生成矩阵： $（机器学习）信息论与编码基础 - 图311$ %5C%5C%0Ax%5E%7Bk-2%7Dg(x)%5C%5C%0A…%5C%5C%0Ag(x)%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A#card=math&code=G%3D%5Cleft%5B%0A%5Cbegin%7Barray%7D%7B1%7D%0Ax%5E%7Bk-1%7Dg%28x%29%5C%5C%0Ax%5E%7Bk-2%7Dg%28x%29%5C%5C%0A…%5C%5C%0Ag%28x%29%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A)

例如 (7,3) 循环码 $（机器学习）信息论与编码基础 - 图312$ %3Dx%5E4%2Bx%5E2%2B1#card=math&code=g%28x%29%3Dx%5E4%2Bx%5E2%2B1)

$（机器学习）信息论与编码基础 - 图313$ %5C%5C%0Axg(x)%5C%5C%0Ag(x)%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A%3D%5Cleft%5B%0A%5Cbegin%7Barray%7D%7B1%7D%0Ax%5E6%2Bx%5E4%2Bx%5E2%5C%5C%0Ax%5E5%2Bx%5E3%2Bx%5C%5C%0Ax%5E4%2Bx%5E2%2B1%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A%3D%5Cleft%5B%0A%5Cbegin%7Barray%7D%7B1%7D%0A1%260%261%260%261%260%260%5C%5C%0A0%261%260%261%260%261%260%5C%5C%0A0%260%261%260%261%260%261%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A#card=math&code=G%3D%5Cleft%5B%0A%5Cbegin%7Barray%7D%7B1%7D%0Ax%5E2g%28x%29%5C%5C%0Axg%28x%29%5C%5C%0Ag%28x%29%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A%3D%5Cleft%5B%0A%5Cbegin%7Barray%7D%7B1%7D%0Ax%5E6%2Bx%5E4%2Bx%5E2%5C%5C%0Ax%5E5%2Bx%5E3%2Bx%5C%5C%0Ax%5E4%2Bx%5E2%2B1%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A%3D%5Cleft%5B%0A%5Cbegin%7Barray%7D%7B1%7D%0A1%260%261%260%261%260%260%5C%5C%0A0%261%260%261%260%261%260%5C%5C%0A0%260%261%260%261%260%261%0A%5Cend%7Barray%7D%0A%5Cright%5D%0A)

生成多项式直接构造的生成矩阵，对应的码一定不是系统码

系统循环码的编码方法：

用 $（机器学习）信息论与编码基础 - 图314$ 乘信息多项式 $（机器学习）信息论与编码基础 - 图315$ #card=math&code=m%28x%29) （把信息码左移 $（机器学习）信息论与编码基础 - 图316$ 位，即附加 $（机器学习）信息论与编码基础 - 图317$ 个0）
求 $（机器学习）信息论与编码基础 - 图318$ #card=math&code=r%28x%29) ：化简 $（机器学习）信息论与编码基础 - 图319$ x%5E%7Bn-k%7D%7D%7Bg(x)%7D#card=math&code=%5Cfrac%7Bm%28x%29x%5E%7Bn-k%7D%7D%7Bg%28x%29%7D)，余式为监督多项式/监督位 $（机器学习）信息论与编码基础 - 图320$ #card=math&code=r%28x%29)
系统码： $（机器学习）信息论与编码基础 - 图321$ %3Dm(x)x%5E%7Bn-k%7D%2Br(x)#card=math&code=C%28x%29%3Dm%28x%29x%5E%7Bn-k%7D%2Br%28x%29)

看一下PPT上例题9.5。

系统循环码生成多项式的一般表示形式为 $（机器学习）信息论与编码基础 - 图322$

得到系统循环码的生成矩阵有两种方法：

先求监督位
- 用典型生成阵的信息位所对应多项式左移n-k位，对生成多项式除法求余，得到相应监督多项式（监督位），继而得到生成矩阵
先求非系统码的生成矩阵：
- 根据生成多项式和循环码的定义，得到非系统码的生成矩阵，然后对该矩阵进行初等变换，变成系统码的生成矩阵

Part 3 计算题

记公式：用维拉图

第二章

符号等概分布时， $（机器学习）信息论与编码基础 - 图323$ #card=math&code=H%28X%29) 熵最大为 $（机器学习）信息论与编码基础 - 图324$

马尔可夫信源的极限熵的计算： $（机器学习）信息论与编码基础 - 图325$

二阶马尔可夫信源的符号稳态分布和状态稳态分布

第二章作业：补充题

第三章

互信息量： $（机器学习）信息论与编码基础 - 图326$ %3D%5Clog%5Cfrac%7Bp(x_i%7Cy_j)%7D%7Bp(x_i)%7D#card=math&code=I%28x_i%3By_j%29%3D%5Clog%5Cfrac%7Bp%28x_i%7Cy_j%29%7D%7Bp%28x_i%29%7D)

平均互信息的计算： $（机器学习）信息论与编码基础 - 图327$ #card=math&code=I%28X%3BY%29)

先求概率分布（矩阵）：条件分布 $（机器学习）信息论与编码基础 - 图328$ 和边缘分布 $（机器学习）信息论与编码基础 - 图329$
求联合概率： $（机器学习）信息论与编码基础 - 图330$ %3Dp(x_i)p(y_j%7Cx_i)#card=math&code=p%28x_i%2Cy_j%29%3Dp%28x_i%29p%28y_j%7Cx_i%29) 矩阵中元素相乘
$（机器学习）信息论与编码基础 - 图331$ %3D-%5Csum%20p(x_i%2Cy_j)%5Clog%20p(y_j%7Cx_i)#card=math&code=H%28Y%7CX%29%3D-%5Csum%20p%28x_i%2Cy_j%29%5Clog%20p%28y_j%7Cx_i%29)
$（机器学习）信息论与编码基础 - 图332$ %3DH(Y)-H(Y%7CX)#card=math&code=I%28X%3BY%29%3DH%28Y%29-H%28Y%7CX%29)

第三章例题3.4

信道容量的计算： $（机器学习）信息论与编码基础 - 图333$ #card=math&code=C%3D%5Cmax%20I%28X%3BY%29)

对称信道的信道容量
1. 设输入等概分布 $（机器学习）信息论与编码基础 - 图334$
2. 求 $（机器学习）信息论与编码基础 - 图335$ #card=math&code=I%28X%3BY%29)

第四章

香农公式：计算 AWGN 信道的信道容量

$（机器学习）信息论与编码基础 - 图336$ %3DW%5Clog(1%2B%5Cfrac%7BP_S%7D%7BP_N%7D)%0A#card=math&code=C%3DW%5Clog%281%2BSNR%29%3DW%5Clog%281%2B%5Cfrac%7BP_S%7D%7BP_N%7D%29%0A)

$（机器学习）信息论与编码基础 - 图337$ ：信道频带宽度，简称带宽，单位 Hz

$（机器学习）信息论与编码基础 - 图338$ ：signal to noise ratio，信噪比，是信号功率（单位为W）与噪声功率（单位为W）的比值

$（机器学习）信息论与编码基础 - 图339$ ：信号发射功率

$（机器学习）信息论与编码基础 - 图340$ ：高斯白噪声的单边功率谱密度

香农公式的计算：

例如题目给出信噪比为20dB
1. $（机器学习）信息论与编码基础 - 图341$

解得 $（机器学习）信息论与编码基础 - 图342$

代香农公式

第六章

MAP译码准则（最大后验概率准则）

取 $（机器学习）信息论与编码基础 - 图343$ 的每一列的最大，加起来 $（机器学习）信息论与编码基础 - 图344$ 之后得到 $（机器学习）信息论与编码基础 - 图345$

ML译码准则

取信道矩阵 $（机器学习）信息论与编码基础 - 图346$ 的每一列的最大，加起来 $（机器学习）信息论与编码基础 - 图347$ 之后得到 $（机器学习）信息论与编码基础 - 图348$

最小汉明距离译码：

码能够纠正几位码元的错误： $（机器学习）信息论与编码基础 - 图349$
$（机器学习）信息论与编码基础 - 图350$

其中 $（机器学习）信息论与编码基础 - 图351$ 为最小汉明距离

第九章

求系统码的码字：

算n, k
用 $（机器学习）信息论与编码基础 - 图352$ 乘信息多项式 $（机器学习）信息论与编码基础 - 图353$ #card=math&code=m%28x%29) （把信息码左移 $（机器学习）信息论与编码基础 - 图354$ 位，即附加 $（机器学习）信息论与编码基础 - 图355$ 个0）
求 $（机器学习）信息论与编码基础 - 图356$ #card=math&code=r%28x%29) ：化简 $（机器学习）信息论与编码基础 - 图357$ x%5E%7Bn-k%7D%7D%7Bg(x)%7D#card=math&code=%5Cfrac%7Bm%28x%29x%5E%7Bn-k%7D%7D%7Bg%28x%29%7D)，余式为监督多项式/监督位 $（机器学习）信息论与编码基础 - 图358$ #card=math&code=r%28x%29)
系统码： $（机器学习）信息论与编码基础 - 图359$ %3Dm(x)x%5E%7Bn-k%7D%2Br(x)#card=math&code=C%28x%29%3Dm%28x%29x%5E%7Bn-k%7D%2Br%28x%29)

判断是否是误码：

由 $（机器学习）信息论与编码基础 - 图360$ #card=math&code=g%28x%29) 写出 $（机器学习）信息论与编码基础 - 图361$
1. 注意要补 $（机器学习）信息论与编码基础 - 图362$ 个0
2. $（机器学习）信息论与编码基础 - 图363$ 进行初等行变换，将左边化成单位矩阵
$（机器学习）信息论与编码基础 - 图364$
$（机器学习）信息论与编码基础 - 图365$ 判断 $（机器学习）信息论与编码基础 - 图366$ 是否是零向量（如果结果是零向量，就没有出错）

Part 4 测试

看着名词，回想起概念：

第一章

消息/信号/信息的区别

第二章

自信息/信息熵的物理意义/性质，N维平稳信源，扩展信源的熵，马尔科夫链的熵，时齐马尔科夫链，遍历性，二阶马尔可夫信源的符号稳态分布/状态稳态分布，信源存在剩余度的原因

第三章

信道疑义度，互信息量的物理意义，互信息量的性质，平均互信息量的物理意义，平均互信息的性质，维拉图，信道容量，信息传输率，配对，信道剩余度，BSC信道的信道容量，对称信道

第五章：

信源/信道编码的目的，非奇异码，唯一可译码，平均码长，定长信源编码定理，Kraft不等式，编码信息率，编码效率，香农第一定理

第六章：

译码规则，（平均）错误译码概率，MAP准则，ML准则，Fano不等式物理意义，汉明距离，最小汉明译码准则，联合渐进等分割性，香农第二定理

第七章：

失真函数，失真矩阵，平均失真度，保真度准则，率失真函数的性质，香农第三定理

第九章：

反馈重传，前向纠错，混合纠错，(n,k)分组码，线性分组码的分类，封闭性，校验矩阵/生成矩阵的关系，伴随式，纠错步骤，完备码，线性分组码最小汉明距离的判定方法，设计一个r=4的汉明码
循环码，码多项式，生成多项式，系统循环码的编码方法，判断是否是误码

（机器学习）信息论与编码基础