信息论与编码-第五章

信息论与编码-信源编码•通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。•将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：•第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；•第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。信息论与编码-信源编码•一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。•然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。信息论与编码-信源编码•编码分为信源编码和信道编码，•信源编码又分为无失真和限失真。•由于这些定理都要求符号数很大才能使它的值接近所规定的值，因而这些定理被称为极限定理。•无失真信源编码定理为第一极限定理；•信道编码定理（包括离散和连续信道）称为第二极限定理；•限失真信编码定理称为第三极限定理。信息论与编码-信源编码•由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。•具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。•信源编码的基本途径有两个，一是使序列中的各个符号尽可能地互相独立，即解除相关性；二是使编码中各个符号出现的概率尽可能地相等，即概率均匀化。信息论与编码-信源编码编码的定义•编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。•讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。5.1编码的定义信源编码器信道码表图5-1信源编码器示意图5.1编码的定义将信源消息分成若干组，即符号序列xi，xi＝(xi1xi2…xil…xiL)，xilA={a1，a2，…，ai，…，an}每个符号序列xi依照固定码表映射成一个码字yi，yi＝(yi1yi2…yil…yiLi)，yilB={b1，b2，…，bi，…，bm}这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。信息论与编码-信源编码•输出的码符号序列称为码字，长度称为码字长度或简称码长。•编码就是从信源符号到码符号的一种映射。•若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。•码字长度有无限长（卷积码）、定长和变长（分组码）。•码元符号通常使用二进制来表示Li信息论与编码-信源编码信源符号取值概率码表码1码2a1a2a3a4p(a1)p(a2)p(a3)p(a4)00011011001001111变长码与定长码信息论与编码-信源编码信源符号信源符号概率码1码2a1a2a3a41/21/41/81/801100110100001码的不同属性码3码411010010001010010001信息论与编码-信源编码即时码（非延长码）非即时码唯一可译码非唯一可译码非奇异码奇异码分组码非分组码码码符号的分类：下图是一个码分类图信息论与编码-信源编码下面，我们给出这些码的定义。1.二元码若码符号集为，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。2.等长码：若一组码中所有码字的码长都相同，即，则称为等长码。3.变长码：若一组码组中所有码字的码长各不相同，则称为变长码。}1,0{X),,2,1(qilli信息论与编码-信源编码4.非奇异码：若一组码中所有码字都不相同，则称为非奇异码。5.奇异码：若一组码中有相同的码字，则称为奇异码。6.唯一可译码：若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。信息论与编码-信源编码•例如{0,10,11}是一种唯一可译码。因为任意一串有限长码序列，如100111000，只能被分割成10，0，11，0，0。任何其他分割法都会产生一些非定义的码字。•显然，奇异码不是唯一可译码，而非奇异码中有非唯一可译码和唯一可译码。•上表中码3是唯一可译码，但码2不是唯一可译码。例如10000100是由码2的（10，0，0，01，00）产生的序列，译码时可有多种分法，如10，0，00，10，0，此时产生歧义。信息论与编码-信源编码7.非即时码和即时码：•如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码•如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码信息论与编码-信源编码•上表中码3是非即时码，而码4是即时码。•码4中只要收到符号1就表示该码字已完整，可以立即译码。•即时码又称为非延长码，任意一个码字都不是其他码字的前缀部分，有时叫做异前缀码。•在延长码中，有的码是唯一可译的，主要取决于码的总体结构，如表中码3的延长码就是唯一可译的。信息论与编码-信源编码码树：•即时码的一种简单构造方法是树图法。•对给定码字的全体集合可以用码树来描述它。•所谓树，就是既有根、枝，又有节点，如图所示。图中，最上端A为根节点，A、B、C、D、E皆为节点，E为终端节点。A、B、C、D为中间节点，中间节点不安排码字，而只在终端节点安排码字.},,,{21qABCD000E11111010010001信息论与编码-信源编码•每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成。•如图3.2中的终端节点E，走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001。•可以看出，按树图法构成的码一定满足即时码的定义（一一对应，非前缀码）。•从码树上可以得知，当第i阶的节点作为终端节点，且分配码字，则码字的码长为i。信息论与编码-信源编码•任一即时码都可以用树图法来表示。•当码字长度给定后，用树图法安排的即时码不是唯一的。如图中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。•对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码。•每个节点上都有个分支的树称为满树，否则为非满树。r5.1编码的定义010101二进制码树0010101010101010110101015.1编码的定义012012012012012012三进制码树码树与码字对应关系图树根树枝数节点终端节点节数非满树满树码字的起点码的进制数码字或码字的一部分码字码长变长码等长码信息论与编码-信源编码克拉夫特（Kraft）不等式对于码符号为的任意唯一可译码，其码字为，所对应的码长为，则必定满足克拉夫特不等式反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码。},,,{21rxxxXqqlll,,,2111qilir信息论与编码-信源编码•注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据（可以排除，不能肯定）。如{0，10，010，111}满足克拉夫特不等式，但却不是唯一可译码。•例题：设二进制码树中，对应的，由上述定理，可得因此不存在满足这种码长的唯一可译码。可以用树码进行检查。),,,(4321xxxxX3,2,2,14321llll18922222322141ili•例题：将各码字长度改为由上述定理，可得因此存在满足这种码长的唯一可译码。如（0，10，110，111）。可以用树码进行检查。但{0，10，010，111}满足克拉夫特不等式，却不是唯一可译码。信息论与编码-信源编码122222332141ili3,3,2,14321llll信息论与编码-信源编码定长编码定理前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。设信源输出符号序列长度为L，码字的长度为，编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代表信源。LK信息论与编码-信源编码在定长编码中，对每一个信源序列，都是定值，设等于K，我们的目的是寻找最小K值。要实现无失真的信源编码，要求信源符号与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的（唯一可译码）。LK),,2,1(qiiX信息论与编码-信源编码定长编码定理：由L个符号组成的、每个符号熵为的无记忆平稳信源符号序列，可用个符号（每个符号有m中可能值）进行定长编码。对任意，只要则当L足够大时，必可使译码差错小于)(XLHLXXX,,,21LKLKYYY,,,210,0)(logXLLHmLK信息论与编码-信源编码反之，当时，译码差错一定是有限值，当L足够大时，译码几乎必定出错。2)(logXLLHmLK信息论与编码-信源编码式中，左边是输出码字每符号所能载荷的最大信息量上述定理的条件可改写成上式大于号左边为KL长码字所能携带的最大信息量，右边为L长信源序列携带的信息量。XHLHmKLLXlogmLKLlog信息论与编码-信源编码所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件是所取得符号数L足够大。信息论与编码-信源编码•例如，某信源有8种等概率符号，L＝1，信源序列熵达到最大值：H1(X)=log8=3bit/符号•即该信源符号肯定可以用3比特的信息率进行无失真的编码。这就是说，如果采用二进制符号作为码字输出符号，则用3个比特就可以表示一个符号。信息论与编码-信源编码•当信源符号输出概率不相等时，如，p(xi)={.4,.18,.1,.1,.07,.06,.05,.04}则此时，H1(X)=2.55bit/符号•因22.55=5.856，即若用2.55bit来表示，只有5.856种可能码字，还有部分符号没有对应的码字•这些符号一旦出现，被传输至接受端，就没有对应的码字译码，因而引起译码差错。所以定长编码一般都存在译码差错，只是差错大小不同。•当L足够大时，有些序列发生的概率很小，因此可使得译码差错达到足够小。•设是信源序列的样本矢量，，则共有种样本•我们把它分成两个互补的集和•集中的元素（样本矢量）有与之对应的不同码字•而集中的元素没有对应的输出码字，因而会在译码时发生差错。信息论与编码-信源编码),,,,,(21LlixxxxXnilaaaax,,,,,21LnACAACA信息论与编码-信源编码•如果允许一定的差错，则编码时只需对属于中的个样本矢量赋予相应的不同字码，即输出码字的总个数只要大于就可以了。•在这种编码方式下，差错概率即为集中元素发生的概率,此时要求，因而集中的样本都应是小概率事件。•当L则增大时虽然样本数也随着增多，但小概率事件的概率将更小，有望使更小。AMKmMePCACAPCAPCACAP设差错概率为，信源序列的自方差为根据契比雪夫不等式，得：当和均为定值时，只要L足够大，可以小于任一整数，即信息论与编码-信源编码)(2XP22(){[()()]}iXEIxHX22)(LXP2P22)(LX信息论与编码-信源编码此时要求：只要足够小，就可以几乎无差错地译码，当然代价是L变得更大。22)(XL信息论与编码-信源编码令为码字最大平均符号信息量。定义编码效率为：最佳编码效率为mLKKLlog()()()()logLLLLLHXHXHXKKHXmL)()(XHXHLL信息论与编码-信源编码无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信