通信原理--第9章 差错控制编码

1、1 欢迎各位同学光临欢迎各位同学光临 通信原理通信原理课程课程 禹思敏禹思敏 2 第第9章章 差错控制编码差错控制编码 信道编码信道编码, 纠错码纠错码,差错控制编码差错控制编码 提高了可靠性提高了可靠性, 但降低了有效性但降低了有效性 3 9.1 概述概述 9.1.1 差错控制编码的概念差错控制编码的概念 是一种有效的方法信道编码技术 降低误码率提高信噪比加大发射功率 提高可靠性的方法 提高可靠性 加入的码元称监督码元按一定规则加入多余度 信道编码 提高有效性去掉信源的多余度 信源编码 编码 , , ),( : , : 4 9.1.2 差错控制方式差错控制方式 1、检错重发式：发送端发出能检

2、错的码，接收端收、检错重发式：发送端发出能检错的码，接收端收 到后，首先进行检测，当发现错误时到后，首先进行检测，当发现错误时,通知发送端重发通知发送端重发 一次，直到正确。如奇偶校验等。一次，直到正确。如奇偶校验等。 特点：译码简单，实时性差，双向传输。特点：译码简单，实时性差，双向传输。 2、前向纠错：发送能自动纠错的码、前向纠错：发送能自动纠错的码,在接收端能自动在接收端能自动 纠错。特点：实时性好，单向传输。纠错。特点：实时性好，单向传输。 3、混合方式：上述两者的组合。在接收端若能自动、混合方式：上述两者的组合。在接收端若能自动 纠正，则不必重发，若超出自动纠错的范围，则通知纠正，则

3、不必重发，若超出自动纠错的范围，则通知 对方重发，取各自的优点。对方重发，取各自的优点。 5 9.1.3 纠错码的分类纠错码的分类 1、线性码：监督码与信息码之间的关系是线性的、线性码：监督码与信息码之间的关系是线性的 2、非线性码：监督码与信息码间的关系是非线性的、非线性码：监督码与信息码间的关系是非线性的 3、分组码：属于线性码的一种、分组码：属于线性码的一种 4、循环码：属于线性码的一种、循环码：属于线性码的一种 5、卷积码：属于非线性码的一种、卷积码：属于非线性码的一种 6、其它类型的纠错码、其它类型的纠错码 6 9.1.4 纠错码的基本原理纠错码的基本原理 一、分组码：把信息码按一、

4、分组码：把信息码按 k 个码元一组，并按一定的规个码元一组，并按一定的规 律编码，产生律编码，产生 r 个监督码元，形成长度为个监督码元，形成长度为 n=k+r 组码，组码， 称为码字，用称为码字，用(n,k)表示，其特点是：表示，其特点是： 1、共有、共有2k 个不同的码字，称为许用码组；个不同的码字，称为许用码组； 2、共有、共有2n-2k个码字未用，称为禁用码组。个码字未用，称为禁用码组。 正是存在禁用码组，使得正是存在禁用码组，使得(n,k)码具有纠错能力，禁码具有纠错能力，禁 用码越多，纠错能力越强。用码越多，纠错能力越强。 7 2、汉明距离、汉明距离d0的概念的概念: （1）两个码

5、字）两个码字A,B之间的距离定义为之间的距离定义为: 3),(: 0111 1011 1100: ),( , ),( nn nn baBAd B A mBAd mBA baBAd 得 例 则其距离为个码元不同之间有即若两个码字 81,)(,)3( 12,)2( 1,) 1 ( :, , )3( 1 110 101 010 000 :, ,)2( 0 0 0 0 0 etdteet tdt ede d d D C B A 则要求随机错误个同时检测个纠 则要求个随机错误纠 则要求个随机错误检测 有如下结论可以证明 能力越强越大距离有关检错与纠错能力与汉明 检错与纠错能力 如离最小距离定义为汉明距

6、则码字之间的的情况设一个集中有多个码字 9 ., , 01, 10 ., 1 0 ) 1 , 1 (),( ,) 1 ( :. 5 / )(. 4 无任何纠检错能力没有监督码时 因此码组出错后的码组仍为许用或 原因是无法纠正故出错时由于没有禁用码组 雨 晴 没有监督码时只有信息码 雨和晴用二进码表示例题 编码效率 有效性的一种指标编码效率 kn nkR 10 可检出一个随机错误错误 可检出这个故在接收端组范围由于它们不属于许用码 或收到的码组变为产生了错误在传输过程中 许用码组的汉明距离 雨 晴 禁用码组许用码组 种位编码共有 后监督码加上一位重复码 , , ),0 , 1 () 1 , 0(

7、, 2: 1011 0100 11,10,01,00:42 ) 1 , 2(),( ,)()2( 0 01 d aa kn 11 )6(110,101,100,011,010,001: 3 111 000 : )2( 111,110,101,100,011,010,001,000: ) 1 , 3(),( ,)3( 0 012 012 个共禁用码组 许用码组的汉明距离为 雨 晴 个共许用码组 全部码字为 加上两位监督码元 d aaa aaa kn 12 3 0 d 000111 001 010 100 011 101 110 由(000) 错一位的结果 由(111) 错一位的结果 由上图可知,

8、若传输过程中 错一位,能够将其纠正 13 9.2 常用的几种简单的分组码常用的几种简单的分组码 9.2.1 奇偶监督码奇偶监督码 一、二进制运算规则一、二进制运算规则 对于二进制的按位运算来说对于二进制的按位运算来说, 加法加法, 减法减法, 异或异或 三种运算的结果相同三种运算的结果相同, 这三个符号可视为相同即, , 0 111111 000000 1100110011001 0111111 0000000 AAAAAA AAAAAAA AAAAAAA 14 1210 1210 0121 0121 , 0 ,1 . 1 , ) 1,(),(. aaaa aaaa aaaa aaaaA nn

9、 nn nn nn nn 之间的关系为与信息码得监督码元 有的个数为偶数满足 偶监督码 设码字 码奇偶监督码奇偶校验二 监督码 信息码 15 a7 a6 a5 a4 a3 a2 a1 a7 a6 a5 a4 a3 a2 a1 a0 信道信道 a7a6a5a4a3a2a1a0 输出输出 S 应答信号应答信号 校正子电路校正子电路 发送端发送端接收端接收端 16 只能用于检错重发方式 不能纠错只能检错 但无法检测偶数个错个错奇偶监督码可检测奇数 小结 需要重发有错若不要重发无错若 端作为应答信号通知发送利用 有错 无错 满足又称为校正子应答信号在纠错码中 )3( ;,)2( ;,) 1 ( : .

10、, 1, 0 : 1 0 :, 01234567 SS S aaaaaaaaS S 17 9.2.2 行列监督码行列监督码 对水平方向的码元和垂直方向的码元同时实施对水平方向的码元和垂直方向的码元同时实施 奇偶监督，在一般情况下有：奇偶监督，在一般情况下有： LM 个信息码元加个信息码元加 L+M+1个监督元，组成个监督元，组成LM+(L+M+1), LM行行 列监督码的一个码字（列监督码的一个码字（L+1行行,M+1列）。列）。 现以现以(n,k)=(66,50)为例加以说明。为例加以说明。 18 11001010000 01000011010 01111000011 10011100000

11、 10101010101 11000111100 水 平 方 向 偶 校 验 垂直方向偶校验 19 有关差错的分类有关差错的分类: 1、随机差错：、随机差错：由加性高斯噪声等引起，特点：一般只错由加性高斯噪声等引起，特点：一般只错 一位的可能最大，但哪位出错则是随机的，经计算得：一位的可能最大，但哪位出错则是随机的，经计算得： （1）错一位的概率为：）错一位的概率为：Pe(1) = 710-3 （2）错二位的概率为：）错二位的概率为：Pe(2) = 2.110-5 （3）错三位的概率为：）错三位的概率为：Pe(3) = 3.510-8 由上述结果可见，出一位错的可能性最大。由上述结果可见，出一

12、位错的可能性最大。 2、突发差错：、突发差错：连续的一串码元出现错误，出错的长度称连续的一串码元出现错误，出错的长度称 为突发长度。如磁盘上磁粉失落或划伤后，对其读写会出为突发长度。如磁盘上磁粉失落或划伤后，对其读写会出 突发错。突发错。 20 9.3 线性分组码线性分组码 .,)3( ., ,)2( ,) 1 ( : 1 0 0 : , 0121 0121 0121 似之处译码电路与偶校验有类线性分组码的编码 既可检错又可纠错较多 码元而线性分组码由于监督不能纠错偶校验只能检错 督码元线性分组码则有多个监元偶校验只有一个监督码 别与偶校验码的联系及区本节讨论的线性分组码 分组码中来上述方法可

13、推广到线性 表示有错 表示无错 校正子 系之间满足如下的编码关 与监督码信息码在偶校验码中 aaaaS aaaa aaaa nn nn nn 21 9.3.1 基本概念基本概念 个禁用码字为 个许用码字为 许用码组与禁用码组 设码字为 点来说明线性分组码的特 分组码为例现以 监督码元信息码元 11222 162 :) 1 ( : )4 , 7( 47 4 3460 3561 4562 0123456 aaaa aaaa aaaa aaaaaaaA a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1

14、 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 22 )( 112:)3( 3, 3 ,0, :)4 , 7()2( 0 0 能纠一位错 纠错能力 故得最小码重为 码外除全由于该码具有封闭性 码的汉明距离的求法 ttd d 23 9.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G （1）监督矩阵）监督矩

15、阵H及其物理意义及其物理意义 )( | 001 1011 010 1101 100 1110 ,: 0 0 0 0 0 0 1011001 1101010 1110100 0 0 0 0123456 0 1 2 3 4 5 6 0346 1356 2456 3460 3561 4562 标准监督矩阵 可表为为监督矩阵为码字式中 IPH HaaaaaaaA AHHAHA a a a a a a a aaaa aaaa aaaa aaaa aaaa aaaa T T T TT 单位矩阵单位矩阵 线性分组码的编码规则！线性分组码的编码规则！ 24 监督矩阵监督矩阵H的物理意义：的物理意义： 1）在发

16、送端，可利用监督）在发送端，可利用监督 H来进行编码，因此来进行编码，因此 H 实际上是一种编码规则。利用这种编码规实际上是一种编码规则。利用这种编码规 则，使得则，使得H和码字和码字A满足满足AHT=0或或HAT=0 2）在接收端，可利用）在接收端，可利用 H，对经信道传送过来的，对经信道传送过来的 码字码字 A进行监督或检测，判断其正确性，若进行监督或检测，判断其正确性，若 正确，必满足正确，必满足AHT=0或或HAT=0，若不正确，若不正确， 则则AHT不为不为0或或HAT不为不为0。 3）下文中将要讲述的校正子正是根据这一原理）下文中将要讲述的校正子正是根据这一原理 来判断接收码字来判

17、断接收码字 A的正确性并进行纠错的。的正确性并进行纠错的。 25 GaaaaA a a a a GA a a a a a a a a a a a aaaa aaaa aaaa aa aa aa aa aaaa aaaa aaaa aa aa aa aa TT 3456 3 4 5 6 3 4 5 6 0 1 2 3 4 5 6 3460 3561 4562 33 44 55 66 3460 3561 4562 33 44 55 66 : 1011 1101 1110 0001 0010 0100 1000 : 转置 即 如下形式前面的式子还可表示为 物理意义：由生物理意义：由生 成矩阵成矩阵G

18、 和信息和信息 码产生一个码字码产生一个码字 （2）生成矩阵）生成矩阵G及其物理意义及其物理意义 增加的增加的 原来的原来的 26 ., , )(| 001 1011 010 1101 100 1110 )(| 011 0001 101 0010 110 0100 111 1000 HGGH PQQP GH IPH QIG TT 求或由求可由由此可见 或 的关系为和生成矩阵监督矩阵显然 标准监督矩阵 矩阵为由前面得到的标准监督 标准生成矩阵 （3）生成矩阵）生成矩阵G和监督矩阵和监督矩阵H的关系的关系 27 9.3.3 一种编码电路介绍：根据一种编码电路介绍：根据 得编码电路：得编码电路： 6

19、 a 5 a 4 a 3 a 2 a 1 a 0 a 3460 3561 4562 aaaa aaaa aaaa 28 例题：例题：设（设（7,3）线性分组码的监督矩阵为）线性分组码的监督矩阵为 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0123456 H aaaaaaa 监督码元信息码元 试求：试求： （1）监督码元与信息码元之间的关系表达式；）监督码元与信息码元之间的关系表达式； （2）列出所有的许用码组）列出所有的许用码组（必须自己完成）（必须自己完成）； （3）求汉明距离；能纠几位错？）求汉明距离；能纠几位错？（自己

20、完成）（自己完成） ； （4）画出编码器电路。）画出编码器电路。 需要用初等变换将其需要用初等变换将其 化成标准单位矩阵化成标准单位矩阵 29 解：解：由于由于H矩阵不是标准矩阵矩阵不是标准矩阵,需经初等变换后变换成需经初等变换后变换成 标准矩阵。得变换后的标准矩阵为：标准矩阵。得变换后的标准矩阵为： 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 H 从而得监督码元与信息码元之间的关系表达式为从而得监督码元与信息码元之间的关系表达式为 450 561 4562 463 aaa aaa aaaa aaa 30 进一步可画出编码器电

21、路如下：进一步可画出编码器电路如下： 6 a 5 a 4 a 3 a 2 a 1 a 0 a 31 9.3.4 S校正子（伴随式）校正子（伴随式） 时当 时当 并且有其中 或 即也称为误差矢量误图样定义收发码字之差为错 接收码字变为可能会发生错误 由于传输过程中设发送码字为 工作原理来讨论其校正子的基本为例 我们仍然以线性分组码 ii ii iii nn nn nn ab ab abe eeeeE EABABE E bbbbB aaaaA aaaa aaaa aaaa 1 0 , , :, , , ., 0121 0121 0121 3460 3561 4562 32 ., , , 0, 0

22、, 0, 0 : 0: : 0: . 对接收的码进行纠错利用这一关系对应关系 之间有确定的样正子与错误图样由上式知 表明有错若不为 表明无错若等于 故有 由发送端的编码规则知 校正子为则令接收端的 若发送端的编码规则为 发送端编码规则应相同注意接收端解码规则与 ES E E EHS AH EHAHHEABHS S AHS T T TTTT T 33:710317, 0 0 0 0 0 0 ., )4 , 7( 03460 13561 24562 0346 1356 2456 0346 1356 2456 3460 3561 4562 3460 3561 4562 的结果如下表可得书中由上式 法

23、来说明校正子的产生方为例 码现以以 P eeees eeees eeees eeee eeee eeee aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 34 ., 0, , 0,)2( ., 0, , 0,) 1 ( : : 012 0123456 012 0123456 03460 13561 24562 需校正表明传输不正确则 若误差 不需校正表明传输正确则 若误差 说明 校正子公式 ssss eeeeeeee ssss eeeeeeee eeees eeees eeees 35 b6错错 1 1 11 0 0 0 0 0 0 b6 7 b5错错

24、 1 1 00 1 0 0 0 0 0 b5 6 b4错错 1 0 10 0 1 0 0 0 0 b4 5 b3错错 0 1 10 0 0 1 0 0 0 b3 4 b2错错 1 0 00 0 0 0 1 0 0 b2 3 b1错错 0 1 00 0 0 0 0 1 0 b1 2 b0错错 0 0 10 0 0 0 0 0 1 b0 1 无错无错0 0 00 0 0 0 0 0 0无无0 S2 S1 S0e6e5e4e3e2e1e0 说明说明 SE 错误错误 码位码位 序序 号号 .,12 8) 3(2: 可代表不同的错误图样即校正子的不同输出种有错以及 无错种形式分别表示码字校正子的由此表可

25、知 r r ArS 36 9.3.5 一种（一种（7,4）码（又称为汉明码）的译码电路）码（又称为汉明码）的译码电路 1、复习数字电路中的、复习数字电路中的3-8译码器译码器 3-8译码器有三个输入，八个输出，其逻辑电路图译码器有三个输入，八个输出，其逻辑电路图 为为 6 Z 3-83-8 译译 码码 器器 0 S 1 S 2 S 5 Z 4 Z 7 Z 3 Z 2 Z 1 Z 0 Z 37 1 0 0 0 0 0 0 01 1 1 b6错错 0 1 0 0 0 0 0 01 1 0 b5错错 0 0 1 0 0 0 0 01 0 1 b4错错 0 0 0 1 0 0 0 01 0 0 b2错

26、错 0 0 0 0 1 0 0 00 1 1 b3错错 0 0 0 0 0 1 0 00 1 0 b1错错 0 0 0 0 0 0 1 00 0 1 b0错错 0 0 0 0 0 0 0 10 0 0无错无错 z7z6z5z4z3z2z1z0S2 S1 S0 说明说明 2、根据、根据3-8译码器的工作原理，得其真值表为：译码器的工作原理，得其真值表为： 38 2. 进一步得译码电路为（只需校正信息码进一步得译码电路为（只需校正信息码b3b4b5b6） 6 b 5 b 4 b 3 b 2 b 1 b 0 b 6 Z 3-83-8 译译 码码 器器 0 S 1 S 2 S 5 Z 4 Z 7 Z

27、3 Z 2 Z 1 Z 0 Z 或或 门门 出错出错 指示指示 6 b 5 b 4 b 3 b 纠错电路纠错电路 异或运算异或运算 39 9.4 循环码循环码 循环码的循环特性：循环码的循环特性： （1）是线性码。）是线性码。 （2）具有循环性。即码组中的任一码字循环）具有循环性。即码组中的任一码字循环 移位所得码字仍是该码组中的一个码字。移位所得码字仍是该码组中的一个码字。 （3）封闭性。对任意二个码字的（异或）运）封闭性。对任意二个码字的（异或）运 算所得码字仍属于该码组中的一个码字。算所得码字仍属于该码组中的一个码字。 （4）(n,k)循环码的码字可用多项式表示：循环码的码字可用多项式表

28、示： 1)(: )( :4 )( 46 5 236 4 01 2 2 1 1 xxxxA xxxxxA axaxaxaxA n n n n 同理有 的码多项式可表为如右表中码字 信息码信息码 监督码监督码 a6a5a4 a3a2a1a0 000 0000 001 1101 010 0111 011 1010 100 1110 101 0011 110 1001 111 0100 (7,3) 码码 0 1 2 3 4 5 6 7 循环码码字循环码码字序号序号 40 本节的主要内容：本节的主要内容： 一、在线性分组码中，我们求出了生成矩阵一、在线性分组码中，我们求出了生成矩阵 G 和监督矩阵和监督

29、矩阵 H。同样，我们在这里首。同样，我们在这里首 先求循环码的生成矩阵先求循环码的生成矩阵 G和监督矩阵和监督矩阵 H 二、循环码的编码规则与编码方法二、循环码的编码规则与编码方法 三、循环码的编码电路三、循环码的编码电路 四、循环码的译码以及译码电路的组成四、循环码的译码以及译码电路的组成 41 .)(,)( :)(. 1 )()(1 . 4 . 9 为该码的生成多项式则称的倍式 项式都是某个多项式若一种码的所有码字多 的定义生成多项式 及生成矩阵生成多项式 xgxg xg xGxg 由此可见，生成多项式对于循环码来说十分重要！由此可见，生成多项式对于循环码来说十分重要！ 42 的一个因式生

30、成多项式是 督码元位数 为监为信息码的位数码长为 次多项式的是常数项为生成多项式 多项式就是生成多项式 次数最低的码外除全在循环码组中可以证明 的获取及性质生成多项式 1)3( ,: ),( 1)()2( )( ,0,) 1 ( )(. 2 n x rkrknkn rxg xg xg （非常重要！（非常重要！ ） 43 10) 1 , 2, 1()( 1)( )( )( )( )( )( : )(. 3 1 2 2 1 1 2 1 或的取值为中的各个系数 其中 形式来表示 可用多项式的循环码的生成矩阵 rrigxg xgxgxgxxg xg xxg xgx xgx xG xG i r r r

31、r r k k 44 标准生成矩阵 其生成多项式为 循环码对于前述的例如 变成标准阵 经初等变换 101 1 001 0111 010 1101 100 101 1 001 010 1 011 100 0 111 1 )( )( )( )( 1)( : ,) 3 , 7(, 234 345 2456 2 234 G xxx xxxx xxxx xg xxg xgx xG xxxxg 信息码信息码 监督码监督码 a6a5a4 a3a2a1a0 000 0000 001 1101 010 0111 011 1010 100 1110 101 0011 110 1001 111 0100 (7,3)

32、 码码 0 1 2 3 4 5 6 7 循环码码字循环码码字序号序号 k-1, k=3 45 46 【例题】 设（7,3）循环码的生成多项式为 1)( 24 xxxxg，试根据（9-25）式列出所有的许 用码字。 解 首先应得出标准生成矩阵： 0111 001 1110 010 1011 100 0111 001 1110 010 1100 101 1 )( )( )( )( 24 235 2346 2 GG xxx xxxx xxxx xg xxg xgx xG 标准生成矩阵 47 其次，根据（9-25）式，得 0000000 0111 001 1110 010 1011 100 000 0

33、 T 0010111 0111 001 1110 010 1011 100 001 1 T 0101110 0111 001 1110 010 1011 100 010 2 T 0111001 0111 001 1110 010 1011 100 011 3 T 1001011 0111 001 1110 010 1011 100 100 4 T 1011100 0111 001 1110 010 1011 100 101 5 T 1100101 0111 001 1110 010 1011 100 110 6 T 1110010 0111 001 1110 010 1011 100 111

34、7 T 最后得表 9-5 所示的（7,3）循环码的所有许用码字表。 48 1)( 24 xxxxg产生循环码对应的许用码字表 序号 循环码码字 （7,3）码 信息码 监督码 456 aaa 0123 aaaa 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 49 11)( 11 )( 1 )( 1)(,)3 , 7( , )(,)(),(, 1)( )()(. 2 1 1 )( 1 )(

35、)(. 1 )()()( 2 . 4 . 9 3 2 2 1 3*1, 0 1 2 2 323 7 234 * 1 2 2 1 1 * * 1 2 2 1 1 * 21 xxxhxhxxh xhxhxxx xg x xh xxxxg xhxhxh xhxhxhxxh xhxh k xhxhxhx xg x xh xh xHxhxh hh k kkk k k k k k n 已知循环码例如 就可求出的系数利用只要求出了因此 的逆多项式 次多项式的它是常数项为 的定义监督多项式 以及监督矩阵及逆多项式监督多项式 系数对称交换法系数对称交换法 g(x)的最高次为的最高次为r 50 )( 000101

36、1 0010110 0101100 1011000 1)( )( )( )( )( )()3 , 7(, )( )( )( )( )()3( 3 24 235 346 * * *2 *3 * * *1 监督矩阵 为循环码的可求得根据的上面的结果例如 监督矩阵 H xx xxx xxx xxx xh xxh xhx xhx xH xH xh xxh xhx xH xH kn 51H GGH PQQPGHQIG G IPH H TT 求或由求可由况是一致的这与线性分组码中的情 或的关系为和进一步得 标准生成矩阵 由前面推导的结果 标准监督矩阵 变成标准阵 经初等变换 变成标准阵 经初等变换 , :

37、,| 101 1 001 0111 010 1101 100 101 1 001 010 1 011 100 0 111 | 0001 011 0010 110 0100 111 1000 101 1011 000 0110 001 1100 010 1000 101 （4）循环码中监督矩阵）循环码中监督矩阵H与生成矩阵与生成矩阵G关系关系 52 .,) 1 , 2, 1( 0 1 ) 1 , 2, 1( :,)( 1)( . 1 3 . 4 . 9 1 2 2 1 1 为异或电路为位移寄存器 开关断开 开关接通 图中除法电路如下图对输入作除法运算用生成多项式 设生成多项式为 除法电路的一般形

38、式 编码方法与编码电路 rriD rrig xg xgxgxgxxg i i r r r r r 1r g 0 D 输入 输出 1 D 2 D 2r D 1r D 2r g 3 g 2 g 1 g1 0 g 1 r g 它是内环式，并解释其构成规律。它是内环式，并解释其构成规律。 53 :, 1)(: ,: : : )(: 234 0 电路为对输入信号作除法运算例如 最低位存于存于寄存器单元余数 商输出输出 被除数的输入输入 即为除数 各个部分的功能 xxxxg DD xg i 0 D 输入输入 输出输出 1 D 2 D 3 D 54 : 1)(: 24 的电路为对输入信号作除法运算 再如xx

39、xxg 0 D 输入输入 输出输出 1 D 2 D 3 D 55 )()()()()( : ,)4( )()()()(: )()(),()()3( )(),)()2( . 1 ),(,) 1 ( )7(, ,)3 , 7( :. 2 4, 0123 3, 456 xRxmxxQxgxA xRxQxgxmx xRxQxmxxg xmxrxmx k xm rknaaaaaaaA r r r rr rk 码多项式为故最后可求得循环码的 的倍式循环码都是生成多项式前面提及 即 和余式得商式除用 得位相当于左移乘用 其最高次数为 可求得其码多项式根据给定的信息码 设码字为循环码为例以 除法电路为其核心电

40、路循环码的编码规则 监督码信息码 56 . ,),()( ),0(, ),()(,)( ,)(,)6( . ,)()(,)5( 错的位进行纠错 出最后利用余数的特征对表明有错 则表明余数不为若不能除尽表明没有出错 则若能除尽除收到的码字同的 首先用与发送端相后在收到码字在接收端 则这就是循环码的编码规 除尽能够被循环码的码多项式很显然 xBxA xBxAxg xB xgxA 57 0 D 1 D 2 D 3 D 输入信息码 输出码字 1 K 2 K 1 2 . )()()()()(, ) 3( .,.0 , ,2,)2( .4 , ,1)1 ( 21 21 编码的循环码是按编码规则由上述分析知

41、 息码才能重新输入下一个信部输出完后注意要等到四位余数全全部为 寄存器的状态也后当四位余数全部输出完完成循环码编码息码的后面接着输出 寄存器中余数跟在信断开接位置此时除法运算也已完成码输入完成后 个移位寄存器中余数保存在码作除法运算 除法电路对输入信息另一方面将信息码直接输出一方面接通时接位置 xRxmxxQxgxA KK KK r 3.编码电路的组成与工作原理编码电路的组成与工作原理 58 编码电路工作原理分析编码电路工作原理分析 根据（9-34）式，若输入信息码 456 aaam ，用生成多项式 1)( 24 xxxxg除)( 4 xmx ，得余多项式)(/ )()( 4 xgxmxxR，

42、余 数R与信息码m的对应关系如表 9-6 所示。 表 9-6 输入信息码m与余数R的对应关系 456 aaam 0123 aaaaR 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 59 根据图 9-10 所示的电路， 设寄存器 3333 DDDD对应的当前 状态为 nnnn QQQQ 1234 ，次态为 1 1 1 2 1 3 1 4 nnnn QQQQ，则它们之间 满足如下状态方程 mQQ mQQQ mQQQ QQ

43、nn nnn nnn nn 4 1 1 14 1 2 24 1 3 3 1 4 由上式， 进一步得寄存器中的余数与输入信息码之间的逻辑关 系如表 9-7 所示。由此可知，表 9-6 与表 9-7 的结果是一致的。 60 表 9-7 寄存器中的余数与输入信息码之间的逻辑关系 nnnn QQQQm 1234 1 1 1 2 1 3 1 4 nnnn QQQQ 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 a 5 a 4 a 3 a 2 a 1 a 0 a nnnn QQQQm 1234 1 1 1 2 1 3 1 4 nnnn QQQ

44、Q 1 0 0 0 00 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 6 a 5 a 4 a 3 a 2 a 1 a 0 a nnnn QQQQm 1234 1 1 1 2 1 3 1 4 nnnn QQQQ 0 0 0 0 00 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 6 a 5 a 4 a 3 a 2 a 1 a 0 a nnnn QQQQm 1234 1 1 1 2 1 3 1 4 nnnn QQQQ 1 0 0 0 00 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 0 6 a 5 a 4 a 3 a 2 a 1 a 0 a nnnn QQQQm 1234 1 1 1 2 1 3 1 4 nnnn QQQQ 1 0 0 0 00 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 6 a 5 a 4 a 3 a 2 a 1 a 0 a nnnn QQQQm 1234 1 1 1 2 1 3 1 4 nnnn QQQQ 1 0 0 0 00 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 6 a 5 a 4 a 3 a 2 a 1 a