三章信源编码一离散信源无失真编码ppt课件

1、第三章第三章 信源编码一信源编码一离散信源无失真编码离散信源无失真编码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

2、元码，能够选择的不同码字的个数为DN，不等长D元码的个数,能够选择的不同码字的个数为D1+D2+DN=D(DN-1)/(D-1)离散无记忆源的等长编码离散无记忆源的等长编码l编码速率编码速率 lR=NlogD/L。l无错编码无错编码 (U1U2UL)的不同事件用不同的码字来表的不同事件用不同的码字来表示。能够实现无错编码的充要条件是示。能够实现无错编码的充要条件是DNKL。（即。（即编码速率编码速率R=NlogD/LlogK）l有错编码有错编码 (U1U2UL)的有些不同事件用相同的码字的有些不同事件用相同的码字来表示。来表示。l有错编码的译码方法与有错编码的译码方法与 “译码错误概率译码错误

3、概率 当使用有当使用有错编码时，必须给出译码方法一个码字究竟翻译成错编码时，必须给出译码方法一个码字究竟翻译成哪个事件）。哪个事件）。“译码错误的概率定义为译码错误的概率定义为lpe= P(U1U2UL)=(u1u2uL)| (u1u2uL)的码字的码字在译码时并不译为在译码时并不译为(u1u2uL)。离散无记忆源的等长编码离散无记忆源的等长编码关于编码速率的说明：编码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率R0，然后选择N和L，使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0 ：R=NlogD/LR0。当编码速率R比较高时，可以选择比较大的N，因此可供

4、选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。当编码速率R比较低时，意味着使用低成本的编码设备。此时只能选择不大的N，因此更需要编码的技巧。 离散无记忆源的等长编码离散无记忆源的等长编码在无错编码的前提下，编码的最低代价在无错编码的前提下，编码的最低代价当当RlogK时，能够实现无错编码。时，能够实现无错编码。当当RH(U1)时，无论怎样编码都是有错编码。这是因为时，无论怎样编码都是有错编码。这是因为RH(U1)logK。（如果（如果H(U1)=logK，则以上两种情形已经概括了全部，则以上两种情形已经概括了全部情形。但如果情形。但如果H(U1)RH(U1)时，虽然无论怎

5、样编码都是有错编码时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率，但可以适当地编码和译码使译码错误的概率pe任任意小。这就是所谓意小。这就是所谓“渐进无错编码渐进无错编码”。离散无记忆源的等长编码离散无记忆源的等长编码渐进无错编码渐进无错编码 （简单地说就是：当（简单地说就是：当RH(U1)时，可以适当地编码时，可以适当地编码和译码使得译码错误的概率和译码使得译码错误的概率pe任意小。严格地说就是：）任意小。严格地说就是：）设给定了编码设备的编码速率设给定了编码设备的编码速率R0，R0H(U1)。则对任意的。则对任意的0，总存在一个总存在一个L0，使得对任意的，使得对

6、任意的LL0，都有对，都有对(U1U2UL)的等的等长编码和对应的译码方法，满足长编码和对应的译码方法，满足实际的编码速率实际的编码速率R=NlogD/LR0，译码错误的概率译码错误的概率pe。（11渐进无错编码的原理渐进无错编码的原理 大数定律。随着大数定律。随着L的增加，的增加，(U1U2UL)的所有事件中，某些事件所占的比例越来越小（的所有事件中，某些事件所占的比例越来越小（0），其发生的概率却越来越大（），其发生的概率却越来越大（1）。）。 离散无记忆源的等长编码离散无记忆源的等长编码不能渐进无错的编码不能渐进无错的编码 （简单地说就是：当（简单地说就是：当RH(U1)时时，无论怎样编

7、码和译码都不能使译码错误的概率，无论怎样编码和译码都不能使译码错误的概率pe任任意小。严格地说就是：意小。严格地说就是： ）设给定了编码设备的编码速率设给定了编码设备的编码速率R0，R00,当L，PrT(L, e)1,或对所有e0，存在有正整数L0，使得当LL0时有( , )1rLUP uTL 信源划分定理信源划分定理()()2()2L H UL H ULP u系1：特定典型序列出现的概率若uLTU(L,),那么()()2LH ULpu信源划分定理信源划分定理l典型序列的数目：l系2：当L足够大时，对于给定的信源和e0,典型序列的个数TU(L,e)满足()()()(1)2|( , )| 2|(

8、 , )| 2L H UL H UULH UUTLTL信源划分定理信源划分定理l信源消息可以分为2组：（渐进等同分割性）l1、典型序列l 高概率集，渐进等概序列，AEP序列l2、非典型序列l 低概率集编码速率和等长编码定理编码速率和等长编码定理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.0

9、1。DMS的等长编码的等长编码取=0.1。找L0使得即L0=253。当L253时总有P(U1U2UL)=(u1u2uL)| -0.1IL-H(U) 0.10.9。另一方面，当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时，201LDV43496.252310DVL005747. 0960037. 7005747. 0965784. 7LkLkLLkIL031840148. 0960037. 7)(LkUHILDMS的等长编码的等长编码事件(u1u2uL)属于典型序列集TU(L, 0.1)；当且仅当-0.1IL-H(U) 0.1；当且仅当；当且仅当1 . 0031840148. 09

10、60037. 71 . 0Lk；当且仅当LkL01656276. 000856276. 0Lk01656276. 00DMS的等长编码的等长编码设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)的个数为6 .219253355557444.33355557444.33)1 . 0)(4025322/222占全部事件的比例为

11、；UHLkkCDMS的等长编码的等长编码对L=253，对应地取整数N=R0L=126。则N/LR0，这就是说2元编码的实际编码速率并未超出编码设备的编码速率。2元编码的编码方法： 将TU(253, 0.1)中的事件用不同的126长码字表示；将TU(253, 0.1)外的事件用同一个126长码字表示，该码字已经用于表示了TU(253, 0.1)中的一个事件。由于|TU(253, 0.1)|233.3555574442126，码字足够用。2元编码的译码方法： 将码字译为它所表示的TU(253, 0.1)中的事件(u1u2u253) 。于是，译码错误的概率为P(u1u2u253)不属于TU(253,

12、 0.1)=0.1。DMS的等长编码的等长编码取=0.05。找L0使得即L0=2020。当L2020时总有P(U1U2UL)=(u1u2uL)| -0.05IL-H(U) 0.050.95。另一方面，当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时，201LDV47968.2019310DVL005747. 0960037. 7005747. 0965784. 7LkLkLLkIL031840148. 0960037. 7)(LkUHILDMS的等长编码的等长编码事件(u1u2uL)属于典型序列集TU(L, 0.05)；当且仅当-0.05IL-H(U) 0.05；当且仅当；当且仅当

13、05. 0031840148. 0960037. 705. 0Lk；当且仅当LkL01028137. 000228137. 0Lk01028137. 00DMS的等长编码的等长编码设L=2020。此时0.01028137L=20.7683674。当事件(u1u2u2020)中a1的个数不超过20时， (u1u2u2020)TU(2020, 0.05)；否则(u1u2u2020)不属于TU(2020, 0.05)。(u1u2u2020)TU(2020, 0.05)的概率不小于0.95；(u1u2u2020)TU(2020, 0.05)的个数为07.1843202092603896.1769260

14、3896.176)01. 0)(200202022/222占全部事件的比例为；UHLkkCDMS的等长编码的等长编码对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.9260389621010，码字足够用。2元编码的译码方法： 将码字译为它所表示的TU(2020, 0

15、.05)中的事件(u1u2u2020) 。于是，译码错误的概率为P(u1u2u2020)不属于TU(2020, 0.05)=0.05。DMS的等长编码的等长编码取=0.01。找L0使得即L0=252435。当L252435时总有P(U1U2UL)=(u1u2uL)| -0.01IL-H(U) 0.010.99。另一方面，当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时，201LDV96.252434310DVL005747. 0960037. 7005747. 0965784. 7LkLkLLkIL031840148. 0960037. 7)(LkUHILDMS的等长编码的等长编码

16、事件(u1u2uL)属于典型序列集TU(L, 0.01)；当且仅当-0.01IL-H(U) 0.01；当且仅当；当且仅当01. 0031840148. 0960037. 701. 0LkLkL00525628. 000274372. 0DMS的等长编码的等长编码设L=252435。此时0.00274372L=692.61096 ； 0.00525628L=1326.8690 。 当事件(u1u2u252435)中a1的个数不超出闭区间693，1326内时， (u1u2u252435)TU(252435, 0.01)；否则(u1u2u252435)不属于TU(252435, 0.01)。(u1u

17、2u252435) TU(252435, 0.01)的概率不小于0.99；(u1u2u252435) TU(252435, 0.01)的个数为34.2404222524356617.120126617.12012)01. 0)(132669325243522/222占全部事件的比例为；UHLkkCDMS的等长编码的等长编码对L=252435，对应地取整数N=R0L=126217。则N/LR0，这就是说2元编码的实际编码速率小于编码设备的编码速率。2元编码的编码方法： 将TU(252435, 0.01)中的事件用不同的126217长码字表示；将TU(252435, 0.01)外的事件用同一个12

18、6217长码字表示，该码字已经用于表示了TU(252435, 0.01)中的一个事件。由于|TU(252435, 0.01)|212019.6617pk，则njnkl最长的2个码字码长相同l最长的2个码字除了最后一位不同外其余位置的值都相同多元多元Huffman编码编码 number = 1k (D - 1)LZ编码编码l是否存在编码方法与信源的统计特性无关？l基于字典编码的基本原理l定长码LZ编码：适用于长消息序列的编码，信源符号间既可以相互独立也可以有一定的相关性，当消息序列较短时，码字可能不能达到压缩的目的，但当消息序列很长时，LZ编码方法相对于只对典型序列进行编码，因此压缩效果比较好，

19、而且实际应用也很多。如计算机文件压缩。 Eg：对下面信息序列进行LZ编码10101101001001110101000011001110101100011011 分段phrases：1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011 序号字典位置字典内容码字10001100001200100000003001110000104010011000115010101001016011000001007011110000110810001110100191001010010101010101000011

20、1011101101101011121100001011011311011100100014111010100111151111100011010116101111101游程编码游程编码l信源产生消息具有相关性，同一个消息连续输出的个数称为游程l对信源序列BBBBBBXXXXXXXAAAAAAAAJJJJJJJJJJJ编码，可得到码序列：B#6X#7A#8J#11算术编码算术编码lHuffman编码的局限性l算术编码无需计算信源序列分布，直接对信源符号序列编码，可达到渐进最佳性能l思想：计算输入信源符号序列所对应的区间，在区间内任取一点，以其二进制表示适当截断作为序列的编码结果l例题1：设无记

21、忆源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位( )(000)(001)(010)F sppp( 0)(0000)(0001)(0010)(0011)(0100)(0101)F spppppp(000)(001)(010)( )pppF s( 1)(0000)(0001)(0010)(0011)(0100)(0101)(0110)F sppppppp(000)(001)(