信息论与编码

第一章 绪论

1． 信息是指各个事物运动的状态及状态变化的方式。 2． 消息是指包括信息的语言、文字和图像等。

3． 信号是消息的物理体现，为了在信道上传输消息，就必须把消息加载到具有某种物理特性的信号上去。

信号是信息的载荷子或载体。

4． 信息的基本概念在于它的不确定性，任何已确定的事物都不含有信息。 5． 信息的特征：（1）接收者在收到信息之前，对其内容是未知的。（2）信息是能使认识主体对某一事物

的未知性或不确定性减少的有用知识。（3）信息可以产生，也可以消失，同时信息可以被携带、存储及处理。（4）信息是可以量度的，信息量有多少的差别。 6． 编码问题可分解为3类：信源编码、信道编码、加密编码。

信源编码：信源编码器的作用有两个：一是把信源发出的消息变换成由二进制码元组成的代码组，这种代码组就是基带信号；另一个作用是通过信源编码可以压缩信源的冗余度，以提高通信系统 传输消息的效率。信源编码可分为无失真信源编码和限失真信源编码。

信道编码：信道编码器的作用是在信源编码器输出的代码组上有目的地增加一些监督码元，使之具有检错或纠错的能力。

加密编码：加密编码是研究如何隐蔽消息中的信息内容，以便在传输过程中不被窃听，提高通信系统的安全性。 7．编码效率?理论上传输的最少信息量

实际需要的信息量第二章 信源与信息熵

1．每次只发出一个符号代表一个消息的信源叫做发出单个符号的无记忆信源。

2．由一系列符号组成，这种用每次发出1组含2个以上符号序列来代表一个信息的信源叫做发出符号序列的信源。

3．信源发出的序列的统计性质与时间的推移无关，是平稳的随机序列。

4．当信源的记忆长度为m+1时，该时刻发出的符号与前m个符号有关联性，而与更前面的符号无关，这种有记忆信源叫做m阶马尔可夫信源。若上述条件概率与时间起点无关，则信源输出的符号序列可看成齐次马尔可夫链，这样的信源叫做齐次马尔可夫信源。 5．例题：稳态分布概率|稳定后的符号概率分布：

?1/21/2?0??1/21/20?1/32/3??0?01/32/3?状态转移概率矩阵[p(s|s)]=?? ????符号条件概率矩阵：[p(sj|si)]=?ji?1/43/4??1/43/400?????4/51/501/54/5????0令各稳态分布概率为W1,W2,W3,W4： W1?11131124W1?W3 W2?W1?W3 W3?W2?W4 W4?W2?W4 24243535W1?W2?W3?W4?1 得稳态分布的概率：W1=3/35 W2=6/35 W3=6/35 W4=4/7稳定后的符号

概率分布：

131616149p(a1)??p(a1|si)p(si)?????????

2353354355735i1326364426p(a2)??p(a2|si)p(si)?????????

2353354355735i6．定义具有概率为p(xi)的符号xi的自信息量为：

I(xi)??logp(xi)

7．自信息量具有下列特性：（1）

p(xi)?1,I(xi)?0（2）p(xi)?0,I(xi)??（3）非负性（4）

单调递减性（5）可加性

8．信源熵是在平均意义上来表征信源的总体特征，它是信源X的 函数，一般写成H（X）。 9．平均自信息量、平均不确定度、信源熵：H(X)???p(x)logp(x)

iii10．条件熵：H(X|Y)???p(xi,yj)logp(xi|yj)

ij11．联合熵： 12

H(X|Y)???p(xi,yj)logp(xi,yj)

ij．联合熵H(X,Y)与熵H(X)及条件熵H(Y|X)的关系：

H(X,Y)?H(X)?H(Y|X)?H(X)?H(X|Y)

13.互信息:

I(X;Y)??p(xi,yj)logijp(yj|xi)p(yj)??p(xi)p(yj|xi)logi,jp(yj|xi)p(yj)

14.熵的性质：非负性，对称性，确定性，极值性。 （1）非负性：H(0,1)?（2）对称性：H(p1,H(1,0,0,?0)?0H(X)?H(p1,p2?pn)?0

p2?pn)?H(p2,p1?pn)

H(1,0,0,?0)?0（只要信源符号表中有一个符号出现概率为1，信源熵就等

（3）确定性：H(0,1)?于零）

（4）香农辅助定理：对于任意n维概率矢量

nnH(p1,p2?pn)和Q(p1,p2?pn)，下列不等式成立：

H(p1,p2?pn)???pilogpi???pilogqi

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

（6）条件熵小于无条件熵：条件熵小于信息熵，当且仅当 y和x相互独立时，p(y|号。

15．数据处理过程中会丢失一些信息，绝不会创造新信息，即所谓信息不增性。 16．无记忆平稳信源序列熵：HL(X)?17．平均符号（信息）熵：HL(X)?x)?p(y)，取等

1H(X)?H(X)LH(X)?LH(X)

1H(X)?H(X) L第三章

1.信道的分类

根据用户数可以分为，单用户和多用户；根据输入端和输出端可以分为无反馈和反馈信道；根据信道参数

与时间可以分为固定参数和时变参数；根据信道受噪声种类分为随机差错信道和突发差错信道根据输入输出信号的特点分为离散信道，连续信道，半离散半连续，波形信道 2信道容量

C=maxI(X;Y)含义，表征信道能传输的最大信息量，或者信道的最大传输能力。

p(ai)3，DMC信道容量C?logm-H（Y|ai）=logm+第四章

?pj?1mijlog

pij

1．一般失真函数：

d(xi,yi)?{,?0xi?yi????0,xi?yi，失真矩阵：d???d(a1,bm)?????? ?d(an,bn)?d(an,bm)???d(a1,b1)2．均方失真：d(xi,yi)=(xi?yi)2，绝对失真：d(xi,yi)=|xi?yi|，相对失真：d(xi,yi)=|xi?yi|/|xi|，

0ii误码失真：d(xi,yi)=?(xi,yi)={1,其他

x?y????D?3.对于连续随机变量的平均失真??????p（x，y）d（x，y）dxdy

x，y1L1LE[d(x,yjl)]??Dl ；L长序列编码的为DL??ilLl?1Ll?14，信息率失真函数：R（D）=minI（X，Y）；对于无记忆信源

R（D）= p?pijDmin?i?1np(bi|ai)p(ai)p(bi|ai)log?p(bi) j?1m5.互信息的关系：I（X；Y）=H（Y）-H（Y|X）=H（X）-H（X|Y）

6.R（D）的计算

(1)当d(xi,yi)=(xi?yi)2，p（x）=1e?2??x22?2，R（D）=log?D

（2）当d(xi,yi)=|xi?yi|，P（x）=??D2e??|x|，R（D）=log

1 ?D（3）当d(xi,yi)=?(xi,yi)，p（x=0）=p，p（x=1）=1-p，R（D）=H（p）-H（D） 第五章 信源编码

1．分组码:将信源消息分成若干组，即符号序列xi，xi?(xi1,xi2,?,xil,?,xiL)，序列中的每个符号取自符号集A，xil?{a1,a2,a3,?,ai,?an}。而每个符号序列xi依照固定的码表映射一个码字yi，这样的码称为分组码，也叫快码。

2．码可以分为固定长度码和变长码；

分组码又分为奇异码和非奇异码；若信源符号和码字是一一对应的，该码为非奇异码，反之为奇异码。 非奇异码又分为非唯一可译码和唯一可译码；任意有限长的码元序列，只能被唯一分割成一个个码字，称唯一可译码；注：奇异码不是唯一可译码，而非奇异码中有唯一可译码和非唯一可译码。

唯一可译码又分为非即时码和即时码；接收端收到一个完整的码字后，不能立即译码，还需等下一个码

字开始接受后才能判断是否可以译码，称为非即时码，即时码又称非延时码，任意一个码字都不是其他码字的前缀部分，叫异前缀码。 3．唯一可译码的充要条件：

?mi?1n?Ki?1

4．定长编码定理：由L个符号组成的、每个符号的熵为HL(?)的无记忆平稳信源符号序列（X1,X2,?,Xl,?,XL）,可用KL个符号Y1,Y2,?,Yk,?,YKL(每个符号有m种可能值)进行定长编码。对

,任意??0,??0只要KLlogm?HLL(X?),+则当L足够大时，必可使译码差错小于?；当

KLlogm?HL(X)?-2时，译码差错一定是有限值。当L足够大时，译码几乎必定出错。 LHL(X)HL(X),?>0 5．编码效率：??,其中HL(X)为平均符号熵。 最佳编码效率：??KLHL(X)+?logmL6单个符号变长编码定理：若离散无记忆信源的符号熵为H(X),每个信源符号用m进制码元进行变长编码，

H(X)H(X)?K?+1. 一定存在一种无失真编码方法，其码字平均长度K满足下列不等式

logmlogm7离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率K满足不等式HL(X)?K?HL(X)+?,式中?为任意小正数。 8平均输出信息率为K?KLlogm。 9。码字平均长度：k?L?pk

iii?1nHL(X)H(X)?1?L9码的剩余度为??1???1? 10码字平均长度：KL?KLKlogmL 信源符号的平均码长：K??pk

iii?1nKLlogm Ln11费诺编码：平均码长K??p(ai)Ki，Ki为码长； 信息传输速率：R?i?1H(X) K13.m进制的哈夫曼编码：m>2

1)m进制的全树的终结点数=m+k(m-1),k=0,1,…2)当n

i?1q14在二元序列中，只有两种符号，即“0”和“1”这些符号可连续出现，连“0”的这段即为0的游程，

如：000101110010001，可变换游程序列3113213。

连着出现符号ar的游程，其长度L(r)就是“r”的游程长度。但是这种变换必须再加一些符号，才能成为一一对应或可逆的。 15算术编码：为非分组码

编码的基本思想：从全序列出发，将个信源序列的各概率映射到[0,1]区间上，使每个序列对应区间内的一点，即一个二进制小数。

例：有4个符号a,b,c,d构成简单序列S=(a,b,d,a),各符号及其对应概率如表，算术编码过程如下；

符号 a b c d 符号概率pi 0.100(1/2) 0.010(1/4) 0.001(1/8) 0.001(1/8) 符号累计概率Pj 0.000 0.100 0.110 0.111 设起始状态为空序列?，则A(?)=1，C(?)=0。递推得：

?C(?a)?C(?)?A(?)Pa?0?1?0?0?

A(?a)?A(?)p?1?0.1?0.1a??C(a,b)?C(a)?A(a)Pb?0?0.1?0.1?0.01 ?A(a,b)?A(a)p?0.1?0.01?0.001b??C(a,b,d)?C(a,b)?A(a,b)Pd?0.01?0.001?0.111?0.010111?

A(a,b,d)?A(a,b)p?0.001?0.001?0.000001d??C(a,b,d,a)?C(a,b,d)?A(a,b,d)Pa?0.010111?0.000001?0?0.010111 ?A(a,b,d,a)?A(a,b,d)p?0.000001?0.1?0.0000001a?因此C(a,b,d,a)即为编码后的码字010111。

17.三进制哈夫曼编码例：

解：六个字母的概率分别为0.32,0.22,0.18,0.16,0.08,0.04，则m=3，n=6，S=3+2（3-1）-6=1，得m-S=3-1=2 第六章 信道编码

1．突发差错模型为双状态一阶马尔可夫链模型，或吉尔伯特模型或Gi模型。

2．纠错码分类：1）从功能角度，分为检错码和纠错码；2）从对信息序列的处理方法，分为分组码和卷积码；3）从码元与原始信息的关系，分为线性码和非线性码 3．差错控制系统分类：前向纠错，反馈重发，混合纠错。

前向纠错优点：无需反向通道，时延小，实时性好，适用点对点和广播是通信。

反馈重发：发送端发送检错码，如循环冗余校验码（CRC）,接收端通过检测接收码是否符合编码规律来判断该码是否存在差错。

4.噪声均化的三种方法：增加码长N，卷积，交错 5．1）基底不是唯一的，生成矩阵也就不是唯一的。

2）非系统码的生产矩阵可以通过运算转变为系统形式，此过程叫系统化。

3）与任何一个（n,k）分组线性码的码空间C相对应，一定存在一个对偶空间D.

4）空间的n-k个基底排列起来可构成一个（n-k）?n矩阵，将这个矩阵称为码空间C的校验矩阵H. 5）,k）线性码的任意码字c一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵H的任意一个行矢量，即cH?0,0为零矩阵，若cH?0，则c为码字，反之，则不是码字。 6）校验矩阵HTT?[?PT?In?k]

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库信息论与编码在线全文阅读。