《信源编码》PPT课件.ppt

第 5 章 信源编码,5.1 编码的定义,5.2 无失真信源编码,5.3 限失真信源编码定理,5.4 常用信源编码方法简介,编码,通信的实质是传输信息，通信系统的性能指标主,要有有效性、可靠性、安全性等，这些指标正是信息,论研究的对象。编码的目的是为了优化通信系统，就,是使这些指标达到最佳。,按不同的编码目的，编码分为三类：,信源编码,信道编码,安全编码/密码,信源编码,信源编码是以提高通信的有效性为目的编码。,通常通过压缩信源的冗余度来实现。,采用的一般方法是压缩每个信源符号的平均比特,数或信源的码率。同样多的信息用较少的码率来,传送，使单位时间内传送的平均信息量增加，从,而提高通信的有效性。,在不失真或允许失真的条件下，用,尽可能少的符号传送信源信息。,信道编码：, 是以提高信息传输的可靠性为目的的编码。, 通常通过增加信源的冗余度来实现。采用的,一般方法是增大码率/带宽。,在信道受干扰的情况下增加信号的抗干,扰能力，同时又使得信息传输率最大。,密码：,是以提高通信系统的安全性为目的的编码。,通常通过加密和解密来实现。,无失真编码,无失真信源编码定理,信源编码,限失真编码,限失真信源编码定理,无失真 ( 冗余度压缩编码 ) ：仅对信源的冗余度进行,压缩，不改变信源的熵。无失真编码是可逆的，即当,信源符号变换成代码后，可从代码无失真地恢复出原,信源符号。只适用于离散信源。,限失真 ( 熵压缩编码 ) ：在失真受限的情况下进行限,失真编码。在连续信源的情况下，由于信源的信息量,趋于无限，显然不能用离散符号序列来完成无失真编,码，而只能进行限失真编码。,离散信源,无失真信源编码定理称为第一极限定理,离散和连续信道,信道编码定理称为第二极限定理,限失真信源编码定理称为第三极限定理,连续信源,信源编码的主要任务,符号变换：使信源输出符号与信道输入符号匹配。,减少冗余，提高编码效率。,针对信源输出符号序列的统计特性，寻找一定的方,法把信源输出符号序列变换为最短的码字序列。,信源编码的基本途径,使序列中的各个符号尽可能地互相独立，即解,除相关性，去冗余；,使编码中各个符号出现的概率尽可能地相等，,即概率均匀化。,本章讨论离散信源编码。首先从无失真编码定理,出发，重点讨论以香农码、费诺码和霍夫曼码为,代表的最佳无失真码。,5.1 编码的定义,信源编码：信源输出符号经信源编码器编码后,转换成另外的压缩符号,无失真信源编码：可精确无失真地复制信源输,出的消息,编码器的作用,将信源符号集 X 中的符号 变换成由码,符号集 y 中的码元 组成的长度为 Ki 的一,一对应的码字 。,码字集合叫做代码组Y；码字 所含码元的个数称,为该码字的码长，记为 Ki 。,分组码,将信源消息分成若干组，即符号序列，每个符号,序列依照固定码表映射成一个码字，这样的码称,为分组码，有时也叫块码。只有分组码才有对应,的码表，而非分组码中则不存在码表。,例：,若将信源 X 通过二元信道传输，就必须把信源符,号ai 变换成由0 、 1符号组成的码符号序列，这个,过程就是信源编码。,定长码,固定长度的码，码中所,有码字的长度都相同。,变长码,可变长度码，码中的码字长短不一。,定长码 变长码,若 0 、 01 都是码字，译码时如何分离？,分组码 / 块码将信源符号集中的每个符号映射成一个固,定的码字。分组码必须具有某些属性，才能保证在接,收端能够迅速可靠地译码。,码的不同属性,码表,信源符号,信源,出现概率 p(ai),符号 ai,码 1,码 2,码 3,码 4,a 1,1/2,0,0,1,1,a 2,1/4,11,10,10,01,a 3,1/8,00,00,100,001,a 4,1/8,11,01,1000,0001,奇异码,奇异码和非奇异码,1,若信源符号和码字是一一对应的，则该码为非奇异,码。反之为奇异码。,唯一可译码,2,任意有限长的码元序列，只能,被唯一地分割成一个个码字。,例： 0,10,11 是一种唯一可译码。,任意一串有限长码序列，如 100111000 ，只能被分割,成 10、0、11、10 、0、0 。任何其他分割法都会产生,一些非定义的码字。,奇异码不是唯一可译码,非唯一可译码,码 2 ，可译成 a1a1或a3,非奇异码,唯一可译码,码 3 ， 但译码有延时,非即时码,唯一可译码,即时码,非即时码,接收端收到一个完整的码字后，不能立即译码，还需,等下一个码字开始接收后才能判断是否可以译码。 码 3,即时码 ( 非延长码 ) ( 异前缀码 ),在译码时无需参考后续的码符号就能立即作出判断，,译成对应的信源符号。,码 4,任意一个码字都不是其它码字的前缀部分,码 1,码 2,码 3,码 4,ai,a1,0,0,1,1,a2,11,10,10,01,a3,00,00,100,001,a4,11,01,1000,0001,即时码,奇异码,非唯一 可译码,非即时码,用码树来构造码字,码树从树根开始向下长出 m 个树枝，成为 m 进制,码树，树枝代表码元，树枝与树枝的交点叫做节点。,经过 r 个树枝才能到达的节点称为 r 阶节点。向下不长,出树枝的节点称为终端节点或端点。 m 进制码树各节,点 ( 包括树根 ) 向下长出的树枝不会超过m，若等于m称,为满树 (整树) ，否则称为非满树 (非整树 ) 。,码树上任一节点都对应一个码字，组成该码字的,码元就是从树根开始到该节点所经过的树枝 ( 码元 ) 。,若一个码所有码字均处于终端节点，则该码为即时码。,满树 等长码,节数 码长,非满树 变长码,树码：若有 n 个信源符号，那么在码树上就要选择 n,个终端节点，用相应的 m 元基本符号表示这些码字。,任一即时码都可用树图法来表示。,当码字长度给定，即时码不是唯一的。,该码树从根到终端节点所经路径上，,每一个中间节点皆为码字，因此码 3,不是即时码，但它是唯一可译码。,唯一可译码存在的充分和必要条件,各码字的长度 K i 应符合克劳夫特 (Kraft) 不等式：,m ：码元进制数,n ：信源符号数,Ki ：各个码字的长度,例： 设二进制码树中 X( a1, a2, a3, a4)，,K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。,应用 Kraft 不等式，得：,不存在满足这种 K i 的唯一可译码,要形成满足上述长度 的码字，必须在中间 节点放置码字。,中间节点,如果将各码字长度改成：,存在唯一可译码,K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。,K1 =1 , K2 =2 , K3 =3 , K4 =3 。,注意,Kraft 不等式只是用来说明唯一可译码是,否存在，并不能作为唯一可译码的判据。,如码字 0，10，010，111 虽然满足 Kraft 不等式，,但它不是唯一可译码。,K1 =1 , K2 =2 , K3 =3 , K4 =3 。,5.2 无失真信源编码,要求能够无失真或无差错地译码，同时希望所,得编码的平均码长最小。,对信源的 L 长符号序列进行 m 进制编码，码长 KL,只要可用的码字数不少于扩展信源的符号数：,就可做到唯一译码,编码输出码,字的个数,KL/L 是平均每个信源符号所需要的码元符号个数,编码后平均每个信源符号能载荷的最大信息量为：,5.2.1 定长编码定理,在定长编码中， K=KL 是定值，且为唯一可译码。,编码的目的是寻找最小 K 值,若对信源进行定长编码，必须满足:,对于定长唯一可译码，每个信源符号至少需用,（ log n / log m ）个码符号来变换。,例: 英文电报符号， n =27 ， L =1 ， m =2( 二元编码 ),log 2 n,K ,= log 2 27 5,每个英文电报符号至少,log 2 m,要用5位二元符号编码,实际英文电报符号信源，平均每个英文电报符号所,提供的信息量约等于 1.4 比特，大大小于 5 比特。,定长编码后每个码字 (5个二元符号)只携带约1.4比特,信息量。定长编码的信息传输效率极低,当考虑信源符号出现的概率及符号间的依赖关系后,（考虑信源的冗余度），在定长编码中每个信源符,号平均所需的码长可以减少。,定长编码定理给出了信源进行定长编码所需码,长的理论极限值。,定长编码定理,编码器的平均输出信息率,对于二进制编码，每个信源符号必须,输出的码长,定长编码定理说明：,只要码字所能携带的信息量大于信源序列输出的,信息量，则可以使传输几乎无失真，当然条件是,L足够大。,当 时，不可能构成无失真的编码，也,就是不可能做一种编码器，能使收端译码时差,错概率趋于零。,当 时，则为临界状态，可能无失真，,也可能有失真。,差错概率,设差错概率用 Pe 表示，则有：, 为一正数,为信源序列的自信息方差,当 均为定值时，只要 L 足够大， Pe可以小,于任一正数。即：,当信源序列长度 L 满足,能达到差错率要求：,编码效率,编码效率总,定义编码效率为：,是小于 1,信源的平均符号熵为 HL (X) ，采用平均符号码长,为 K 来编码后所得的效率。,最佳编码效率：,编码定理从理论上阐明了编码效率接近 1 的理想编码,器的存在性，它使输出符号的信息率与信源熵之比接,近于 1 ，即：,若要实现，取无限长 L 的,信源符号进行统一编码。,例： 设离散无记忆信源概率空间为,信源熵： H ( X ) = - p ( xi ) log p ( xi ) = 2.55 bit / 符号,i = 1,对信源符号采用定长二元编码, 要求编码效率为 90 ,若取 L 1 ，则,即每个符号用 2.83bit 进行定长编码，共有 22.83 =7.11 种,可能，按 7 种可能性计算，信源符号中就有一种符号,没有对应的码字，取概率最小的 a8 ，则 Pe=0.04 , 太大,信源序列的自信息方差：,若要求译码错误概率 10-6,L 应满足：,对于定长编码，即使在编码效率和译码错误概率的要,求并不十分苛刻的情况下，就需要 10 8 个信源符号一,起进行编码。这显然是很难实现的。,5.2.2 变长编码定理,在变长编码中，码长 KL是变化的。,根据信源各个符号的统计特性，如概率大的符号用,短码，概率小的用较长的码，使得编码后平均码长,降低，从而提高编码效率。（统计匹配）,编码后码字 Y1 , Y 2 , , Y n 码长分别为 K 1 , K 2 , , K n,码的平均长度为：,编码后的信息传输率为：,对于某一信源和某一码符号集，若有一个唯一可译,码，其平均长度小于所有其他唯一可译码的平均长,度，则称该码为最佳码（紧致码）。,单个符号变长编码定理,若离散无记忆信源的符号熵为 H(X) ，每个信源符号,用 m 进制码元进行变长编码，一定存在一种无失真,编码方法，其码字平均长度 K 满足下列不等式：,H ( X ),H ( X ), K ,+ 1,log m,log m,离散平稳无记忆序列变长编码定理,对于平均符号熵为 HL(X) 的离散平稳无记忆信,源，必存在一种无失真编码方法，使平均信息率R ,满足不等式：,其中 为任意小正数。,无失真变长信源编码定理（香农第一定理）,对于平均符号熵为 HL(X) 的离散平稳无记忆信源（离散,无记忆信源 X 的 L 次扩展信源,对其进行 m 元编码，必存在一种无失真编码方法，构,成唯一可译码，使信源 X 中每个信源符号所需的平均码,长 满足：,用变长编码可达到相当高的编码效率，一般所要求,的符号长度 L 可以比定长编码小得多。,编码效率的下界,为了衡量各种编码方法与最佳码的差距，定义码的,剩余度为：,同前例：,设离散无记忆信源概率空间为,信源熵： H ( X ) = 2 . 55 bit / 符号,要求编码效率为 90 ,用二进制变长编码， m 2,例： 设离散无记忆信源概率空间为,信源熵： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信源符号,若用二元定长编码 (0,1) 来构造一个即时码：,平均码长： 二元码符号 / 信源符号,编码效率：,输出的信息传输率：,再对长度 L 为 2 的信源序列进行,变长编码，其即时码如表：,码字平均长度：,单个符号的平均码长,编码效率,输出的信息传输率： R2 0.961bit/ 二元码符号,信源序列的长度增加 :,编码复杂一些，但信息传输率有了提高,变长编码： L 2 ， 2 = 0.961,定长编码：,要求编码效率达到 96 时，允许译码错误概率 10 5,说明,(1) 定长码需要的信源序列长，使码表很大，且总存,在译码差错。而用变长码编码时， L 不需要很大就可,达到相当高的编码效率，而且可实现无失真编码。,(2) 随着信源序列长度的增加，编码的效率越来越接,近于 1 。编码后的传输率 R 也越来越接近于无噪无损,二元对称信道的信道容量 (1bit/ 二元码符号 ) ，达到信,源与信道的匹配。,最佳变长编码,5.2.3,凡是能载荷一定的信息量，且码字的平均长度最,短，可分离的变长码的码字集合称为最佳变长码。,编码主要方法有：香农编码、费诺编码、哈夫曼,编码等。,仅哈夫曼编码是真正意义下的最佳编码,哈夫曼编码效率最高，费诺编码效率次之，香农,编码效率最低，甚至低于定长编码的效率。因此，香,农编码的实用价值不大，但却有深远的理论意义，因,为按香农的方法对信源序列编码，当序列长度趋于无,穷时，平均码长会趋于信源的熵。,香农（ Shannon ）编码方法,1,香农第一定理指出了平均码长与信源之间的关系，同,时也指出了可以通过编码使平均码长达到极限值。,香农第一定理指出，选择每个码字的长度 K i 满足下,式，就可以得到香农码：,二进制香农码的编码步骤,按信源符号的概率从大到小的顺序排队，不妨设：,1,确定满足下列不等式的整数码长 K i ：,2,令 p ( a0 )=0 ，计算第 i 个消息的累加概率 P i ：,3,将累加概率 Pi 变换成二进制数，并取小数点后 Ki 位,4,作为符号 ai的编码。,例： 有一单符号离散无记忆信源,对该信源编二,进制香农码。,香农码的平均码长,信源熵,编码效率,为提高编码效率，可把 x 4 x 5 换成前面的节,点，可减小平均码长。,不应先规定码长，而是由码树来规定码,字，可得更好的结果。,例： 设信源共 7 个符号消息，其概率如表所示：,费诺（ Fano ）编码方法,概率匹配,2,按信源符号的概率从大到小的顺序排队，不妨设：,p ( a 1 ) p ( a 2 ) p ( a n ),按编码进制数将概率分组，使每组概率尽可能接,近或相等。如编二进制码就分成两组，编 m 进制,码就分成 m 组。,给每一组分配一位码元。,将每一分组再按同样原则划分，重复步骤 2 和 3 ，,直至概率不再可分为止。,信源符号对应的码字即为费诺码。,例： 对前例信源进行二进制费诺编码。,费诺编码的基本特点 :,1) 费诺编码在构造码树时，是从树根开始到终端节,点结束；,2) 由于赋码元时的任意性，因此编出的码字不唯一；,3) 费诺编码虽属于概率匹配范畴，但并未严格遵守,匹配规则，有时出现概率小的码长反而小。因此,平均码长一般不会最小。,费诺码比较适合于每次分组概率都很接近的信源，特,别是对每次分组概率都相等的信源进行编码时，可达,到理想的编码效率。,例：,对该信源进行二,进制费诺编码。,平均码长：,编码效率：,例：,二进制费诺编码,信源符号,概率,编码,码字,码长,x 1,0.25,0,0,00,2,x 2,0.25,1,01,2,x 3,0.125,0,100,3,0,x 4,0.125,1,101,3,x 5,0.0625,0,1100,4,1,0,x 6,0.0625,1,1101,4,1,x 7,0.0625,0,1110,4,1,x 8,0.0625,1,1111,4,平均码长,K = 2 . 75 码元 / 符号,每次所分两组的,信源熵,H ( X ) = 2 . 75 bit / 符号,概率恰好相等。,H ( X ),编码效率 =,= 1,K log 2,树图：,哈夫曼（ Huffman ）编码方法,3,将信源符号按概率由大到小顺序排队,1,给两个概率最小的符号各分配一个码元，将其概率,2,相加后合并作为一个新的符号，与剩下的符号一,起，再重新排队,给缩减信源中概率最小的两个符号各分配一个码元,3,4 重复步骤 2 、 3 直至概率和为 1,从最后一级开始，向前返回得到各个信源符号所对,5,应的码元序列，即相应的码字。,例：,试对该信源编二进制哈夫曼码。,读取码字的时候，要从后向前读，此,时编出来的码字是可分离的即时码。,平均码长,信源熵,H(X) = H (0.2,0.19,0.18,0.17,0.15,0.1,0.01)=2.61 bit/ 符号,编码效率,哈夫曼编码的基本特点,1) 哈夫曼编码在构造码树时，是从端点开始直到树,根结束；,2) 哈夫曼编码采用概率匹配方法来决定各码字长度，,概率大的符号对应于短码，概率小的符号对应与长,码，充分利用了短码，从而使平均码长最小；,3) 哈夫曼编码时，缩减信源的最后二个码字总是最,后一位不同，从而保证了哈夫曼码是即时码。,费诺码是从树根开始，把各节点分给某子集，若子,集已是单点集，它就是一片树叶而作为码字。,哈夫曼编码是先给每一符号一片树叶，逐步合并成,节点直到树根。,哈夫曼的编法并不惟一。,说明,每次对概率最小的符号分配 “0” 和 “1” 码元是任意,的，所以可得到不同的码字。只要在各次缩减信源,中保持码元分配的一致性，即能得到可分离码字。,不同的码元分配，得到的具体码字不同，但码长 K i,不变，平均码长也不变，所以没有本质区别。,缩减信源时，若合并后的新符号概率与其他符号概,率相等，从编码方法上来说，这几个符号的次序可,任意排列，编出的码都是正确的，但得到的码字不,相同，不同的编法得到的码字长度 K i 也不尽相同。,在哈夫曼编码过程中，对缩减信源符号按概率由大,到小的顺序重新排列时，应使合并后的新符号尽可,能排在靠前的位置，这样可使合并后的新符号重复,编码次数减少，使短码得到充分利用。,m 进制哈夫曼编码,在编 m 进制哈夫曼码时，为了使短码得到充分利用，,使平均码长最短，必须使最后一步的缩减信源有 m 个,信源符号。,缩减次数,每次缩减所减少,的信源符号个数,信源符号数 n 应满足：,不满足时：设q个概率为 0 的信源符号，使q+n 满足要求,第一次对最小概率符号分配码元时只取 (m-q) 个，分别,配以 0,1, m-q-1 ，把这些符号的概率相加作为一个新,符号的概率，与其它符号一起重新排列。以后每次取,m 个符号，分别配以 0,1, m-1；如此下去，直至所有,概率相加得 1 为止，即得到各符号的 m 进制码字。,单符号离散无记忆信源，,例,试对该信源编三进制哈夫曼码。,m =3 ， n =8,无法满足 n = s ( m -1) + m,s =3 ， q =1,q + n = s ( m -1) + m,第一次取 m - q =2 个符号进行编码,平均码长,信息传输率,编码效率,香农码、费诺码、哈夫曼码都考虑了信源的统计特,性，使经常出现的信源符号对应较短的码字，使平,均码长缩短，从而实现了对信源的压缩；,香农码有系统的、惟一的编码方法，费诺码和哈夫,曼码的编码方法都不惟一；,费诺码比较适