第7章_信道编码

1、第7章 信 道 编 码 教学目标 通过本章的学习，熟悉信道编码的概念，了解信道编码的目的及意义；掌握差错控制编码的基本原理，熟悉差错控制的工作方式及几种常用的差错控制编码，了解其性能优劣；熟悉码距、码重对编码器检纠错能力的影响；掌握如何利用线性分组码实现纠检错，熟悉生成矩阵和监督矩阵的概念，了解汉明码的基本构成；理解循环码的概念，掌握其编解码过程及如何用电路实现循环码的编解码；了解卷积码的概念及其代数表示方式。清华大学出版社第七章 信道编码7.1 信道编码的基本概念7.1.1 差错控制编码基本方式和类型 1. 常用差错控制工作方式 按照噪声或干扰所引起的错码分布规律的不同，信道可以分为三类：随

2、机信道、突发信道和混合信道。 差错控制的基本工作方式有检错重发、前向纠错、反馈校验、混合纠错等四种。它们的基本构成及工作原理如图7.1所示。 清华大学出版社第七章 信道编码图7.1 差错控制工作方式(1)检错重发(ARQ)方式又称自动请求重传。 (2)常用的检错重发系统有三种，即停止等待ARQ系统、拉后ARQ系统和选择重发ARQ系统，图7.2中给出了这三种系统的工作原理图。清华大学出版社第七章 信道编码图7.2 ARQ系统的工作原理(a) 停止等待ARQ系统 (b) 拉后ARQ系统 (c) 选择重发ARQ系统清华大学出版社第七章 信道编码 差错控制编码常称为纠错编码。不同的编码方式有不同的检错

3、或纠错能力。有的编码方法只能检错，不能纠错。一般来说，付出的代价越大，检纠错的能力就越强。这里所指的代价，就是指增加的监督码元位数，它通常用冗余度或多余度来衡量。设编码序列中信息码元位数为 ，监督码元位数为 ，码字位数为 ，则比值 称为编码效率简称码率又称编码速率，比值 称为冗余度，比值 称为多余度。 krrknnk /kr /nr /清华大学出版社第七章 信道编码 2. 差错控制编码分类 差错控制系统中使用的信道编码可以有很多种。 (1)按照信息码元和监督码元之间的函数关系可以分为线性码和非线性码。 (2)按照信息码元和监督码元之间的约束关系涉及的范围可以分为分组码和卷积码。 (3)按照纠错

4、码组中信息码元是否隐蔽，可划分为系统码和非系统码。 (4)按照纠正错误的类型不同，可以分为纠正随机错误的码和纠正突发错误的码。 (5)按照构造差错控制编码的数学方法来分类，又可以分为代数码、几何码和算术码。 清华大学出版社第七章 信道编码 7.1.2 码重、码距与检错、纠错能力 差错控制编码的基本思想是在被传输的信息码元中增加一些监督码元，在两者之间建立某种校验关系，呈现某种关联性。当这种校验关系因传输错误而受到破坏时，可以被发现并予以纠正。这种检错和纠错能力是用信息量的冗余度来换取的。清华大学出版社第七章 信道编码 在信道编码中，定义码组中非零码元的数目为码组的重量，简称码重。 把两个码组中

5、对应码元位置上具有不同二进制码元的位数定义为两个码组的距离，称为汉明距离，简称码距。 一种编码的最小码距的大小直接关系着这种编码的检错和纠错能力： (1) 为检测 个错码，要求最小码距为 (7-1) (2) 为了纠正 个错码，要求最小码距为 (7-2) (3)为了纠正 个错码同时检测 个错码，要求最小码距为 (7-3)1min ed12min tdette1minetd清华大学出版社第七章 信道编码7.1.3 几种常用的差错控制码 1. 奇偶监督码 奇偶监督码又称奇偶校验码，分为奇数监督和偶数监督两种，两者的原理相同，都是在原信息码后面附加1个监督元，使得码组中“1”的个数是奇数或者偶数。无论

6、信息位是多少位，监督位或校验位都只有1位。清华大学出版社第七章 信道编码 2. 行列奇偶监督码 奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列奇偶监督码，又称二维奇偶监督码。这种编码不仅对水平方向的码元，而且对垂直方向的码元实施监督。行列奇偶监督码先把上述奇偶监督码的若干码组，每个写成一行，然后再按列的方向增加每一列的监督位，如图7.3所示。 清华大学出版社第七章 信道编码图7.5 行列奇偶监督码 3. 恒比码 恒比码又称等重码或定“1”码，它是从某确定码长的码组中挑选那些“1”和“0”的比例为恒定值的码组作为许用码组，即码组中“1”和“0”的位数保持恒定的比例。 清华大学出版社第七

7、章 信道编码 4. 群计数码 群计数码是将信息码元分组后，计算每组码元中“1”的个数，然后将这个数目的二进制表示作为监督码元附加在信息码元之后组成码字。 5重复码 一种k=1的(n, k)分组码，其编码规则是n-1个监督码元均是信息码元的重复。 清华大学出版社第七章 信道编码7.2 线性分组码 7.2.1 线性分组码的定义及性质 1定义 线性分组码是一种同时具有分组特性和线性特性的纠错码。 所谓分组特性是指将信码进行分组，并为每组信码附加若干监督码。分组码一般用符号( )表示，其中 是一个码字(又称码组、码矢)的总位数，又称为码组的长度， 是码组中信息码元的数目， 为码组中监督码元的数目。 k

8、n,nrknk清华大学出版社第七章 信道编码因此，分组码的任一码字A可表示为 其中 为信息码元， 为监督码元。在分组码中，监督码元仅监督本码组中的信息码元。 所谓线性特性是指信息码元与监督码元之间的关系可以用一组线性方程式来表示，任一监督码元都是本码组中信息码元的线性叠加(二进制编码是模2加)。如(7,4)线性分组码的码字为 ，前四位 是信息元，后三位 是监督元，则监督元的产生可用以下线性方程组描述012121aaaaaaaArrrnnrnnaaa210121aaaarr0123456aaaaaaaA 3456aaaa012aaa清华大学出版社第七章 信道编码 (7-4)34603561456

9、2aaaaaaaaaaaa清华大学出版社第七章 信道编码 从生成线性分组码各码字的角度看，可将(n,k)线性分组码的每一个码字看成n维线性空间中的一个矢量。长为n的码字共有 个，它们组成一个n维的线性空间；而(n,k)线性分组码只有 个许用码字( )，它们构成一个k维的线性子空间。由此定义： (n,k)线性分组码C是码字A的n维向量的集合 (7-5) 其中m为任意的k维向量，称为信息向量。矩阵G称为生成矩阵，它有k行n列秩为k，记为n2k2nk CA AmG清华大学出版社第七章 信道编码 (7-6)0,00,10,11,01,11,11,01,11,1k nnnkkknGggggggggg 2

10、性质线性分组码的主要性质如下：(1) 任意两许用码组之和(逐位模2加)仍为一许用码组，即线性码具有封闭性。(2) 任一码字是生成矩阵的行向量的线性组合。(3) 最小码距等于码组中非全零码的最小码重。清华大学出版社第七章 信道编码 7.2.2 生成方程和生成矩阵G 描述监督码元和信息码元之间相互关系的方程，称为生成方程，即 A=mG (7-7)7.2.3 监督方程和监督矩阵H7.2.4 线性分组码的译码伴随式(校正子)S7.2.5 汉明码 能纠正单个错误且对监督位的利用最充分的线性分组码称为汉明码。汉明码具有以下特点：清华大学出版社第七章 信道编码(1) 监督码位数； (2) 信息码位数；(3)

11、 码长；(4) 无论码长多少，最小码距(又称汉明距离)；(5) 纠错能力。这里为不小于2的正整数。给定后，即可构造出具体的汉明码。清华大学出版社第七章 信道编码7.2.6 线性分组码的实现1编码2译码清华大学出版社第七章 信道编码 7.3 循 环 码 7.3.1 循环码的含义与特点 线性分组码中，有一种重要的码称为循环码。它是在严密的代数学理论基础上建立起来的，是目前研究得最成熟的一类码。循环码的编码和解码设备都不太复杂(由循环性决定)，而且检纠错能力较强。循环码还具有易于实现的特点，很容易用带反馈的移位寄存器实现其硬件，而且性能较好，不但可用于纠正独立的随机错误，也可以用于纠正突发错误。清华

12、大学出版社第七章 信道编码 7.3.2 循环码的生成多项式、生成矩阵和监督矩阵 1生成多项式 循环码完全由其码组长度 及生成多项式 所决定。对于(n,k)循环码，可以证明， 具有以下性质：)(xgn)(xg)(xg清华大学出版社第七章 信道编码(1) 是一个能除尽的码多项式。或者说， 是 的一个因式。(2) 是一个r次多项式，常数项为1。即 (7-8)(3) 其它码多项式都是 的倍式。假设信息码多项式是 ，则码多项式为 (7-9)(xg)(xg1nx)(xg1)(111xaxaxxgrrr)()()(xgxMxC)(xg)(xM清华大学出版社第七章 信道编码2生成矩阵 和监督矩阵 循环码的生成

13、矩阵很容易由多项式得到，表示为 (7-10)(xG)(xHnkkkxgxxgxgxxgxxG)()()()()(21清华大学出版社第七章 信道编码 7.3.3 循环码的编译码方法1编码过程及实现 生成循环码的码字有两种方法：一种是利用生成矩阵产生，一种是利用多项式除法产生。前者电路实现难度较大，后者编码电路实现比较简单，且编码没有延迟。下面介绍利用多项式除法产生码字的原理及实现方法。清华大学出版社第七章 信道编码2译码过程及实现循环码的纠错过程可按以下步骤进行：(1) 用生成多项式 去除接收码组 ，得出余式 。(2) 按余式 用查表的方法或通过某种运算得到错误图样 ，就可以确定错码位置。(3)

14、 从 中减去，便得到已纠正错误的原发送码组 。)(xg)()()(xExAxB)(xr)(xr)(xE)(xE)(xB)(xA 7.4 卷 积 码7.4.1 卷积码的基本原理卷积码编码器一般原理框图 清华大学出版社第七章 信道编码7.4.2 卷积码的代数表示 一个线性码可以由一个监督矩阵H或生成矩阵G所确定。首先设在第一个信息位 进入编码器之前，各级移存器多处于“0”状态，则监督位 、 和信息位 之间的关系可写为 (7-11)ibidieib23442441233133122221111bbbebbdbbbebbdbbebdbebd清华大学出版社第七章 信道编码 7.4.3 卷积码的图形表示

15、卷积码的译码方式中其大数逻辑译码时给予卷积码的代数表示之上的，而其维特比译码方式是基于卷积码的几何表述之上的。所以在介绍卷积码的译码算法之前，先引入集中几何表述方法。1. 树形图清华大学出版社第七章 信道编码卷积码树形图清华大学出版社第七章 信道编码2. 状态图卷积码状态图 清华大学出版社第七章 信道编码3. 网格图卷积码网格图 清华大学出版社第七章 信道编码 7.4.4 卷积码的译码方法 卷积码的译码方式有三种：大数逻辑译码、维特比译码、门限译码。其中维特比译码具有最佳性能，但硬件实现复杂；大数逻辑译码性能最差，但硬件简单；序列译码在性能和硬件方面介于维特比译码和大数逻辑译码之间。清华大学出

16、版社第七章 信道编码 1. 大数逻辑译码 大数逻辑译码又称门限译码，它曾经是卷积码最常用的译码方法，虽然现在维特比译码和序列译码已成为主要的译码方法，但是由于大数逻辑译码设备简单，译码速度快，并且适合于有突发错误的信道，因此在某些情况下仍有实用价值。清华大学出版社第七章 信道编码 2. 维特比译码 维特比译码算法是维特比于1967年提出的。由于这种译码方法比较简单，计算快，故得到广泛应用，特别是在卫星通信和蜂窝通信系统中应用。维特比译码是一种最大似然译码算法。最大似然译码算法的基本思路是：把接收码字与所有可能的码字比较，选择一种码距最小的码字作为译码输出。若发送一个 位序列，则有 种可能的发送

17、序列。计算机应存储这些序列，以便用于比较。当 较大时，存储量太大，使实用性受到限制。维特比算法对此做了简化，即把接收码字分段累计处理，每接收一段码字计算、比较一次，保留码距最小的路径，直至译完整个序列。kk2k清华大学出版社第七章 信道编码 3. 序列译码 在卷积码 中 值很大的情况下，可以采用序列译码。序列译码早在维特比译码之前就已提出，它也是以最大似然译码原理为基础。如同维特比译码，序列译码也是以汉明距离为准则，选择与接收序列最接近的路径作为译码输出。与维特比译码不同的是，序列译码只是延伸一条具有最小汉明距离的路径，而不是把所有可能的路径保留，然后进行比较、选择。计算，并建立一定的算法。)

18、,(NknN清华大学出版社第七章 信道编码 由于序列译码中一次只搜索一条路径，在有限搜索情况下，这条路径并不能肯定是最好的，它只能认为是一种寻找正确路径的试探方法。它总是在一条单一的路径上，以序列的方式进行搜索。译码器每向前延伸已调支路就进行一次判断，选择呈现出具有最大似然概率的路径。如果所作的判决时错误的，则以后的路径就是错误的。根据路径量度变化，译码器最终可以识别路径是否正确。当译码器识别出路径是错误的时候，就后退搜索并试探其他路径，知道选择已一条正确的路径位置。为了恢复正确路径，需要进行大量清华大学出版社第七章 信道编码 本章 小 结 在数字信号传输过程中，为了提高信道的可靠性，常通过信道编码的方式来实现差错控制。信道编码即差错控制编码，其基本原则是发送端在信息码元中按照一定的规律加入一些冗余的码元，这些冗余码元被称为监督码。而接收端则利用监督码元与信息码元之间的约束关系来进行判断，衡量传输过程中是否存在误码。利用这些差错控制编码，接收端可以发现或纠正传输过程中的误码。清华大学出版社第七章 信道编码 差错控制的方式一般有4种：检错重发、前向纠错、反馈校验、混合纠错。检错重发方式的通信系统需要有双向信道传送重发指令。常用的检错重发系统