《第3章-无失真信源编码》由会员分享，可在线阅读，更多相关《第3章-无失真信源编码（82页珍藏版）》请在金锄头文库上搜索。
1、日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 3章 无失真信源编码 第 1节 几个概念 第 2节 单义可译码 第 3节 非延长码及其构造 第 4节 单义可译性定理 第 5节 编码长度和编码效率 第 6节 平均码长的界限定理 第 7节 第 8节 香农编码 第 9节 费诺编码 第 10节 行程编码 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 1 信源符号的码字：用来表示信源符号的数字序列 W 如在 2 信源符号码字长度：用来表示信源符号的数字序列长度 如： 第 1节 几个概念 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波
2、 符号 信源码字 符号 信源码字 A 00 E 101 B 010 F 110 C 011 G 1110 D 100 H 1111 4 变长码：各符号用不同长度的码字表示 第 1节 几个概念 符号 信源码字 符号 信源码字 A 000 E 100 B 001 F 101 C 010 G 110 D 011 H 111 3 定长码：所有的符号用相同长度的码字表示 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 符号 信源码字 符号 信源码字 A 01 E 0020 B 02 F 0021 C 000 G 00220 D 001 H 00221 第 1节 几个概念 符号 信源
3、码字 符号 信源码字 A 000 E 100 B 001 F 101 C 010 G 110 D 011 H 111 5 信源码符号：信源编码中构成信源码字的符号集 A=0,1 A=0,1,2 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 111信源 编码器 信道 , 21 1、编码原理方框图 设信源发出的符号集 S=s1,s q，每个信源符号编码成一个信源码字，对应的码字集为 W=w1,w q，每个码字均由信源码符号集 A=a1,a r中的元素组成。 第 2节 单义可译码 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 如 11 0 1 1001
4、A s w设 信 源 码 符 号 集 ， ， 信 源 符 号 编 码 成 信 源 码 字2、单义可译码 如果所有的码字与信源符号一一对应，并且连续的码字符号 也与连续的信源符号一一对应，则称编码为单义可译编码。 1) 定义： 第 2节 单义可译码 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 2节 单义可译码 符号 码字 符号 码字 A 000 E 100 B 001 F 101 C 010 G 110 D 011 H 111 符号 码字 符号 码字 A 00 E 101 B 010 F 110 C 011 G 1110 D 100 H 1111 例：若信源符号为：
5、 A 可编码为： 00 001 000 011 010 000 001 1 0 010 00 100 011 00 010 8 两种编码都是单义可译码 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 字母 符号 字母 符号 A 0 E 10 B 1 F 11 C 00 G 000 D 01 H 111 0 1 0 01 00 0 1 A B A D C A B 01 00 10 00 1 D C E C B 01 00 1 000 1 D C B G B 若接收符号序列为： 010010001，则可能有很多种可能的译码。如： 3) 例子 第 2节 单义可译码 日 思 日
6、睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 2节 单义可译码 说明： 1、单义可译码的要求一定： 信源码字与信源符号一一对应； 信源符号序列与信源码字序列一一对应。 2、通常情况下，变长码具有较高的效率（平均码字程度小） 问题： 如何判断及构造单义可译码？ 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 2节 单义可译码 1) 前缀编码条件：任何一个有效信源码字不可能是其它有效码字的前缀。 3、前缀编码：是一种单义可译码 2) 前缀编码：满足前缀编码条件的信源编码称为前缀编码 问题：前缀编码 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电
7、学院蒋碧波 1、非延长码定义 第 3节 非延长码及其构成 符号 码字 A 1 B 10 C 100 D 1000 符号 码字 A 1 B 01 C 001 D 0001 这两种编码都是单义可译码 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 3节 非延长码及其构成 例： 1001011001101 非延长码：也叫即时码，是指接收到码字后能立刻确定对应的符号。 信源符号 A B C D 编码 1 1 10 100 101 编码 2 1 01 001 000 编码 1： 100,10,1,100,1,10,1 编码 2： 1,001,01,1,001,1,01 日 思
8、日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 3节 非延长码及其构成 2 说明： 1、非延长码也叫即时码，是一种单义可译码 2、非延长码也是前缀编码，满足前缀编码条件 3、任何一种单义可译码总可以找到一种对应的具有相同码字长度的非延长码 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 0 0 0 0 0 0 0 1 1 1 1 1 1 任何一个有效码字所对应的点，不能经过另外一个有效码字对应的点。 第 3节 非延长码及其构成 3、非延长码的树图构造法 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 1、 若 下面不等式一定成立 1
9、11,0X 则 22,1,0X 则 3节 单义可译定理 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 4节 单义可译定理 2、单义可译性定理 任何一种单义可译编码，必满足克拉夫不等式；同样，只要码字长度满足克拉夫不等式，至少可以找到一种单义可译编码。 说明：满足 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 符号 码字 符号 码字 A 000 E 100 B 001 F 101 C 010 G 110 D 011 H 111 符号 码字 符号 码字 A 00 E 101 B 010 F 110 C 011 G 1110 D 100 H 111
10、1 122283331 节 单义可译定理 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 4节 单义可译定理 3、图解 0 0 0 0 0 0 0 1 1 1 1 1 1 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 4节 单义可译定理 例题： 1、已知信源码字长度分别为以下各值，至少能够找到一种单义可译码的是 （ ） A 1， 1， 3， 4 B 1， 2， 2， 3 C 1， 3， 3， 2 D 1， 2， 2， 2 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 2、下面哪种说法是 不正确 的 （ ） A 任何满
11、足 B 任何前缀编码一定满足 C 前缀编码条件是：任何一个有效信源码字不能是其它有效信源码字的前缀。 D 若某信源编码要求的编码长度满足 至少可以找到一种前缀编码。 第 4节 单义可译定理 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 2、平均码字长度，平均每个信源符号对应码字的长度 1p n 1、模型 321321321321码字长度码字概率符号第 5节 平均码长与编码有效性 信源码符号 /信源码字 平均每个信源码字由几个信源码符号组成 日 思 日 睿 笃 志 笃 行 信息论与编码 湖北大学物电学院蒋碧波 第 5节 平均码长与编码有效性 3、码率 1) 信源的熵 信源符号比特 /l 12) 信息率 () /平 均 每 信 源 符 的 信 息 量 比 特 信 源 码 符 号平 均 信 源 码 字 长 度平均每个信源信源码符号携带多少比特的信息量
