信息论与编码全部课件.ppt

1,1绪论,1.1信息的概念1.1.1信息的定义与性质1.1.2信息的分类1.2信息传输系统的组成及功能1.2.1模拟信息传输系统1.2.2数字信息传输系统1.3信息论研究对象和内容1.4信息论发展简史,2,1.1.1信息的定义与性质,古时的通信：烽火台信息传播五阶段：手势和语言文字印刷术电磁波计算机和通信微电子技术、通信技术和计算机技术促进了信息技术发展。信息产业的发展促进了社会产业结构的变化与发展。,3,1.1.1信息的定义与性质,信息：认识主体所感受的或所表达的事物的运动状态和运动状态的变化方式。（1）信息是普遍存在的。（2）信息与物质。（3）信息与能量。（4）人类认识事物，变革事物必须要有信息。信息载体：运载信息的物质。,4,1.1.1信息的定义与性质,消息：以文字、语音、图像等这些能够为人们的感觉器官所感知的物理现象，把客观物质运动和主观思维活动的状态表达出来就成为消息。,信号：消息的表现形式和载体。同一信息可用不同的信号来表示，同一信号也可表达不同的信息。,5,1.1.1信息的定义与性质,信息十分抽象而又复杂的概念，是人们对客观事物感触到的新认识。消息信息的载荷者，是描述信息的一种表现形式，是对某个事物的描述和反应。信号运载或携带消息的任何物理量，达到迅速有效地传递和交换信息的目的。,6,1.1.1信息的定义与性质,性质：（1）普遍性：信息是普遍存在的。（2）无限性：信息是无限的。（3）相对性：对同一事物不同的观察者所获得的信息量可能不同。,（4）转换性：信息可以在时间上或空间中从一点转移到另一点。（5）变换性：信息是可变的，它可以由不同的载体或不同的方法来载荷。,7,1.1.1信息的定义与性质,（6）有序性：信息可以用来消除系统的不定性，增加系统的有序性。（7）动态性：信息具有动态性质，一切活的信息都随时间变化，具有时效性。（8）转化性：在一定条件下，信息可以转化为物质、能量、时间等。,（9）共享性：同一信息可以被无限的人所获得，可以交流而不会减少。（10）可量度性：信息的数量与质量是可量度的即信息量。,8,1.1.2信息的分类,（1）从性质分：语法信息、语义信息、语用信息。,9,1.1.2信息的分类,举例说明，两个布袋中装有对人手感觉完全一样的球，但颜色和数量不同，（1）50个红球和50个白球（2）红球、白球、黑球、黄球各25个随意拿出一个球，被告知是红球所获得的信息量。,10,1.1.2信息的分类,（2）按观察的过程分：实在信息、先验信息、实得信息。（3）按信息的地位分：客观信息、主观信息。（4）按作用分：有用信息、无用信息、干扰信息。,（5）按逻辑意义分：真实信息、虚假信息、不定信息。（6）按传递方向分：前馈信息、反馈信息。,11,1.1.2信息的分类,（7）按生成领域分：宇宙信息、自然信息、社会信息、思维信息等。（8）按应用部门分：工业信息、农业信息、军事信息、政治信息、科技信息、文化信息等。,（9）按信息源的性质分：语声信息、图像信息、文字信息、数据信息、计算信息等。（10）按载体性质分：电子信息、光学信息、生物信息等。（11）按携带信息的信号形式分：连续信息、离散信息、半连续信息等。,12,1.2.1模拟信息传输系统,该系统传递的是模拟信号，它在任意时刻的取值是任意的，是时间的连续函数。基本模型如图1.1所示：,13,1.2.1模拟信息传输系统,信息源：产生含有信息的消息，是被传输的对象。信息宿：信息传送的目的地，即原消息的归宿或接受者。,14,1.2.1模拟信息传输系统,变换器：将非电量变换成宜于远距离传输的电信号。反变换器：将信息信号恢复成原消息。,15,1.2.1模拟信息传输系统,调制器：将频率较低的信号调制到频率更高的载波信号上。(调制方式有调幅AM、调频FM、调相、单边带调制SSB等)。,解调器：从已调的高频载波信号中解调出被传输的低频信息信号。,16,1.2.1模拟信息传输系统,发射机：变频器和功率放大器，使已调载波信号的频率和功率达到实际应用所要求的数值。,接收机：低噪声高频放大器、混频器、中频放大器，将微弱信号放大到解调器所需强度的信号，并最大限度地降低信道噪声的影响。,17,1.2.1模拟信息传输系统,信道：消息的信号从发射端传到接受端的媒质或通道。（有线信道：架空明线、同轴电缆、波导、光纤等；无线信道：无线电波、激光自由空间传播等）,噪声源：实际传输系统中客观存在的干扰源，有内部噪声和外部干扰两方面。,18,1.2.2数字信息传输系统,该系统中传输的是数字信号，它只能取有限个离散值，且出现的时间也是离散的。基本模型如图1.2所示：,19,1.2.2数字信息传输系统,调制方式有幅度键控ASK、频移键控FSK、相移键控PSK等。,信源编码器：模/数（A/D）变换器，将模拟信号变换成数字信号。信源译码器：数/模（D/A）变换器，将数字信号变换成模拟信号。信道编译码器：提高传输系统的抗干扰能力。,20,1.2.2数字信息传输系统,优点：（1）抗干扰能力强，特别在中继传输中尤为明显。（2）可以进行差错控制，提高了信息传输的灵活性。,（3）便于使用现代计算机技术对信号进行处理、存储和变换。（4）便于加密，实现保密信息传输。,21,1.2.2数字信息传输系统,（5）易于与其他系统配合使用，构成综合业务信息传输网。（6）易于集成化和大规模生产，性能一致性好且成本低。,缺点：（1）占用信道频带较宽。（2）要有一个复杂的同步系统。,22,1.3信息论研究对象和内容,研究对象：消息传输系统即信息传输系统，通信系统。,研究目的：提高通信系统的可靠性和有效性。（1）可靠性高：使信源发出的消息经过传输后尽可能准确地不失真地再现在接收端。（2）有效性高：经济效果好，用尽可能短的时间和尽可能少的设备传送一定数量的信息。,23,1.3信息论研究对象和内容,研究内容：（1）通信的统计理论的研究。（2）信源的统计特性的研究。（3）收信者接受器官的研究。,（4）编码理论与技术。（5）如何提高信息传输效率。（6）抗干扰理论与技术。（7）噪声中信号检测理论与技术。,24,1.3信息论研究对象和内容,信息论的三个层次：（1）信息论基础（狭义信息论）：主要研究信息的测度、信道容量、信源和信道编码理论等问题。,（2）一般信息论：主要研究信息传输和处理问题，除香农理论外，还包括噪声理论、信号滤波和预测、统计检测与估计理论、调制理论以及信息处理理论等。,（3）广义信息论：不仅包括上述两方面内容，还包括与信息有关的领域，如心理学、遗传学、神经生理学、语言学、语义学等。,25,1.4信息论发展简史,电信系统的发展：电磁理论和电子学理论的发展促进了电信系统的创造发明或改进。1823年-1835年，莫尔斯建立了电报系统。1876年，贝尔发明了电话系统。,1895年，马可尼和波波夫发明了无线电通信。1925年-1927年，建立起电视系统。二次大战初期，微波通信系统和微波雷达系统迅速发展起来。20世纪60年代，人类进入光纤通信时代。,26,1.4信息论发展简史,信息理论的发展：1924年，奈奎斯特首先将信息率与信号带宽联系起来。1928年，哈特莱引入了非统计（等概率事件）信息量概念。,20世纪40年代初期，维纳把随机过程和数理统计的观点引入通信和控制系统中。1948、1949年，香农用概率测度和数理统计的方法，系统地讨论了通信的基本问题。,27,1.4信息论发展简史,无失真信源编码的发展：（香农编码理论）惟一可译码费诺码哈夫曼码（最佳码）算术编码LZ码（通用信源编码）。,信道编码的发展：纠错码汉明码（代数编码）卷积码（概率编码）并行极点卷积码。,28,2信息的量度,2.1自信息量和条件自信息量2.2互信息量和条件互信息量2.3离散集的平均自信息量2.4离散集的平均互信息量2.5例题,29,2.1自信息量和条件自信息量,2.1.1自信息量2.1.2条件自信息量,30,2.1.1自信息量,信源发出的消息常常是随机的，其状态存在某种程度的不确定性，经过通信将信息传给了收信者，收信者得到消息后，才消除了不确定性并获得了信息。,获得信息量的多少与信源的不确定性的消除有关。不确定度惊讶度信息量,31,2.1.1自信息量,（1）直观定义信息量为：收到某消息获得的信息量=不确定性减少的量=收到此消息前关于某事件发生的不确定性-收到此消息后关于某事件发生的不确定性,（2）无噪声时信息量为：收到消息前获得的信息量=收到此消息前关于某事件发生的不确定性=信源输出的某消息中所含有的信息量,32,2.1.1自信息量,举例说明，一个布袋中装有对人手感觉完全一样的球，但颜色和数量不同，问下面三种情况下随意拿出一个球的不确定程度的大小。（1）99个红球和1个白球（2）50个红球和50个白球（3）红球、白球、黑球、黄球各25个,33,2.1.1自信息量,事件发生的不确定性与事件发生的概率有关，一般情况下，一个信源可以用一个概率空间来描述，信源的不确定程度可以用这个概率空间的可能状态数目及其概率来描述。,34,2.1.1自信息量,设信源X的概率空间为其中：X是信源的状态空间，即随机事件的状态数；是随机事件可能状态的概率分布，且，各状态是相互独立的。通常记为,35,2.1.1自信息量,应用概率空间的概念分析上例，设取红球的状态为x1，白球为x2，黑球为x3，黄球为x4，则概率空间为：（1）（2）（3）,36,2.1.1自信息量,结论：（1）不确定度与信源概率空间的状态数及其概率分布有关。,（2）信源概率空间的概率分布为等概率时不确定度最大。,（3）等概率时，不确定度与信源概率空间的状态数或相应的概率有关。,37,2.1.1自信息量,任意随机事件的自信息量定义为该事件发生概率的对数的负值。若随机事件出现的概率为，那么它的自信息量为通常取对数的底为2，单位为比特（bit）。,38,2.1.1自信息量,三个单位间的转换关系为：1奈特=log2e1.433比特1哈特莱=log2103.332比特自信息量非负且单调递减。,39,2.1.1自信息量,例：某地的天气情况分布是：晴天占1/2，阴天占1/4，雨天占1/8，雪天占1/8。求各种天气的自信息量。解：设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4,40,2.1.1自信息量,在二维联合集上的元素的联合自信息量定义为其中，为元素的二维联合概率。当二者相互独立时，则有。元素的不确定度在数值上也等于他们的自信息量。,41,2.1.1自信息量,例2.1.1在盒子中放入n个不同阻值的电阻，随机取出一个并猜测阻值，概率空间为其中xi代表阻值为表示取出电阻值为i的电阻的概率。假定取出电阻是等概率的，即那么被告知取出阻值为i的电阻，所获得的信息量为,42,2.1.1自信息量,若盒中放入个不同阻值的电阻，其中阻值为1欧姆的1个，2欧姆的2个，n欧姆的n个。概率空间为其中xi代表阻值为表示取出电阻值为i的电阻的概率。那么被告知取出阻值为i的电阻，所获得的信息量为,43,2.1.2条件自信息量,在联合集对事件，设在条件下，随机事件的条件概率为，那么其条件自信息量定义为三种自信息量的关系：,44,2.1.2条件自信息量,例2.1.2设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随机地放在棋盘中某方格内让乙猜。（1）将方格按顺序编号，猜测顺序号；（2）将方格按行和列编号并告知行或列编号，猜测位置。,45,2.1.2条件自信息量,解：由于棋子位置是二维等概率分布，故（1）在二维联合集上的元素的自信息量为（2）在二维联合集上，元素相对的条件自信息量为,46,2.2互信息量和条件互信息量,2.2.1互信息量2.2.2互信息量的性质2.2.3条件互信息量,47,2.2.1互信息量,（1）通常预先知道信源集合X的概率空间，即其中为集合X中各个消息的取值，概率称为先验概率。,48,2.2.1互信息量,（2）信宿收到的消息符号集合Y的概率空间为其中为集合Y中各个消息的取值。当信宿收到集合Y中的一个符号消息后，接收者重新估计关于信源各个消息Xi发生的概率就成为条件概率也称为后验概率。,49,2.2.1互信息量,对两个离散随机事件X和Y，事件的出现给出关于事件的信息量定义为互信息量，即,互信息量定义为后验概率与先验概率比值的对数，也等于自信息量减去条件自信息量。当对数底分别为2、e、10时，互信息量的单位分别为比特、奈特、哈特莱。,50,2.2.1互信息量,例2.2.1：当告知不是晴天时，某地的天气情况分布是阴天占1/2，雨天占1/4，雪天占1/4。求不是晴天时，获得的各种天气的互信息量。解：设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4。不是晴天的状态为y1,51,2.2.1互信息量,此时，各种天气的条件自信息量：,52,2.2.2互信息量的性质,（1）互信息量的互易性对称性证：,53,2.2.2互信息量的性质,（2）当事件xi和yj相互独立时，互信息量为零。证：由得,54,2.2.2互信息量的性质,（3）互信息量可正可负,当后验概率大于先验概率时，互信息量为正值，反之为负值。互信息量为正意味着事件的出现有助于肯定事件的出现，反之是不利的。,55,2.2.2互信息量的性质,（4）任何两个事件的互信息量不可能大于其中任一事件的自信息量。证：由于故,56,2.2.2互信息量的性质,例2.2.2某人A预先知道他的三个朋友B、C、D中有一人晚上到他家，且这三人来的可能性相同，先验概率P(B)=P(C)=P(D)=1/3。,但上午A接到D的电话说不能来了，将这次电话作为事件E，那么有后验概率P(D|E)=0,P(B|E)=P(C|E)=1/2。,下午又接到C的电话说不能来，将此作为事件F，则有P(C|EF)=P(D|EF)=0,P(B|EF)=1。,57,2.2.2互信息量的性质,在接到上午电话后，A获得关于B、C、D的互信息量为因为P(D|E)=0,故无需考虑事件D与事件E间的互信息量。在接到两次电话后，A获得关于B、C、D的互信息量为因为P(C|EF)=P(D|EF)=0,故无需考虑事件D与事件E间的互信息量。,58,2.2.3条件互信息量,在联合集,在给定的条件下，之间的互信息量。在联合集,还存在与之间的互信息量。,59,2.3离散集的平均信息量,2.3.1平均自信息量（熵）2.3.2熵函数的数学特性2.3.3条件熵2.3.4联合熵（共熵）2.3.5各种熵的性质2.3.6加权熵,60,2.3.1平均自信息量（熵）,自信息量是一个随机变量，不能作为整个信源的信息测度，故引入平均自信息量，即信息熵。,信息熵H(X)是从整个信源的统计特性来考虑的，是从平均意义上表征信源的总体特性。对某特定的信源，其信息熵只有一个。,定义集X上，随机变量自信息I(xi)的数学期望为平均自信息量H(X)即信息熵，简称熵。,61,2.3.1平均自信息量（熵）,例2.3.1有一个布袋内放100个球，其中80个红球，20个白球。随便摸一个球猜测是什么颜色，求平均摸取一次获得的信息量。解：设事件x1表示摸到红球，事件x2表示摸到白球，则概率空间为,62,2.3.1平均自信息量（熵）,当告知摸出的是红球时，获得的信息量当告知摸出的是白球时，获得的信息量,若每次摸出一个球后又放回去，进行第二次摸取，那么摸取n次中，红球出现的次数为nP(x1)，白球出现的次数为nP(x2)。则摸取n次后获得的信息量为,63,2.3.1平均自信息量（熵）,平均随机摸取一次所能获得的信息量为,64,2.3.1平均自信息量（熵）,信息熵分别为可见H(Y)H(X),例2.3.2比较两个信源,65,2.3.1平均自信息量（熵）,信息熵的三种物理含义：（1）表示信源输出后每个消息所提供的平均信息量。（2）表示信源输出前信源的平均不确定性。（3）表征变量的随机性。,66,2.3.2熵函数的数学特性,因为随机变量集的熵H(X)只是其概率分布的函数，所以熵函数H(X)又可记为,由于概率的完备性，H(P)实际上是(q-1)元函数。如二元熵H(P)=Hp,(1-p)=H(p)。,67,2.3.2熵函数的数学特性,设为一多元函数，若对于任意小于1的正数以及函数定义域内的任意两个矢量X1和X2有则称f(X)为定义域上的上凸函数。,68,2.3.2熵函数的数学特性,（1）对称性当概率矢量中的各个分量的次序任意互换时，熵函数的值不变，即例如两个信源信息熵为,69,2.3.2熵函数的数学特性,（2）非负性（离散信源）等号成立的充要条件是当且仅当某Pi=1,其余的Pk=0。这表明确定信源的熵最小。证：,当每一项为零时等号成立，由于，故只能有某一个Pi=1,其余的Pk=0,70,2.3.2熵函数的数学特性,（3）扩展性证：因为,说明信源的取值数增多时，若这些取值对应的概率很小（接近于零），则信源的熵不变。,71,2.3.2熵函数的数学特性,（4）可加性如果有两个随机变量X和Y，他们不是相互独立的，则二维随机变量的熵H(XY)等于X的无条件熵H(X)加上当X已给定时Y的条件概率定义的熵的统计平均值H(Y|X)。H(XY)=H(X)+H(Y|X)H(XY)=H(Y)+H(X|Y),72,2.3.2熵函数的数学特性,（5）极值性式中，n是集合X的元素数目。上式表明，在离散情况下，集合X中的各事件依等概率发生时，熵达到极大值，即最大熵定理。,73,2.3.2熵函数的数学特性,（6）确定性从总体看，信源虽然有不同的输出符号，但当它只有一个符号几乎必然出现，而其他符号都是几乎不可能出现时，那么这个信源是一个确知信源，其熵等于零。（7）上凸性,74,2.3.3条件熵,条件熵是在联合符号集XY上的条件自信息量的联合概率加权统计平均值。,条件熵H(X|Y)表示收到全部输出符号后，对信道输出符号集还存在的平均不确定性，称为信道疑义度。,条件熵H(Y|X)可以衡量信号通过信道后损失信息量的多少。,75,2.3.4联合熵（共熵）,联合熵是在符号集XY上的每个元素对xiyj的自信息量的概率加权统计平均值，其定义式为,76,2.3.5各种熵的性质,（1）联合熵与信源熵、条件熵的关系若集X和集Y相互独立则有表示熵的可加性。称为熵的强可加性。,77,2.3.5各种熵的性质,推广到多个随机变量构成的概率空间之间的关系。设有N个变量，其联合熵可表示为若N个变量相互独立，则有,78,2.3.5各种熵的性质,（2）联合熵与信源熵的关系当且仅当两个集合相互独立时，上式取等号，此时可得联合熵的最大值，即,此性质同样可推广到N个变量构成的概率空间等号成立的充要条件是概率空间相互独立。,79,2.3.5各种熵的性质,（3）信源熵与条件熵的关系当且仅当两个集合相互独立时，上式取等号。,80,2.3.5各种熵的性质,例2.3.3输入输出的联合分布如下表,81,2.3.5各种熵的性质,例2.3.4P(x),P(y|x),P(xy)如下表,82,2.3.5各种熵的性质,例2.3.5,83,2.3.6加权熵,设有随机变量X，引入事件的重量后，其概率空间为其中离散无记忆信源XPW的加权熵定义为,84,2.3.6加权熵,重要性质：,85,2.4离散集的平均互信息量,2.4.1平均条件互信息量2.4.2平均互信息量2.4.3平均互信息量的性质,86,2.4离散集的平均互信息量,以XP表示输入概率空间,87,2.4离散集的平均互信息量,以YP表示输出概率空间,88,2.4离散集的平均互信息量,X和Y的联合空间,89,2.4离散集的平均互信息量,以XYp(xy)表示联合概率空间，一般有当事件xi和yj相互独立时有若上式对所有的i,j成立，则称集X与Y统计独立，否则称为统计相关。,90,2.4.1平均条件互信息量,在联合集XY上，由yj提供的关于集X的平均条件互信息量等于由yj提供的互信息量在整个X中的后验概率加权的平均值，其定义式为,联合集XY上的平均条件互信息量有当且仅当集X中的各个xi都与事件yj相互独立时取等号。,91,2.4.2平均互信息量,互信息量在整个集上的概率加权平均值，称为平均互信息量,当事件xi与yj相互独立时,92,2.4.3平均互信息量的性质,（1）非负性：当且仅当事件xi与yj相互独立时取等号。,（2）对称性,93,2.4.3平均互信息量的性质,（3）平均互信息与各类熵的关系用维拉图表示为,94,2.4.3平均互信息量的性质,（4）极值性,（5）凸函数性平均互信息量是信源概率分布p(x)和信道传递概率p(x|y)的凸函数。,95,96,例1有一个布袋内放100个球，其中80个红球，20个白球。随便摸一个球猜测是什么颜色，求平均摸取一次获得的信息量。解：设事件x1表示摸到红球，事件x2表示摸到白球，则概率空间为,97,当告知摸出的是红球时，获得的信息量当告知摸出的是白球时，获得的信息量,若每次摸出一个球后又放回去，进行第二次摸取，那么摸取n次中，红球出现的次数为nP(x1)，白球出现的次数为nP(x2)。则摸取n次后获得的信息量为,98,平均随机摸取一次所能获得的信息量为,99,例2某人A预先知道他的三个朋友B、C、D中有一人晚上到他家，且这三人来的可能性相同，先验概率P(B)=P(C)=P(D)=1/3。,但上午A接到D的电话说不能来了，将这次电话作为事件E，那么有后验概率P(D|E)=0,P(B|E)=P(C|E)=1/2。,下午又接到C的电话说不能来，将此作为事件F，则有P(C|EF)=P(D|EF)=0,P(B|EF)=1。,100,在接到上午电话后，A获得关于B、C、D的互信息量为因为P(D|E)=0,故无需考虑事件D与事件E间的互信息量。在接到两次电话后，A获得关于B、C、D的互信息量为因为P(C|EF)=P(D|EF)=0,故无需考虑事件D与事件E间的互信息量。,101,例3：某地的天气情况分布是：晴天占1/2，阴天占1/4，雨天占1/8，雪天占1/8。求各种天气的自信息量。解：设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4,102,例2.1.1在盒子中放入n个不同阻值的电阻，随机取出一个并猜测阻值，概率空间为其中xi代表阻值为表示取出电阻值为i的电阻的概率。假定取出电阻是等概率的，即那么被告知取出阻值为i的电阻，所获得的信息量为,103,若盒中放入个不同阻值的电阻，其中阻值为1欧姆的1个，2欧姆的2个，n欧姆的n个。概率空间为其中xi代表阻值为表示取出电阻值为i的电阻的概率。那么被告知取出阻值为i的电阻，所获得的信息量为,104,例设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随机地放在棋盘中某方格内让乙猜。（1）将方格按顺序编号，猜测顺序号；（2）将方格按行和列编号并告知行或列编号，猜测位置。,105,解：由于棋子位置是二维等概率分布，故（1）在二维联合集上的元素的自信息量为（2）在二维联合集上，元素相对的条件自信息量为,106,第三章信源编码-离散信源无失真编码,3.1信源的数学模型及其分类3.2离散无记忆信源3.3离散无记忆信源的扩展信源3.4离散平稳信源,107,3.1信源的数学模型及其分类,3.1.1信源的数学模型3.1.2信源的分类,108,3.1.1信源的数学模型,(1)离散信源信源输出的是单个符号或代码的消息，信源符号集的取值是有限的或可数的，可以用一维离散型随机变量来描述，其数学模型是,109,3.1.1信源的数学模型,(2)连续信源信源输出的是单个符号或代码的消息，信源符号集的取值是连续的，可以用一维连续型随机变量来描述，其数学模型是其中p(x)为连续随机变量X的概率密度函数，(a,b)为X的存在域。,110,3.1.1信源的数学模型,若N维随机矢量中信源的N重概率空间为,这个空间共有元素qN个，取决于序列长度N和符号集的符号个数q。,111,3.1.2信源的分类,(1)按照消息取值集合以及取值时刻集合的离散性和连续性，信源可分为数字信源和模拟信源（波形信源）。(2)按照某取值时刻消息的取值集合的离散性和连续性，信源可分为离散信源和连续信源。,112,3.1.2信源的分类,(3)按照信源输出消息所对应的随机序列的平稳性，信源可分为平稳信源和非平稳信源。,(4)按照信源输出的信息所对应的随机序列中随机变量前后之间有无统计依赖关系，信源可分为无记忆信源和有记忆信源。,113,3.1.2信源的分类,在某些简单情况下，信源发出的一个个符号是彼此统计独立的，并且它们具有相同的概率分布，则N维随机矢量的概率分布满足其中，这种信源称为离散无记忆信源。,114,3.1.2信源的分类,在通常情况下，信源发出的符号是彼此依赖的，要引入条件概率分布来说明它们间的关联，这种信源称为有记忆信源。,有记忆信源可用有限状态马尔可夫链来描述。当信源记忆长度为m+1时，称为m阶马尔可夫信源，即信源每次发出的符号只与前m个有关,与更前面的符号无关。,115,3.2离散无记忆信源,在信源X中，事件xi发生的概率为p(xi)，则xi所含的自信息量定义为I(xi)=-logp(xi),信源输出各消息的自信息I(xi)的数学期望为信源的平均自信息量H(X)即信源的信息熵。,116,3.3离散无记忆信源的扩展信源,3.3.1最简单的离散信源3.3.2N次扩展信源3.3.3N次扩展信源的熵,117,3.3.1最简单的离散信源,最简单的离散信源的输出可用一维离散随机变量描述。对于二进制信源，其数学模型为,118,3.3.2N次扩展信源,（1）离散无记忆二进制信源X的二次扩展信源每两个二进制数字组成一组，新的等效信源的输出符号为x1=00，x2=01，x3=10，x4=11。二次扩展信源的数学模型为其中,119,3.3.2N次扩展信源,（2）离散无记忆二进制信源X的三次扩展信源每三个二进制数字组成一组，新的等效信源的输出符号为x1=000，x2=001，x3=100，x8=111。三次扩展信源的数学模型为其中,120,3.3.2N次扩展信源,以此类推，由N个二进制数字为一组构成的新信源共有2N个符号，每个符号长度为N，称为二进制信源的N次扩展信源。,121,3.3.2N次扩展信源,（3）离散无记忆信源的N次扩展设一个离散无记忆信源X的概率空间为,q为信源的符号个数，则信源X的N次扩展信源用XN表示，它是具有qN个符号的离散信源，其N重概率空间为,122,3.3.3N次扩展信源的熵,根据信息熵的定义，离散无记忆信源X的N次扩展信源XN的熵等于信源X的熵的N倍，即H(XN)=NH(X),123,3.3.3N次扩展信源的熵,例3.3.1,124,3.4离散平稳信源,3.4.1定义3.4.2N长信源序列的熵,125,3.4.1定义,定义：信源产生的随机序列满足：1）所有都取值于有限的信源符号集；2）随机序列是平稳的，即对所有的非负整数有,126,3.4.1定义,一维平稳信源：任意两个不同时刻信源发出符号的概率分布完全相同，即其中，i,j为任意整数,127,3.4.1定义,二维平稳信源：除上述条件外，如果联合概率分布p(x1x2)也与时间起点无关，即其中，i,j为任意整数,128,3.4.1定义,完全平稳信源：如果各维联合概率分布均与时间起点无关，即当t=i,t=j,(i,j为任意整数且不相等）时有,129,3.4.2N长信源序列的熵,平稳有记忆信源发出符号序列为，假设信源符号间的依赖长度为N，则联合概率为,130,3.4.2N长信源序列的熵,131,3.4.2N长信源序列的熵,例：设有一信源，产生0,1序列的消息，且在任意时间，不论前面发生过什么符号，均按P(0)=0.4,P(1)=0.6的概率发出符号。（1）试问这个信源是否是平稳的。（2）计算（3）计算H(X4)并写出X4信源中可能有的所有符号。,132,3.4.2N长信源序列的熵,解：（1）依题意，信源发出符号的概率分布与时间平移无关，且信源发出的序列之间也是彼此无依赖的，故此信源是平稳信源，而且是离散无记忆信源。,133,3.4.2N长信源序列的熵,（2）信源概率空间为可计算得因为信源是平稳无记忆信源，所以,134,3.4.2N长信源序列的熵,（3）X4信源中可能有的符号有16种,135,3.4.2N长信源序列的熵,对于离散、平稳、有记忆信源，当时，下列结论成立：（1）条件熵随N的增加是非递增的（即N的单调非增函数）；（2）（4）,（3）HN(X)是随N的增加是非递增的（即N的单调非增函数）；,136,3.5信源编码,3.5.1无失真信源编码3.5.2编码器3.5.3分组码3.5.4等长信源编码定理3.5.5变长编码定理3.5.6限失真信源编码3.5.7常用的信源编码方法,137,例中文电报对于汉字采用l=4,r=10的等长编码,即每个汉字用4位十进制数字表示,例如”中国北京”的代码是0022,0948,0554,0079当l=5,r=2时,就是5单位的二元码,138,3.5.1编码器,无失真信源编码可以不考虑抗干扰问题，其数学模型比较简单，如图所示,139,3.5.2编码器,编码器的作用就是将信源符号集中的符号（或者长度为N的符号序列）变换成由基本符号组成的长度为N的一一对应的输出符号序列。即而码字其中，长度称为码字长度，简称码长。,140,3.5.2编码器,二进制码,如果码中所有码字含有的码符号个数相同，则称为固定长度码或等长码，反之称为变长码。,141,3.5.2编码器,142,3.5.3分组码,同价码：每个码符号所占的传输时间都相同的码。对同价码而言，等长码中的每个码字的传输时间相同，而变长码中的每个码字的传输时间不一定相同。,143,3.5.3分组码,信源编码过程可以抽象为一种映射，即将信源符号集中的每一个元素si映射为码集合中的一个长度为li的码字,这样的码称为分组码。,144,3.5.3分组码,码字前缀的定义是：设为一个码字，对于任意的，称码符号序列的前j个元素为码字Wi的前缀。,145,3.5.3分组码,分组码的基本类型：（1）奇异码若分组码中的所有码字互不相同，则称此分组码为非奇异码，否则称为奇异码。,146,3.5.3分组码,（2）惟一可译码1若分组码对任意有限整数N，其N阶扩展码均为非奇异的，则称之为惟一可译码。,2任意有限长的码元序列，只能被惟一的分割成一个个的码字，便称为惟一可译码。,147,3.5.3分组码,例如0，10，11是一种惟一可译码，因为任意一串有限长码序列，如100111000只能被分割成10，0，11，10，0，0任何其他分割都会产生一些非定义的码字。,148,3.5.3分组码,（3）即时码无需考虑后续的码符号即可从码符号序列中译出码字，这样的惟一可译码称为即时码（瞬时码、非延长码或异前置码）。,已构成的码字的任何延长不再构成码字，故称为非延长码。任意一个码字都不是其他码字的前缀部分，也称为异前缀码或异前置码。,149,3.5.3分组码,定理：一个惟一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。,150,3.5.3分组码,即时码可以用树图法来构造。,151,3.5.3分组码,综上所述，可将码作如下分类：,152,3.5.3分组码,例：一个信源有六个可能的输出，其概率分布和对应的编码如下表。求哪些是惟一可译码，哪些是即时码。,153,3.5.3分组码,判断方法：对于变长码，计算出分组码中所有可能的尾随后缀集合，观察其中有没有包含任一码字，若没有则该分组码是惟一可译码，否则就不是。,154,3.5.3分组码,解：码组A是等长码，其中没有相同的码字，所以是惟一可译码。其他码组是变长码，可采用惟一可译变长码的判断法来判断。码组B：最短码字为“0”，是其他码字的前缀，但其尾随后缀都不是码字。同样对其他码字，其尾随后缀都不是码字，所以是惟一可译码。,155,3.5.3分组码,码组C：没有码字是其他码字的前缀，他们都不存在尾随后缀，所以是惟一可译码。码组D：最短码字为“0”，不是其他码字的前缀，但码字“10”是码字“1011”的前缀，其尾随后缀11是码字“110”的前缀，进一步得到11的尾随后缀0,其中0是最短的码字。所以D不是惟一可译码。,156,3.5.3分组码,码组E：最短码字为“0”，不是其他码字的前缀。码字“10”也不是其他码字的前缀，而剩下四个码字是等长码，都不相同，所以E是惟一可译码。码组F：最短码字为“0”，是码字“011”的前缀，其尾随后缀11是码字“110”的前缀，进一步得到11的尾随后缀0和1，其中0是最短的码字。所以F不是惟一可译码。,157,3.5.3分组码,综上所述，码组A,B,C,E是惟一可译码，并且码组A,C,E是即时码。,158,信源符号X=S1，S2，S3，S4，其码字如表,159,奇异码:,码1,唯一可译码：,非唯一可译码：,码2,码3,码0,码4,等长码:,码0,160,满树：每个节点上都有r个分枝的树等长码非满树：变长码用树的概念可导出唯一可译码存在的充分和必要条件,即各码字的长度Ki应符合Kraft不等式,式中:m是进制数n是信源符号数,161,例：设二进制码树中X=(a1,a2,a3,a4),K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得：,不存在满足这种Ki的唯一可译码,如果将各码字长度改成K1=1,K2=2,K3=3,K4=3,则,162,必须注意：Kraft不等式只是用来说明唯一可译码是否存在,并不能作为唯一可译码的判据。如码字0，10，010，111虽然满足Kraft不等式,但它不是唯一可译码。,163,无失真信源编码,信源编码器输入的消息序列:X=(X1X2XlXL),Xla1,an,输入的消息总共有nL种可能的组合输出的码字为:Y=(Y1Y2YkYK),Ykb1,bm输出的码字总共有mK种可能的组合。,信源编码器,码表,信源,信道,Y,L长序列,K长码字,X,164,实现无失真的信源编码,要求:信源符号X1X2XlXL是一一对应的码字Y1Y2YkYK能够无失真或无差错地从Y恢复X,也就是能正确地进行反变换或译码;传送Y时所需要的信息率最小,信息率最小就是找到一种编码方式使,最小,165,定长编码定理,在定长编码中,K是定值。我们的目的是寻找最小K值。编码器输入X=(X1X2XlXL),Xla1,an,输入的消息总共有nL种可能的组合输出的码字Y=(Y1Y2YkYK),Ykb1,bm输出的码字总共有mK种可能的组合。若对信源进行定长编码,必须满足:nLmK,信源编码器,信源,信道,X,Y,L长序列,K长码字,码表,166,若对信源进行定长编码,必须满足:,只有当K长的码符号序列数mK大于或等于信源的符号数nL时,才可能存在定长非奇异码。例如英文电报有27个符号,n=27,L=1,m=2(二元编码),每个英文电报符号至少要用5位二元符号编码,167,实际英文电报符号信源,在考虑了符号出现的概率以及符号之间的依赖性后,平均每个英文电报符号所提供的信息量约等于1.4比特。编码后5个二元符号只携带约1.4比特信息量。定长编码的信息传输效率极低。,168,等长信源编码定理,定理（等长信源编码定理）：设有离散无记忆信源，其熵为H(S)，若对信源长为N的符号序列进行等长编码，设码字是从r个码符号集中选取l个码元构成，对于任意，只要满足则当N足够大时，几乎可实现无失真编码。反之，当时，不可能实现无失真编码，而当N足够大时，译码错误概率近似等于1。,169,等长信源编码定理,该定理是在平稳无记忆离散信源的条件下论证的，但同样适于平稳有记忆信源，只是要求信源的极限熵和极限方差存在，并将式中的H(S)改为。,170,等长信源编码定理,将定理中的条件改写成llogrNH(S)左边表示长为l的码字符号序列能载荷的最大信息量。,右边表示长为N的信源序列平均携带的信息量。,故只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码。,171,等长信源编码定理,编码速率：编码效率：取等号时得到最佳编码效率。,172,等长信源编码定理,当允许错误概率时，信源序列长度必满足,173,例5-2：设离散无记忆信源概率空间,信源熵：,方差：,若取差错率,编码效率为90%,则L应满足,在差错率和编码效率要求并不十分苛刻的条件下,就需要9.8信源符号进行联合编码,这显然是很难实现的。,174,等长信源编码定理,例5.1.2设一简单离散信源如下对其进行等长近似无失真编码，若取编码效率为95%，差错概率，求信源符号联合编码长度。,175,等长信源编码定理,解：,176,变长编码定理,在变长编码中码长K是变化的。我们可根据信源各个符号的统计特性,如概率大的符号用短码,概率小的用较长的码,这样在大量信源符号编成码后平均每个信源符号所需的输出符号数就可以降低,从而提高编码效率,177,变长编码定理,对一个信源中的不同符号采用不同长度的码字表示，就称为变长编码或不等长编码。要实现无失真的信源编码，变长码必须是惟一可译码。为了能即时进行译码，变长码还必须是即时码。,178,变长编码定理,基本思想：一般离散无记忆信源输出的各消息概率是不等的，若对概率大的采用较短的码字，对概率小的采用较长的码字，使编码的平均码长最短，也实现了与信源统计特性相匹配。,179,变长编码定理,定理：对于熵为H(S)的离散无记忆信源若用具有r个码符号的集对其进行编码，则一定存在一种编码方法构成惟一可译码，其平均码长满足：,180,定理：设离散无记忆信源S的熵为H(S)，其N次扩展信源为SN其信源熵为H(SN)。用码符号集对SN进行编码，总可以找到一种编码方法构成惟一可译码，使信源S的每个信源符号所需的码字平均码长满足：,181,变长编码定理,是无记忆N次扩展信源SN中每个信源符号ai所对应的平均码长式中，li是ai所对应的码字长度。,和两者都是每个原始信源符号si所需要的码符号的平均数。,前者是直接对单个信源符号si进行编码。后者是对N次扩展信源SN符号序列ai进行编码。,182,变长编码定理,编码效率：用来衡量各种编码距极限压缩值的情况。码的剩余度：,183,变长编码定理,若对该信源进行变长编码,184,单个符号变长编码定理：若一离散无记忆信源的符号熵为H(X),每个信源符号用m进制码元进行变长编码,一定存在一种无失真编码方法,其码字平均长度满足下列不等式:,185,离散平稳无记忆序列变长编码定理对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率满足不等式,其中为任意小正数,186,用变长编码来达到相当高的编码效率,一般所要求的符号长度L可以比定长编码小得多。编码效率的下界：,187,若对例5-2用变长码实现,要求90%,用二进制,m2,log2m=l。,得L=4,188,再对长度为L=2的信源序列进行变长编码,其即时码如表,平均码长为：,单个符号的平均码长,编码效率为,输出的信息效率,189,将信源序列的长度增加,L3或L=4,对这些信源序列X进行编码,并求出其编码效率为,信息传输率分别为,如果对这一信源采用定长二元码编码,要求编码效率达到96时,允许译码错误概率10-5自信息的方差,所需要的信源序列长度,190,信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。,191,密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发“加密”可视为增熵的过程,“解密”可视为减熵的过程。,192,信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。信源编码的分类：离散信源编码：独立信源编码,可做到无失真编码；连续信源编码：独立信源编码,只能做到限失真信源编码；相关信源编码：非独立信源编码。,193,信源A,B,C,D,信源编码器,信道Error:10-4,解码,信宿,194,码字平均长度,C1和C2平均长度,C2的效率比C1高,C2的区分：0表示码字的结束,195,信息率,编码效率,196,最佳码：对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。紧致码香农（Shannon）费诺（Fano）哈夫曼（Huffma）,197,香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。香农第一定理指出,选择每个码字的长度Ki满足下式：,香农编码,或:log2p(xi)Ki1log2p(xi)就可以得到这种码。这种编码方法称为香农编码,198,二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列,p(a1)p(a2)p(an)确定满足下列不等式的整数Ki,log2p(ai)KiNH(S)左边表示长为l的码字符号序列能载荷的最大信息量。,右边表示长为N的信源序列平均携带的信息量。,故只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码。,233,5.1.3等长信源编码定理,编码速率：编码效率：取等号时得到最佳编码效率。,234,5.1.3等长信源编码定理,当允许错误概率时，信源序列长度必满足,235,5.1.3等长信源编码定理,例5.1.2设一简单离散信源如下对其进行等长近似无失真编码，若取编码效率为95%，差错概率，求信源符号联合编码长度。,236,5.1.3等长信源编码定理,解：,237,5.1.4变长编码定理,若对该信源进行变长编码,238,5.1.4变长编码定理,对一个信源中的不同符号采用不同长度的码字表示，就称为变长编码或不等长编码。要实现无失真的信源编码，变长码必须是惟一可译码。为了能即时进行译码，变长码还必须是即时码。,239,5.1.4变长编码定理,基本思想：一般离散无记忆信源输出的各消息概率是不等的，若对概率大的采用较短的码字，对概率小的采用较长的码字，使编码的平均码长最短，也实现了与信源统计特性相匹配。,240,5.1.4变长编码定理,定理：对于熵为H(S)的离散无记忆信源若用具有r个码符号的集对其进行编码，则一定存在一种编码方法构成惟一可译码，其平均码长满足：,241,5.1.4变长编码定理,定理：设离散无记忆信源S的熵为H(S)，其N次扩展信源为SN其信源熵为H(SN)。用码符号集对SN进行编码，总可以找到一种编码方法构成惟一可译码，使信源S的每个信源符号所需的码字平均码长满足：,242,5.1.4变长编码定理,是无记忆N次扩展信源SN中每个信源符号ai所对应的平均码长式中，li是ai所对应的码字长度。,和两者都是每个原始信源符号si所需要的码符号的平均数。,前者是直接对单个信源符号si进行编码。后者是对N次扩展信源SN符号序列ai进行编码。,243,5.1