信源编码与编码定理

信源编码与编码定理第一页，共四十二页，2022年，8月28日第五章：无失真信源编码

§5.1

编码问题的一般概念与定义

(GeneralConceptsandDefinitionsforCoding)

所谓编码即信号的变换，或信号形式的变换。

(signaltransformorsignalformtransform)

“通信的根本问题是将信源的输出经信道传输后在接收端(信宿)精确地或近似地重现出来。”这就是通信的本质，能在宿端再现发端的信号，所以信号形式上的变换就是通信的核心问题。

变换(transform)——称为编码(encoding)

反变换(inverse-transform)——则称为解(译)码

(decoding)

所有编码手段无外乎为了四个目的：

Ⅰ.有效性(effectiveness)、Ⅱ.可靠性(reliability)

、

Ⅲ.安全性(security)

、Ⅳ.

经济性(economically)

、

第二页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义Ⅰ.解决有效性问题的编码——信源编码(Sourcecoding)

亦称压缩编码(Compressedcoding),所谓信源编码是指在无失真，或在有失真的条件下，如何利用尽可能少的符号来表述信源发出的消息。很显然，这种编码在于压缩信息的冗余度。根据编码的前提条件，信源编码又分为两类：

⒈无失真信源编码(Sourcecodingwithoutdistortion)

这种编码是一种可逆性编码(invertiblecoding)

，即编码后的码字序列再经解码处理后，可无失真地恢复出原来的消息或消息序列。显然对于离散信源来说才有可能实现这种可逆编码，所以无失真信源编码仅适用离散信源。第三页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义

⒉限失真信源编码(Sourcecodingwithfinitedistortion)

此编码方式不能构成可逆编码，即编码后的码字序列经解码(反变换)处理后，所恢复的消息序列与发端的原消息序列存在有一定的失真。这种编码适合于连续信源模拟信号的编码，因为对连续信源的信号无论做何种处理，都无法避免信息的损失。比如语音信号，即使采用64Kbit/s以上的速率量化，也会有相当的信息产生丢失，只不过有时人耳察觉不到而已。实际工程中失真大量存在，而且在允许失真的限度下进行编码处理对于大多数用户都是可以接受的。因此对于信息量无限大的连续变量来说，按照熵编码的原则压缩，信息丢失的程度应该是最小。限失真信源编码的方法有很多，而且随信源的特性不同也有其不同的压缩模式。但它们都没有达到Shannon所给出的理论极限。第四页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义Ⅱ.解决可靠性问题的编码——信道编码

(Channelcoding)

亦称纠错编码。此类编码方式的目的，主要是解决如何充分地利用信道的能力来可靠地传输信息。我们把这种增加信道中抗干扰能力的编码称为信道编码。它所采用的处理方针恰恰与信源编码中压缩冗余的方针正好相反，是充分利用原有冗余度和进一步扩展冗余度的方针。所以这种编码技术是以牺牲传输的有效性为代价来提高传输的可靠性。Ⅲ.解决安全性问题的编码——密码(Cryptography)

这里的编码方法主要是为了解决信息传输过程中的安全性问题。即为使授权用户(empower-user)尽可能无失真地接收信息；而对于非授权用户(empower-user),则不允许其获取信息。第五页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义

Ⅳ.

解决传输经济性问题的编码——调制与复用

(modulation&multiplex)

是指为了充分利用信道，进一步提高通信系统的通信能力和降低通信成本而采用的编码技术。这类编码技术不仅广泛地应用于通信网络中，而且在计算机网络和有线电视网中也有大量的使用。这种编码技术大体分为这几类：时分复用与时分多址接入技术(TDM&TDMA)频分复用与频分多址接入技术(FDM&FDMA)码分复用与码分多址接入技术(CDM&CDMA)波分复用(WDM)空分复用(SDM)统计复用(Statisticalmultiplex)第六页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义

以上四类编码技术都有其专门的学科论述，而信息论中仅定性、定量地给出各种编码方法的理论极限和性能界限。这些都是以极限定理的方式给出，因此它们就预示着在每一种具体的编码方法实现之前，就可给出它的实现前提和最好目标或可实现性。所以信息论中的编码定理，大多是我们用以评估系统优劣的界限；或估计系统是否值得改善的尺度；以及用以比较系统目标的最佳性或可实现性。

总之学习信息论就是为了掌握这些性能界限；应用编码定理来评估实际问题。而具体的编码技术应在其它相应的专业课程来解决。第七页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义一、编码器与解码器(encoder&decoder)

编码器就是将消息符号序列变换成码字序列的装置(器件)，而解码器则是相应的反变换装置(或器件)。EncoderDecoder而码字序列可由K个码字所组成，则两种序列的个数分别为：

编码器的输入是消息符号序列，其中符号的取值集合为S:；如果给定一个码字符号集合则编码器的输出可以由码字符号构造出一个码字序列与输入的消息符号序列相对应。设消息序列由L个符号构成，才可能产生一一对应的映射关系,形成可逆编码。则不可能实现无失真编码,只能实现有失真编码。第八页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义

例5-1.如果消息符号为一16进制符号集合，若采用二进制码字符号，来对其进行可逆编码时需要码字长度如何？题解：

如果信源所发的消息是以两个16进制符号组成的序列，即所谓信源的二次扩展，我们称为并源处理：Combined─SourceProcessing

则此刻的码字序列的长度正是一个字节(byte)长度。第九页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义二、分组码(块码)与非分组码(序列码)

（Blockcode&Non-blockcode=Sequencecode）

以上例子中的码字序列均有一个固定字长，我们称为定长码字。(Fixed-lengthcodeword)

如果码字长度不是一个固定的常数，我们则称为码字为变长码字。(Variable-lengthcodeword)

无论是定长码，还是变长码它们均属于所谓分组码，因其特征是每一个码字都有一个有限的字长

l

，所以分组码亦称为块码结构。还有一类码字是没有特定的字长，它是一个无限长或相当长的码字序列，不能按一个个的码字进行编译码，而是随消息序列按边输入边输出的机制实现编译码。这类编码方法称为非分组码——

序列码，如算术码等。

第十页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义三、码树结构(CodeTreeStructure)RootNodeBranchJointbranch0

1111111000000101

一个码树，从根部可分出m个分枝(或树叶leaf),这相对于m进制码。如果从根部开始，对于每个节点上引出的分枝都分配一个代码，则由根出发到任意一个终端节点，形成一联枝。若将一联枝的所有分枝的代码组合则形成码字序列。如果所有的联枝其长度相同，称为整树结构。由整树中可以得到定长码字，反之将得到变长码字。第十一页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义四、满树原则

(FullTreePrinciple)01200112201201122

比较以上两码树其相互差别在于从任意一节点出发能否保证其后续的枝数一定是m枝(相对于m进制码)。满足这一原则为满树结构，否则为非满树结构(non-fulltreestructure)。FullTreePrinciple:

其中k表示为中间节点的个数；N表示码树的联枝数或码字个数。满数结构非满数结构第十二页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义

显然，任何一个二进制码字序列，其码树一定符合满树结构，因为给定一个N，总可以找得到k个中间节点来满足满树原则：

如果满树结构与整数结构相同时,有

其中，L是联枝串接的分枝数，k是中间节点个数。任何一个整树都符合满树结构，但任意的满树却不一定满足整树结构。由于整树的联枝长度相同，故此码树对应定长编码；而符合满树原则但又不是整树的结构常用于对应变长编码。第十三页，共四十二页，2022年，8月28日§5.1

编码问题的一般概念与定义000111222012Root书中图5.3有误应符合整树定义。

N=r³112000000001111111222222220第十四页，共四十二页，2022年，8月28日第五章：无失真信源编码

§5.2定长编码及定长编码定理

(TheFixed-lengthCodinganditsTheorem)

前面我们已经推出利用定长编码实现可逆编码的条件是：WhereKisthecodelength.因为定长编码可以实现一一对应的无失真编码，但是这时却没有实现信源编码的主要目的——压缩消息序列的冗余度，甚至编码后的码字序列还可能增加新的冗余。那么如何采用定长编码来达到压缩的目的，这是我们这节重点概念。在第二章中已知道这样的结论：第十五页，共四十二页，2022年，8月28日§5.2

定长编码及定长编码定理

上式表明对信源特性了解越多，则所需传输的信息量就越少。因此我们对Hm感兴趣，若把L个消息符号排成一个序列，不论其是否有记忆，只要统计出Hm的值，就对压缩序列的冗余有利。我们可以仅从符号间相互独立的序列中看到这一特点。从数学的大数定律中可以证明这样一个结论，如果对L个消息符号可构成无记忆序列，则按每一个序列的出现概率可将所有序列分成两大类：一类是高概率序列类；另一类是低概率序列类。所谓高概率序列是指属于此集合的元素，大体上将以几乎相同的概率出现。一般称为渐近等概率集合，记AL。而且L越大这种等概率特性越明显。另一类集合中的序列，它的出现概率很低，几乎为零。所以我们把这一部分序列集合称为低概率集合，记为第十六页，共四十二页，2022年，8月28日§5.2

定长编码及定长编码定理

例5－2.设如一个小盒子中装有100枚围棋子，其中75枚为白色棋子，25枚为黑色棋子。如果将100只同样比例的围棋子盒子倒入一大盒子中搅匀，问若随机性的装一小盒子围棋子，这盒棋子全是白色的概率是多少？若全是黑色棋子的概率又是多少？解：根据数学中的大数定律，落入高概率类集合的事件数目为：第十七页，共四十二页，2022年，8月28日§5.2

定长编码及定长编码定理

这就是说如果给定了，总可以找到一个L

使得落入两个概率类集合的序列各有自己的出现概率。而落入渐近等概率集合的序列个数将是一个常数：第十八页，共四十二页，2022年，8月28日§5.2

定长编码及定长编码定理

给出此例并不是希望大家掌握计算序列概率的方法，而是要大家了解定长编码达到压缩的目的。因为消息序列中的个数为：

且，

显然，如果采用一一对应的定长编码策略，仅对渐进等概率集合中的消息序列一一对应的编码；而对那些几乎不出现的序列，不给分配码字序列，这样编码的出错概率将会控制到以下。如果认为这样的失真还不够小，可以增加L的值，使得足够小。因此无失真定长编码的理论是建立在误差概率几乎为零的意义下的无失真结果。

即保证对于高概率类序列集合中的每一消息序列都能实现一一对应的编码，而且由于：这就体现出定长编码压缩序列冗余的效果。第十九页，共四十二页，2022年，8月28日§5.2

定长编码及定长编码定理

介绍定长编码极限定理：设消息序列：和码字序列：再设：第二十页，共四十二页，2022年，8月28日§5.2

定长编码及定长编码定理定理的含义：对于任何给定的，只要满足不等式的条件，则当L足够大时，就一定可以实现无失真编码，即Pe。逆定理：如果不满足第一个不等式，而满足第二个不等式，则编码一定会产生失真，而且当L时出错概率Pe将很快接近于1。

例5－3.一幅黑白图象信号，若每一行有100个象素点，每个象素点的黑白灰度级为8；则对每一行100个点所构成的象素序列进行编码。即：如果每一个象素点的分布于其位置无关这是一个无记忆序列。再举一例看其压缩比。第二十一页，共四十二页，2022年，8月28日§5.2

定长编码及定长编码定理

由于需要编码的序列个数仅占原来序列的

分之一。即冗余度压缩掉倍，但这仅是理论上的推导，实际上很难完成。因为不可能将所有的渐近等概率序列一一列出来，进行编码或存储到计算机内存中形成码书实现解码。所以这是定长编码的缺陷，一般我们常选用变长编码的方法。第二十二页，共四十二页，2022年，8月28日第五章：无失真信源编码

§5.3

变长编码及变长编码定理

(TheVariable-lengthCodinganditsTheorem)

一、变长码字的唯一可分码条件(TheuniquelydecodableconditionforV-Lcoding)先看一个变长码字的例子：例5－411011111101/8S4111100011/8S300101001/4S2100001/2S1C4C3C2C1出现概率信源符号11XX000非既时码译码演示即时码第二十三页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理

以上四种变长码方案中的后两种码字属于唯一可分码，即不用码字分隔符就能自行分隔解码。但这两者之间也有差别，C3属于即时码(instantaneouscode);而

C4属于非即时码(non-instantaneouscode),它在解码时往往需要等后续码字出现时才能正确解码，因此效率不如前者高。为了得出最佳变长码，我们比较变长码的特点：

1º.高概率符号对应于短码字；低概率符号对应于长码字。

2º.无需额外的分隔符就可构成唯一可分码(Uniquely-decodablecode)——异前置码(prefixcode):

即任何码字都不能成为其它码字的前缀。满足这样条件的变长码一定是唯一可分码，而且还是即时码。下面给出变长码的唯一可分性的充分必要条件

(sufficientandnecessarycondition)

：

二、Kraft’s不等式(Kraft’sInequality)用码树可以导出码字的唯一可分离性的充要条件是：第二十四页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理

这里，Ki

表示第i种码字的长度；m为m进制下码字符号的取值数。

证明：设Ki的最大值为N，对于N节的整树来说，它的总联枝数为

,如果对于一个Ki

长的码字来说，则它所对应的码树中的一个联枝的最终节点之后的个分枝将不能再用，否则将不满足异前缀的条件。因此总共不用的枝数为：010101两边除以则得：第二十五页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理

以上证明的是

Kraft’s

不等式是满足码字可分离的必要条件。下面证明它的充分条件。若设不等式⑴成立,则不等式(2)也一定成立。如果将满足不等式的一组码长为的码字，在一个N节码树上按找联枝，则我们一定可以找出符合关系的码树，且保证每一个长度为的联枝的终点没有后续分枝。这就保证了这套码字的唯一可分离性，即充分条件成立。010101010110111

所以Kraft’s

不等式是满足码字唯一可分离性的充要条件。第二十六页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理

三、最佳变长码(TheOptimalCodes)

对于变长编码而言，是否一定存在有一个最佳方案或称有一套最佳码字?即这套码字是满足唯一可分性中平均码长最短，而且是即时码。这个问题是信息论所应该讨论的问题。如果考虑一般性，设信源的消息符号序列为独立序列。为证明其编码的压缩性，可取N个码字来作为上述消息序列的变长码。则用Ki表示第i个码字的长度，可以采用以下原则来规定Ki的取值：

第二十七页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理注意：取整的概念是为了适应码长Ki是一个整数的事实。第二十八页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理而平均每一个消息符号的平均码长为：第二十九页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理四、变长编码定理(Thevariable-lengthcodingtheorem)

①.按消息符号的变长编码定理(Theoremtothesourceletters)

对于熵为H(S)的离散无记忆信源：若用m进制下的码字符号对该信源实现变长编码，则一定存在着一种唯一可分码，使其平均码长满足：

反之，不满足上述不等式则一定会产生编码失真！反之，不满足上述不等式的平均序列码长，则一定会导致失真。②.按消息符号序列的变长编码定理(TheVariable-LengthCodingTheoremtoSequencesofLSourceLetters)第三十页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理

五、某些常用的变长编码方法(SomeV-Lcodingmethods)

(1).

Shannon’salgorithm:

Ⅰ.把信源所给出的N个消息符号，按其概率递减顺序排列：

Ⅱ.计算第

i个消息的累加概率；(CumulativeProbability)

Ⅲ.将累加概率转换成二进制数；如0.5=0.1(二);0.25=0.01(二)

Ⅳ.按Shannon’s

公式求出每一个码字的长度；

Ⅴ.根据取二进制的累加概率小数点之后的位作为Shannon’s

码字。第三十一页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理例5－5.Shannon变长码111105.1111010.960.04111015.1110100.910.05110115.1101100.850.0611004.1100000.780.0710104.101010.680.110014.100100.580.10113.011000.40.18002.0000000.4codewordki

(二)PiSi第三十二页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理(2).

最佳变长码字——Huffman’salgorithm

在概率已知的前提下，可以证明Huffman

方法是最佳编码法，因为目前还没有一种变长编码方法可以超出Huffman

方法的编码效率。所以最佳变长码字就是

Huffman

codeword.

下面给出二元Huffman变长编码的编码步骤：第三十三页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理2º.对概率最小的两个消息符号分别分配码字符号“1”和

“0”，分配原则应保持一致，如概率大的事件都是“1”。3º.将最小的两个消息概率相加并且以相加后的概率之和重新参加概率排队；4º.

重复上述步骤(2º,3º);直至概率之和为1；5º.从树根开始顺序地依次取出Huffman码字。

下面以前题为例，按Huffman编码步骤完成二元最佳变长编码：

例5-6.

二元Huffman编码方法图示：1º.把N个消息符号按其概率递减的顺序排列；第三十四页，共四十二页，2022年，8月28日010.370.601101.0=root

§5.3

变长编码及变长编码定理0.180.040.050.060.070.10.10.4010.09010.13010.190.2310Huffman’scodes10010110000010001010001000011第三十五页，共四十二页，2022年，8月28日

§5.3

变长编码及变长编码定理00000001111111

显然从码