目录可能有点bug,刷新下就好了

本文随复习进度更新

第1章 绪论

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

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

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

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

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

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

完整的通信系统模型

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

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

第2章 信源和信息熵

2.1信源

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

1.连续信源

2.离散信源

2.2离散信源熵和互信息

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

自信息量
两个消息xi,yj同时出现的联合自信息量

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

当xi,yj相互独立时,有p(xiyj)=p(xi)p(yj),那么就有I(xiyj)=I(xi)+I(yj)。

2.条件自信息量(bit)

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

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

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

4.条件熵

给定Y (即各个yi)

H(X/Y)表示已知Y后,X的不确定度。

给定X

5.联合熵

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

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

6.互信息

先验概率:信息X发出的各个符号消息的集合,以及它们的概率分布.

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

互信息定义:收到消息y后对x的疑问(获得的关于时间x的信息量)

互信息
平均互信息量

常用公式:p(xiyj)=p(xi)p(yj/xi)

推导性质: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.序列熵

无记忆
有记忆

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

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

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

状态转移概率Pij(m,n):m时刻系统处于状态Si经过n-m步转移到Sj的概率

一步状态转移概率:Pij(m):m时刻系统处于状态Si经过1步转移到Sj的概率

一步状态转移概率矩阵:其中Pij=(Sj/Si)

pij(k)从Si状态转到Sj状态需要K步

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

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

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

非周期性

所有pii(n)的n中没有比1大的公因子

状态极限概率

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

马尔可夫信源极限熵

(其中P(Si)代入Wi计算)

2.5冗余度

冗余度
信息效率

第3章 无失真信源编码

3.1编码的定义

编码:设信源X输出的符号集{x1,x2...},将信源发出的符号xi转换成0,1符号组成的码符号序列(码字)。

非奇异码: 单个符号对应不同的码字

唯一可译码:任意有限长的码元序列,只能被唯一地分割成一个个的码字

非即时码和即时码:如果接收端收到一个完整的码字后,不能立即译码,还需等下一个码开始接收后才能判断是否可以译码,这样的码叫做非即时码。

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

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

3.2 定长编码定理(了解)

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

KL≥H(X) *粗斜体X表示序列

(无记忆平稳信源符号X1X2...XL L:符号个数 HL(X)=H(X)/L:平均符号熵(bit/序列) H(X)=H(X1X2...XL)=(:信源序列的熵)--编码-->(用KL个符号进行编码 m:每个符号可能值数)

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

3.3变长编码定理(了解)

3.4最佳编码

香农编码

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

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

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

哈夫曼编码(重点)

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

第4章 限失真信源编码

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

信道矩阵
信道模型

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

d(xi,yj)是失真函数

x是信源符号

y是编码器输出符号

失真矩阵

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

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

无失真时:R=H(X)

有失真时:R=R(D)=H(X)-H(X/Y)≤H(X)

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

1.Dmin和R(Dmin)

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

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

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

2.Dmax和R(Dmax)

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

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

R(D)定义域

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

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

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

5.1信道模型

转移概率矩阵

x:输入

y:输出

二进制离散信道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)

二进制码:

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

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)=xn-k+gn-k-1xn-k-1+...+g2x2+g1x+1 *n-k次项的系数是1 g(x)一定是(xn+1)的因子

生成多项式不唯一

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

系统循环码

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

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

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

6.5卷积码

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

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

生成子矩阵

glpq表示第P输入行,第l时延列对第q个输出码元的影响

转移函数矩阵

G(D)=G0+G1D+...+GLDL D:一个时延

编码器

G(D)=

状态流图

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

以(3,2,1)G(D)=(1,1+D, 1+D+D2 )为例

编码器状态定义
状态流图

网格图

上图输入信息序列是10110

第7章 密码学

7.1基础知识

加密Ek: 对真实数据施加变化的过程

明文M:  加密前的真实数据

密文C: 加密后输出的数据。

解密Dk:  从密文恢复出明文的过程。

密钥K:  变换变换过程中使用的参数。

密码体制: 完成加密和解密的算法

破译: 把密文转换成明文的过程

密码体制:

DES(对称体制):单密钥,传统体制,常用于加密私人文件

RSA(非对称体制):双密钥,公开密钥体制,常用于数字签名

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

7.2数据加密标准DES

密钥表计算

16个子密钥是由同一个64比特的密钥源循环移位产生。密钥源中56比特是随机的,所有8的倍数位是为奇偶校验而设。左图为计算子密钥的流程图,首先对64比特的密钥源进行第一次置换选择,变成56比特.

7.3公开密钥加密法

数字签名过程

数字前面验证过程

终端A操作:

      与终端B预先协商好通信过程中所使用到的对称加密算法、非对称加密算法和哈希函数;

      1) 采用对称加密算法(密钥称之为会话密钥)对传输信息进行加密得到密文,确保传输信息的保密性;

      2) 使用终端B的公钥对会话密钥进行加密,确保传输信息的保密性以及信息接收方的不可否认性;

      3) 采用哈希函数(生成文件摘要)确保传输信息的完整性,并使用自己的私钥对文件摘要进行签名(得到数字签名),确保信息发送方的不可否认性;

       将密文、加密后的会话密钥和数字签名打包封装(放到一起)后,通过网络传输给终端B。

终端B操作:

       1) 使用自己的私钥对终端A加密的会话密钥进行解密,得到准会话密钥;

       2)使用准会话密钥对得到的密文进行解密,得到准明文;

       3) 使用终端A的公钥对得到的数字签名进行解密,得到准明文摘要;

       4) 使用哈希函数计算得到准明文摘要;

       将计算得到的摘要与准明文摘要进行比较,若相同则表明文件安全传输成功。