第7讲离散无记忆信源等长编码

离散无记忆信源等长编码第七讲信源编码基本概念KKpppaaa,,,,,,2121A字母表信源输出序列),,,(21LLuuuuDbbb,,,21B),,,(21NNvvvv消息集码字集LuNv集合码字序列等长码不等长码D元码唯一可译码信源符号信源符号出现概率码表码0码1码2码3码4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001信源编码基本概念信源编码器码表信源信道XYL长序列N长码字无失真等长编码LNKDKLDNloglogLKND英文电报27个符号,K=27,L=1,D=2(二元编码)527logloglog222DKLN每个英文电报符号至少要用5位二元符号编码实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，平均每个英文电报符号所提供的信息量约等于1.4比特，即编码后5个二元符号只携带约1.4比特的信息量，远小于5比特(最大熵)，可见编码后的信息传输效率极低。实例LNKD信源编码器码表信源信道XYL长序列N长码字无失真等长编码LNKDKLDNloglog)(logULHDN几乎无失真编码几乎无失真等长编码选择L足够长，使其中，为与L有关的正数，且当时有,才能不损失信息。然而这样的编码不总能保证单义可译，但非单义可译所引起的错误可渐近为任意小。反之，若，编码误差变得任意大。])([logLUHLDNLL0L])([logLUHLDNDNlog)(ULHllLupp)()(ullllllLLuIupuppI)()](log[)(log)(log)(uuLIILL/)(u)(UH)(luI2ILI令信源的熵为，的方差为，则的均值为)()()()(UHLuIELuIELIEllllLu方差为222)]()([1)]()([ULHIELUHLIELLuu22)]()([1llULHuIELLLLII/*1222由契比雪夫大数定理，对于022()()LIrIPHULLu22()()1LIrIPHULLu可选，这可以通过适当选择L来实现，上式可以写成1)()(UHLIPLru即当L足够大时，LI将以概率1取值为H(U)。)(logULHDN1典型序列)(,kapU0)()(:),(UHIUHLTLLUu),(LTU令H(U)是集的熵，定义为给定信源U输出长为L的典型序列集，又可称作弱ε典型序列集；的补集为非典型序列集。)(,kapU0])([])([:),(kkkLUapLLapLLTuka令H(U)是集的熵，定义为给定信源U输出长为L的典型序列集，其中，是L序列中出现的次数，又称之为强典型序列集。kL相应信源划分定理定理：)(,kapU0L1),(LTPUr给定信源和，当时，由契比雪夫大数定理，对于022)()(LUHLIPILru11)()(22LUHLIPILru可选，这可以通过适当选择L来实现，上式可以写成1)()(UHLIPLru即当L足够大时，LI将以概率1取值为H(U)。信源划分定理定理：)(,kapU0L1),(LTPUr给定信源和，当时，00L0LL1),(LTPULru对于任意小，存在有正整数，使得当时，有由契比雪夫大数定理，对于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(典型序列数目)),(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理解典型序列一个离散无记忆信源输出的消息序列可以分为两组，),(LT),(LT各序列出现的概率近于相等；每个序列平均符号的信息量接近于信源熵H(U)；所有典型序列的概率和趋近于1。个别非典型序列的概率不一定比个别典型序列的概率低。虽然非典型序列集中序列的总概率很小，但是元素数目不一定小。理解典型序列个别非典型序列的概率不一定比个别典型序列的概率低。虽然非典型序列集中序列的总概率很小，但是元素数目不一定小。掷硬币试验：正面出现概率p，反面出现概率1-p典型序列非典型序列（全反）pLLpLpp)1(Lp)1(LUHLLUKULT])([2),(KLUHLlog])([22])([log2UHKL离散无记忆信源编码模型无扰信道信宿DMS)(LEu)(xDLuxxLuˆLLLUuuu),,,(21u),,,(21NxxxxLLuuˆLLuuˆLLreppuuˆ无错有错错误概率DLNMLRloglog1编码速率可达00L)(E)(D0LLep对于给定的信源和编码速率R以及任意若存在有使当码长时就称R是可达的，否则称此R不可达。无扰编码定理若RH(U)，则R是可达的；若RH(U)，则R是不可达的。对于给定的离散无记忆信源，若D元码的速率R超过信源的熵，即，则存在有编码方法，当L足够大时就能使译码错误概率任意小。])([log/UHDLNRUH/)(编码效率()/()HUHU证明充分性)(UHR0LL0令，取。由信源划分定理推论2，对于通过选择足够大的L，可使LRUHLULT22),(])([),(LTULu),(LTULu对于每个依次标以码号1,2,…,2LR-1,并令作为相应消息的码字；而对于，都用第2LR个标号(000···000)表示。编码：相应号数的二元序列译码：LR2xLLuuˆLR2x)000(ˆ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)([LUHLUHLpLLULrLTPuuuˆ),(而由此得)1/(2ˆLLLrPuu随着L的加大，上式趋于0，即1ep从而R是不可达的。而典型中的DLNMLRloglog1])([])([2),(2)1(UHLUUHLLTpLTPLLULruuuˆ),()1/(2L本节小结信源编码基本概念DMS等长编码–无失真编码充要条件–几乎无失真编码充要条件（本节内容见课本53-62页）–定义LuNvLNKDKLDNloglog()HU)(logULHDNLDNRlog等长码不等长码唯一可译码–D元码–典型序列例题掷硬币：正面出现p=0.25，这时信源熵H(U)=0.81。1logDLNR()/0.81HUR（1）若采用等长二元无错编码时，510ep95.0/)(RUH（2）若采用只对典型序列编码，要求译码错误概率，求L95.0])(/[)(UHUH0427.095.0)(05.0UH471.0]81.075.01[log75.0]81.025.01[log25.0222I7221058.2eIpL由可得又可得22()()LIreIPHUpLLu作业3.13.2本节小结信源编码基本概念DMS等长编码–无失真编码充要条件–几乎无失真编码充要条件（本节内容见课本53-62页）–定义LuNvLNKDKLDNloglog()HU)(logULHDNLDNRlog等长码不等长码唯一可译码–D元码–典型序列