第3章节无失真信源编码.pptVIP

第三章 无失真信源编码 引言 编码的定义 定长编码定理 变长编码定理 变长编码方法 引言 什么是编码 香农信息论三大定理 编码的分类 编码的任务和途径 编码器 什么是编码 信源编码和信道编码 通信的实质是传输信息，要求传输具有高效率和质量： （1）在不失真和允许一定失真的条件下，用尽可能少的符号传送信源信息，以便提高信息传输率。 （2）在信道受干扰的情况下，增加信号的抗干扰能力，以便提高信息传输的可靠性。 解决以上两个问题需要引入信源编码和信道编码。 什么是编码 生活中编码实例? 学号、身份证号码、一卡通、汉语等编码。 编码实质：信息的表示。 结论: 信息无处不在 ，编码无处不在。 香农信息论三大定理 第一极限定理: 无失真信源编码定理。 第二极限定理: 信道编码定理(包括离 散和连续信道)。 第三极限定理: 限失真信源编码定理。 编码的分类 编码：信源编码、信道编码。 信源编码：无失真信源编码、限失真信源编码。 无失真信源编码：适用于离散信源或数字 信号。 限失真信源编码：适用于连续信源或模拟信号，如语音、图像等信号的数字处理。 信源编码目的与方法 信源编码：将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的冗余度尽可能地减少。 目的：提高通信的有效性。 方法：减少信源冗余度。 信源编码的基本途径 信源编码的基本途径 解除相关性：使序列中的各个符号尽可能地互相独立。 概率均匀化：使编码中各个符号出现的概率尽可能地相等。 信源编码的基础 信源编码的基础：无失真信源编码定理和限失真信源编码定理。 编码定理表明：（1）必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵。（2）达到这目标的途径，就是使概率与码长匹配。  编码器 不少原始信源的消息符号不适应信道的传输； 原始信源消息符号的传输效率低； 编码器输入端为原始信源u，其符号集为S:{s1,s2,…,sq}；si(i=1,2,…q)；而信道所能传输的符号集为x:{x1,x2,…,xr}； 编码器的功能：用符号集x中的元素，将原始信源的符号si变换为相应的码字符号Wi，(i=1,2,…,q)，所以编码器输出端的符号集为C={W1,W2,…,Wq}。 编码器的数学模型 S=原始信源符号集； x=码元符号集； C=码字符号集；（码组） 一些基本概念 二元码 定长码 变长码 非奇异码 奇异码 同价码 分组码 唯一可译码 即时码 码的前缀 码树 1.二元码 若码符号集为X={0,1}，所有码字都是二元符号序列，则称为二元码。 2.定长码 若一组码中所有码字的码长都相同，即 li=l（i=1,2…,n）,则称为定长码。 3.变长码若一组码中所有码字的码长各不相同，即任意码字由不同长度li的码符号序列组成，则称为变长码。 4.非奇异码 若一组码中所有码字都不相同，即所有信源符号映射到不同的码符号序列，则称码为非奇异码。 5.奇异码若一组码中有相同的码字，则称码为奇异码。 6.同价码若码符号集中每个码符号所占的传输时间都相同，则所得的码为同价码。 7.分组码 将信源符号集中的每个信源符号映射成一个固定的码字，这样的码称为分组码。 8.唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则此码称为唯一可译码。也称单义可译码。 注意：定长码是非奇异的就是唯一可译码，因为它能固定长度分组。 变长码则不一定，主要是不能固定长度分组。 唯一可译码还有判定准则，后面将介绍。 唯一可译码(续) 9.即时码无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码或瞬时码或逗点码或非延长码或异前缀码。 10.码的前缀 定理:唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。 11.码树 码字的构造可用树的形式来表示，称为 码的树图构造法。r元码通常对应于r元树（r叉树，r进制树）。当然二元码对应的是二叉树或二元树。 树根、叶子节点、中间节点、深度、码长。 整树、非整树、全树。 码树图 唯一可译码定理 设原始信源符号集为S:{S1,S2,…Sq}，码元符号集为x:{x1,x2,…,xr}，码字集合为W:{W1,W2,…Wq}，其码长分别为L1,L2,…,Lq；则唯一可译码存在的充要条件为码长组合满足Kraft不等式，即