[理学]信息论基础教案-第六章 无失真信源编码.ppt

第六章 无失真信源编码 * 信 源 信源编码 信道编码 信 道 信 宿 信源译码 信道译码 信源编码： 1. 信源适合信道传输 2. 无失真传输 3. 有效传输——减少信源的剩余度 第一节 单义可译定理 （一）适合信道传输 无噪信道 编码器 信 道 码字 （二）单义可译： 1. 码字与信源符号一一对应 2. 不同的符号序列——不同的码字序列 例： 1. 奇异码 2. 非奇异码 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 3. 等长码 非奇异码 0 0 0 1 1 0 1 1 单义可译 4. 非奇异码 1 1 0 1 0 0 1 0 0 0 单义可译 1 0 0 1 不即时 任何一个码字是其它码字的延长或前缀 5. 非奇异码 1 0 1 0 0 1 0 0 0 1 单义可译 0 1 即时 任何一个码字不是其它码字的延长或前缀 即 时 码 （三）即时码（非延长码）——码树 0 1 0 1 0 1 00 01 0 1 10 11 0 1 0 1 000 001 010 011 0 1 0 1 000 001 010 011 一阶节点 二阶节点 三阶节点 r1 r2 r3 （四）单义可译定理 定理：设信源S的符号集为S：{s1,s2,…,sq}，码符 号集X:{a1,a2,…,ar}，又设码字为W:{w1,w2,…,wq} 其码长分别为n1,n2,…,nq。则存在单义可译码的充 分必要条件是：q，r，ni(i=1,2,…,q)满足Kraft不等 式，即： 必要性： 非用尽： 用尽： 充分性： 单义 Kraft不等式 非延长码 第二节 码率与有效编码 平均码长： 码符/信符 bit/信符 bit/信符 码符/信符 =bit/码符 码率 Huffman码： 例1： 0 1 0 1 0 1 0 1 例2： 0 1 2 0 1 2 0 1 2 0 1 0 1 0 1 0 1 码符/信符 0 1 0 1 0 1 0 1 码符/信符 *