三章信源编码一离信源无失真编码.ppt

第三章第三章 信源编码（一）信源编码（一）离散信源无失真编码离散信源无失真编码l3.1信源及其分类l3.2离散无记忆信源的等长编码l3.3离散无记忆信源的不等长编码l3.4最佳不等长编码3.1 信源及其分类信源及其分类信源及其分类信源及其分类l离散信源l连续信源l无记忆信源l有记忆信源l简单信源－独立同分布l平稳信源，各态历经源lM阶记忆源l时间离散连续源l随机波形源3.2 离散无记忆源的等长离散无记忆源的等长编码编码离散无记忆源离散无记忆源l字母表A={a1,…,aK},概率分别为p1,…,pK,长为L的源输出序列uL={u1,…,uL}，共有KL种序列l码符号字母表B={b1,…,bD},以码符号表示源输出序列，D元码l等长D元码，能够选择的不同码字的个数为DN，不等长D元码的个数,能够选择的不同码字的个数为D1+D2+…+DN=D(DN-1)/(D-1)离散无记忆源的等长编码离散无记忆源的等长编码l编码速率编码速率 R=NlogD/Ll无错编码无错编码 (U1U2…UL)的不同事件用不同的码字来表示能够实现无错编码的充要条件是DN≥KL即编码速率R=NlogD/L≥logK）l有错编码有错编码 (U1U2…UL)的有些不同事件用相同的码字来表示。

l有错编码的译码方法与有错编码的译码方法与 “译码错误译码错误”概率概率 当使用有错编码时，必须给出译码方法（一个码字究竟翻译成哪个事件）译码错误”的概率定义为pe= P{(U1U2…UL)=(u1u2…uL)| (u1u2…uL)的码字在译码时并不译为(u1u2…uL)}离散无记忆源的等长编码离散无记忆源的等长编码关于编码速率的说明：p编码速率本来是编码设备的性能指标这就是说，首先有了编码设备的编码速率R0，然后选择N和L，使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0 ：R=NlogD/L≤R0p当编码速率R比较高时，可以选择比较大的N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度p当编码速率R比较低时，意味着使用低成本的编码设备此时只能选择不大的N，因此更需要编码的技巧 离散无记忆源的等长编码离散无记忆源的等长编码在无错编码的前提下，编码的最低代价在无错编码的前提下，编码的最低代价l当R≥logK时，能够实现无错编码l当R

但如果H(U1)R>H(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小这就是所谓“渐进无错编码”离散无记忆源的等长编码离散无记忆源的等长编码渐进无错编码渐进无错编码 （简单地说就是：当R>H(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小严格地说就是：）设给定了编码设备的编码速率R0，R0>H(U1)则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的等长编码和对应的译码方法，满足①实际的编码速率R=NlogD/L≤R0，②译码错误的概率pe<ε11）渐进无错编码的原理渐进无错编码的原理 大数定律随着L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越来越小（→0），其发生的概率却越来越大（→1） 离散无记忆源的等长编码离散无记忆源的等长编码不能渐进无错的编码不能渐进无错的编码 （简单地说就是：当R

DMS的等长编码的等长编码lNlogD≥LH(U)lH(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)l选L足够长，使 NlogD≥L[H(U)+eL]lL趋向于无穷，eL趋向于0，保证不降低效率不能保证单义可译，但可以保证非单义可译引起的误差可以渐进的任意小如何证明？弱、强弱、强e e典型序列集典型序列集定义3.2.1：令H(U)是集{U, p(ak)}的熵，e是正数，集合定义为给定源U输出的长为L的典型序列集定义3.2.2：令H(U)是集{U, p(ak)}的熵，e是正数，集合——弱e-典型序列集定义为给定源输出的长为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),则信源划分定理信源划分定理l典型序列的数目：系2：当L足够大时，对于给定的信源和e>0,典型序列的个数｜TU(L,e)｜满足信源划分定理信源划分定理l信源消息可以分为2组：（渐进等同分割性）1、典型序列 高概率集，渐进等概序列，AEP序列2、非典型序列 低概率集编码速率和等长编码定理编码速率和等长编码定理l编码速率：R=(1/L)logM=(N/L)logD, M为码字总数l可达速率：对于给定信源和编码速率R以及任意e>0，若有L0,以及编译码方法，使得L>L0,错误概率小于e，R是可达的l等长编码定理：lR>H(U),R是可达的，R

则R0>0.037587148=H(U)希望：①2元编码的实际编码速率R≤R0；②译码错误的概率不超过ε其中取ε=0.1；ε=0.05；ε=0.01DMS的等长编码的等长编码取ε=0.1找L0使得即L0=253当L≥253时总有P{(U1U2…UL)=(u1u2…uL)| -0.1≤IL-H(U) ≤0.1}≥0.9另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，DMS的等长编码的等长编码事件(u1u2…uL)属于典型序列集TU(L, 0.1)；当且仅当-0.1≤IL-H(U) ≤0.1；当且仅当DMS的等长编码的等长编码设L=253此时0.01656276L=4.19037828当事件(u1u2…u253)中a1的个数不超过4时， (u1u2…u253)∈TU(253, 0.1)；否则(u1u2…u253)不属于TU(253, 0.1)u1u2…u253)∈TU(253, 0.1)的概率不小于0.9；(u1u2…u253)∈TU(253, 0.1)的个数为DMS的等长编码的等长编码对L=253，对应地取整数N=[R0L]=126则N/L

2元编码的编码方法： 将TU(253, 0.1)中的事件用不同的126长码字表示；将TU(253, 0.1)外的事件用同一个126长码字表示，该码字已经用于表示了TU(253, 0.1)中的一个事件由于|TU(253, 0.1)|≤233.355557444<2126，码字足够用2元编码的译码方法： 将码字译为它所表示的TU(253, 0.1)中的事件(u1u2…u253) 于是，译码错误的概率为P((u1u2…u253)不属于TU(253, 0.1))≤ε=0.1DMS的等长编码的等长编码取ε=0.05找L0使得即L0=2020当L≥2020时总有P{(U1U2…UL)=(u1u2…uL)| -0.05≤IL-H(U) ≤0.05}≥0.95另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，DMS的等长编码的等长编码事件(u1u2…uL)属于典型序列集TU(L, 0.05)；当且仅当-0.05≤IL-H(U) ≤0.05；当且仅当DMS的等长编码的等长编码设L=2020此时0.01028137L=20.7683674当事件(u1u2…u2020)中a1的个数不超过20时， (u1u2…u2020)∈TU(2020, 0.05)；否则(u1u2…u2020)不属于TU(2020, 0.05)。

u1u2…u2020)∈TU(2020, 0.05)的概率不小于0.95；(u1u2…u2020)∈TU(2020, 0.05)的个数为DMS的等长编码的等长编码对L=2020，对应地取整数N=[R0L]=1010则N/L=R0，这就是说2元编码的实际编码速率等于编码设备的编码速率2元编码的编码方法： 将TU(2020, 0.05)中的事件用不同的1010长码字表示；将TU(2020, 0.05)外的事件用同一个1010长码字表示，该码字已经用于表示了TU(2020, 0.05)中的一个事件由于|TU(2020, 0.05)|≤2176.92603896<21010，码字足够用2元编码的译码方法： 将码字译为它所表示的TU(2020, 0.05)中的事件(u1u2…u2020) 于是，译码错误的概率为P((u1u2…u2020)不属于TU(2020, 0.05))≤ε=0.05DMS的等长编码的等长编码取ε=0.01找L0使得即L0=252435当L≥252435时总有P{(U1U2…UL)=(u1u2…uL)| -0.01≤IL-H(U) ≤0.01}≥0.99另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，DMS的等长编码的等长编码事件(u1u2…uL)属于典型序列集TU(L, 0.01)；当且仅当-0.01≤IL-H(U) ≤0.01；当且仅当DMS的等长编码的等长编码设L=252435。

此时0.00274372L=692.61096 ； 0.00525628L=1326.8690 当事件(u1u2…u252435)中a1的个数不超出闭区间[693，1326]内时， (u1u2…u252435)∈TU(252435, 0.01)；否则(u1u2…u252435)不属于TU(252435, 0.01)u1u2…u252435)∈ TU(252435, 0.01)的概率不小于0.99；(u1u2…u252435)∈ TU(252435, 0.01)的个数为DMS的等长编码的等长编码对L=252435，对应地取整数N=[R0L]=126217则N/L

于是，译码错误的概率为P((u1u2…u252435)不属于TU(252435, 0.01))≤ε=0.013.3 DMS的不等长编码的不等长编码DMS的不等长编码的不等长编码（1）不等长编码的优越性不等长编码的优越性 总体上减少码字的长度2）不等长编码的特殊问题不等长编码的特殊问题 唯一可译性，或者叫做可识别性对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列这个码就被称为是唯一可译的解决方案：适当地编码，使得每个码字都具有识别标记注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个这是因为两个码字c(1)和c(2) 连接成的字母串c(1)c(2) 不能是码字）平均码长平均码长希望平均码长小解决方案：概率大的事件用短码字不等长编码面临问题不等长编码面临问题l同步问题l划分唯一性l译码延迟l缓存问题几个定义几个定义l唯一可译码l逗点码，无逗点码：若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。

则称这个字母串为逗号，称此码为逗点码逗点码逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始见到逗号就识别为一个码字的开始l字头或前缀l异字头码或异前缀码：①若事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）则称此码为异字头码异字头码异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识到一个码字就识别为一个码字别为一个码字l树码，满树，非满树，全树l树码构造异字头码例子例子信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.125001100100110101101110010110111例例 观察表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编码编码异字头码可以通过树图构成异字头码可以通过树图构成lD元码l将信源符号按出现概率从大到小排列l每次信源符号化为概率近似相等的D个子集l这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短l理想情况I(ak)=nklogD, p(ak)=D-nk异字头码存在的充分必要条件异字头码存在的充分必要条件lKraft不等式l定理3.3.1: 长度为n1,n2,…,nk的D元异字头码存在的充分必要条件是：异字头码不唯一，且满足上式的码不一定是异字头码唯一可译码唯一可译码l定理3.3.2：唯一可译码必然满足Kraft不等式系：任一唯一可译码可用各相应码字长度一样的异字头码代替不等长编码定理不等长编码定理不等长编码定理不等长编码定理任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足不等长编码定理不等长编码定理证明 设信源随机变量U的概率分布为如果唯一可译的D元不等长码的码字长度为则不等长编码定理不等长编码定理因此 。

另一方面，取n1、n2、…、nK，则: 由于 , 存在码字长度为的唯一可译的D元不等长码不等长编码定理不等长编码定理对信源随机向量UL=(U1U2…UL)做唯一可译的D元不等长码此时UL的事件的个数为KL则任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足不等长编码定理不等长编码定理任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足关于不等长编码的几个概念关于不等长编码的几个概念l不等长编码的速率：l不等长编码的效率：h=H(U)/Rl码的多余度：1-h注解注解 不等长编码与等长编码具有相似的性质：当不等长编码与等长编码具有相似的性质：当L增大时，对增大时，对UL的编的编码可以使用更短的平均码长，因而更加节省码可以使用更短的平均码长，因而更加节省编码速率但编码速率但节省节省编码编码速率的下限是速率的下限是H(U)3.4最佳不等长编码最佳不等长编码两个定理两个定理1.对于给定信源，存在最佳唯一二元可译码，最小概率的两个码字码长相等且最长，他们之间仅最后一位不同2. 对辅助集为最佳的码，对原始集也是最佳的二元二元Huffman编码编码l1、将符号（符号序列）概率从大到小排列l2、最后的2个符号分别分配为0，1l3、将最后的2个符号的概率值相加，合并起来作为一新的符号l4、重复第一步骤Huffman编码编码l例(0.20,0.19,0.18,0.17,0.15,0.10,0.01)Huffman编码编码l若pj>pk，则nj≤nkl最长的2个码字码长相同l最长的2个码字除了最后一位不同外其余位置的值都相同多元多元Huffman编码编码 number = 1＋k (D - 1)LZ编码编码l是否存在编码方法与信源的统计特性无关？l基于字典编码的基本原理l定长码LZ编码：适用于长消息序列的编码，信源符号间既可以相互独立也可以有一定的相关性，当消息序列较短时，码字可能不能达到压缩的目的，但当消息序列很长时，LZ编码方法相对于只对典型序列进行编码，因此压缩效果比较好，而且实际应用也很多。

如计算机文件压缩 Eg：对下面信息序列进行LZ编码10101101001001110101000011001110101100011011 分段phrases：1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011 序号字典位置字典内容码字100011000012001000000030011100001040100110001150101010010160110000010070111100001108100011101001910010100101010101010000111011101101101011121100001011011311011100100014111010100111151111100011010116101111101游程编码游程编码l信源产生消息具有相关性，同一个消息连续输出的个数称为游程l对信源序列BBBBBBXXXXXXXAAAAAAAAJJJJJJJJJJJ编码，可得到码序列：B#6X#7A#8J#11算术编码算术编码lHuffman编码的局限性l算术编码无需计算信源序列分布，直接对信源符号序列编码，可达到渐进最佳性能l思想：计算输入信源符号序列所对应的区间，在区间内任取一点，以其二进制表示适当截断作为序列的编码结果l例题1：设无记忆源U={0，1},其概率分布矢量为{0.25, 0.75}。

对信源序列u=11011101做算术编码l例题2：无记忆信源U={1,2,3,4}，概率矢量｛0.5,0.25,0.125,0.125}，对信源序列21134121算术编码算术编码算术编码经过算术编码，上例题的结果为1000011，用7比特的码字表示了8比特的信息算术编码算术编码l1、初始化：起点P＝0，宽度A＝1l2、如码元全部处理，转第五步l3、读入的码元为0，区间的起点P不变，宽度缩短为Ap,用公式P=P，A=Ap迭代计算，转第二步l4、读入的码元为1，区间的起点右移Ap，宽度缩短为A(1-p)，用公式P=P+Ap，A=A(1-p)迭代计算，返回第二步l5、根据区间的最终宽度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)10.1110.010.110.100110.01110.110.01101120.1001010.1110.0101000120.101001110.1110.001111001130.11000011010.11110.00101101100130.1101001001110.11100.0000101101100150.1101001001110.1101100.000000101101100170.1101001001110.1101010C：用〔0,1）区间表示 第三章结束第三章结束。