第6讲――离散无记忆信源等长编码2014

离散无记忆信源等长编码第6讲信源编码通信的根本问题:将信源输出消息中信息在接收端精确或近似地重现出来。为此需要解决两大问题：信源的输出如何描述？——信源熵与互信息量(第2章）信源的输出如何表示？——信源编码这两个问题与信宿对于通信质量的要求有关。要求精确的重现信源输出。无失真编码不要求精确的复制出信源输出，而且在有干扰下传输时，要精确复制信源的输出也是不可能的。限失真信源编码信源编码分类:无失真编码（第3章）限失真信源编码（第9章）信源及其分类【分类方法】按照某时刻信源输出消息的取值集合的离散性和连续性，信源可分为离散信源和连续信源；按照信源输出消息的所对应的随机序列的平稳性，信源可分为平稳信源和非平稳信源；按照信源输出消息的所对应的随机序列中随机变量前后之间有无依赖关系，信源可分为无记忆信源和有记忆信源。离散无记忆信源的等长编码设有一离散无记忆源，以DMS表示，其中则长为L的信源输出序列有种不同的排列。设有一个含D个字母的集合，称B为码的字母(或符号)表。从B中选出不同的符号序列表示信源的输出，每个符号序列就称为码字。信源编码就是从消息集到码字集上的一种映射。1212,,,=,,,KKaaaUppp101,1Kkkkpp),,,(21LLuuuuLK12,,,DbbbB信源编码基本概念KKpppaaa,,,,,,2121A字母表信源输出序列12(,,,),,1,2,,LLiuuuuAiLu12,,,,,1DbbbDB或B=0,1,12(,,,),,1,2,,NNivvvvBiNv消息集码字集LuNv集合码字序列等长码不等长码D元码唯一可译码映射基本概念若B={0，1}，则{01，011，0111，01111}可以表示四个不同的信源序列，同样{000，011，110，101}也可表示信源输出的四个不同序列。这两个码字集合都称作2-元码，前者为不等长码，后者为等长码。一般地，B={0，1，…，D-1}，称为D-元码。等长码与不等长码的最大码字数：等长D元码，长度为N，至多有DN个码字；不等长D元码，最大长度为N，至多有D+D2+…+DN=D(1-DN)/(1-D)个码字。信源符号信源符号出现概率码表码0码1码2码3码4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001信源编码基本概念唯一可译码？码0，码3，码4是唯一可译码。码1，码2不是唯一可译码。码0是等长码，码3，码4是不等长码。唯一可译码？•若对每个消息序列都至少有一个码字序列与之对应，且不同的消息序列对应不同的码字序列，则称这样的码为唯一可译码，否则就称为非唯一可译码。•显然在无扰传输时，唯一可译码的译码错误概率为零。•注意：等长码与不等长码对唯一可译码要求！等长编码：映射1-1不等长编码：映射1-1是不够的！信源编码器码表信源信道XYL长序列N长码字无失真等长编码LNKDKLDKLNDloglog/log：即LKND等长的唯一可译码存在的充要条件：其中，D为码元数，N为码长。英文电报27个符号,K=27,L=1,D=2(二元编码)527logloglog222DKLN每个英文电报符号至少要用5位二元符号编码实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，平均每个英文电报符号所提供的信息量约等于1.4比特，即编码后5个二元符号只携带约1.4比特的信息量，远小于5比特(最大熵)，可见单字母编码的信息传输效率极低。实例LNKD若我们注意到每个信源符号包含的平均信息量为H(U)，长为L的信源输出序列集的平均熵值为LH(U)。编码时若D个符号为独立等概，则每个码元符号能携带的信息量最大，为logD，码长为最短。理论上，最小码长N只要满足：NlogD≥L[H(U)＋εL]，其中εL为与L有关的正数，且当L→∞时有εL→0，能够无信息损失。然而，这样编码不保证在任何情况下单义可译，但保证非单义可译所引起的误差可渐近地为任意小。反之，若NlogDL[H(U)－εL]，编码的误差变得任意大，其中εL为与L有关的正数。这一结论是本节课的中心内容，我们主要通过两个定理来得到这一结论。信源划分定理，无扰编码定理怎样提高编码效率？信源划分定理给定信源和，当时，有给定信源，对于所有，存在有正整数，使得当时，有,()kUpa0L(,)1rUPTL,()kUpa00L0LL(,)1rLUPTLu典型序列集TU(L,ε)={uL：H(U)-ε≤IL≤H(U)+ε}无扰编码定理若RH(U)，则R是可达的；若RH(U)，则R是不可达的。对于给定的离散无记忆信源，若D元码的速率R超过信源的熵，即，则存在有编码方法，当L足够大时就能使译码错误概率任意小。])([log/UHDLN编码速率,logDLNR信源划分定理把所有可能的消息序列分成两个子集：子集1是最常出现的部分：每个消息给以不同的码字，保证单义可译；子集2是消息概率足够小，不保证单义可译。典型序列集的概念设信源输出的L长的序列为，所以的概率为（因为是无记忆源）消息序列的自信息量为其中，是信源从字母集A中独立选出某个字母所获得的信息量。llLupp)()(ullllllLLuIupuppI)()](log[)(log)(log)(uu),,,(21LLuuuuLu)(luI这时，可以计算平均每个符号的信息量为令对于均值的方差为，即则对于均值的方差为LIILL/)(u)(kaI)(UH22221[()()]()()()KIkkkkEIaHUpaIaHULI)(UH222222()1[()][()()]1[()()]LLllIIEHUEILHULLEIuLHULuu2I由契比雪夫定理，有即当L足够大时，IL将以概率1取值为H(U)。022)()(LUHLIPILru11)()(22LUHLIPILru我们对信源输出的所有可能的KL个序列进行如下分类：【典型序列集的定义】令H(U)是集的熵，定义为给定信源U输出长为L的典型序列集，其中IL=I(uL)/L，uL∈UL。相应地，的补集为给定信源U输出长为L的非典型序列集。(,)UTL,()kUpa0),(LTUTU(L,ε)={uL：H(U)-ε≤IL≤H(U)+ε}信源划分定理给定信源和，当时，有给定信源，对于所有，存在有正整数，使得当时，有,()kUpa0L(,)1rUPTL,()kUpa00L0LL(,)1rLUPTLu由契比雪夫大数定理，对于022)()(LUHLIPILru11)()(22LUHLIPILru可选，这可以通过适当选择L来实现，上式可以写成1)()(UHLIPLru即当L足够大时，LI将以概率1取值为H(U)。),(LTULu])([])([2)(2UHLLUHLpu)(2)(ULHLpu)()(:),(UHIUHLTLLUu)()(log1)(UHpLUHLu])([)(log])([UHLpUHLLu，则证明：从典型序列定义式有即等式两边各项取指数，即得若推论1(特定序列出现的概率)即])([])([2)(2UHLLUHLpu推论2(典型序列数目)),(LTU])([])([2),(2)1(UHLUUHLLT)(2),(ULHULT).()()(1LTLULULLppuuu).())((2LTUHLULu])([2),(UHLULT])([2),(UHLULT])([])([2)(2UHLLUHLpu(())(.)(.)()2LULULHULTLTLpuuu])([2),(UHLULT])([2)1(),(UHLULT当L足够大时，对于给定的信源的个数满足证明：即由有即)(,kapU0和,典型序列即1])([])([2)(2UHLLUHLpu(,)1rLUPTLu理解典型序列一个离散无记忆信源输出的消息序列可以分为两组，),(LT),(LT各序列出现的概率近于相等；每个序列平均符号的信息量接近于信源熵H(U)；所有典型序列的概率和趋近于1。个别非典型序列的概率不一定比个别典型序列的概率低。虽然非典型序列集中序列的总概率很小，但是元素数目不一定小。)(2)(ULHLpu(,)1rLUPTLu理解典型序列个别非典型序列的概率不一定比个别典型序列的概率低。虽然非典型序列集中序列的总概率很小，但是元素数目不一定小。掷硬币试验：正面出现概率p，反面出现概率1-p，p0.5典型序列的概率非典型序列（全反）pLLpLpp)1((1)LpLUHLLUKULT])([2),(KLUHLlog])([22])([log2UHKL0()logHUK几乎无失真等长编码选择L足够长，使其中，为与L有关的正数。且当时有,才能不损失信息。然而这样的编码不总能保证单义可译，但非单义可译所引起的错误可渐近为任意小。])([logLUHLDNLL0L])([logLUHLDN反之，若，编码误差变得任意大。离散无记忆信源编码模型无扰信道信宿DMS)(LEu)(xDLuxxLuˆ12(,,,)LLuuuu12(,,,)NxxxxLLuuˆLLuuˆLLreppuuˆ无错有错错误概率NDMDLNMLR,loglog1编码速率可达00L)(E)(D0LLep对于给定的信源和编码速率R以及任意若存在有使当码长时就称R是可达的，否则称此R不可达。无扰编码定理若RH(U)，则R是可达的；若RH(U)，则R是不可达的。对于给定的离散无记忆信源，若D元码的速率R超过信源的熵，即，则存在有编码方法，当L足够大时就能使译码错误概率任意小。])([log/UHDLNRUH/)(编码效率()/(())HUHUR=H(U)，R是否可达？定理没有给出反之，若，编码误差变得任意大。])([logLUHLDN证明充分性)(UHR0LL0令，取。由信源划分定理推论2，对于通过选择足够大的L，可使LRUHLULT22),(])([),(LTULu),(LTULu对于每个依次标以码号1,2,…,2LR-1,并令作为相应消息的码字；而对于，都用第0标号(000···000)表示。编码：相应标号数的二元序列译码：LR20xLLuuˆ0x任意指定Luˆ若若),(ˆLTPPpLrLLreuuu因此，R为可达速率。则则])([])([2),(2)1(UHLUUHLLT证明必要性令2)(UHR，则正确译码概率为LLULrLLrLTPPuuuuuˆ),(ˆLLULrLTPuuuˆ),(2)(UHR]2)([2UHL因为，所以有个码字，])([2)1(UHL),(LTU序列的个数至少为，所以在序列可以找到码字的概率为)1/(22)1/(2])([]2)([LUHLUHLLLULrLTPuuuˆ),(而由此得)1/(2ˆLLLrPuu随着L的加大，上式趋于0，即1ep从而R是不