第三章 信源编码（一） 离散信源无失真编码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/L。l无错编码 (U1U2UL)的不同事件用不同的码字来表 示。能够实现无错编码的充要条件是DNKL。（即编 码速率R=NlogD/LlogK）l有错编码 (U1U2UL)的有些不同事件用相同的码字 来表示。l有错编码的译码方法与 “译码错误”概率 当使用有错 编码时，必须给出译码方法（一个码字究竟翻译成哪 个事件）。“译码错误”的概率定义为 pe= P(U1U2UL)=(u1u2uL)| (u1u2uL)的码字在译码时 并不译为(u1u2uL)。离散无记忆源的等长编码关于编码速率的说明：p编码速率本来是编码设备的性能指标。这就是说，首 先有了编码设备的编码速率R0，然后选择N和L，使得 实际的编码速率NlogD/L不能超过编码设备的编码速率 R0 ：R=NlogD/LR0。p当编码速率R比较高时，可以选择比较大的N，因此可 供选择的码字比较多，因此更容易设计出能够快速识 别的码，降低译码的难度。p当编码速率R比较低时，意味着使用低成本的编码设备 。此时只能选择不大的N，因此更需要编码的技巧。 离散无记忆源的等长编码在无错编码的前提下，编码的最低代价l当RlogK时，能够实现无错编码。l当RRH(U1)时，虽然无论怎样编码都是有错编 码，但可以适当地编码和译码使译码错误的概率pe 任意小。这就是所谓“渐进无错编码”。离散无记忆源的等长编码渐进无错编码 （简单地说就是：当RH(U1)时，可以适当地编码 和译码使得译码错误的概率pe任意小。严格地说就是：） 设给定了编码设备的编码速率R0，R0H(U1)。则对任意的0，总 存在一个L0，使得对任意的LL0，都有对(U1U2UL)的等长编 码和对应的译码方法，满足 实际的编码速率R=NlogD/LR0， 译码错误的概率pe0,当 L，PrT(L, e)1,或对所有e0，存 在有正整数L0，使得当LL0时有信源划分定理系1：特定典型序列出现的概率若uLTU(L,e),则信源划分定理l典型序列的数目： 系2：当L足够大时，对于给定的信源和e0, 典型序列的个数TU(L,e)满足信源划分定理l信源消息可以分为2组：（渐进等同分割性） 1、典型序列高概率集，渐进等概序列，AEP序列 2、非典型序列低概率集编码速率和等长编码定理l编码速率：R=(1/L)logM=(N/L)logD, M为 码字总数l可达速率：对于给定信源和编码速率R以 及任意e0，若有L0,以及编译码方法，使 得LL0,错误概率小于e，R是可达的l等长编码定理：lRH(U),R是可达的，R0.037587148=H(U)。希望： 2元编码的实际编码速率RR0； 译码错误的概率不超过。其中取 =0.1； =0.05； =0.01。DMS的等长编码取=0.1。找L0使得即L0=253。当L253时总有 P(U1U2UL)=(u1u2uL)| -0.1IL-H(U) 0.10.9。 另一方面，当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时 ，DMS的等长编码事件(u1u2uL)属于典型序列集TU(L, 0.1)；当且仅当 -0.1IL-H(U) 0.1；当且仅当DMS的等长编码设L=253。此时0.01656276L=4.19037828。 当事件(u1u2u253)中a1的个数不超过4时， (u1u2u253)TU(253, 0.1)； 否则(u1u2u253)不属于TU(253, 0.1)。 (u1u2u253)TU(253, 0.1)的概率不小于0.9； (u1u2u253)TU(253, 0.1)的个数为DMS的等长编码对L=253，对应地取整数N=R0L=126。则N/Lpk，则njnkl最长的2个码字码长相同l最长的2个码字除了最后一位不同外 其余位置的值都相同多元Huffman编码number = 1k (D - 1)LZ编码l是否存在编码方法与信源的统计特性无关？l基于字典编码的基本原理l定长码LZ编码：适用于长消息序列的编码，信源符号 间既可以相互独立也可以有一定的相关性，当 消息序列较短时，码字可能不能达到压缩的目 的，但当消息序列很长时，LZ编码方法相对 于只对典型序列进行编码，因此压缩效果比较 好，而且实际应用也很多。如计算机文件压缩 。 Eg：对下面信息序列进行LZ编码 1010110100100111010100001100111010110 0011011 分段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、初始化：起点P0，宽度A1l2、如码元全部处理，转第五步l3、读入的码元为0，区间的起点P不变，宽度缩短为 Ap,用公式P=P，A=Ap迭代计算，转第二步l4、读入的码元为1，区间的起点右移Ap，宽度缩短为 A(1-p)，用公式P=P+Ap，A=A(1-p)迭代计算，返回第 二步l5、根据区间的最终宽度A，通过2-LA2-(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.0000101101100 150.1101001001110.1101100.0000001011011 00170.1101001001110.1101010C：用0,1）区间表示 第三章结束