一般来说，若（an-1,an-2,…a0)是循环码的码组，则 （an-2,an-3,…a0,an-1) （an-3,an-4,…an-1,an-2) …… （a0,an-1,…a2,a1) 也是该循环码的码组。 为了使用代数工具研究循环码，码组（an-1,an-2,…,a1,a0)也可以用一个多项式来表示 A(X)=an-1xn-1+an-2xn-2+…+a1x+a0 例如：对于一个（7，3）循环码，任一码组可以表示为 A(X)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0 式中a6,a5,…a1,a0是编码，x只是码元位置的标记。 对于一个循环码组，各个码多项式存在如下的关系： A0（X）=an-1xn-1+an-2xn-2+…+a1x+a0 A1（X）=an-2xn-1+an-3xn-2+…+a1x2+a0x+an-1 Ai（X）=an-i-1xn-1+an-i-2xn-2+…+a0xi+an-1xi-1+…+an-i 式中采用模2加减，所以加法与减法是等效的。 上式说明，xA0(X)对xn+1求余的结果为A1(X)。求余运算又称为模运算。所以，上式表明：若A0(x)表示循环码的一个许用码，则xA0(x)在模xn+1运算下也是一个许用码。 xiA0(x)在模xn+1运算下也是一个许用码。 * * * * 第八章 纠错编码 对于数据传输，人们主要关心的是信息码元的差错概率，即误码率Pe。 在中等传输速率（1200/2400波特）下，采用一般的调制方法，对于干线的数量级，对于无线的数量级，对于传输速率更高的系统，误码性能还要差。 在数据通信中，如计算机与计算机之间的数据传送，Pe要求低于10-9。 信道实际性能与要求存在很大差距，需要使用检纠错编码提高传输性能。 8.1 差错控制 一、差错及信道分类 1、随机差错：误码随机出现，各个误码之间统计独立，整个码流差错概率稳定，如由正态分布白噪声引起的差错。以随机差错为主的信道称为随机信道。 2、突发差错：一个差错的出现引起后续码元差错率提高，出现成串差错。脉冲干扰、衰落现象都可能引发突发差错。以突发差错为主的信道称为突发信道。 突发长度：从第一位差错到最后一位差错间的长度。 3、混合信道：既存在随机差错又存在突发差错的信道称为混合信道。 二、信道差错模型 信源 编码器 信道 泽码器 信宿 M=(m1，……mk) C=(c1，……cn) E=(e1，……en) R=(C⊕E) M’=(m’1，……m’k) E称为干扰向量或错误图样。其中的每一位代表信息码对应位是否发生差错。 三、差错控制方式 1、前向纠错FEC(Forward Error Correction) 发送端经编码发出能纠正错误的码，接收端收到这些码组后，通过译码能发现并纠正误码。 前向纠错方式不需要反馈通道，特别适合只能提供单向信道的场合，特点是时延小，实时性好，但系统复杂、编码效率较低。随着编码理论和微电子技术的发展，编译码设备成本下降，在实际应用中日益增多。 2、自动反馈重发ARQ(Automatic Repeat Request) 采用自动反馈重发方式，发端经编码后发出能够发现错误的码，接收端收到后经检验如果发现传输中有错误，则通过反向信道把这一判断结果反馈给发送端。然后，发送端把信息重发一次，直到接收端确认为止。 采用这种差错控制方法编码效率较高、设备也较简单，但需要具备双向通道，一般在计算机数据通信中应用。 检错重发方式分为三种类型。 （1）停发等待重发 （2）返回重发 （3）选择重发 3、混合纠错HEC(Hybrid Error Correction) 发端把原始码流编成能在一定范围内检错和纠错的代码，然后发送。 收端发现错误后，能纠则纠，不能纠则通知发端重发。 4、反馈校验IRQ 收端把收到的数据序列全部由反向信道送回发送端，发送端比较发送数据与回送数据，从而发现是否有错误。 三、差错控制基本原理 信息码直接传输是不可能检错或纠错的 通信时，发送端发送的数码是随机的，接收端事先不可能预知将要收到什么样的代码。因此，当接收端收到的代码与原发端发送的代码不相同时，接收端无法判断是否有错码。 解决办法： 在待传送的信息码元中附加一些监督码元（nBmB)，监督码对原码构成某种校验关系（使整码具有一定规律），当这种校验关系（规律）因传输错误而受到破坏时，可以被发现并予以纠正。 检错和纠错能力是用降低编码效率来换取的 8.2 线性分组码 系统码：分组码中，前k位保持原信息位BG大游不变，后加r位冗余位。一般称为(n,k)码。 cn-1=mk-1 cn-2=mk-2 cn-k=m0 …… 8.2.1 线性分组码的概念 分组码：将待传信息分为k位一组，分别加入r位冗余位，形成n=k+r位码字。 mk-1mk-2……m0 cn-1cn-2……c0 mk-1mk-2……m0 0110100… 分组码的各位由原信息码的各位通过一组函数来确定： cn-1=fn-1(mk-1,mk-2,…,m0) cn-2=fn-2(mk-1,mk-2,…,m0) c0=f0(mk-1,mk-2,…,m0) …… 若函数f0~fn-1都是线性函数，则编出的码为线性分组码 一般情况下，线由一组代数式构成 cn-1=gn-1k-1mk-1+gn-1k-2mk-2+…+gn-10m0 cn-2=gn-2k-1mk-1+gn-2k-2mk-2+…+gn-20m0 c0=g0k-1mk-1+g0k-2mk-2+…+g00m0) …… 一、生成矩阵与监督矩阵 上述方程组可以表示成如下矩阵运算形式： 简记为： C=MG 矩阵G被称为生成矩阵。利用生成矩阵，可以直接对信息码进行编码。 [思考：系统码的生成矩阵有什么特点？］ 例1：待发送码流为0…，生成矩阵为： 写出对应的线性分组码码流。 解：对原码流进行线性分组码编码时，先分为k位一组，G有四行，所以k=4；原码流分为：1011、0101、1100等 分别代入C=MG算出：1011100、0101100、1100110 所以编码后的码流为：100110 线性分组码一般都用在信息码后直接增加冗余位来获得，即： cn-1=mk-1 cn-2=mk-2 c0=f0(mk-1,mk-2,…,m0)= f0(cn-1,cn-2,…,cn-k) …… cn-k=m0 cr-1=fr-1(mk-1,mk-2,…,m0)=fr-1(cn-1,cn-2,…cn-k) …… r个冗余位的关系式可改写为： s0=f0(cn-1,cn-2,…,cn-k)+c0=0 sr-1=fr-1(cn-1,cn-2,…cn-k)＋cr-1=0 …… 这r个方程是r个冗余位对信息位的约束方程，称为监督方程；接收方可以用这r个方程对接收信息进行正确性校验，s被称为校验子。 由前面介绍的内容可知，r个监督方程可写为： sr-1=fr-1(cn-1,cn-2,…cn-k)＋cr-1 =gr-1k-1cn-1+gr-1k-2cn-2+…+gr-10cn-k+cr-1=0 …… s0=f0(cn-1,cn-2,…cn-k)＋c0 =g0k-1cn-1+g0k-2cn-2+…+g00cn-k+c0=0 同样可以写成矩阵形式： H矩阵称为监督矩阵，利用该式可以进行接收端差错校验。 二、生成矩阵与监督矩阵的关系 Ik Ir P PT G=[IkP] H=[PTIr] 例2：在例1所述数字传输系统中，若接收端接到某组七位信息为0111101，试判断是否发生了传输差错。 解：∵ ∴ 不为零矩阵，说明代码中有传输差错 8.3 线性分组码的检错与纠错 几个定义： 1、码重：码组中非零码元的个数。如001，码重为1；011，码重为2。 2、码距：两个码组中对应码位上具有的不同二进制码元的个数定义为两个码组的距离（又叫汉明距离，简称码距），如111和000的码距为3，111和100码距为2，111和110码距为1。 3、最小码距：对于许用的n个码组，各码组之间最小的码距称为最小码距。 一种编码的最小码距直接关系到这种码的检错和纠错能力，因此最小码距是信道编码的一个重要参数。 在一般情况下，对于分组码有如下结论： （1）在一个码组内检测e个误码，要求最小码距 dmin=e+1 （2）在一个码组内纠正t个误码，要求最小码距 dmin=2t+1 （3）在一个码组内纠正t个误码，同时检测e个(e=t)误码（当误码数大于t时就不能纠错，只能检测e个误码），要求最小码距 dmin=t+e+1 ci cj d 几种实用的简单检错码 1、奇偶监督码 奇偶校验码只能发现奇数个误码，对检测突发错误不适用。 2、水平奇偶监督码 将经过奇偶监督编码的码元按行排成方阵，但传送时则按列进行的顺序传送。接收端仍将码元排成发送时的方形阵式，然后再进行奇偶校验。如： 信息码流顺序 传输码流顺序 3、水平垂直奇偶校验码 在水平奇偶监督码的基础上，对方阵中的每一列也进行奇偶校验。发送时按列序顺次传送，接收端恢复成方阵后进行奇偶校验，如： 信息顺序 传输顺序 4、群计数码 用信息码中1个数的编码做个冗余位。 5、恒比码 编码时，0、1个数比例保持恒定。 8.4 汉明码 线性分组码（n,k)中，一共可以构成r=n-k个监督方程（或校验子）。这r个校验子可以构成2r种组合，全零组合代表编码正确，而其余的2r－1种组合可以代表各种不同类型的差错。 若传输时只发生单个位的差错，而总码长为2r-1，则可以利用不同的校验子状态组合实现差错定位，即纠错。 这种能够纠正单个错误的线性分组码，称为汉明码。 汉明码码长n与冗余位长r的关系： n=2r-1 汉明码的最小码距为3 伴随式与差错位置的关系： 设H＝[h1 h2 … hn]，其中hi是H矩阵中的第i列 则： 即：伴随式ST是H矩阵中与出错位相对应的各列之和。根据汉明码定义，若只发生一位差错，则可确定差错位置。 汉明码的编制： 1、自定义伴随式与差错位置的对应关系； 2、写出监督矩阵； 3、写出生成矩阵，编制汉明码。 例3：构造一种（7，4）汉明码。 解：1、定义各校验子状态与差错位置的关系如下表所示： c6 111 c2 100 c5 110 c1 010 c4 101 c0 001 c3 011 无 000 差错位置 s2s1s0 差错位置 s2s1s0 2、写出H： 3、写出G并编码： 编出全码如下表所示： 111 1111 001 1011 000 0111 110 0011 100 1110 010 1010 011 0110 101 0010 010 1101 100 1001 101 0101 011 0001 001 1100 111 1000 110 0100 000 0000 冗余位 信息位 冗余位 信息位 冗余位 信息位 冗余位 信息位 截短汉明码： 在汉明码的H矩阵中，人为截去若干列，这样构成的编码称为截短汉明码。在截短汉明码中，码长n2r-1，最小码距可能会大于3。 奇权码： 在汉明码的H矩阵中，人为截去所有1的个数为偶数的列，这样构成的编码称为奇权码。在奇权码中，最小码距＝4，可以纠正一位差错同时检测两位差错。 最佳奇权码： 在奇权码的基础上同时要求： 1、总的1的个数尽量少； 2、每行中1的个数尽量相等。 例4：根据前例中的（7，4）汉明码，写出其对应的奇权码编码。 该奇权码只有两个码字： 0→0000 1→1111 例5：构造一种（15，11）汉明码的监督矩阵，写出它对应的奇权码的监督矩阵和生成矩阵。 汉明码监督矩阵： 奇权码监督矩阵： 奇权码监督矩阵： 8.5 循环码 循环码是线性分组码中的一类，是以现代代数理论作为基础建立起来的。 循环码的编码和译码设备相对简单 循环码的检错和纠错能力较强。 循环码与其它线性分组码一样，设总长度为n，前k位是信息位，后r位是监督位。(r=n-k) 循环码中任意一许用码组经过循环移位后(将最右端的码元移至左端)，所得到的码组仍是许用码组。如下表所示。 *BG大游 *
2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
3、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
2024年02月[北京]2024年中国金融电子化集团有限公司录用招考（招考）笔试历年参考题库附带答案详解.docx
剑桥国际少儿英语(第二版) Level 4 8 Let’s party! Lesson 4 课件.ppt
原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者
