计算机软件及应用信源编码PPT课件

1、信源编码 信源编码是以提高通信的有效性为目的编码。 通常通过压缩信源的冗余度来实现。 采用的一般方法是压缩每个信源符号的平均比特 数或信源的码率。同样多的信息用较少的码率来 传送，使单位时间内传送的平均信息量增加，从 而提高通信的有效性。 在不失真或允许失真的条件下，用 尽可能少的符号传送信源信息。 第1页/共69页 信道编码： 是以提高信息传输的可靠性为目的的编码。 通常通过增加信源的冗余度来实现。采用的 一般方法是增大码率/带宽。 在信道受干扰的情况下增加信号的抗干 扰能力，同时又使得信息传输率最大。 密码： 是以提高通信系统的安全性为目的的编码。 通常通过加密和解密来实现。 第2页/共6

2、9页无失真编码 无失真信源编码定理 信源编码 限失真编码 限失真信源编码定理 无失真 ( 冗余度压缩编码 ) ：仅对信源的冗余度进行 压缩，不改变信源的熵。无失真编码是可逆的，即当 信源符号变换成代码后，可从代码无失真地恢复出原 信源符号。只适用于离散信源。 限失真 ( 熵压缩编码 ) ：在失真受限的情况下进行限 失真编码。在连续信源的情况下，由于信源的信息量 趋于无限，显然不能用离散符号序列来完成无失真编 码，而只能进行限失真编码。 第3页/共69页离散信源 无失真信源编码定理称为第一极限定理 离散和连续信道 信道编码定理称为第二极限定理 限失真信源编码定理称为第三极限定理 连续信源 信源编

3、码的主要任务 符号变换：使信源输出符号与信道输入符号匹配。 减少冗余，提高编码效率。 针对信源输出符号序列的统计特性，寻找一定的方 法把信源输出符号序列变换为最短的码字序列。 第4页/共69页信源编码的基本途径 使序列中的各个符号尽可能地互相独立，即解 除相关性，去冗余； 使编码中各个符号出现的概率尽可能地相等， 即概率均匀化。 本章讨论离散信源编码。首先从无失真编码定理 出发，重点讨论以香农码、费诺码和霍夫曼码为 代表的最佳无失真码。 第5页/共69页5.1 编码的定义 信源编码：信源输出符号经信源编码器编码后 转换成另外的压缩符号 无失真信源编码：可精确无失真地复制信源输 出的消息 第6页

4、/共69页编码器的作用 将信源符号集 X 中的符号 变换成由码 符号集 y 中的码元 组成的长度为 Ki 的一 一对应的码字 。 码字集合叫做代码组Y；码字 所含码元的个数称 为该码字的码长，记为 Ki 。 第7页/共69页分组码 将信源消息分成若干组，即符号序列，每个符号 序列依照固定码表映射成一个码字，这样的码称 为分组码，有时也叫块码。只有分组码才有对应 的码表，而非分组码中则不存在码表。 例：若将信源 X 通过二元信道传输，就必须把信源符 号ai 变换成由0 、 1符号组成的码符号序列，这个 过程就是信源编码。 第8页/共69页定长码 固定长度的码，码中所 有码字的长度都相同。 变长码

5、 可变长度码，码中的码字长短不一。 定长码 变长码 若 0 、 01 都是码字，译码时如何分离？ 分组码 / 块码将信源符号集中的每个符号映射成一个固 定的码字。分组码必须具有某些属性，才能保证在接 收端能够迅速可靠地译码。 第9页/共69页码的不同属性 码表 信源符号 信源 出现概率 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 若信源符号和码字是一一对应的，则该码为非奇异 码。反之为奇异码

6、。 第10页/共69页唯一可译码 2 任意有限长的码元序列，只能 被唯一地分割成一个个码字。 例： 0,10,11 是一种唯一可译码。 任意一串有限长码序列，如 100111000 ，只能被分割 成 10、0、11、10 、0、0 。任何其他分割法都会产生 一些非定义的码字。 奇异码不是唯一可译码 非唯一可译码 码 2 ，可译成 a1a1或a3 非奇异码 唯一可译码 码 3 ， 但译码有延时 第11页/共69页非即时码 唯一可译码 即时码 非即时码 接收端收到一个完整的码字后，不能立即译码，还需 等下一个码字开始接收后才能判断是否可以译码。 码 3 即时码 ( 非延长码 ) ( 异前缀码 )

7、在译码时无需参考后续的码符号就能立即作出判断， 译成对应的信源符号。 码 4 任意一个码字都不是其它码字的前缀部分 第12页/共69页码 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 即时码 奇异码 非唯一 可译码非即时码 第13页/共69页用码树来构造码字 码树从树根开始向下长出 m 个树枝，成为 m 进制 码树，树枝代表码元，树枝与树枝的交点叫做节点。 经过 r 个树枝才能到达的节点称为 r 阶节点。向下不长 出树枝的节点称为终端节点或端点。 m 进制码树各节 点 ( 包括树根

8、) 向下长出的树枝不会超过m，若等于m称 为满树 (整树) ，否则称为非满树 (非整树 ) 。 码树上任一节点都对应一个码字，组成该码字的 码元就是从树根开始到该节点所经过的树枝 ( 码元 ) 。 若一个码所有码字均处于终端节点，则该码为即时码。 第14页/共69页满树 等长码 节数 码长 非满树 变长码 第15页/共69页树码：若有 n 个信源符号，那么在码树上就要选择 n 个终端节点，用相应的 m 元基本符号表示这些码字。 任一即时码都可用树图法来表示。 当码字长度给定，即时码不是唯一的。 该码树从根到终端节点所经路径上， 每一个中间节点皆为码字，因此码 3 不是即时码，但它是唯一可译码。

9、 第16页/共69页唯一可译码存在的充分和必要条件 各码字的长度 K i 应符合克劳夫特 (Kraft) 不等式： m ：码元进制数 n ：信源符号数 Ki ：各个码字的长度 例： 设二进制码树中 X( a1, a2, a3, a4)， K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。 第17页/共69页应用 Kraft 不等式，得：不存在满足这种 K i 的唯一可译码 要形成满足上述长度的码字，必须在中间 节点放置码字。 中间节点如果将各码字长度改成：存在唯一可译码 K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。 K1 =1 , K2 =2 , K3 =3 ,

10、K4 =3 。 第18页/共69页注意 Kraft 不等式只是用来说明唯一可译码是 否存在，并不能作为唯一可译码的判据。 如码字 0，10，010，111 虽然满足 Kraft 不等式， 但它不是唯一可译码。 K1 =1 , K2 =2 , K3 =3 , K4 =3 。 第19页/共69页5.2 无失真信源编码 要求能够无失真或无差错地译码，同时希望所 得编码的平均码长最小。 第20页/共69页对信源的 L 长符号序列进行 m 进制编码，码长 KL 只要可用的码字数不少于扩展信源的符号数：就可做到唯一译码 编码输出码 字的个数 KL/L 是平均每个信源符号所需要的码元符号个数 编码后平均每个

11、信源符号能载荷的最大信息量为： 第21页/共69页定长编码定理 在定长编码中， 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位二元符号编码 第22页/共69页 实际英文电报符号信源，平均每个英文电报符号所 提供的信息量约等于 1.4 比特，大大小于 5 比特。 定长编码后每个码字

12、(5个二元符号)只携带约1.4比特 信息量。定长编码的信息传输效率极低 当考虑信源符号出现的概率及符号间的依赖关系后 （考虑信源的冗余度），在定长编码中每个信源符 号平均所需的码长可以减少。 定长编码定理给出了信源进行定长编码所需码 长的理论极限值。 第23页/共69页定长编码定理 第24页/共69页 编码器的平均输出信息率 对于二进制编码，每个信源符号必须 输出的码长 定长编码定理说明： 第25页/共69页只要码字所能携带的信息量大于信源序列输出的 信息量，则可以使传输几乎无失真，当然条件是 L足够大。 当 时，不可能构成无失真的编码，也 就是不可能做一种编码器，能使收端译码时差 错概率趋于

13、零。 当 时，则为临界状态，可能无失真， 也可能有失真。 第26页/共69页 差错概率 设差错概率用 Pe 表示，则有： 为一正数 为信源序列的自信息方差 当 均为定值时，只要 L 足够大， Pe可以小 于任一正数。即：当信源序列长度 L 满足能达到差错率要求：第27页/共69页 编码效率 编码效率总 定义编码效率为：是小于 1 信源的平均符号熵为 HL (X) ，采用平均符号码长 为 K 来编码后所得的效率。 最佳编码效率：编码定理从理论上阐明了编码效率接近 1 的理想编码 器的存在性，它使输出符号的信息率与信源熵之比接 近于 1 ，即：若要实现，取无限长 L 的 信源符号进行统一编码。 第

14、28页/共69页例： 设离散无记忆信源概率空间为 信源熵： 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 , 太大 第29页/共69页 信源序列的自信息方差： 若要求译码错误概率 10-6 L 应满足：对于定长编码，即使在编码效率和译码错误概率的要 求并不十分苛刻的情况下，就

15、需要 10 8 个信源符号一 起进行编码。这显然是很难实现的。 第30页/共69页变长编码定理 在变长编码中，码长 KL是变化的。 根据信源各个符号的统计特性，如概率大的符号用 短码，概率小的用较长的码，使得编码后平均码长 降低，从而提高编码效率。（统计匹配） 编码后码字 Y1 , Y 2 , , Y n 码长分别为 K 1 , K 2 , , K n 码的平均长度为：编码后的信息传输率为： 第31页/共69页对于某一信源和某一码符号集，若有一个唯一可译 码，其平均长度小于所有其他唯一可译码的平均长 度，则称该码为最佳码（紧致码）。 单个符号变长编码定理 若离散无记忆信源的符号熵为 H(X)

16、，每个信源符号 用 m 进制码元进行变长编码，一定存在一种无失真 编码方法，其码字平均长度 K 满足下列不等式： H ( X ) H ( X ) K + 1 log m log m 第32页/共69页离散平稳无记忆序列变长编码定理 对于平均符号熵为 HL(X) 的离散平稳无记忆信 源，必存在一种无失真编码方法，使平均信息率R 满足不等式： 其中 为任意小正数。 第33页/共69页无失真变长信源编码定理（香农第一定理） 对于平均符号熵为 HL(X) 的离散平稳无记忆信源（离散 无记忆信源 X 的 L 次扩展信源对其进行 m 元编码，必存在一种无失真编码方法，构 成唯一可译码，使信源 X 中每个信

17、源符号所需的平均码 长 满足：第34页/共69页用变长编码可达到相当高的编码效率，一般所要求 的符号长度 L 可以比定长编码小得多。 编码效率的下界 为了衡量各种编码方法与最佳码的差距，定义码的 剩余度为：第35页/共69页同前例： 设离散无记忆信源概率空间为 信源熵： H ( X ) = 2 . 55 bit / 符号 要求编码效率为 90 用二进制变长编码， m 2 第36页/共69页例： 设离散无记忆信源概率空间为 信源熵： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信源符号 若用二元定长编码 (0,1) 来构造一个即时码： 平均码长：

18、二元码符号 / 信源符号 编码效率： 输出的信息传输率：第37页/共69页再对长度 L 为 2 的信源序列进行 变长编码，其即时码如表： 码字平均长度： 单个符号的平均码长 编码效率 输出的信息传输率： R2 0.961bit/ 二元码符号 第38页/共69页信源序列的长度增加 : 编码复杂一些，但信息传输率有了提高 变长编码： L 2 ， 2 = 0.961 定长编码： 要求编码效率达到 96 时，允许译码错误概率 10 5 第39页/共69页说明 (1) 定长码需要的信源序列长，使码表很大，且总存 在译码差错。而用变长码编码时， L 不需要很大就可 达到相当高的编码效率，而且可实现无失真编

19、码。 (2) 随着信源序列长度的增加，编码的效率越来越接 近于 1 。编码后的传输率 R 也越来越接近于无噪无损 二元对称信道的信道容量 (1bit/ 二元码符号 ) ，达到信 源与信道的匹配。 第40页/共69页最佳变长编码 凡是能载荷一定的信息量，且码字的平均长度最 短，可分离的变长码的码字集合称为最佳变长码。 编码主要方法有：香农编码、费诺编码、哈夫曼 编码等。 仅哈夫曼编码是真正意义下的最佳编码 哈夫曼编码效率最高，费诺编码效率次之，香农 编码效率最低，甚至低于定长编码的效率。因此，香 农编码的实用价值不大，但却有深远的理论意义，因 为按香农的方法对信源序列编码，当序列长度趋于无 穷时

20、，平均码长会趋于信源的熵。 第41页/共69页香农（ Shannon ）编码方法 1 香农第一定理指出了平均码长与信源之间的关系，同 时也指出了可以通过编码使平均码长达到极限值。 香农第一定理指出，选择每个码字的长度 K i 满足下 式，就可以得到香农码： 第42页/共69页二进制香农码的编码步骤 按信源符号的概率从大到小的顺序排队，不妨设： 1 确定满足下列不等式的整数码长 K i ： 2 令 p ( a0 )=0 ，计算第 i 个消息的累加概率 P i ： 3 将累加概率 Pi 变换成二进制数，并取小数点后 Ki 位 4 作为符号 ai的编码。 第43页/共69页例： 有一单符号离散无记忆

21、信源 对该信源编二 进制香农码。 第44页/共69页 香农码的平均码长 信源熵 编码效率 为提高编码效率，可把 x 4 x 5 换成前面的节 点，可减小平均码长。 不应先规定码长，而是由码树来规定码 字，可得更好的结果。 第45页/共69页例： 设信源共 7 个符号消息，其概率如表所示： 第46页/共69页费诺（ Fano ）编码方法 概率匹配 2 按信源符号的概率从大到小的顺序排队，不妨设： p ( a 1 ) p ( a 2 ) p ( a n ) 按编码进制数将概率分组，使每组概率尽可能接 近或相等。如编二进制码就分成两组，编 m 进制 码就分成 m 组。 给每一组分配一位码元。 将每一

22、分组再按同样原则划分，重复步骤 2 和 3 ， 直至概率不再可分为止。 信源符号对应的码字即为费诺码。 第47页/共69页例： 对前例信源进行二进制费诺编码。 第48页/共69页费诺编码的基本特点: 1) 费诺编码在构造码树时，是从树根开始到终端节 点结束； 2) 由于赋码元时的任意性，因此编出的码字不唯一； 3) 费诺编码虽属于概率匹配范畴，但并未严格遵守 匹配规则，有时出现概率小的码长反而小。因此 平均码长一般不会最小。 费诺码比较适合于每次分组概率都很接近的信源，特 别是对每次分组概率都相等的信源进行编码时，可达 到理想的编码效率。 第49页/共69页例： 对该信源进行二 进制费诺编码。

23、 平均码长： 编码效率：第50页/共69页例： 二进制费诺编码 信源符号 概率 编码 码字 码长 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

24、log 2 第51页/共69页树图： 第52页/共69页哈夫曼（ Huffman ）编码方法 3 将信源符号按概率由大到小顺序排队 1 给两个概率最小的符号各分配一个码元，将其概率 2 相加后合并作为一个新的符号，与剩下的符号一 起，再重新排队 给缩减信源中概率最小的两个符号各分配一个码元 3 4 重复步骤 2 、 3 直至概率和为 1 从最后一级开始，向前返回得到各个信源符号所对 5 应的码元序列，即相应的码字。 第53页/共69页例：试对该信源编二进制哈夫曼码。 读取码字的时候，要从后向前读，此 时编出来的码字是可分离的即时码。 第54页/共69页平均码长 信源熵 H(X) = H (0.

25、2,0.19,0.18,0.17,0.15,0.1,0.01)=2.61 bit/ 符号 编码效率 第55页/共69页哈夫曼编码的基本特点 1) 哈夫曼编码在构造码树时，是从端点开始直到树 根结束； 2) 哈夫曼编码采用概率匹配方法来决定各码字长度， 概率大的符号对应于短码，概率小的符号对应与长 码，充分利用了短码，从而使平均码长最小； 3) 哈夫曼编码时，缩减信源的最后二个码字总是最 后一位不同，从而保证了哈夫曼码是即时码。 第56页/共69页费诺码是从树根开始，把各节点分给某子集，若子 集已是单点集，它就是一片树叶而作为码字。 哈夫曼编码是先给每一符号一片树叶，逐步合并成 节点直到树根。

26、第57页/共69页哈夫曼的编法并不惟一。 说明 每次对概率最小的符号分配 “0” 和 “1” 码元是任意 的，所以可得到不同的码字。只要在各次缩减信源 中保持码元分配的一致性，即能得到可分离码字。 不同的码元分配，得到的具体码字不同，但码长 K i 不变，平均码长也不变，所以没有本质区别。 缩减信源时，若合并后的新符号概率与其他符号概 率相等，从编码方法上来说，这几个符号的次序可 任意排列，编出的码都是正确的，但得到的码字不 相同，不同的编法得到的码字长度 K i 也不尽相同。 第58页/共69页 在哈夫曼编码过程中，对缩减信源符号按概率由大 到小的顺序重新排列时，应使合并后的新符号尽可 能排

27、在靠前的位置，这样可使合并后的新符号重复 编码次数减少，使短码得到充分利用。 第59页/共69页m 进制哈夫曼编码 在编 m 进制哈夫曼码时，为了使短码得到充分利用， 使平均码长最短，必须使最后一步的缩减信源有 m 个 信源符号。 缩减次数 每次缩减所减少 的信源符号个数 信源符号数 n 应满足：不满足时：设q个概率为 0 的信源符号，使q+n 满足要求 第一次对最小概率符号分配码元时只取 (m-q) 个，分别 配以 0,1, m-q-1 ，把这些符号的概率相加作为一个新 符号的概率，与其它符号一起重新排列。以后每次取 m 个符号，分别配以 0,1, m-1；如此下去，直至所有 概率相加得 1 为止，即得到各符号的 m 进制码字。 第60页/共69页单符号离散无记忆信源， 例 试对该信源编三进制哈夫曼码。 m =3 ， n =8 无法满足 n = s ( m -1) + m s =3 ， q =1 q + n = s ( m -1) + m 第一次取 m - q =2 个符号进行编码 第61页/共69页第62页/共69页平均码长 信息传输率 编码效率 第63页/共69页 香农码、费诺码、哈夫曼码都考虑了信源的统计特 性，使经常出现的信源符号对应较短的码字，使平 均码长缩短，从而实现了对信源的压缩； 香农码有系统的、惟一的编码方法，费诺码和哈夫 曼码的编码方法都不惟一；