资源描述：
《近代信息论-第三章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章信源编码定理&1~2引言信源信源编码信道编码信道通信的根本任务——有效、可靠地传输信息。信源编码用信道能传输的符号代表信源的消息，使信源的消息适于传输（变换）在不失真或允许一定失真下，用尽可能少的符号来传递信息（通信的有效性，数据压缩）信道编码增加信号抗干扰能力，同时保持尽可能大的信息传输率（通信的可靠性，纠错编码）主要内容第一节Kraft不等式及单义可译定理第二节等长编码定理第一节：Kraft不等式及单义可译定理信源编码单义可译性即时码与前缀条件二进异前缀码的构成Kraft不等式单义可译定理信源编码信源发出符号集，而信道只能传输输入符号中的符号。用X集中的符号序列来代
2、表——这一过程就是信源的编码。编码器码符号ASCII码S:{A,B,C,……}X:{0,1}W:{41,42,43,……}11000001,01000010信源编码例1X:{0,1}S:{S1,S2,S3,S4}:{0,11,00,11}——奇异码：非一一对应:{0,10,00,01}——变长码（码字中码符号数不同）:{00,01,10,11}——定长码（等长码）:{1,10,100,1000}——变长码:{1,01,001,0001}——变长码信源编码例2问题：是否一一对应就足够？——要求单义可译单义可译(uniquelydecodable)定义：任意有限长N的信源S的符号
3、序列与任意有限长N的码字序列一一对应。引例：对不满足单义可译01000可译为：S4S3S101000S1S2S301000S1S2S1S101000{00,01,10,11}定长，非奇异码，单义可译即时码和（异）前缀条件(prefixcondition)译码时，要等下一个码子出现时才能做判断。——非即时码{1,10,100,1000}{1,01,001,0001}都是单义可译每个码以1为终结，只要收到1,则码字结束。1起逗点作用——逗点码时间上，无需后续符号就能立即译码——即时码构成即时码的充要条件：任何一个码字都不是其它码字的前缀。即时码和（异）前缀条件(prefixcon
4、dition)例{0，10，110，111}异前缀码是单义可译的一类子码。二进异前缀码的构成(binaryprefixcode)画二进码树，然后根据需要，在树上挑合适的码。01011011101111根节点枝branch节点node要点码字对应的节点不再产生新的枝。节点的某一枝被用作码字，则其他由该节点产生的枝也可用作码字。这样构造的码——异前缀码。找码不唯一1111111011011100101110101001100001110110010101000011001000010000可选的等长码：0000~1111可选逗点码：1，01，001，0001，0000可选：111
5、1，1110，110，10，011，0101，0011，0010，0001，0000100000011111Kraft不等式定理：r进制证明必要性充分性证证prefix码存在必要性充分性即：用树模型说明：第一级节点数为,……,第n级节点数长度为1的码字数不大于第一级的节点数长度为2的码字数不大于该级节点总数减去因第一级的码而失效的码数例：2级节点01100每个不等式表示因被前面的节点阻断后，每级最多可能的码字数。长度为2的码字数小于该级节点总数减去因第一级的码而失效的码数这正是prefixcode的构成方式所以，存在prefixcode也就是说，已知ni,可由树构造prefi
6、xcodePrefixcode满足Kraft不等式，反之，若有一组整数满足Kraft不等式，则存在相应码长的prefixcode。满足Kraft不等式的prefixcode不唯一。满足Kraft不等式的码也不一定是prefixcode,Kraft不等式只是说明存在prefixcode。Kraft不等式——表明单义可译定理定理：单义可译定理必须满足Kraft不等式。证明单义可译性总长为i个码元的码字的所有序列一定互不相同。单义可译定理证明单义可译定理证明小结：单义可译码Kraft不等式Prefixcode满足存在满足Kraft不等式可以找到Prefixcode单义可译码可用相应
7、码长的prefix码代替。back第二节：等长编码定理等长编码性质：等长非奇异码是单义可译的。（通过等长截取）对于信源等长编码，必须满足对于任意S的N次扩展信源进行编码，则有:等长编码定理定理一个熵为H(S)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个符号集中选取l个符号组成。则，当N足够大时，几乎可实现无失真编码，即译码错误可以任意小。逆定理不可能实现无失真编码，而当N足够大时，译码错误概率近似为1。证明思路：设码长N,样本空间=所有长为N的源符号序列;划分样本空间——空间1
