第三章 信源编码（一）离散信源无失真编码

3.1信源及其分类 3.2离散无记忆信源的等长编码 3.3离散无记忆信源的不等长编码 3.4最佳不等长编码

3.1 信源及其分类

信源及其分类 离散信源 连续信源 无记忆信源 有记忆信源 简单信源－独立同分布 平稳信源，各态历经源 M阶记忆源 时间离散连续源 随机波形源

3.2 离散无记忆源的等长编码

离散无记忆源 字母表A={a1,…,aK},概率分别为p1,…,pK,长为L的源输出序列uL={u1,…,uL}，共有KL种序列 码符号字母表B={b1,…,bD},以码符号表示源输出序列，D元码 等长D元码，不等长D元码的个数 单义可译码，每个消息都至少有一个码字与之对应。 单义等长可译码存在充要条件DN≥KL 由此可得，N≥LlogK/logD

DMS的等长编码 NlogD≥LH(U) H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U) 选L足够长，使 NlogD≥L[H(U)+eL] L趋向于无穷，eL趋向于0，保证不降低效率。不能保证单义可译，但可以保证非单义可译引起的误差可以渐进的任意小。 如何证明？

弱、强e典型序列集 定义3.2.1：令H(U)是集{U, p(ak)}的熵，e是正数，集合 定义为给定源U输出的长为L的典型序列集。 定义为给定源输出的长为L的e－典型序列集，其中Lk 是在L长序列中符号ak出现的次数 ——强e-典型序列集

例3.2.2 典型二项序列出现的概率： 当L足够大，

信源划分定理 定理3.2.1:给定信源｛U, p(ak)｝和e>0,当L∞，Pr{T(L, e)}1,或对所有e>0，存在有正整数L0，使得当L>L0时有

信源划分定理 系1：特定典型序列出现的概率 若uL∈TU(L,e),则

信源划分定理 典型序列的数目： 系2：当L足够大时，对于给定的信源和e>0,典型序列的个数｜TU(L,e)｜满足

信源划分定理 信源消息可以分为2组：（渐进等同分割性） 1、典型序列 高概率集，渐进等概序列，AEP序列 2、非典型序列 低概率集

编码速率和等长编码定理 编码速率：R=(1/L)logM=(N/L)logD, M为码字总数 可达速率：对于给定信源和编码速率R以及任意e>0，若有L0,以及编译码方法，使得L>L0,错误概率小于e，R是可达的 等长编码定理： R>H(U),R是可达的，R<H(U)，R是不可达的 编码效率：h=H(U)/R

3.3 DMS的不等长编码

平均码长

不等长编码面临问题 同步问题 划分唯一性 译码延迟 缓存问题

几个定义 唯一可译码 逗点码，无逗点码 字头或前缀 异字头码或异前缀码 树码，满树，非满树，全树 树码构造异字头码

例子 信源字母集 概率 码A 码B 码C 码D a1 a2 a3 a4 0.5 0.25 0.125 1 10 00 11 110 111 1 10 00 11 110 111 01 011 0111

例 观察表3.3.1。 码A不是唯一可译的。码B不是唯一可译的。 码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码C是异字头码。 码D是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实际上，码D是逗点码，其中“0”是逗号。 码C不是逗点码。码D不是异字头码。 码C的平均码长比码D的平均码长小： 码C的平均码长为1×0.5+2×0.25+3×0.125+3×0.125=1.75； 码D的平均码长为1×0.5+2×0.25+3×0.125+4×0.125=1.875。

异字头码的第一种构造方法：Shannon-Fano编码法 （D元编码，字母表为{0, 1, …, D-1}） （1）将源随机变量的事件按概率从大到小排成一行。 （2）将此行切分为D段，分别赋予标号“0”到“D-1”，称为1级标号。 （3）将每个非空段再切分为D段，分别赋予标号“0”到“D-1”，称为2级标号。 （4）将每个非空段再切分为D段，分别赋予标号“0”到“D-1”，称为3级标号。 如此一直到每个段均含有至多一个事件为止。 此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。 为了使平均码长小，每次切分段时应使D段的概率尽可能相近。 （注解：当然可以把“切分段”操作换为“任意分组”操作，使D组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。 ）

Shannon－Fano编码 异字头码可以通过树图构成 D元码 将信源符号按出现概率从大到小排列 每次信源符号化为概率近似相等的D个子集 这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。 理想情况I(ak)=nklogD, p(ak)=D-nk

异字头码存在的充分必要条件 Kraft不等式 定理3.3.1: 长度为n1,n2,…,nk的D元异字头码存在的充分必要条件是： 异字头码不唯一，且满足上式的码不一定是异字头码

唯一可译码 定理3.3.2：唯一可译码必然满足Kraft不等式 系：任一唯一可译码可用各相应码字长度一样的异字头码代替

不等长编码定理

关于不等长编码的几个概念 不等长编码的速率： 不等长编码的效率：h=H(U)/R 码的多余度：1-h

3.4最佳不等长编码

两个定理 1.对于给定信源，存在最佳唯一二元可译码，最小概率的两个码字码长相等且最长，他们之间仅最后一位不同 2. 对辅助集为最佳的码，对原始集也是最佳的

二元Huffman编码 1、将符号（符号序列）概率从大到小排列 2、最后的2个符号分别分配为0，1 3、将最后的2个符号的概率值相加，合并起来作为一新的符号 4、重复第一步骤

Huffman编码 例(0.20,0.19,0.18,0.17,0.15,0.10,0.01)

Huffman编码 若pj>pk，则nj≤nk 最长的2个码字码长相同 最长的2个码字除了最后一位不同外其余位置的值都相同

多元Huffman编码 number = 1＋k (D - 1)

LZ编码 是否存在编码方法与信源的统计特性无关？ 基于字典编码的基本原理 定长码 LZ编码：适用于长消息序列的编码，信源符号间既可以相互独立也可以有一定的相关性，当消息序列较短时，码字可能不能达到压缩的目的，但当消息序列很长时，LZ编码方法相对于只对典型序列进行编码，因此压缩效果比较好，而且实际应用也很多。如计算机文件压缩。

Eg：对下面信息序列进行LZ编码10101101001001110101000011001110101100011011 分段phrases：1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011

序号 字典位置 字典内容 码字 1 0001 00001 2 0010 00000 3 0011 10 00010 4 0100 11 00011 5 0101 01 00101 6 0110 00 00100 7 0111 100 00110 8 1000 111 01001 9 1001 010 01010 1010 01110 1011 011 01011 12 1100 001 01101 13 1101 110 01000 14 1110 101 00111 15 1111 10001 10101 16 11101

游程编码 信源产生消息具有相关性，同一个消息连续输出的个数称为游程 对信源序列BBBBBBXXXXXXXAAAAAAAAJJJJJJJJJJJ编码，可得到码序列：B#6X#7A#8J#11

算术编码 Huffman编码的局限性 算术编码无需计算信源序列分布，直接对信源符号序列编码，可达到渐进最佳性能 思想：计算输入信源符号序列所对应的区间，在区间内任取一点，以其二进制表示适当截断作为序列的编码结果 例题1：设无记忆源U={0，1},其概率分布矢量为{0.25, 0.75}。对信源序列u=11011101做算术编码 例题2：无记忆信源U={1,2,3,4}，概率矢量｛0.5,0.25,0.125,0.125}，对信源序列21134121算术编码

算术编码 经过算术编码，上例题的结果为1000011，用7比特 的码字表示了8比特的信息

算术编码 1、初始化：起点P＝0，宽度A＝1 2、如码元全部处理，转第五步 3、读入的码元为0，区间的起点P不变，宽度缩短为Ap,用公式P=P，A=Ap迭代计算，转第二步 4、读入的码元为1，区间的起点右移Ap，宽度缩短为A(1-p)，用公式P=P+Ap，A=A(1-p)迭代计算，返回第二步 5、根据区间的最终宽度A，通过2-L≤A<2-(L-1)求得码字长度，将区间起点P截取小数点后L位，剩余部分若不为0，进位到小数点后第L位

Eg：s=011，说明U＝（000, 001, 010, 011, …, 111）, 所以 若 若 所以 其中

Eg：s=11111100，p(0)=1/4, p(1)=3/4, 所以有H(u)=0.81bit/符号； ，

A：通过计算来编码， F(s)=p(00000000)+p(00000001)+…+p(11111011) =1-p(11111111)-p(11111110)-p(11111101) -p(11111100)=1-p(1111111)-p(1111110) =1-p(111111) =1- =0.110100100111 所以C(s)=0.1101010

B：用递推公式编码 输入符号 P(s) L(s) F(s) C(s) 1 0.11 0.01 0.1 0.1001 0.0111 0.011011 2 0.100101 0.01010001 0.10100111 0.0011110011 3 0.1100001101 0.111 0.001011011001 0.110100100111 0.00001011011001 5 0.11011 0.0000001011011001 7 0.1101010

C：用〔0,1）区间表示

第三章结束