信息论与编码 知识点总结

本文随复习进度更新

第1章 绪论

信息科学：研究如何获取信息，并完成它的传输、交换、处理、检测、识别、存储、显示等功能的科学。

信息论：信息科学的主要理论基础之一。它研究信息的基本理论，主要研究可能性和存在性问题，为具体实现提供理论依据。

信息：信息是指各个事物运动的状态及状态变化的方式。

消息：消息是指包含有信息的语言、文字和图像等。

信号：信号是信息的载荷子或载体，是物理性的。如电信号、光信号等。

信息的基本概念在于它的不确定性，任何已确定的事物都不含有信息

信源编码的作用：增加系统的有效性（把信源发出的消息变换成由二进制码元组成的代码组以提高通信系统传输消息的效率）

信道编码的作用：增加系统的可靠性（在信源编码输出代码组上有目的地增加一些监督码元，使之具有纠错检错能力）

第2章 信源和信息熵

2.1信源

描述：用随机变量来表示信源

1.连续信源

2.离散信源

2.2离散信源熵和互信息

1.自信息量&不确定度（bit)

不确定度：表征该事件的特性 信息量：事件发生后给予观察者的信息量

当x_i,y_j相互独立时，有p(x_iy_j)=p(x_i)p(y_j)，那么就有I(x_iy_j)=I(x_i)+I(y_j)。

2.条件自信息量(bit)

3.信源的平均不确定度（平均信息量、信源熵）(bit/符号）：

信源中各个符号不确定度的数学期望

平均自信息量：消除信源不确定度时所需要的信息的量度，即收到一个信源符号，全部解除了这个符号的不确定度

4.条件熵

给定Y （即各个yi)

5.联合熵

X和Y同时发生的不确定度

推导性质 H(XY)=H(X)+H(Y/X)，H(XY)=H(Y)+H(X/Y)

6.互信息

先验概率：信息X发出的各个符号消息的集合，以及它们的概率分布．

后验概率：当信宿收到一个符号消息后，信宿可以计算的信源各消息的条件概率．

互信息定义：收到消息y后对x的疑问（获得的关于时间x的信息量）

常用公式：p(x_iy_j)＝p(x_i)p(y_j/x_i)

推导性质：I(X;Y)=H(X)-H(X/Y)；I(Y;X)=H(Y)-H(Y/X)=I(X;Y)．

信息=先验不确定性-后验不确定性=不确定性减少的量

7.计算题常用概率论公式

7.熵的性质

①非负性②对称性(变元可以互换)③确定性(有一个符号的出现概率为1，信源熵就等于零)

④香农辅助定理：对于任意n维概率矢量P=(p1,p2，…，pn)和Q=(q1，q2，…，qn)如下不等式成立

⑤最大熵定理：离散无记忆信源输出M个不同的信息符号，当且仅当各个符号出现概率相等时，熵最大。

⑥条件熵小于无条件熵

2.3连续信源的熵和互信息

连续信源的不确定度应为无穷大：因为连续信源可以假设是一个不可数的无限多个幅度值的信源，需要无限多个二进制比特来表示，因而它的熵为无穷大(绝对熵)

1.信源熵

相对熵（熵的部分值）：

2.最大熵定理

限峰功率最大熵定理：对于定义域为有限的随机矢量X，当它是均匀分布时具有最大熵。

限平均功率最大熵定理：对于相关矩阵一定的随机变量X，当它是正态分布时具有最大熵。

2.4离散序列信源的熵

*无下标的X表示序列

1.序列熵

平均符号熵H_L(X)=H(X)/L

2.离散有记忆信源的序列熵-齐次马尔可夫信源

当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源，信源每次发出的符号只与前m个符号有关。

状态转移概率P_ij(m,n)：m时刻系统处于状态S_i经过n-m步转移到S_j的概率

一步状态转移概率：P_ij(m)：m时刻系统处于状态S_i经过1步转移到S_j的概率

一步状态转移概率矩阵：其中P_ij=(S_j/S_i)

p_ij^(k)从S_i状态转到S_j状态需要K步

马尔可夫信源状态稳定分布概率存在的条件：

不可约性：每个状态都可以经过有限步进入任意其它状态

（对任意一对i和j，都存在至少一个k，使pij^(k) >0）

非周期性：

所有p_ii⁽ⁿ⁾的n中没有比1大的公因子

状态极限概率

常用联合以下两方程求解：

马尔可夫信源极限熵

（其中P(S_i)代入Wi计算）

2.5冗余度

第3章 无失真信源编码

3.1编码的定义

编码：设信源X输出的符号集｛x₁,x₂...｝，将信源发出的符号x_i转换成0，1符号组成的码符号序列(码字)。

平均码长计算：K=Σ每个码字的概率*码长

信息传输速率R=H(X)/K

3.2 定长编码定理（了解）

只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真.

K_L≥H（X） *粗斜体X表示序列

（无记忆平稳信源符号X₁X₂...X_L L：符号个数 H_L(X)=H(X)/L：平均符号熵(bit/序列） H(X)=H(X₁X₂...X_L)=(:信源序列的熵）--编码-->（用K_L个符号进行编码 m:每个符号可能值数）

δ:错误概率 平均码长（平均每个符号二进制位数）

3.3变长编码定理（了解）

3.4最佳编码

香农编码

列表：符号、累加概率、-logP(X_i) 、码长ki、 码字

码长ki取决于 -logP(X_i) ~-logP(X_i) +1

码字是累加概率2进制形式保留ki位

哈夫曼编码(重点）

始终按概率从大到小排序，每次取后两个相加后重新排序，直到1为止。

第4章 限失真信源编码

要规定失真限度，必须先有一个定量的失真测度

4.1平均失真和信息率失真函数

平均失真：失真函数的数学期望

信息率失真函数R(D)：在一定允许失真度D的条件下，用尽可能少的码符号(信息率尽可能小)来传送信源消息，以提高通信系统的可靠性。

无失真时：R=H(X)

有失真时：R=R(D)=H(X)－H(X/Y)≤H(X)

H(X/Y)：由于压缩编码损失的信息

1.D_min和R(D_min)

D_min=0:只有当失真矩阵中每行至少有一个零元素

求概率矩阵：失真矩阵每行最小数对应转移概率矩阵相同位置为1，转移概率矩阵其它位置是0。

R(D_min)=R(0)=H(X)：只有当失真矩阵中每行至少有一个零，并每一列最多只有一个零。

2.D_max和R(D_max)

R(Dmax)=0:选择所有满足R(D)＝0中D的最小值，定义为R(D)定义域的上限D_max，即

R(D)＝0就是I(X;Y)＝0，这时试验信道输入与输出是互相独立的，所以条件概率p(y_j/x_i)与x_i无关。

R(D)定义域

pi:输入x的概率分布函数 在j（失真矩阵的列）分别为1，…，m找到最小和

j*表示min中选出的列 p(y_j*)=1

第5章 信道模型和信道容量

5.1信道模型

二进制离散信道BSC：对称的二进制输入、输出（输入位数=输出位数）

准对称BSC：

输入对称：转移概率矩阵P的每一行都是第一行的置换（包含同样元素）

输出不对称

离散无记忆信道DMC：（输出位数＞输入位数）

对称DMC信道：同时满足输入、输出对称的DMC信道

输入对称：转移概率矩阵P的每一行都是第一行的置换（包含同样元素）

输出对称：转移概率矩阵P的每一列都是第一列的置换（包含同样元素）

5.2信道容量

5.2.1 DMC信道容量

Q：输出的符号个数

单位：bit/符号

对称DMC：

5.2.2 准BSC信道的容量

当信道输入符号等概分布时，准对称DMC信道达到其信道容量C。

第6章 信道编码

6.1有扰离散信道的编码定理

6.1.1差错&差错控制系统分类

1.差错比特

差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示。

差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示。

*对于二进制传输系统，符号差错等效于比特差错，对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。

2.差错图样

定量地描述信号的差错，收、发码之“差” ：

                                差错图样E＝发码C－ 收码R （模M）

二进制码：

差错图样中的“１”既是符号差错也是比特差错，差错的个数叫汉明距离。

3.差错图样类型

随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；

突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。

4差错控制系统分类

前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错

反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码

例：奇偶校验、CRC冗余校验。

混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力

6.1.2 矢量空间与码空间

K:信息序列长度 n:码字长度 q:进制数

n维空间需要n个基地 描述点在该空间的位置需要n个分量

信源编码经过编码器后形成的码字构成码集

6.1.3 矢量空间与码空间

6.1.4 信道编码定理

6.2 纠错编译码的基本原理与分析方法

6.2.1译码方法

先确定译码规则

最佳译码（最大后验概率译码）：在已知r的条件下找到可能性最大的发码作为译码估值

最大似然译码：在已知r的条件下使先验概率最大的译码方法

6.3 线性分组码

系统形式的生成矩阵

6.3.1 伴随式与标准阵列译码

6.3.4汉明码

汉明码概念——汉明码是能纠正单个错误的线性分组码。如(n,k)码，它有以下特点：

码长             n=2m-1

                  信息码位      k=2m-m-1

                  监督码位      r=m=n-k

                 最小码距      d=3

                  纠错能力      t=1

码集C中任何一个码字的循环移位仍是码字。

6.4循环码

循环码是线性码的一个子类

码多项式C(x)=m(x)g(x) m(x)：信息多项式 g(x)：生成多项式

g(x)=x^n-k+g_n-k-1x^n-k-1+...+g₂x²+g₁x+1 *n-k次项的系数是1 g(x)一定是(xⁿ+1)的因子

生成多项式不唯一

校验多项式h(x) xⁿ+1=g(x)h(x) 任何码多项式C(x)*h(x)作模xⁿ+1运算一定为0，非码字与h(x)乘积必不为0

系统循环码

码字前K位照搬信息位，后n-k位为校验位 系统循环码的码多项式：C(x)=x^n-km(x)+R(x)

x^n-km(x):信息位预乘x^n-k即实现右移n-k位

x^n-km(x)除以g(x)得余式r(x)

6.5卷积码

将信息序列分隔成长度k的一个个分组,某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的L个分组,L＋1为约束长度。

（n,K,L) n：码长 K：信息序列长度 编码效率R=k/n

生成子矩阵

转移函数矩阵

G(D)=G⁰+G¹D+...+G^LD^L D:一个时延

编码器

状态流图

sn状态，位数为N约束长度 输入信息/输出码字

以（3，2，1）G(D)=(1,1+D, 1+D+D² )为例

网格图

上图输入信息序列是10110

第7章 密码学

7.1基础知识

密码体制：

根据加密时对明文数据的处理方式的不同，可以把密码分为换位密码和替代密码两类。

7.2数据加密标准DES

7.3公开密钥加密法

数字签名过程

数字前面验证过程