信息论与编码复习5-6.ppt

1、2020/7/20,1,第5章信源编码,重点掌握 分组码的属性 唯一可译码的判断方法 信源编码定理 香农编码、费诺编码、哈夫曼编码 一般了解 编码的术语 游程编码、算术编码,2020/7/20,2,分组码属性,码,非分组码 分组码,奇异码 非奇异码,非唯一可译码 唯一可译码,非即时码 即时码（非延长码）,2020/7/20,3,码树,中间节点不安排码字，只在终端节点安排码字 每个终端节点对应的码字由从根节点出发到终端节点走过的路径上所对应的符号组成 当第i阶的节点作为终端节点，且分配码字，则码字的码长为i 按树图法构成的码一定满足即时码的定义 树码的各个分支都延伸到最后一级端点，则称为满树，否

2、则为非满树 满树码是定长码，非满树码是变长码,2020/7/20,4,克劳夫特不等式,唯一可译码存在的充分和必要条件为：各码字的长度Ki 应满足下式。 m是进制数，n是信源符号数 注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据。,2020/7/20,5,唯一可译码的判断法,将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。 集合F的构成方法 首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀（或者某些码字是这些尾随后缀的前缀），再将这些尾随后缀

3、产生的新的尾随后缀列出。依此下去，直到没有一个尾随后缀是码字的前缀为止。 按照上述步骤将次短码字、等等所有码字可能产生的尾随后缀全部列出。最终得到码C的所有可能的尾随后缀的集合F。,2020/7/20,6,唯一可译码判断方法和步骤,首先，观察是否是奇异码。若是，一定不是唯一可译码。 其次，计算码长是否满足Kraft不等式。若不满足，一定不是唯一可译码。 按照树图的构造法则，若能将码画成码树则是即时码，也就是唯一可译码。 按唯一可译码判断法进行判断。,只有唯一可译码判断法能确切判断是否是唯一可译码,2020/7/20,7,无失真信源编码,设信源符号序列的长度为L 变换成由KL个符号组成的 码序列

4、（码字） 变换要求 能够无失真或无差错地从Y 恢复X，也就是能正确地进行反变换或译码 传送Y 时所需要的信息率最小,2020/7/20,8,定长编码定理,定长编码定理：由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL个符号Y1, Y2, Yk,YKL（每个符号有m种可能值）进行定长编码。 对任意0，0，只要 则当L足够大时，必可使译码差错小于； 反之，当 时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。,2020/7/20,9,编码效率,差错概率 当信源序列长度L满足时， 就能达到差错率要求。 编码效率 最佳编码效率为,2020/7/20

5、,10,变长编码定理,单个符号变长编码定理 若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式,2020/7/20,11,变长编码定理,离散平稳无记忆序列变长编码定理 对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率 满足不等式 其中，为任意小正数。,2020/7/20,12,香农编码步骤,将信源消息符号按其概率从大到小排列 确定满足下列不等式的整数码长Ki 令P1=0，计算第i个消息的累加概率 将累加概率Pi变换成二进制数，取小数点后Ki位为该消息的码字,2020/7/20

6、,13,费诺编码方法,费诺编码属于概率匹配编码，不是最佳的编码方法。编码过程如下： 将信源消息符号按其出现的概率依次排列 p(x1) p(x2) p(xn) 按编码进制数将概率分组，使每组概率尽可能接近或相等，并为每一组分配一位码元。如编二进制码就分成两组，编m进制码就分成m组。 将每一分组再按同样原则划分，重复步骤2，直至概率不再可分为止。 信源符号所对应的码字即为费诺码。,2020/7/20,14,哈夫曼编码方法,哈夫曼编码的步骤 将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2) p(xn) 取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配

7、码元的符号重新排队。 对重排后的两个概率最小符号重复步骤2的过程。 继续上述过程，直到最后两个符号配以0和1为止。 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,2020/7/20,15,三种编码的比较,香农码、费诺码、哈夫曼码都考虑了信源的统计特性，经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现对信源的压缩。 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高。 费诺码和哈夫曼码的编码方法都不惟一。 费诺码比较适合于对分组概率相等或接近的信源编码。 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此

8、综合性能优于香农码和费诺码。,2020/7/20,16,限失真信源编码定理,设离散无记忆信源X的信息率失真函数为R(D) 当信息率 RR(D)时，只要信源序列长度 L 足够长，一定存在一种编码方法，其译码失真小于或等于 D，为任意小的正数。 反之，若RR(D) ，则无论采用什么样的编码方法，其译码失真必大于D。 如果是二元信源，则对于任意小的0，每一个信源符号的平均码长满足如下公式：,2020/7/20,17,第6章信道编码,重点掌握 差错控制相关的基本概念 差错控制系统分类 检、纠错能力 有扰离散信道编码定理 一般了解 纠错码分类 纠错码的基本思路,2020/7/20,18,与差错控制有关的

9、基本概念,汉明重量（码重）：码字中非0码元的个数，用W表示。对于二进制来说，指码字中码元1的数目。 汉明距离（码距）：两个等长码字之间对应码元不相同的数目，用D表示。 码的最小距离dmin：在某一码集C中，任意两个码字之间汉明距离的最小值称为该码的最小距离，即,最小码距是衡量该码纠错能力的重要依据,2020/7/20,19,与差错控制有关的基本概念,错误图样 在二元无记忆N次扩展信道中，差错的形式也可以用二元序列来描述，称为错误图样。 设发送码字为C=(c1c2cn)，接收码字为R=(r1r2rn)，两者的差别为 分组码：每个码字中增加的r 个校验元只由本组的k个信息元产生，与其他信息组的信息

10、元无关。记为(n, k) 卷积码：增加的r个校验元既与本组信息元有关，还与前面L组信息元有关。记为(n, k, L),2020/7/20,20,差错控制系统分类,前向纠错方式（FEC） 自动请求重发方式（ARQ） 混合纠错（HEC）,译码设备不复杂，对突发错误特别有效,实时性好，适用于单工通信,检错、纠错能力强，译码设备复杂，应用广泛,2020/7/20,21,检错与纠错能力,检错与纠错能力 纠错码的检、纠错能力是指能够检测、纠正差错的数目。 检错能力 纠错能力 检、纠错能力 将检错和纠错统一考虑，情况会有所变化。 要增加检错能力，必须抑制纠错能力。,e dmin1,ed+ec dmin-1,t =INT(dmin-1)/2,2020/7/20,22,有扰离散信道编码定理,若有一离散无记忆平稳信道，其容量为C，输入符号序列长度为N。只要待传送的信息率RC，总可以找到一种编码方法，当N足够长时，使译码错误概率Pe，为任意正数。 反之，当RC时，任何编码的Pe0。当N时， Pe1。 与信源编码定理类似，香农第二定理只是一