信息论与编码复习5-6

第5章信源编码重点掌握分组码的属性唯一可译码的判断方法信源编码定理香农编码、费诺编码、哈夫曼编码一般了解编码的术语游程编码、算术编码8/13/20241分组码属性码非分组码分组码奇异码非奇异码非唯一可译码唯一可译码非即时码即时码（非延长码）

8/13/20242码树中间节点不安排码字，只在终端节点安排码字每个终端节点对应的码字由从根节点出发到终端节点走过的路径上所对应的符号组成当第i阶的节点作为终端节点，且分配码字，则码字的码长为i按树图法构成的码一定满足即时码的定义树码的各个分支都延伸到最后一级端点，则称为满树，否则为非满树

满树码是定长码，非满树码是变长码8/13/20243克劳夫特不等式唯一可译码存在的充分和必要条件为：各码字的长度Ki

应满足下式。m是进制数，n是信源符号数注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据。8/13/20244唯一可译码的判断法将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。集合F的构成方法首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀（或者某些码字是这些尾随后缀的前缀），再将这些尾随后缀产生的新的尾随后缀列出。依此下去，直到没有一个尾随后缀是码字的前缀为止。按照上述步骤将次短码字、…等等所有码字可能产生的尾随后缀全部列出。最终得到码C的所有可能的尾随后缀的集合F。8/13/20245唯一可译码判断方法和步骤首先，观察是否是奇异码。若是，一定不是唯一可译码。其次，计算码长是否满足Kraft不等式。若不满足，一定不是唯一可译码。按照树图的构造法则，若能将码画成码树则是即时码，也就是唯一可译码。按唯一可译码判断法进行判断。只有唯一可译码判断法能确切判断是否是唯一可译码8/13/20246无失真信源编码设信源符号序列的长度为L变换成由KL个符号组成的 码序列（码字）变换要求能够无失真或无差错地从Y恢复X，也就是能正确地进行反变换或译码传送Y时所需要的信息率最小8/13/20247定长编码定理定长编码定理：由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL，可用KL个符号Y1,Y2,…,Yk,…YKL（每个符号有m种可能值）进行定长编码。对任意ε>0，δ>0，只要 则当L足够大时，必可使译码差错小于δ；反之，当 时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。8/13/20248编码效率差错概率当信源序列长度L满足 时， 就能达到差错率要求。编码效率最佳编码效率为8/13/20249变长编码定理单个符号变长编码定理若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式8/13/202410变长编码定理离散平稳无记忆序列变长编码定理对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中，ε为任意小正数。8/13/202411香农编码步骤将信源消息符号按其概率从大到小排列确定满足下列不等式的整数码长Ki令P1=0，计算第i个消息的累加概率将累加概率Pi变换成二进制数，取小数点后Ki位为该消息的码字8/13/202412费诺编码方法费诺编码属于概率匹配编码，不是最佳的编码方法。编码过程如下：将信源消息符号按其出现的概率依次排列

p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等，并为每一组分配一位码元。如编二进制码就分成两组，编m进制码就分成m组。将每一分组再按同样原则划分，重复步骤2，直至概率不再可分为止。信源符号所对应的码字即为费诺码。8/13/202413哈夫曼编码方法哈夫曼编码的步骤将信源消息符号按其出现的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。对重排后的两个概率最小符号重复步骤2的过程。继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。8/13/202414三种编码的比较香农码、费诺码、哈夫曼码都考虑了信源的统计特性，经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现对信源的压缩。香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高。费诺码和哈夫曼码的编码方法都不惟一。费诺码比较适合于对分组概率相等或接近的信源编码。哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。8/13/202415限失真信源编码定理设离散无记忆信源X的信息率失真函数为R(D)当信息率R＞R(D)时，只要信源序列长度L

足够长，一定存在一种编码方法，其译码失真小于或等于D＋ε，ε为任意小的正数。反之，若R＜R(D)，则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，则对于任意小的ε＞0，每一个信源符号的平均码长满足如下公式：8/13/202416第6章信道编码重点掌握差错控制相关的基本概念差错控制系统分类检、纠错能力有扰离散信道编码定理一般了解纠错码分类纠错码的基本思路8/13/202417与差错控制有关的基本概念汉明重量（码重）：码字中非0码元的个数，用W表示。对于二进制来说，指码字中码元1的数目。汉明距离（码距）：两个等长码字之间对应码元不相同的数目，用D表示。码的最小距离dmin：在某一码集C中，任意两个码字之间汉明距离的最小值称为该码的最小距离，即最小码距是衡量该码纠错能力的重要依据8/13/202418与差错控制有关的基本概念错误图样在二元无记忆N次扩展信道中，差错的形式也可以用二元序列来描述，称为错误图样。设发送码字为C=(c1c2…cn)，接收码字为R=(r1r2…rn)，两者的差别为分组码：每个码字中增加的r个校验元只由本组的k个信息元产生，与其他信息组的信息元无关。记为(n,k)卷积码：增加的r个校验元既与本组信息元有关，还与前面L组信息元有关。记为(n,k,L)8/13/202419差错控制系统分类前向纠错方式（FEC）自动请求重发方式（ARQ）混合纠错（HEC）译码设备不复杂，对突发错误特别有效实时性好，适用于单工通信检错、纠错能力强，译码设备复杂，应用广泛8/13/202420检错与纠错能力检错与纠错能力纠错码的检、纠错能力是指能够检测、纠正差错的数目。检错能力纠错能力检、纠错能力将检错和纠错统一考虑，情况会有所变化。要增加检错能力，必须抑制纠错能力。e≤dmin－1ed+ec≤dmin-1t=INT[(dmin-1)/2]8/13/202421有扰离散信道编码定理若有一离散无记忆平稳信道，其容量为C，输入符号序列长度为N。只要待传送的信息率R＜C，总可以找到一种编码方法，当N足够长时，使译码错误概率Pe＜ε，ε为任意正数。反之，当R＞C时，任何编码的Pe＞0。当N→∞时，Pe→1。与信源编码定理类似，香农第二定理只