信息论与编码第5章-信源编码.ppt

2020/5/5,1,编码,信息传输需要解决的两个问题：在不失真或允许一定失真的条件下，如何用尽可能少的信息率来传送信源信息？在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大？有效性和可靠性提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。,信源编码,信道编码,2020/5/5,2,编码,编码的分类信道编码：以提高信息传输的可靠性为目的的编码通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。密码：以提高通信系统的安全性为目的的编码通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,第一极限定理,第三极限定理,第二极限定理,2020/5/5,3,编码,信源编码：以提高通信系统的有效性为目的的编码信源符号之间存在分布不均匀和相关性，使得信源存在冗余度。主要任务：减少冗余，提高编码效率。即用较少的码率传送较多的信息，使单位时间内传送的平均信息量增加，从而提高通信的有效性。针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。解除相关性：使序列中的各个符号尽可能地互相独立概率均匀化：使编码中各个符号出现的概率尽可能地相等,2020/5/5,4,编码,无失真编码定理可逆编码的基础。当信源符号转换成代码后，可从代码无失真地恢复原符号。适用于离散信源/数字信号编码。限失真编码定理对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为取值可以有无限多个。此时只能根据限失真编码定理进行限失真编码。适用于连续信源/模拟信号编码。,2020/5/5,5,第5章信源编码,5.1编码的定义5.2无失真信源编码5.3限失真信源编码定理5.4常用信源编码方法简介,游程编码、算术编码,2020/5/5,6,编码的定义,编码器输入端为原始信源X=(X1X2XlXL)，其符号集为A，即Xla1,a2,ai,an信道所能传输的符号集B=b1,b2,bj,bm编码器的功能是用符号集B中的元素，将原始信源的符号序列Xi变换为相应的符号序列Yj=(Y1Y2YjYKL),2020/5/5,7,编码的定义,设信源输出的符号序列长度为1，即信源符号集为X=x1,x2,xi,xn，信源概率空间为,二元信道是常用的一种信道，其基本符号集为0,1若将信源X通过一个二元信道传输，就必须把信源符号xi变换成由0,1符号组成的码符号序列，即编码。,分组码：每个符号序列Xi依照固定的码表映射成一个符号序列Yj,2020/5/5,8,术语,码字：码长：码元：码：编码：,变换后的各个符号序列Yj,码字Yj的长度（符号数）KL,组成码字Yj的各位代码符号bj,所有码字的集合,全部XiYj的映射关系,2020/5/5,9,编码的定义,定长码和变长码定长码：所有码字的长度都相同变长码：可变长度码，码中的码字长短不一,2020/5/5,10,编码的定义,奇异码和非奇异码奇异码：一组码中有相同的码字。如码1非奇异码：信源符号和码字一一对应，所有码字都不相同。唯一可译码任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码。奇异码不是唯一可译码，而非奇异码中有非唯一可译码（如码2）和唯一可译码（如码3）。,2020/5/5,11,编码的定义,非即时码和即时码非即时码：指接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。如码3即时码：无须考虑后续的码符号，即可从码元序列中译出码字。如码4唯一可译码成为即时码的充分条件是：其中任何一个码字都不是其他码字的前缀。,2020/5/5,12,编码的定义,码,非分组码分组码,奇异码非奇异码,非唯一可译码唯一可译码,非即时码即时码（非延长码）,所有的码,非奇异码,唯一可译码,即时码,2020/5/5,13,码树,码树用来表示各码字的构成。,树根码字的起点,分成r个树枝码的进制数,中间节点生出树枝,终端节点码字1101,0021,2020/5/5,14,码树,中间节点不安排码字，只在终端节点安排码字每个终端节点对应的码字由从根节点出发到终端节点走过的路径上所对应的符号组成当第i阶的节点作为终端节点，且分配码字，则码字的码长为i按树图法构成的码一定满足即时码的定义树码的各个分支都延伸到最后一级端点，则称为满树，否则为非满树满树码是定长码，非满树码是变长码,2020/5/5,15,码树,克劳夫特不等式唯一可译码存在的充分和必要条件为：各码字的长度Ki应满足下式。m是进制数，n是信源符号数注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据。,2020/5/5,16,例题,设二进制码树中X=x1,x2,x3,x4，K1=1,K2=2,K3=2,K4=3，由上述定理，可得因此不存在满足这种码长的唯一可译码。,0,0,1,1,0,10,11,110,如果将各码字长度改成K1=1,K2=2,K3=3,K4=3，则存在满足这种码长的唯一可译码。,111,中间节点,2020/5/5,17,唯一可译码的判断法,将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。集合F的构成方法首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀（或者某些码字是这些尾随后缀的前缀），再将这些尾随后缀产生的新的尾随后缀列出。依此下去，直到没有一个尾随后缀是码字的前缀为止。按照上述步骤将次短码字、等等所有码字可能产生的尾随后缀全部列出。最终得到码C的所有可能的尾随后缀的集合F。,2020/5/5,18,例题,例：设码C=0,10,1100,1110,1011,1101，根据上述测试方法，判断是否是唯一可译码解：1.先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀。2.再观察次短码字“10”，它是码字“1011”的前缀，因此有尾随后缀“11”。“11”是码字“1100”、“1110”和“1101”的前缀，得到后缀“00”、“10”和“01”。“0”是新尾随后缀“00”和“01”的前缀，产生后缀“0”和“1”，“1”又产生新后缀“100”、“110”、“011”和“101”最终得到集合F=11,00,10,01,0,1,100,110,011,101。其中“10”、“0”为码字，故码C不是唯一可译码。,101110,101110,101110,2020/5/5,19,唯一可译码判断方法和步骤,首先，观察是否是奇异码。若是，一定不是唯一可译码。其次，计算码长是否满足Kraft不等式。若不满足，一定不是唯一可译码。按照树图的构造法则，若能将码画成码树则是即时码，也就是唯一可译码。按唯一可译码判断法进行判断。,只有唯一可译码判断法能确切判断是否是唯一可译码,2020/5/5,20,第5章信源编码,5.1编码的定义5.2无失真信源编码5.3限失真信源编码定理5.4常用信源编码方法简介,2020/5/5,21,有mKL种可能的组合,无失真信源编码,设信源符号序列的长度为L变换成由KL个符号组成的码序列（码字）,有nL种序列组合,有nL种信源消息,有mKL种可能的码字,2020/5/5,22,无失真信源编码,变换要求能够无失真或无差错地从Y恢复X，也就是能正确地进行反变换或译码传送Y时所需要的信息率最小信息率Yk有m种可能值，平均每个符号输出的最大信息量为log2m，KL长码字的最大信息量为KLlog2m。用该码字表示L长的信源序列，送出一个信源符号所需要的信息率平均为,Y所能编成的码字的个数,找到使最小的编码方式,2020/5/5,23,定长编码,在定长编码中，各码字的码长相等，即K为定值。编码器输入X=(X1X2XlXL),Xla1,an,输入的消息总共有nL种可能的组合输出的码字Y=(Y1Y2YkYK),Ykb1,bm输出的码字总共有mK种可能的组合只要码长K足够长，即满足:则每个信源符号串都可以找到一一对应的码字定长编码的目的：寻找最小K值,2020/5/5,24,例题,例如英文电报有27个符号，n=27，L=1，m=2(二元编码)在考虑了符号出现的概率以及符号之间的依赖性后，实际英文电报符号信源平均每个符号所提供的信息量约等于1.4比特，大大小于5比特。编码后，5个二元符号只携带约1.4比特信息量。定长编码的信息传输效率极低。,每个英文电报符号至少要用5位二元符号编码,2020/5/5,25,定长编码定理,定长编码定理：由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL个符号Y1,Y2,Yk,YKL（每个符号有m种可能值）进行定长编码。对任意0，0，只要则当L足够大时，必可使译码差错小于；反之，当时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。,2020/5/5,26,定长编码定理,当编码器容许的输出信息率，即每个信源符号所需要的信息率为时，只要，这种编码器一定可以做到几乎无失真，也就是收端的译码差错概率接近于零，条件是所取的符号数L足够大。定理的条件可以改写为,KL长码字所能携带的最大信息,L长信源序列携带的信息量,2020/5/5,27,定长编码定理,定理表明：只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，条件是L足够大。反之，当时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，也可能有失真。,2020/5/5,28,例题,例：某信源有8种等概率符号，L=1时，信源熵H1(X)=3bit/符号。若采用二进制编码，则用3位二进制码元表示一个信源符号。当信源符号输出概率不相等时，p(ai)=0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04则H1(X)=2.55bit/符号，即用2.55位二进制码元代表一个信源符号。部分信源符号没有对应的码字，引起差错。,22.55=5.856,2020/5/5,29,差错概率,差错概率式中，为信源序列的自信息方差，为一正数。当自信息方差和均为定值时，只要L足够大，Pe可以小于任一正数。当信源序列长度L满足时，就能达到差错率要求。,2020/5/5,30,编码效率,编码效率信源的平均符号熵HL(X)，采用平均符号信息率来编码，所得的效率。最佳编码效率为编码定理从理论上给出了编码效率接近1的理想编码器的存在，即,2020/5/5,31,例题,例：设离散无记忆信源概率空间为信源熵为自信息方差,2020/5/5,32,例题,要求编码效率为90%，则要求译码错误概率，得说明：在对编码效率和译码错误概率要求不十分苛刻的情况下，仍然需要对非常大数量的信源符号同时编码，对存储或处理技术要求太高。,2020/5/5,33,变长编码定理,在变长编码中，码长K是变化的。我们可根据信源各个符号的统计特性，概率大的符号用短码，概率小的用较长的码，这样在大量信源符号编成码后平均每个信源符号所需的输出符号数就可以降低，从而提高编码效率。,2020/5/5,34,变长编码定理,单个符号变长编码定理若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式,2020/5/5,35,变长编码定理,离散平稳无记忆序列变长编码定理对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中，为任意小正数。,2020/5/5,36,变长编码定理,编码效率的下界编码效率总是小于1的，可以用它来衡量各种编码方法的优劣。码的剩余度：衡量各种编码方法与最佳码的差距如上例中，H(X)=2.55比特/符号，若m=2，=90%，则用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。,2020/5/5,37,例题,例：设离散无记忆信源的概率空间为信源熵：若用二元定长编码(0,1)来构造一个即时码:x10,x21，则平均码长为编码效率为输出的信息率为,R代表平均每个码元携带的信息量，即编码后信道的信息传输率。在二元无噪无损信道中，R,2020/5/5,38,例题,对长度为L=2的信源序列进行变长编码，其即时码如表所示。平均码长为,每个符号的平均码长为编码效率为信息传输率为,2020/5/5,39,例题,增加信源序列长度为L3或L=4编码效率分别为信息传输率分别为如果对该信源采用定长二元码编码，要求编码效率达到96时，允许译码错误概率10-5自信息方差为所需要的信源序列长度为,2020/5/5,40,最佳编码,最佳码（紧致码）对于某个给定信源，在所有可能的唯一可译码中平均码长最短的码。最佳码可能不止一个。平均码长为了使平均码长最短，将概率大的信息符号编以短的码字，概率小的符号编以长的码字。,2020/5/5,41,香农编码方法,香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值。香农第一定理指出，选择每个码字的长度Ki满足就可以得到这种码。这种编码方法称为香农编码。,2020/5/5,42,香农编码步骤,将信源消息符号按其概率从大到小排列确定满足下列不等式的整数码长Ki令P1=0，计算第i个消息的累加概率将累加概率Pi变换成二进制数，取小数点后Ki位为该消息的码字,2020/5/5,43,例题,例题：有一单符号离散无记忆信源，对该信源编二进制香农码。,码字长度：K3=log0.2=3累加概率：Pi=0.700.10110,0,0.4,0.7,0.9,0.95,1.32,1.73,2.32,4.3,4.3,2,2,3,5,5,00,01,101,11100,11110,2020/5/5,44,例题,香农编码的平均码长信源熵编码效率,2020/5/5,45,例题,例：设信源共7个符号消息，其概率和累加概率如下表所示。,2020/5/5,46,例题,信源符号的平均码长信源熵平均信息传输率,2020/5/5,47,费诺编码方法,费诺编码属于概率匹配编码，不是最佳的编码方法。编码过程如下：将信源消息符号按其出现的概率依次排列p(x1)p(x2)p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等，并为每一组分配一位码元。如编二进制码就分成两组，编m进制码就分成m组。将每一分组再按同样原则划分，重复步骤2，直至概率不再可分为止。信源符号所对应的码字即为费诺码。,2020/5/5,48,费诺编码方法,例：对以下单符号离散信源编二进制费诺码,0,1,0,1,0,1,0,1,00,010,011,10,11,2,3,3,2,2,0,1,0,1,0,1,0,1,0,10,110,1110,1111,1,2,3,4,4,2020/5/5,49,费诺编码方法,信源熵平均码长编码效率,费诺码比较适合于每次分组概率都很接近的信源,2020/5/5,50,费诺编码方法,例：有一单符号离散无记忆信源对该信源编二进制费诺码。,H(X)=2.75比特/符号,平均码长为2.75码元/符号,编码效率为=1,每次所分两组的概率恰好相等,2020/5/5,51,哈夫曼编码方法,哈夫曼编码的步骤将信源消息符号按其出现的概率大小依次排列p(x1)p(x2)p(xn)取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。对重排后的两个概率最小符号重复步骤2的过程。继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,2020/5/5,52,例：设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。,01,0.200.190.180.170.150.11,0.260.200.190.180.17,0.350.260.200.19,0.390.350.26,0.610.39,01,01,01,01,01,哈夫曼编码方法,2020/5/5,53,哈夫曼编码方法,信源熵平均码长编码效率,2020/5/5,54,哈夫曼编码方法,哈夫曼的编法并不惟一每次对信源缩减时，给两个概率最小的符号分配“0”和“1”是任意的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长Ki不变，平均码长也不变，所以没有本质区别。缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，由此编出的码都是正确的，而得到的码字却不相同。不同的编码方法得到的码长Ki不尽相同。,2020/5/5,55,哈夫曼编码方法,例：设有离散无记忆信源,01,0.40.20.20.2,01,0.40.40.2,01,0.60.4,01,2020/5/5,56,哈夫曼编码方法,平均码长码长的方差2,两种编法的平均码长相同,所以编码效率相同,第二种编码方法的码长方差较小说明：码长变化较小，比较接近于平均码长,2020/5/5,57,哈夫曼编码方法,结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号被重复编码的次数减少，使短码得到充分利用。哈夫曼编码的特点保证了概率小的符号对应于长码，概率大的符号对应于短码，充分利用了短码。缩减信源的最后两个码字的最后一位不同，保证了哈夫曼码是即时码。,2020/5/5,58,总结,香农码、费诺码、哈夫曼码都考虑了信源的统计特性，经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现对信源的压缩。香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高。费诺码和哈夫曼码的编码方法都不惟一。费诺码比较适合于对分组概率相等或接近的信源编码。哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。,2020/5/5,59,第5章信源编码,5.1编码的定义5.2无失真信源编码5.3限失真信源编码定理5.4常用信源编码方法简介,2020/5/5,60,限失真信源编码定理,从信息处理的角度看，无失真信源编码是保熵的，只是对冗余度进行了压缩。限失真信源编码的中心任务是：在允许的失真范围内，把编码后的信息率压缩到最小。编码后的信息率得到压缩，属于熵压缩编码。引入熵压缩编码的原因：保熵编码并非总是必需的；保熵编码并非总是可能的；降低信息率有利于传输和处理，因此有必要进行熵压缩编码。,2020/5/5,61,限失真信源编码定理,设离散无记忆信源X的信息率失真函数为R(D)当信息率RR(D)时，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D，为任意小的正数。反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，则对于任意小的0，每一个信源符号的平均码长满足如下公式：,2020/5/5,62,第5章信源编码,5.1编码的定义5.2无失真信源编码5.3限失真信源编码定理5.4常用信源编码方法简介,2020/5/5,63,游程编码,游程符号序列中某符号连续重复出现而形成符号串的长度，又称为游程长度或游长。游程编码将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。,2020/5/5,64,游程编码,二元序列的游程连续出现“0”，称为“0”游程，表示为L(0)。连续出现“1”，称为“1”游程，表示为L(1)。若规定二元序列总是从“0”开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程对于随机序列，游程长度是随机的其取值可为1,2,3,，直至无穷。用交替出现的“0”游程和“1”游程长度表示任意二元序列。一种一一对应的变换，是可逆变换。,2020/5/5,65,游程编码,游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列，这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源。对新的信源(游程序列)进行哈夫曼编码。,2020/5/5,66,游程编码,多元序列游程多元序列也可以变换成游程序列，如m元序列可有m种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的“长度”是m种游程中的哪一个的长度，否则，变换就不可逆。增加的标志位可能会抵消压缩编码得到的好处。所以，对多元序列进行游程变换的意义不大。,2020/5/5,67,例题,例：考虑如下比特流11111111111111100000000000000000001111它由十五个1、十九个0和四个1组成。最大重复次数为19，可以用5位二进制表示。(01111,1)、(10011,0)、(00100,1)压缩率：18：381：2.11,游程编码是一种用来缩减重复字符串大小的技术,2020/5/5,68,MH编码,MH编码是用于黑白文件传真的数据压缩。传真一页A4文件：宽210mm，高297mm分辨率：8点/mm，4线/mm需传送：210829742Mbit大多数传真机速率：9600bit/s传送一页A4文件需要：3.5分钟MH码以8幅标准文件样张作统计，计算出“黑”、“白”各种游程长度的出现概率。,2020/5/5,69,MH编码,2020/5/5,70,MH编码,如黑游程长度85683224，查表得000000100110100000010111,例：设某页传真文件中某一扫描行的象素点为：17白5黑55白10黑1641白,数据压缩比：1728：5432,2020/5/5,71,算术编码,算术编码是近十多年来发展迅速的一种无失真信源编码，它与最佳的哈夫曼码相比，理论性能稍加逊色，而实际压缩率和编码效率却往往还优于哈夫曼码，且实现简单，故很受工程上的重视。算术编码不同于哈夫曼码，它属于非分组码。它从全序列出发，考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术码主要的编码方法是计算输入信源符号序列所对应的区间。,2020/5/5,72,算术码的主要概念把信源输出序列概率和实数段0,1中的一个数C联系起来。设信源字母表为a1,a2，其概率p(a1)=0.6,p(a2)=0.4将0,1分成与概率比例相应的区间，0,0.6和0.6,l,设信源输出序列S=S1S2S3Sn当信源输出的第一个符号S1=a1时，数C的值处在0,0.6当信源输出的第一个符号S1=a2时，数C的值处在0.6,l,根据信源S1的情况，把C所在的段再次按概率比例划分,算术编码,p(a1),p(a2),00.61,00.360.60.841,p(a1a1),p(a1a2),p(a2a1),p(a2a2),2020/5/5,73,算术编码,设信源符号集A=a1,a2,an，其相应概率分布为p(ai)信源符号的累积概率为,累积概率Pr+1和Pr都是小于1的正数，可用0,1区间内的两个点来表示。,P1,p1,P2,P3,P4,p2,p3,pr就是这两点间的小区间的长度，如下图所示：,当A=0,1二元信源时：P(0)=0;P(1)=p(0),P(0),P(1),0,1,p(0),p(1),2020/5/5,74,P(0),0,P(1),1,p(0),设输入符号序列S=011,p(1),P(0),P(1),p(00),P(01),p(01),P(01),P(1),P(011),p(010),p(011),p(0)=p(00)+p(01)p(01)=p(010)+p(011)归一律,P(0)=0P(01)=p(00)P(011)=P(01)+p(010),算术编