《离散无记忆源》由会员分享，可在线阅读，更多相关《离散无记忆源（31页珍藏版）》请在金锄头文库上搜索。
1、离散无记忆源离散无记忆源l字母表A=a1,aK,概率分别为p1,pK,长为L的源输出序列uL=u1,uL，共有KL种序列l码符号字母表B=b1,bD,以码符号表示源输出序列，D元码l等长D元码，不等长D元码的个数l单义可译码，每个消息都至少有一个码字与之对应。l单义等长可译码存在充要条件DNKL 由此可得，NLlogK/logDDMS的等长编码的等长编码lNlogDLH(U)lH(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)l选L足够长，使 NlogDLH(U)+eLlL趋向于无穷，eL趋向于0，保证不降低效率。不能保证单义可译，但可以保证非单义可译引
2、起的误差可以渐进的任意小。如何证明？弱、强弱、强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)和e0,当L，PrT(L, e)1,或对所有e0，存在有正整数L0，使得当LL0时有信源划分定理信源划分定理系1：特定典型序列出
3、现的概率若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是可达的，Rpk，则njnkl最长的2个码字码长相同l
4、最长的2个码字除了最后一位不同外其余位置的值都相同多元多元Huffman编码编码 number = 1k (D - 1)LZ编码编码l是否存在编码方法与信源的统计特性无关？l基于字典编码的基本原理l定长码LZ编码：适用于长消息序列的编码，信源符号间既可以相互独立也可以有一定的相关性，当消息序列较短时，码字可能不能达到压缩的目的，但当消息序列很长时，LZ编码方法相对于只对典型序列进行编码，因此压缩效果比较好，而且实际应用也很多。如计算机文件压缩。 Eg：对下面信息序列进行LZ编码10101101001001110101000011001110101100011011 分段phrases：1, 0
5、, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011 序号字典位置字典内容码字100011000012001000000030011100001040100110001150101010010160110000010070111100001108100011101001910010100101010101010000111011101101101011121100001011011311011100100014111010100111151111100011010116101111101算术编码算术编码lH
6、uffman编码的局限性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、如码元全部处理，转第五
7、步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)=
8、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.1101010C：用0,1）区间表示
