信息论与编码考点

1、信息是指各个事物运动的状态及状态变化的方式。消息是指包含信息的语言文字图像。 信号时消息的物理体现。载有信息的可观测、可传输、可存储及可处理的信号均称为数据。连续信源是指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源。离散信源是指发出在时间和幅度上都是离散分布的离散消息的信源。信源分成离散信源和连续信源。信源又分为无记忆和有记忆信源。无记忆的分为发出单个符号和符号序列的。有记忆的分为符号序列的有记忆信源和符号序列的马尔可夫信源。离散有记忆序列信源：当信源输出的随机矢量中各个分量之间不相互独立而可以是任意相关的,则称此类信源为有记忆信源。时域采样：频带受限fm的时间连续函数f(t),

2、不失真采样频率fs 2fm，若时间上受限0 t tB，采样点数为tB(1/2fm)2fmtB。频域采样：时间受限于tB的频域连续函数，在02p的数字频域上要采L点的条件是时域延拓周期LT tB，若频率受限fm，则采样点数L tB/TtBfs 2fmtB。模拟信号：在幅度时间频率上都是连续的消息。当信源的记忆长度为m+1时，该时刻发出的符号与前m个符号有关联性，而与更前面的符号无关。记忆长度为m，称为m阶马尔可夫信源，若条件概率与时间起点无关，则称为齐次马尔可夫信源m阶马尔科夫信源,将该时刻之前出现的m个符号组成的序列定义为状态si：si共有Q=nm种取值可能。条件概率表示p(xj/si)。状态

3、转移概率表示为p(sj/si)。转移概率：转移矩阵每行元素之和均为1。 具有概率为p(xi)的符号xi的自信息量为 当xi和yj相互独立时，有p(xi,yj)=p(xi)p(yj)，那么就有 I(xi,yj)=I(xi)+I(yj)。若两个符号的出现不是独立的p(xi,yj)=p(xi/yj)p(yj)，则有I(xi,yj)=I(xi/yj)+I(yj)。自信息量I(xi)表征信源中各个符号xi的不确定度。信源的平均不确定度叫做信源熵各符号概率相等时，信源熵达到极大值。H（X/yj）= H（X/Y）= H(Y/X)=H（XY）= H（XY）H（X）H（YX）H（XY）H（Y）H（XY） 互信息

4、I(X;Y)=H(X)-H(X/Y)=互信息I(xi；yj)表示接收到某消息yj后获得的关于事件xi的信息量。信源X的熵等于接收到的信息量加上损失掉的信息量。 条件熵H（YX）唯一地确定信道噪声所需要的平均信息量，故又称噪声熵或散布度。I（X;YZ）I（X;Y）I（X;ZY） I(X;YZ)I(X;Z)I(X;Y/Z) I(YZ;X)I(Y;X)I(Z;X/Y)消息通过多级处理器时，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。 数据处理定理：数据处理过程中只会丢失掉一些信息，绝不会创造新的信息，就是所谓的信息不增性。条件熵小于信源熵：H(X/Y) H(X)。当且仅当X和

5、Y相互独立时，p(x/y)p(x)，取等号。 离散无记忆序列信源熵： 离散有记忆序列信源熵：H（X）=H（XL）=H (X)= HL(X)=H(XL/ X1X2XL-1) H (X)叫极限熵或极限信息量H (X) H2(X) H1(X) H0(X) 连续信源熵(也叫相对熵)定义为:连续信源联合相对熵连续信源条件相对熵I(X;Y)I(Y;X)Hc(X)- Hc(X/Y)Hc(X)Hc(Y)- Hc(XY)Hc(Y)- Hc(Y/X)限峰功率的最大相对熵定理：对于定义域为有限的随机矢量X，当它是均匀分布时，其熵最大。限平均功率最大相对熵定理：对于相关矩阵一定的随机矢量X，当它是正态分布时具有最大相

6、对熵。 定义信息效率： 冗余度：信道分类：按输入/输出信号在幅度和时间上的取值: 离散信道、连续信道、半离散(半连续)信道、波形信道信道中平均每个符号所能传送的信息量定义为信道的信息传输率R：R=I(X;Y)=H(X)-H(X/Y)最大信息量即为信道容量：对称DMC信道的容量： 准对称信道的信道容量，输入分布为等概率时其中n是输入符号集的个数，(p1, p2,pm)为准对称信道矩阵中的行元素。设矩阵可划分成r个互不相交的子集。Nk是第k个子矩阵Pk中行元素之和,Mk是第k个子矩阵Pk中列元素之和。 （转移矩阵划分）离散序列信道容量连续信道：S为信道输入X时的平均功率值，高斯白噪声加性波形信道单

7、位时间信道容量：Ps为信号平均功率；N0W为高斯白噪声在带宽W内平均功率。均方失真: 绝对失真:相对失真: 误码失真:平均失真最小的互信息就称为信息率失真函数R(D)R(D)的物理意义对于给定信源，在平均失真不超过失真限度D的条件下，信息率容许压缩的最小值R(D)R（D）函数的定义域R（Dmin） R（0）H（X）1）R(D)是非负的实数，即R(D) 0。其定义域为0Dmax，其值为0 H(X)。当DDmax时，R(D)=0。2）R(D)是关于D的下凸函数，因而也是关于D的连续函数。3）R(D)是关于D的严格递减函数。 当d(x,y)=(x-y)2, p(x)= 时，R（D）=当d(x,y)=

8、 p(x)= 时 R（D）= 当D(x,y)= 时，R（D）=H（p）- H（D）无失真信源编码第一极限定理 限失真信源编码第三极限定理 信道编码 第二极限定理信源编码：在不失真或允许一定失真条件下,如何用尽可能少的符号来传送信源信息,以便提高信息传输率。将信源输出符号,经信源编码器后变换成另外的压缩符号,然后将压缩后信息经信道传送给信宿。信道编码：在信道受干扰的情况下如何增加信号的抗干扰能力,同时又使得信息传输率最大。只有分组码才有对应的码表，而非分组码中则不存在码表。若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯

9、一可译码。唯一可译码中又分为非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。定长的非奇异码一定是唯一可译码。判断唯一可译码：1、看是否为非奇艺码，若是则转2，若不是则一定不是。2、画码树，看是否满足即时码的构造方法，若满足则为唯一可译码。另判断唯一可译码：计算出各分组码中所有可能尾随后缀集合，观察集合当中有没有包含任一码字，若无则惟一可译。唯一可译码存在的充分和必要条件，各码字的长度Ki 应符合克劳夫特（ Kraft ）不等式： 该不等式是唯一可译码存在的充要条件，而不是唯一可译码的充要条件。 用该码字表示L

10、长的信源序列则送出一个信源符号所需的信息率平均为 又表示平均码长，信息率最小就是找到一种编码方法使最小。 为编码效率 最佳编码效率为 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。香农码的编码步骤: （1）将信源符号按概率从大到小的顺序排列, p(a1) p(a2) p(an)（2）确定满足下列不等式的整数Ki , log2 p(ai) Ki 1log2 p(ai) （3）令p(a1)=0,用Pi表示第i个码字的累加概率， （4）将Pi用二进制表示。（5）取Pi小数点后Ki位作为符号ai的编码。费诺编码步骤: （1）将概率按从大到小的顺序排列,令p(x1

11、) p(x2) p(xn)（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。（5）信源符号所对应的码字即为费诺码。哈夫曼编码的步骤: 将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2) p(xn)取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。 对重排后的两个概率最小符号重复步骤

12、的过程。不断继续上述过程,直到最后两个符号配以0和1为止。 从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。平均码长越短,编码效率就越高。 哈夫曼码平均码长最小,信息传输速率最大,编码效率最高。差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示。差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示差错图样类型随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而

13、是码元差错概率超过了某个额定值。纠错码分类，从功能讲差错码分为两类：一类用于发现差错，叫检错码；另一类要求能自动纠正差错，叫纠错码。按照对信息序列的处理方法，分为分组码和卷积码。按照码元与原始信息位的关系，分为线性码和非线性码。从系统角度讲，运用纠/检错码进行差错控制的基本方式大致分为三类：前向纠错（FEC）、反馈重发（ARQ）、混合纠错（HEC）。ARQ优点：编译码设备简单，同样冗余度下检错码的检错能力比纠错码的纠错能力要高得多。缺点：需要反馈信道，收、发端需要大容量存储器以及复杂的控制设备。当信道误码率很高时，重发将过于频繁而是效率大大降低甚至使系统阻塞。译码器要在已知r的条件下找出可能性

14、最大的发码ci作为译码估值 =max P（ci|r）在已知r的条件下是先验概率最大的译码算法叫做最大似然译码。 =max P（r| ci）P(r/ci)也叫做似然函数，利用贝叶斯公式可以建立先验概率和后验概率之间的联系 P(A|B)=P(B|A)*P(A)/P(B)(n,k)线性分组码是把信息流分割成一串前后独立的kbit信息组，再将每组信息元映射成由n个码元组成的码字。若被称为线性分组码，则其码集一定正好是k维n重子空间。2.2 由符号集0，1组成的二阶马尔可夫链，其转移概率为：=0.8，=0.2，=0.2，=0.8，=0.5，=0.5，=0.5，=0.5。画出状态图，并计算各状态的稳态概率

15、。解： 于是可以列出转移概率矩阵：状态图为： 设各状态00，01，10，11的稳态分布概率为W1,W2,W3,W4 有 得 计算得到2.7 设有一离散无记忆信源，其概率空间为 （1）求每个符号的自信息量 （2）信源发出一消息符号序列为202 120 130 213 001 203 210 110 321 010 021 032 011 223 210，求该序列的自信息量和平均每个符号携带的信息量解：同理可以求得因为信源无记忆，所以此消息序列的信息量就等于该序列中各个符号的信息量之和就有：平均每个符号携带的信息量为bit/符号2-14 在一个二进制信道中，信源消息X0,1，且p(1)=p(0)，

16、信宿的消息Y 0,1，信道传输概率P(y=1|x=0)=1/4， P(y=0|x=1)=1/8.求：（1）在接收端收到y=0后，所提供的关于传输消息x的平均条件互信息量I(X；y=0)；（2）该情况所能提供的平均互信息量I(X；Y)。(1) P(ij)= P(i/j)= (2) 方法1: = 方法2: 2.25 某一无记忆信源的符号集为0, 1，已知P(0) = 1/4，P(1) = 3/4。(1) 求符号的平均熵；(2) 有100个符号构成的序列，求某一特定序列（例如有m个“0”和（100 - m）个“1”）的自信息量的表达式；(3) 计算(2)中序列的熵。解：(1)(2) (3) 2-30

17、有一个马尔可夫信源，已知转移概率为p(s1/s1)=2/3，p(s2/s1)=1/3，p(s1/s2)=1，p(s2/s2)=0。试画出状态转移图，并求出信源熵。(1) 求平稳概率 P(j/i)= 解方程组 得到 (2) 信源熵为: 2-33 一阶马尔可夫信源的状态图如图2-14所示，信源X符号集为0,1,2。（1）求平稳后信源的概率分布；（2）求信源熵H。（3）求当p=0或p=1时信源的熵，并说明其理由。 (1)解方程组: 得p(0)=p(1)=p(2)= (2) (3) 当p=0或p=1时 信源熵为03.1 设二元对称信道的传递矩阵为(1) 若P(0) = 3/4, P(1) = 1/4，

18、求H(X), H(X/Y), H(Y/X)和I(X;Y)；(2) 求该信道的信道容量及其达到信道容量时的输入概率分布；解：1)其最佳输入分布为3.5 求下列二个信道的信道容量，并加以比较（1） （2）其中p+=1解：（1）此信道是准对称信道，信道矩阵中Y可划分成三个互不相交的子集 由于集列所组成的矩阵,而这两个子矩阵满足对称性，因此可直接利用准对称信道的信道容量公式进行计算。C1=logr-H(p1 p2 p3)-其中r=2,N1=M1=1-2 N2= M2=4 所以C1=log2-H(,p-,2)-(1-2)log(1-2)-2log4=log2+()log()+(p-)log(p-)+2log2-(1-2)log(1-2)-2log4=log2-2log2-(1-2)log(1-2)+()log()+(p-)log(p-)=(1-2)log2/(1-2)+()log()+(p-)log(p-)输入等概率分布时达到信道容量。（2）此信道也是准对称信道，也可采用上述两种方法之一来进行计算。先采用准对称信道的信道容量公式进行计算，此信道矩阵中Y可划分成两个互不相交的子集，由子集列所组成的矩阵为，这两矩阵为对称矩阵 其中r=2,N1=M1=1-2 N2=M2=2，所以C=logr-H(-,p-,2,0)-=log2+(-)log(-)+(p-)l