差错控制编码_1课件

《差错控制编码_1课件》由会员分享，可在线阅读，更多相关《差错控制编码_1课件（75页珍藏版）》请在金锄头文库上搜索。

1、2014年3月,1,第八章 差错控制编码,通信原理简明教程（第三版）,2014年3月,2,引 言,信源编码，目的是实现模拟信号数字化 信道编码，目的是提高数字通信的可靠性 差错率是信噪比的函数 信道编码，差错控制编码，抗干扰编码 信道编码过程： 信息码元序列监督码元编码码组 信道译码过程： 编码码组检错或纠错信息码元序列,2014年3月,3,本章目录,8.1 差错控制编码的基本概念* 8.2 线性分组码* 8.3 循环码* 8.4 卷积码 8.5 Turbo码 8.6 低密度校验码 8.7 差错控制编码对系统性能的改善,2014年3月,4,8.1差错控制编码的基本概念,8.1.1 差错控制方式

2、 8.1.2 差错控制编码分类 8.1.3 几种简单的检错码 8.1.4 检错和纠错的基本原理,2014年3月,5,8.1.1 差错控制方式,常用的差错控制方式有三种： 前向纠错（FEC:forward error correction） 发送能纠错的码，在译码时自动发现并纠正传输中的错误 只需正向信道，实时性好 编译码设备复杂，适合单向信道和一发多收系统 检错重发（ARQ:automatic repeat request） 发送端发出能够检错的码，接收端检验，接收端发出反馈应答信号，发送端重新传输 直到正确接收为止 工作原理简单，正向信道+反向信道，传输效率低 混合纠错（HEC:hybrid

3、 error correction） 前向纠错方式和检错重发方式的结合与折衷 外层先采用前向纠错，当前向纠错不能解决问题时，内层再采用检错重发。,2014年3月,6,（a） FEC方式 （b） ARQ方式 （c） HEC方式,2014年3月,7,检 错 重 发 的 三 种 方 式,停发等候重发,返回重发,选择重发,2014年3月,8,8.1.2 差错控制编码分类 在编码前先把信息序列分为k位一组（称为信息码），然后附加m位监督码，形成n = k + m位的码组。 1、按信息码和附加监督码间的检验关系 线性码：监督码是信息码的线性组合 非线性码：监督码是信息码的非线性组合 2、按信息码和监督码间

4、的约束方式 分组码：监督码仅与本码组的信息码有关 卷积码：监督码与之前的若干个信息码组的码元有约束关系,2014年3月,9,8.1.3 几种简单的检错码,1. 奇偶监督码 编码方法 把信息码元先分组，在每组最后加一位监督码元，使该码组中1的数目为奇数或偶数 奇数时称为奇校验码 偶数时称为偶校验码 偶校验码 许用码组为000，011，101，110 禁用码组为001，010，100，111 奇校验码 禁用码组为000，011，101，110 许用码组为001，010，100，111,2014年3月,10,一般情况下： 设码组长为n，且为： 则偶校验时有： 奇校验时有： 译码方法(与编码方法相对应

5、) 不满足校验关系，传输一定错误！ 奇偶校验只能发现奇数个(单个)错误，不能检测出偶数个错误。 编码方法简单且实用性强，适用于检测随机零星错码 满足校验关系，传输一定准确吗？,2014年3月,11,2. 二维奇偶监督码 将奇偶校验码的若干码组排列成矩阵 每一码组写成一行 m个码组m行 m个监督位构成了一监督位列 按列的方向增加第二维校验位 n个监督位构成了一监督位行,检错能力 检出所有行和列中的奇数个差错 能检出大多数偶数个差错 检测突发错码也有一定的适应能力 方阵码，交织码,2014年3月,12,3. 重复码 重复码是在每位信息码元之后，再简单重复多次的编码；接收端译码时采用多数表决法 。

6、4. 恒比码 从固定码长的码组中选择那些1和0的比例恒定的码组作为许用码组，如五单位保护电码等。,2014年3月,13,8.1.4 检错与纠错的基本原理 差错编码的基本思想是在被传输的信息中附加监督码，用信息的冗余度来实现检错和纠错。 例如：000、001、010、011、100、101、110、111用来传递信息，则无法检错； 000、011、101、110用来传递信息可以检一位错，但无法纠错； 000、111用来传递信息可以检一位或两位错码，还可以纠一位错码。 可见，码组间的差异与纠检错能力十分重要。,2014年3月,14,定义1：码组中非零码元的数目称为码组的重量，简称码重。 定义2：两

7、码组中对应码位上具有不同码元的数目称为两码组的距离，简称码距，又叫汉明距。 最小汉明距离dmin决定纠检错能力 例 8种码组000、001、010、011、100、101、110、111均为许用码组时，最小码距为1 在选4种码组000、011、101、110为许用码组情况下，最小码距为2 采用2种许用码组000、111时，最小码距为3,2014年3月,15,下图为码距的几何解释 三种编码组合，其汉明距分别为1，2，3。,2014年3月,16,对于分组码，一般有如下结论： (1) 在一个码组内检测e个误码，要求 ； (2) 在一个码组内纠正t个误码，要求 ； (3) 在一个码组内纠正t个误码，同

8、时检测 个误码，要求 。 差错控制编码提高了通信系统的可靠性，也降低了有效性。 为衡量有效性，定义编码效率 。 k是编码前码组中的码元数，即信息码元数； n是编码后码组中的码元数，它包含了校验码元。,2014年3月,17,8.2 线性分组码 线性码组中的监督码是信息码元的线性组合。 线性码具有封闭性，即任意两个许用码组之和（模2加），结果仍为一许用码组。 设n位分组码用 表示，k位信息码用 表示，记该码组为(n , k)码。 将码组和信息码组用行矩阵表示出来，则有：,2014年3月,18,n=k+m， n：编码以后的位数 k：编码以前的位数，即信息码 m=n-k：监督位或校验位,2014年3月

9、,19,写成矩阵形式，有 ，G为生成矩阵(k*n)，且： 设 则,k行,k+m =n列,2014年3月,20,矩阵P的重要意义, 与监督位或校验位相对应 编码的根据 译码的根据，检纠错的根据 矩阵P如何选择？ 编码前信息码组有k位码元，k位码元共有 种组合 编码后码组有n位码元，n位码元共有 种组合， 矩阵P可有多种选择 较强的检错或纠错能力 实现方法尽可能简单且编码效率高 在数学上已经证明 线性码的最小码距正好等于非零码的最小码重 为了估算线性码的差错控制能力应首先求出码组的最小码距,2014年3月,21,例8-1已知(6,3)码的生成矩阵为G，试求：(1) 编码码组和各码组的码重；(2)

10、最小码距 及其差错控制能力。 解 (1) 由3位码组成的信息码组矩阵为D：,2014年3月,22,由式 ，得码组矩阵为： 信息码组、编码码组及码重如下表所示： 信息码组 编码码组 码重W 信息码组 编码码组 码重W 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 3 0 0 1 0 0 1 1 1 0 3 1 0 1 1 0 1 0 1 1 4 0 1 0 0 1 0 0 1 1 3 1 1 0 1 1 0 1 1 0 4 0 1 1 0 1 1 1 0 1 4 1 1 1 1 1 1 0 0 0 3,2014年3月,23,由前表可知，非零码组的最小码重为： 所以最

11、小码距为： 因此，该码有纠1错，或检2错，或纠一错同时检一错的能力。,2014年3月,24,译码原理 由 可知， 或写成 设 ，则有 。 任何线性分组码码组都应该满足上述关系 信息码与监督码间的校验关系完全取决于H H矩阵称为校验矩阵或监督矩阵，是译码的关键！,2014年3月,25,设接收码组为R，它可分解为 。 其中，C为正确码组，E为错误码组（差错图案） 当无错接收时，E为0，当有错接收时，E为非零矢量。 再设伴随矩阵为： ， 则有： 当出现错码时，S为非零矢量，则根据上式可求得E，然后再经过计算 ，便可得到正确的码组了。,只与E有关，而与发送的码字C无关。只反映信道对码字的干扰,RHT=

12、S E C=R+E,2014年3月,26,由于信息码组有 个，由于由S计算出来的E不唯一，纠正后的C就不同，这时，使用最大似然比准则，选择与R最接近的C作为正确的接收码组。方法是：在 E中选择码重最 小的E，即表示 选择与R最接近 的C。 右图是查表法译 码器原理图。,2014年3月,27,例8-2 按照例8-1生成矩阵G，列出S与E的对照表。当收到码组R=1 1 1 0 1 1时，解出对应的信息码组D。 解：已知生成矩阵为： 又因为 故,2014年3月,28,为6X3的矩阵，由式 可知，共有 种形式，相应的码重最小矢量有8种，见下表。由表可知，(6,3)码具有纠1错能力。虽然S111时对应一

13、种双错图案，但除此以外的双错却不能得到纠正。 E S E S 0 0 0 0 0 0 000 0 0 0 1 0 0 100 1 0 0 0 0 0 101 0 0 0 0 1 0 010 0 1 0 0 0 0 011 0 0 0 0 0 1 001 0 0 1 0 0 0 110 1 0 0 0 1 0 111,2014年3月,29,将码组矢量R=1 1 1 0 1 1代入 ，可得S(如下)。 查E-S对照表，可找到差错矢量为： 由式 ，可得到正确码组，即 所以信息码组为：,2014年3月,30,汉明码：能纠正单个错码的称为汉明码。 为能指出所有单错位置和无错情况，线性码组码长n、信息位k

14、和监督位m间应满足下述关系： 上式取等号时为汉明码，此时有： 由于m = nk， 所以，,2014年3月,31,上式表明：若信息码组长为k，则能纠正单个错码所需的最小码组长度n。此时有 。 由上式可求得有(3 , 1)码，(7 , 4)码，(15 , 11)码，(31 , 26)码等。 汉明码的编码效率为： 一般地，若码组有纠t个差错的能力，则应能指出无错、单错到t个差错所有可能情况，此时校验位数m应满足： 上式称为汉明界。它给出了纠t个错的必要条件。,2014年3月,32,8.3 循环码 8.3.1 循环码的描述 循环码是一种系统分组码，前k位是信息码，后r位是监督码。不仅具有封闭性，还具有

15、循环性，即一许用码组经循环移位后得到另一个许用码组。 设 是一个循环码组，则可将之表示为： 上式称为码多项式。,关于码多项式,x表示多项式的元素，其幂次对应元素的位置 系数ci对应该位置上元素的取值 系数之间的加减运算服从模2加法运算规则。,2014年3月,33,循环移位后的变化,经过i次循环移位得到的 码组所对应的码多项式为 循环码的码多项式的规律 一个长度为n的循环码的码多项式必定是模 运算 的一个余式。,2014年3月,34,2014年3月,35,按模运算： 如果一个多项式 被另一个n次多项式 除，得到一个商式 和一个次数小于n的余式 ， 即 记作 则称在模 运算下， 。,循环码的循环特性与码多项式运算,多项式