《计算机组成与结构》
——本科生课程教学计算机学院计算机学院
(
(
XBXU)
XBXU)
计算机学院(XBXU)
计算机组成与结构计算机组成与结构
?本课程主要讲授计算机系统的硬件和软件构成方法，包括硬件系统中运算器、控制器、存储器、输入设备和输出设备和总线系统的构成原理等；并与当代先进的计算机技术相结合。是计算机科学与技术本科专业核心课程。
?本课程着重计算机系统组成与结构方面的教学和研究。
?计算机结构定义为系统程序员所能见到的计算机硬件特性；
?计算机组成是指计算机硬件的具体实现。
计算机学院(XBXU)
第三章第三章运算方法和运算部件运算方法和运算部件
?数据的表示方法和转换
?带符号数的表示方法及加减运算
?二进制乘法运算
?二进制除法运算
?浮点数的运算方法
?运算部件
?数据校验码计算机学院(XBXU)
3.6
3.6
运算部件运算部件一、运算部件
?书P95，图3.9所示是一个能实现定点加、减、乘、除运算的运算部件。
? 1．在进行加法运算时，应送来A→ALU、B→ALU、ALU→S、
S→A信号(高电位)，另外还应向ALU发出加法运算命令(图中未画出)。
? 2．在进行减法运算时，应送来A→ALU、→ALU、＋1、
ALU→S、S→A信号(高电位)，同样还应向ALU发出减法运算命令。
? 3．乘法运算的实现见前面的流程图。
? 4．除法运算的实现见前面的流程图。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件二、运算部件AM2901A
1、AM2901A逻辑结构及原理图计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?基本组成部件有：
?八功能的ALU：完成算术与逻辑运算；
? 16×4位寄存器组：寄存加减运算的操作数；
? 4位Q寄存器：用于接收ALU的输出数据，具有左、右移功能；
? 3选1和2选1多路开关：用于多路地址、数据的选择。
?下图是AM2901A的逻辑原理图。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件计算机学院(XBXU)
3.6
3.6
运算部件运算部件
2、AM2901A主要特点
?位片式结构，即每片内仅有四位线路，要实现不同位数的运算器，需将几片同样的器件串接起来使用。例如用四片可实现—个16位字长的运算器。
?该运算器的ALU能实现八种运算功能，它每一位上的两个输入端数据分别用R和S表示，则这八种功能是：
三种算术运算功能：
五种逻辑运算功能：
SRRSSR+和,
SRSRSRSRSR ⊕⊕∧∧∨和,,,
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?这八种功能的选择控制，是用外部送入的三位编码值I
5
I
4
I
3
实现的，其具体规定如下表所示。
ALU的功能选择ALU的输入选择计算机学院(XBXU)
3.6
3.6
运算部件运算部件
? ALU的R输入端可以接收外部送入运算器的数据D,寄存器组的—组输出A，或接收逻辑0值。ALU的S输入端可以接收寄存器组的一组输出A和另—组输出B，还可以接收Q寄存器的输出。这样,R和S接收的数据可以有如下12种组合情况：
? R 0000 AAAA DDDD
? S ABQ0 ABQ0 ABQ0
?考虑到R和S同时接收0无实用价值，OA与AO组合、AA和
AB组合、DA和DB组合可以相互替代,故只需留下八种组合情况即可、此时可用外部送来的三位控制码来决定ALU的输入数据，即区分可用的八种组合。对应关系如上表所示。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?运算器中有1个16X4位的通用寄存器组和一个4位的Q寄存器。寄存器组被设计成能双端口输出的部件。每一个寄存器都可以用A地址或B地址选择，将寄存器中的内容分别送到输出端口A或B)。当A和B地址不同时，在输出端口A和B
将得到两个不同寄存器中的内容。该寄存器组的写入控制
，只能用B地址实现，写入的数据是ALU的输出经过移位器送到寄存器组的输入端的。移位器可执行直送、左移一位操作，或右移一位的操作，使加减运算和移位操作可在同一个操作步骤中完成。
? Q寄存器本身具有移位功能，即它可以接收自己左移一位或右移一位的值。Q寄存器还可以接收ALU的输出F的值。Q
的输出可在经ALU的S输入端送入ALU。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
? ALU还给出了Cn+4、F3(可用作符号位)、OVR和F=0000四个状态信息，它们分别是本四位运算器产生的向更高位的进位、本片最高位的取值、结果溢出和结果为零的状态。
ALU的最低位还接收从更低位片送来的进位信号Cn，ALU
还给出了超前进位信号G和P。
?移位器还有接收与送出移位数值的引线，它们分别是RAM3
、RAM0、Q3和Q0，它们都是用三态门给出的具有双向传送功能的线路实现的。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?运算器的四位输出为Y
3
一Y
0
，它可以是ALU的运算结果，
也可以是寄存器组A输出端口上的内容。这里用的是三态门电路，仅当OE#信号为低电平时，y的值才是可用的，否则
Y输出处于高阻状态。
?控制数据传送的方式(移不移位)和数据发送的去向，是用另外三位编码(I
8
I
7
I
6
)来控制的，具体规定如下表所示。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件数据传输控制计算机学院(XBXU)
3.6
3.6
运算部件运算部件
3、16位字长定点运算器
?可以用四片Am2901A组成一个16位字长的定点运算器，其连接关系如下图所示。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件线路工作原理：
?每片器件上的Q
0
和Q
3
端，RAM
0
与RAM
3
端都能用于输入和输出
，因此，它们用三态门电路实现，在ALU的移位控制信号(
由数据传送控制的三位编码I
8
I
7
I
6
给出)控制下，把高位片的Q
0
、RAM
0
输出信号送入低位邻片的Q
3
、RAM
3
输入端，或把低位片的Q
3
、RAM
3
输出信号送入高位片的Q
0
、RAM
0
输入端。
?四片的数据输入端D
3
-D
0
一起作为16位运算器的16个数据输入端D
15
～D
0
，四片的数据输出端Y
3
-Y
0
一起作为16位运算器的16个数据输出端Y
15
-Y
0
。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?四片的三组输入信号I
2
I
1
-I
0
，I
5
I
4
I
3
，I
8
I
7
I
6
，分别用外部送来的三组信号提供给每—片,使四片总使用相同的控制信号
，保证它们的并行工作关系(片间有串行数据信号传送)。
?通用寄存器组RAM的两个地址控制端“A”(读)和“B”(读／写
)、Q寄存器移位用的CP时钟脉冲信号，分别送入每—片
Am2901A的“A”、“B”和CP输入端。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件指令控制过程：
?下述几条指令在运算器部件中的控制方法：
? (1)把主存数据寄存器中读得的数据写入通用寄存器组中的某个寄存器中；
? (2)把通用寄存器组中某个寄存器的内容写进主存数据寄存器中；
? (3)通用寄存器组中的两个寄存器的内容相加。结果写回其中的一个寄存器中。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?按Am2901A的功能规定，可以给出如下表所示的一张信号分配表。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?第一条指令，把主存数据寄存器的输出接到Am2901A的D
输入端：
?用I
2
I
1
I
0
＝111作为ALU的输入数据选择(D，0组合)，
?用I
5
I
4
I
3
＝000作为ALU的功能选择(加，即实现D十0)，
?用I
8
I
7
I
6
＝011作为ALU的数据传送控制，即把ALU的输出送到通用寄存器组的输入，再写入由“B”地址选择的寄存器中
。在此操作过程中，最低位进位输入值给0。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?第二条指令，把通用寄存器中的内容写入主存数据寄存器中：
?用I
2
I
1
I
0
＝011作为ALU的输入选择(0，B组合)，
?用I
5
I
4
I
3
＝000作为ALU的功能选择(加，即实现0+B号寄存器的内容)，
?用I
8
I
7
I
6
＝001作为Am2901A的输出选择并同时给出面信号
，Y输出即为B寄存器的内容，可以把Y接到主存数据寄存器的输入端，从而完成向该寄存器的写入操作。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?第三条指令，把A寄存器的内容加上B寄存器的内容，结果写入B寄存器中：
?用I
2
I
1
I
0
＝001作为ALU的输入数据选择，
?用I
5
I
4
I
3
＝000作为ALU的功能选择，
?用I
8
I
7
I
6
＝010作为ALU的数据传送选择，从而完成A寄存器的内容加B寄存器的内容，并把结果写入B寄存器中的操作过程。此时要使OE#取高电平，使输出Y处于高阻状态，而不是输出A寄存器的内容。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?这三条指令的运行结果，应按某种规定设置运算器的状态标志触发器C、y、Z、N，这些触发器要在Am2901A芯片之外实现，将Am2901A的最高位芯片的输出Cn+4、OVR、F
＝0000和F3的值写入这四个标志触发器中。图上省略了这一部分逻辑电路。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?码距是根据任意两个合法码之间至少有几个二进制位不相同而确定的，仅有一位不同，称其码距为1。例如，用四位二进制表示16种状态，则16种编码都用到了，此时码距为1
，就是说，任何一个状态的四位码中的一位或几位出错，
就变成另一个合法码，此时无查错能力。若用四个二进制位表示8个状态，就可以只用其中的8种编码，而把另8种编码作为非法编码，此时码距为2。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码一、奇偶校验码
?奇偶校验码的原理是在每组代码中增加一个冗余位，使合法编码的最小码距由1增加到2。
1、校验码的构成规则
?偶校验：每个码字(包括校验位)中1的数目为偶数。
?奇校验：每个码字(包括校验位)中1的数目为奇数。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
2、校验位的形成
?设有效信息位为：
?偶校验，在发送端求校验位：
?奇校验，在发送端求校验位：
01234567
DDDDDDDD
01234567
DDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕=
01234567
DDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕=
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(3) 校验原理
?偶校验在接收端求：
?奇校验在接收端求：
?若P’=0，则无错；P’=1，则有错。
?校验电路参见P96图3.10。
PDDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕⊕=
01234567
'
PDDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕⊕=
01234567
'
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
4、局限性
?奇偶校验码能发现数据代码中奇数个位出错情况，并且不能纠正错误，常用于对存储器数据的检查或者传输数据的检查。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码二、海明校验码
?海明校验的基本思想是将有效信息按某种规律分成若干组
，每组安排一个校验位进行奇偶测试。在一个数据位组中加入几个校验位，增加数据代码间的码距，当某一位发生变化时会引起校验结果发生变化，不同代码位上的错误会得出不同的校验结果。因此，海明码能检测出2位错误,并能纠正1位错误。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(1)求海明校验码的步骤。
?①确定海明校验位的位数设K为有效信息的位数，设r为校验位的位数，则整个码字的位数N应满足不等式：
N=K＋r≤2
r
－1
若要求海明码能检测出2位错误，则再增加一位校验位。
?②确定校验位的位置：位号(1～N)为2的权值的那些位，
即：2
0
、2
1
、2
2
、…2
r－1
的位置作为校验位，记作P
1
、P
2
、… P
r
，余下的为有效信息位。
?③分组:将N位分r组，第i位由校验位号之和等于i的那些校验位所校验。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?④校验位的形成
P
1
=第一组中的所有位(除P1外)求异或
P
2
=第二组中的所有位(除P2外)求异或
P
r
=第r组中的所有位(除Pr外)求异或
?为了能检测两个错误，增加一位校验P
r＋1
，放在最高位。
P
r＋1
= 所有位(包括P
1
、P
2
、… P
r
)共N位求异或计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(2)校验原理：在接收端分别求S
1
、S
2
、S
3
、…S
r
S
1
=第一组中的所有位(包括P
1
)求异或
S
2
=第二组中的所有位(包括P
2
)求异或
S
r
=第r组中的所有位(包括P
r
)求异或
S
r＋1
= P
r＋1
⊕所有位(包括P
1
、P
2
、… P
r
)求异或
?当S
r＋1
=1时有一位错：由S
r
…S
3
S
2
S
1
的二进制编码指出出错位号,将其取反，即可纠错。
?当S
r＋1
=0时无错或有偶数个错(两个错的可能性比较大),当
S
r
…S
3
S
2
S
1
=0…000时，接收的数无错，否则有两个错。
?根据此原理，能画出指出两个错误并能纠正一位出错位的海明校验逻辑电路。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例求信息码01101110的海明校验码，画出能指出和纠正一位出错位的海明校验逻辑电路。
【例题分析】
?①确定海明校验位的位数
?设R为校验位的位数，则整个码字的位数应满足不等式：
N=K＋R≤2
R
－1
?设R=3，则2
3
－1=7，N=8＋3=11，不等式不满足；
?设R=4，则2
4
－1=15，N=8＋3=12，不等式满足。所以R最小取4。
?②确定校验位的位置：位号(1～12)为2的权值的那些位，
即：2
0
、2
1
、2
2
、2
3
的位置作为校验位，记作P1、P2、P3
、P4，余下的为有效信息位。即：
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? 12 11 10 9 8 7 6 5 4 3 2 1
? D
7
D
6
D
5
D
4
P4 D
3
D
2
D
1
P3 D
0
P2 P1
?
?③分组：有4个校验位，将12位分4组，第i位由校验位号之和等于i的那些校验位所校验。
?如：第11位D
6
由P1(位号为1)、P2(位号为2)、P4(位号为8)
所校验，因为1＋2＋8=11。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?④校验位的形成
P1=第一组中的所有位(除P1外)求异或=
D
6
⊕D
4
⊕D
3
⊕D
1
⊕D
0
=1⊕0⊕1⊕1⊕0=1
P2=第二组中的所有位(除P2外)求异或=
D
6
⊕D
5
⊕D
3
⊕D
2
⊕D
0
= 1⊕1⊕1⊕1⊕0=0
P3=第三组中的所有位(除P3外)求异或= D
7
⊕D
3
⊕D
2
⊕D
1
=
0⊕1⊕1⊕1=1
P4=第四组中的所有位(除P4外)求异或= D
7
⊕D
6
⊕D
5
⊕D
4
=
0⊕1⊕1⊕0=0
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?为了能检测两个错误，增加一位校验P5，放在最高位。
P5 = D
7
⊕D
6
⊕D
5
⊕D
4
⊕D
3
⊕D
2
⊕0 D
1
⊕D
0
⊕P1⊕P2⊕P3⊕P4
= 0⊕1⊕1⊕0⊕1⊕1⊕1⊕0⊕1⊕0⊕1⊕0 = 1
?【例题答案】信息码01101110的海明校验码为：1 0110
1 111 0 0 10。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (2)校验原理在接收端分别求S
1
、S
2
、S
3
、S
4
、S
5
。
S
1
= P1⊕D
6
⊕D
4
⊕D
3
⊕D
1
⊕D
0
S
2
= P2⊕D
6
⊕D
5
⊕D
3
⊕D
2
⊕D
0
S
3
= P3⊕D
7
⊕D
3
⊕D
2
⊕D
1
S
4
= P4⊕D
7
⊕D
6
⊕D
5
⊕D
4
S
5
= P5⊕D
7
⊕D
6
⊕D
5
⊕D
4
⊕D
3
⊕D
2
⊕0
D
1
⊕D
0
⊕P1⊕P2⊕P3⊕P4
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?当S
5
=1时有一位错：由S
4
S
3
S
2
S
1
的二进制编码指出出错位号。例如S
4
S
3
S
2
S
1
=1001 说明第9位出错，将其取反，即可纠错。
?当S
5
=0时无错或有偶数个错(两个错的可能性比较大)：当
S
4
S
3
S
2
S
1
=0000时，接收的数无错，否则有两个错。
?【例题答案】能指出两个错误并能纠正一位出错位的海明校验逻辑电路如图所示。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
D
7
D
6
D
5
D
4
D
3
D
2
D
1
D
0
无错
一位错
两位错
=1 =1 =1 =1 =1 =1 =1 =1
H
12
H
11
H
10
H
9
H
7
H
6
H
5
H
3
1100 1011 1010 1001 0111 0110 0101 0011 0000
4
：
16
译
码
器
(
设译码器高电平有效
)
S
4
S
3
S
2
S
1
S
5
奇偶形成线路
奇偶形成线路
奇偶形成线路
奇偶形成线路
奇偶形成线路
H
12
H
11
H
10
H
9
H
8
H
12
H
7
H
6
H
5
H
4
H
11
H
10
H
7
H
6
H
3
H
2
H
11
H
9
H
7
H
5
H
3
H
1
所有位
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例：有一个（7，4）码，写出代码0011的海明效验码，画出效验电路
?解答：
(1)求信息码001的海明效验码。
①确定海明效验位的位数因为是（7，4）码，所以N=7，K=4，效验位的位数为3。
②确定效验位的位置：位号（1∽7）为2的权值的那些位，
即：2
0
、2
1
、2
2
的位置作为效验位，即：
1 2 3 4 5 6 7
P1 P2 D
3
P3 D
2
D
1
D
0
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
②
H
7
H
6
H
5
H
4
H
3
H
2
H
1
D
3
D
2
D
1
P3 D
0
P2 P1
第一组（P1） √ √ √ √
第二组（P2） √ √ √ √
第三组（P3） √ √ √ √
0 0 1 1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?④效验位的形成
P1= D
3
⊕D
1
⊕D
0
= 0⊕1⊕1=0
P2= D
3
⊕D
2
⊕D
0
= 0⊕0⊕1=1
P3= D
3
⊕D
2
⊕D
1
= 0⊕0⊕1=1
?所以：信息码0011的海明效验码为：001 1 1 10。
(2)海明效验逻辑电路如图所示。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
D3 D2 D1 D0 =1无错
=0有错
H
7
H
6
H
5
H
3
0011 0101 0110 0111 0000
3：8 译 码 器 （设译码器高电平有效）
S3 S2 S1
奇偶形成线路 奇偶形成线路 奇偶形成线路
H
7
H
6
H
5
H
4
H
7
H
6
H
3
H
2
H
7
H
5
H
3
H
1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码三、循环冗余校验(CRC)码
?二进制信息沿一条线逐位在部件之间或计算机之间传送称为串行传送。CRC(Cyclic Redundancy Check)码可以发现并纠正信息存储或传送过程中连续出现的多位错误。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(1)CRC码的编码
?①模2运算模2运算是指以按位模2相加为基础的四则运算，运算时不考虑进位和借位。
?模2加减：即按位加，可用异或逻辑实现。模2加与模2减的结果相同，即0±0＝0，0±1＝1，1±0＝1，1±1＝0。
?模2乘:按模2加求部分积之和。
?模2除:按模2减求部分余数。上商的原则是：当部分余数的首位为1时，商取l；当部分余数的首位为0时，商取0。当部分的余数的位数小于除数的位数时，该余数即为最后余数
。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?②CRC码的编码方法
CRC码是用多项式M(x)·x
r
除以称为生成多项式的G(x)(产生校验码的多项式)所得余数作为校验位。为了得到r位余数(
校验位)，G(x)必须是r＋1位。
设所得余数表达示为R(x)，商为Q(x)。将余数拼接在信息位左移r位后空出的r位上，就构成这个有效信息的CRC码。这个CRC码可用多项式表示为：
M(x)·x
r
＋R(x)＝[Q(x)·G(x)＋R(x)]＋R(x)
＝[Q(x)·G(x)]＋[R(x)＋R(x)]
＝Q(x)·G(x)
?因此所得CRC码可被G(x)表示的数码除尽。
?将编好的循环校验码称为(n，k)码。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?③CRC码的编码电路
?若G(x)=x
r
＋g
r –1
x
r –1
＋…＋g
2
x
2＋
g
1
x
1
＋1,g
i
∈{0，
1},i∈{r－1，…，2，1},则CRC码的编码电路如下图所示：
k
m
R
g
1
g
2
g
r
－
1
R
0
⊕
R
1
⊕
⊕
R
r
－
1
⊕
信息输入端
(高位在前，低位在后) 码字输出端
k
k
r
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?当g
i
=1时，开关g
i
闭合，当g
i
=0时，开关g
i
断开。开始发送数据时，开关k置于k
m
位置，开关R同时闭合，信息位由输入端从高到低串行输入，一边从码字输出端输出，一边进入编码电路循环运算。当信息发送完毕时，寄存器R
0
，R
1
，…，R
r－1
中的内容即为冗余位的值。此时，开关R断开，
开关k置于k
r
位置，冗余位就紧接在信息位的后面输出。至此发送方编码发送完毕。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例在CRC校验中，已知生成多项式G(x)＝x
4
＋x
3
＋1。要求：①计算信息序列1101101的校验序列。
②画出该G(x)的编码电路。
?分析：
?①对应生成多项式G(x)的二进制序列为：11001
在有效信息后面添4个0。然后用它和G(x)进行模2除法运算，所得的余数即为所求的校验位。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
运算过程如下,
１0 0 1 1 0 1
1１0 0１ １１0 1 1 0 1 0 0 0 0
1１0 0１
1 0 0 1 0
1１0 0１
1 0１１0
1 1 0 0 1
1 1 1 1 0
1 1 0 0 1
1 1 1 0 0
1 1 0 0 1
1 0 1
余数为0101，所求的CRC校验码为：1101101 0101
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?②G(x)= 11001,则CRC码的编码电路如下图所示。
?开始发送数据时，开关k置于k
m
位置，开关R同时闭合，信息位由输入端从高到低串行输入，一边从码字输出端输出
，一边进入编码电路循环运算。当信息发送完毕时，寄存器R
0
，R
1
，R
2
，R
3
中的内容即为冗余位的值。此时，开关
R断开，开关k置于k
r
位置，冗余位就紧接在信息位的后面输出。至此发送方编码发送完毕。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
k
m
0 1 1
R
0
R
1
R
2 ⊕
R
3
⊕
码字输出端
信息输入端
(
高位在前，低位在后
)
k
k
r
R
1 0
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?在实际工作中,接收方一边接收信息，一边利用译码电路进行差错检测。
?若G(x)=x
r
＋g
r –1
x
r –1
＋…＋g
2
x
2＋
g
1
x
1
＋1,g
i
∈{0，1},i∈{r
－1，…，2，1},则译码电路如图2,2所示，当g
i
=1时，开关g
i
闭合，当g
i
=0时，开关g
i
断开。接收方将收到的码字信息逐位送入译码电路计算余数，在码字信息全部进入译码电路后，寄存器R
0
，R
1
，…，R
r－1
中就寄存了余数E(x)。
将余数各位进行或运算。得错误特征位E。若E＝0，则接收正确，将码字中的最末r位去掉，得到原发数据；若E=l，则表示收到的码字有错。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (2) CRC的译码与纠错
?在CRC校验中，发送方已知信息序列M(x)和生成多项式
G(x)，发送方便可利用编码电路形成传输序列T(x)进行发送
。T(x)经信道传输后到达接收方，接收方收到信息T’(x),若
T’(x)＝T(x)，则传输无错，否则就是出错。接收方只是已知G(x)和收到的T’(x),但不知道发送方发送的T(x)。判断
T’(x)是否有错的方法为：将收到的循环校验码用约定的生成多项式G(x)去除，如果码字无误则余数应为0，如有某一位出错，则余数不为0，不同位数出错余数不同。更换不同的待测码字可以证明：余数与出错位的对应关系是不变的
，只与码制和生成多项式有关。对于其他码制或选用其他生成多项式，出错模式将发生变化。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
g1 g2 gr
－
1
R
0 ⊕
R1 ⊕ ⊕ R r
－
1 ⊕
接收码字输入端
≥
1
错误特征位
图
2.2 CRC
的译码电路
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例，求有效信息1010、0111的CRC校验码，并求循环余数，
说明校验原理,画出译码与纠错电路。
?分析：
(1)求有效信息1010的CRC校验码
?①确定校验位的位数设R为校验位的位数，则整个码字的位数应满足不等式：
N=K＋R≤2
R
－1
设R=3，则2
3
－1=7，N=4＋3=7，不等式满足。所以R最小取3。
?②选一个R＋1位的生成多项式G(x),如G(x)=1011
?③在有效信息后面添R个0。然后用它和G(x)进行模2除法运算，所得的余数即为所求的校验位。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
运算过程如下,
１００１
１０１１ １０１００００
１０１１
１０００
１０１１
１１
余数为０１１，所以，所求的CRC校验码为：１０１００１１
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
④求循环余数：在上面１１余数的基础上添０继续进行模２除,如下,
１０１１ １１ 第一个余数
１１０ 第二个余数
１１００ 余数循环次序如下：
１０１１
１１１ 第三个余数
０１１
１１０ １１１
１１１０
１０１１
１０１
１０１ 第四个余数
１０１０
１００
０１０
００１
１０１１
１ 第五个余数
１０ 第六个余数
１００ 第七个余数
１０００
１０１１
１１ 第一个余数
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(2)
求有效信息
0111
的
CRC
校验码
运算过程如下：
１１０
１０１１
０１１１０００
１０１１
１０１０
１０１１
１０
余数为０１０，所以，所求的
CRC
校验码为：１１０１０１０
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码求循环余数：在上面１余数的基础上添０继续进行模２除,如下,
１０１１ １０ 第一个余数
１００ 第二个余数 余数循环次序如下：
１０００
１０１１ ０１１ １１０ １１１
１１ 第三个余数
１１０ 第四个余数 １０１
１１００
１０１１ １００
０１０ ００１
１１１ 第五个余数
１１１０
１０１１
１０１ 第六个余数
１０１０
１０１１
１ 第七个余数
１０ 第一个余数
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (3)校验原理
?从以上(1)、(2)的余数循环次序来看，其余数是相同的，
实际上只要是4位有效数，他们的余数均相同，而且出错模式也是相同的。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
G (x)=1011
时的
1010(7
，
4)
循环码的出错模式
D1 D2 D3 D4 D5 D6 D7
余 数 出错位
正确
1 0 1 0 0 1 1 0 0 0
无
错误
1
1
1
1
1
1
0
0
0
0
0
0
1
0
1
1
1
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
1
1
7
6
5
4
3
2
1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
G (x)=1011
时的
0111(7
，
4)
循环码的出错模式
D1 D2 D3 D4 D5 D6 D7
余 数 出错位
正确
0 1 1 1 0 1 0 0 0 0
无
错误
1
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
1
1
7
6
5
4
3
2
1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (4)译码与纠错电路
?校验的原理是根据余数来判断出错位，取反即可纠错,译码与纠错电路如下。接收方将收到的码字信息逐位送入译码电路计算余数，在码字信息全部进入译码电路后，寄存器R
0
，R
1
，R
2
中就寄存了余数。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?余数=0译码器的0输出端为高，表示无错；
?余数=1译码器的1输出端为高，表示有效信息D
1
错，取反即可纠错；
?余数=2译码器的2输出端为高，表示有效信息D
2
错，取反即可纠错；
?余数=4译码器的4输出端为高，表示有效信息D
3
错，取反即可纠错；
?余数=3译码器的3输出端为高，表示有效信息D
4
错，取反即可纠错；
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
R
R
0 ⊕
R
2
R
3 ⊕
接收码字输入端
3
：
8
译
码
器
(
设译码器高电平有效
)
000 001 010 100 011
D
1
’
D
2
’
D
3
’
D
4
’
⊕
⊕
⊕
⊕
=1
有错
D
1
D
2
D
3
D
4
=0
无错
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (3)关于生成多项式并不是任何一个(r＋1)位多项式都可以作为生成多项式的。从检错及纠错的要求出发，生成多项式应能满足下列要求：
?①任何一位发生错误都应使余数不为0。
?②不同位发生错误应当使余数不同。
?③对余数继续作模2除，应使余数循环。
将这些要求反映为数学关系是比较复杂的，对一个(n，k)码来说，可将(x
n
－1)分解为若干质因子，根据编码所要求的码距选取其中的因式或若干因式的乘积作为生成多项式。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例：有一个（7，3）码，生成多项式为G(x)= x
4
+ x
3
+ x
2
+ 1,写出代码001的效验码和循环余数。
?解：生成多项式为11101，在有效信息后面添４个0，然后用它和
G(x)进行模2除法运算。
计算机学院(XBXU)
运算过程如下,
１００１
１１１０１ ００１００００
１１１０１
１１０１
余数为１１０１，所以，所求的CRC效验码为：
００１１１０１
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码求循环余数的过程如下,
１１１０１ １１０１ 第一个余数
１１０１０
１１１０１ 余数循环次序如下：
１１１ 第二个余数
１１１０ 第三个余数 １１０１ ０１１１ １１１０
１１１００
１１１０１ ０００１
１ 第四个余数
１０ 第五个余数 １０００ ０１００ ００１０
１００ 第六个余数
１０００ 第七个余数
１００００
１１１０１
１１０１第一个余数
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?第三章习题
? P.103,3.9；
? P.104,3.25;3.26;3.27;3.31
END
——本科生课程教学计算机学院计算机学院
(
(
XBXU)
XBXU)
计算机学院(XBXU)
计算机组成与结构计算机组成与结构
?本课程主要讲授计算机系统的硬件和软件构成方法，包括硬件系统中运算器、控制器、存储器、输入设备和输出设备和总线系统的构成原理等；并与当代先进的计算机技术相结合。是计算机科学与技术本科专业核心课程。
?本课程着重计算机系统组成与结构方面的教学和研究。
?计算机结构定义为系统程序员所能见到的计算机硬件特性；
?计算机组成是指计算机硬件的具体实现。
计算机学院(XBXU)
第三章第三章运算方法和运算部件运算方法和运算部件
?数据的表示方法和转换
?带符号数的表示方法及加减运算
?二进制乘法运算
?二进制除法运算
?浮点数的运算方法
?运算部件
?数据校验码计算机学院(XBXU)
3.6
3.6
运算部件运算部件一、运算部件
?书P95，图3.9所示是一个能实现定点加、减、乘、除运算的运算部件。
? 1．在进行加法运算时，应送来A→ALU、B→ALU、ALU→S、
S→A信号(高电位)，另外还应向ALU发出加法运算命令(图中未画出)。
? 2．在进行减法运算时，应送来A→ALU、→ALU、＋1、
ALU→S、S→A信号(高电位)，同样还应向ALU发出减法运算命令。
? 3．乘法运算的实现见前面的流程图。
? 4．除法运算的实现见前面的流程图。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件二、运算部件AM2901A
1、AM2901A逻辑结构及原理图计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?基本组成部件有：
?八功能的ALU：完成算术与逻辑运算；
? 16×4位寄存器组：寄存加减运算的操作数；
? 4位Q寄存器：用于接收ALU的输出数据，具有左、右移功能；
? 3选1和2选1多路开关：用于多路地址、数据的选择。
?下图是AM2901A的逻辑原理图。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件计算机学院(XBXU)
3.6
3.6
运算部件运算部件
2、AM2901A主要特点
?位片式结构，即每片内仅有四位线路，要实现不同位数的运算器，需将几片同样的器件串接起来使用。例如用四片可实现—个16位字长的运算器。
?该运算器的ALU能实现八种运算功能，它每一位上的两个输入端数据分别用R和S表示，则这八种功能是：
三种算术运算功能：
五种逻辑运算功能：
SRRSSR+和,
SRSRSRSRSR ⊕⊕∧∧∨和,,,
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?这八种功能的选择控制，是用外部送入的三位编码值I
5
I
4
I
3
实现的，其具体规定如下表所示。
ALU的功能选择ALU的输入选择计算机学院(XBXU)
3.6
3.6
运算部件运算部件
? ALU的R输入端可以接收外部送入运算器的数据D,寄存器组的—组输出A，或接收逻辑0值。ALU的S输入端可以接收寄存器组的一组输出A和另—组输出B，还可以接收Q寄存器的输出。这样,R和S接收的数据可以有如下12种组合情况：
? R 0000 AAAA DDDD
? S ABQ0 ABQ0 ABQ0
?考虑到R和S同时接收0无实用价值，OA与AO组合、AA和
AB组合、DA和DB组合可以相互替代,故只需留下八种组合情况即可、此时可用外部送来的三位控制码来决定ALU的输入数据，即区分可用的八种组合。对应关系如上表所示。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?运算器中有1个16X4位的通用寄存器组和一个4位的Q寄存器。寄存器组被设计成能双端口输出的部件。每一个寄存器都可以用A地址或B地址选择，将寄存器中的内容分别送到输出端口A或B)。当A和B地址不同时，在输出端口A和B
将得到两个不同寄存器中的内容。该寄存器组的写入控制
，只能用B地址实现，写入的数据是ALU的输出经过移位器送到寄存器组的输入端的。移位器可执行直送、左移一位操作，或右移一位的操作，使加减运算和移位操作可在同一个操作步骤中完成。
? Q寄存器本身具有移位功能，即它可以接收自己左移一位或右移一位的值。Q寄存器还可以接收ALU的输出F的值。Q
的输出可在经ALU的S输入端送入ALU。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
? ALU还给出了Cn+4、F3(可用作符号位)、OVR和F=0000四个状态信息，它们分别是本四位运算器产生的向更高位的进位、本片最高位的取值、结果溢出和结果为零的状态。
ALU的最低位还接收从更低位片送来的进位信号Cn，ALU
还给出了超前进位信号G和P。
?移位器还有接收与送出移位数值的引线，它们分别是RAM3
、RAM0、Q3和Q0，它们都是用三态门给出的具有双向传送功能的线路实现的。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?运算器的四位输出为Y
3
一Y
0
，它可以是ALU的运算结果，
也可以是寄存器组A输出端口上的内容。这里用的是三态门电路，仅当OE#信号为低电平时，y的值才是可用的，否则
Y输出处于高阻状态。
?控制数据传送的方式(移不移位)和数据发送的去向，是用另外三位编码(I
8
I
7
I
6
)来控制的，具体规定如下表所示。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件数据传输控制计算机学院(XBXU)
3.6
3.6
运算部件运算部件
3、16位字长定点运算器
?可以用四片Am2901A组成一个16位字长的定点运算器，其连接关系如下图所示。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件线路工作原理：
?每片器件上的Q
0
和Q
3
端，RAM
0
与RAM
3
端都能用于输入和输出
，因此，它们用三态门电路实现，在ALU的移位控制信号(
由数据传送控制的三位编码I
8
I
7
I
6
给出)控制下，把高位片的Q
0
、RAM
0
输出信号送入低位邻片的Q
3
、RAM
3
输入端，或把低位片的Q
3
、RAM
3
输出信号送入高位片的Q
0
、RAM
0
输入端。
?四片的数据输入端D
3
-D
0
一起作为16位运算器的16个数据输入端D
15
～D
0
，四片的数据输出端Y
3
-Y
0
一起作为16位运算器的16个数据输出端Y
15
-Y
0
。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?四片的三组输入信号I
2
I
1
-I
0
，I
5
I
4
I
3
，I
8
I
7
I
6
，分别用外部送来的三组信号提供给每—片,使四片总使用相同的控制信号
，保证它们的并行工作关系(片间有串行数据信号传送)。
?通用寄存器组RAM的两个地址控制端“A”(读)和“B”(读／写
)、Q寄存器移位用的CP时钟脉冲信号，分别送入每—片
Am2901A的“A”、“B”和CP输入端。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件指令控制过程：
?下述几条指令在运算器部件中的控制方法：
? (1)把主存数据寄存器中读得的数据写入通用寄存器组中的某个寄存器中；
? (2)把通用寄存器组中某个寄存器的内容写进主存数据寄存器中；
? (3)通用寄存器组中的两个寄存器的内容相加。结果写回其中的一个寄存器中。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?按Am2901A的功能规定，可以给出如下表所示的一张信号分配表。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?第一条指令，把主存数据寄存器的输出接到Am2901A的D
输入端：
?用I
2
I
1
I
0
＝111作为ALU的输入数据选择(D，0组合)，
?用I
5
I
4
I
3
＝000作为ALU的功能选择(加，即实现D十0)，
?用I
8
I
7
I
6
＝011作为ALU的数据传送控制，即把ALU的输出送到通用寄存器组的输入，再写入由“B”地址选择的寄存器中
。在此操作过程中，最低位进位输入值给0。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?第二条指令，把通用寄存器中的内容写入主存数据寄存器中：
?用I
2
I
1
I
0
＝011作为ALU的输入选择(0，B组合)，
?用I
5
I
4
I
3
＝000作为ALU的功能选择(加，即实现0+B号寄存器的内容)，
?用I
8
I
7
I
6
＝001作为Am2901A的输出选择并同时给出面信号
，Y输出即为B寄存器的内容，可以把Y接到主存数据寄存器的输入端，从而完成向该寄存器的写入操作。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?第三条指令，把A寄存器的内容加上B寄存器的内容，结果写入B寄存器中：
?用I
2
I
1
I
0
＝001作为ALU的输入数据选择，
?用I
5
I
4
I
3
＝000作为ALU的功能选择，
?用I
8
I
7
I
6
＝010作为ALU的数据传送选择，从而完成A寄存器的内容加B寄存器的内容，并把结果写入B寄存器中的操作过程。此时要使OE#取高电平，使输出Y处于高阻状态，而不是输出A寄存器的内容。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件
?这三条指令的运行结果，应按某种规定设置运算器的状态标志触发器C、y、Z、N，这些触发器要在Am2901A芯片之外实现，将Am2901A的最高位芯片的输出Cn+4、OVR、F
＝0000和F3的值写入这四个标志触发器中。图上省略了这一部分逻辑电路。
计算机学院(XBXU)
3.6
3.6
运算部件运算部件计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?码距是根据任意两个合法码之间至少有几个二进制位不相同而确定的，仅有一位不同，称其码距为1。例如，用四位二进制表示16种状态，则16种编码都用到了，此时码距为1
，就是说，任何一个状态的四位码中的一位或几位出错，
就变成另一个合法码，此时无查错能力。若用四个二进制位表示8个状态，就可以只用其中的8种编码，而把另8种编码作为非法编码，此时码距为2。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码一、奇偶校验码
?奇偶校验码的原理是在每组代码中增加一个冗余位，使合法编码的最小码距由1增加到2。
1、校验码的构成规则
?偶校验：每个码字(包括校验位)中1的数目为偶数。
?奇校验：每个码字(包括校验位)中1的数目为奇数。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
2、校验位的形成
?设有效信息位为：
?偶校验，在发送端求校验位：
?奇校验，在发送端求校验位：
01234567
DDDDDDDD
01234567
DDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕=
01234567
DDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕=
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(3) 校验原理
?偶校验在接收端求：
?奇校验在接收端求：
?若P’=0，则无错；P’=1，则有错。
?校验电路参见P96图3.10。
PDDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕⊕=
01234567
'
PDDDDDDDDP ⊕⊕⊕⊕⊕⊕⊕⊕=
01234567
'
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
4、局限性
?奇偶校验码能发现数据代码中奇数个位出错情况，并且不能纠正错误，常用于对存储器数据的检查或者传输数据的检查。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码二、海明校验码
?海明校验的基本思想是将有效信息按某种规律分成若干组
，每组安排一个校验位进行奇偶测试。在一个数据位组中加入几个校验位，增加数据代码间的码距，当某一位发生变化时会引起校验结果发生变化，不同代码位上的错误会得出不同的校验结果。因此，海明码能检测出2位错误,并能纠正1位错误。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(1)求海明校验码的步骤。
?①确定海明校验位的位数设K为有效信息的位数，设r为校验位的位数，则整个码字的位数N应满足不等式：
N=K＋r≤2
r
－1
若要求海明码能检测出2位错误，则再增加一位校验位。
?②确定校验位的位置：位号(1～N)为2的权值的那些位，
即：2
0
、2
1
、2
2
、…2
r－1
的位置作为校验位，记作P
1
、P
2
、… P
r
，余下的为有效信息位。
?③分组:将N位分r组，第i位由校验位号之和等于i的那些校验位所校验。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?④校验位的形成
P
1
=第一组中的所有位(除P1外)求异或
P
2
=第二组中的所有位(除P2外)求异或
P
r
=第r组中的所有位(除Pr外)求异或
?为了能检测两个错误，增加一位校验P
r＋1
，放在最高位。
P
r＋1
= 所有位(包括P
1
、P
2
、… P
r
)共N位求异或计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(2)校验原理：在接收端分别求S
1
、S
2
、S
3
、…S
r
S
1
=第一组中的所有位(包括P
1
)求异或
S
2
=第二组中的所有位(包括P
2
)求异或
S
r
=第r组中的所有位(包括P
r
)求异或
S
r＋1
= P
r＋1
⊕所有位(包括P
1
、P
2
、… P
r
)求异或
?当S
r＋1
=1时有一位错：由S
r
…S
3
S
2
S
1
的二进制编码指出出错位号,将其取反，即可纠错。
?当S
r＋1
=0时无错或有偶数个错(两个错的可能性比较大),当
S
r
…S
3
S
2
S
1
=0…000时，接收的数无错，否则有两个错。
?根据此原理，能画出指出两个错误并能纠正一位出错位的海明校验逻辑电路。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例求信息码01101110的海明校验码，画出能指出和纠正一位出错位的海明校验逻辑电路。
【例题分析】
?①确定海明校验位的位数
?设R为校验位的位数，则整个码字的位数应满足不等式：
N=K＋R≤2
R
－1
?设R=3，则2
3
－1=7，N=8＋3=11，不等式不满足；
?设R=4，则2
4
－1=15，N=8＋3=12，不等式满足。所以R最小取4。
?②确定校验位的位置：位号(1～12)为2的权值的那些位，
即：2
0
、2
1
、2
2
、2
3
的位置作为校验位，记作P1、P2、P3
、P4，余下的为有效信息位。即：
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? 12 11 10 9 8 7 6 5 4 3 2 1
? D
7
D
6
D
5
D
4
P4 D
3
D
2
D
1
P3 D
0
P2 P1
?
?③分组：有4个校验位，将12位分4组，第i位由校验位号之和等于i的那些校验位所校验。
?如：第11位D
6
由P1(位号为1)、P2(位号为2)、P4(位号为8)
所校验，因为1＋2＋8=11。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?④校验位的形成
P1=第一组中的所有位(除P1外)求异或=
D
6
⊕D
4
⊕D
3
⊕D
1
⊕D
0
=1⊕0⊕1⊕1⊕0=1
P2=第二组中的所有位(除P2外)求异或=
D
6
⊕D
5
⊕D
3
⊕D
2
⊕D
0
= 1⊕1⊕1⊕1⊕0=0
P3=第三组中的所有位(除P3外)求异或= D
7
⊕D
3
⊕D
2
⊕D
1
=
0⊕1⊕1⊕1=1
P4=第四组中的所有位(除P4外)求异或= D
7
⊕D
6
⊕D
5
⊕D
4
=
0⊕1⊕1⊕0=0
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?为了能检测两个错误，增加一位校验P5，放在最高位。
P5 = D
7
⊕D
6
⊕D
5
⊕D
4
⊕D
3
⊕D
2
⊕0 D
1
⊕D
0
⊕P1⊕P2⊕P3⊕P4
= 0⊕1⊕1⊕0⊕1⊕1⊕1⊕0⊕1⊕0⊕1⊕0 = 1
?【例题答案】信息码01101110的海明校验码为：1 0110
1 111 0 0 10。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (2)校验原理在接收端分别求S
1
、S
2
、S
3
、S
4
、S
5
。
S
1
= P1⊕D
6
⊕D
4
⊕D
3
⊕D
1
⊕D
0
S
2
= P2⊕D
6
⊕D
5
⊕D
3
⊕D
2
⊕D
0
S
3
= P3⊕D
7
⊕D
3
⊕D
2
⊕D
1
S
4
= P4⊕D
7
⊕D
6
⊕D
5
⊕D
4
S
5
= P5⊕D
7
⊕D
6
⊕D
5
⊕D
4
⊕D
3
⊕D
2
⊕0
D
1
⊕D
0
⊕P1⊕P2⊕P3⊕P4
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?当S
5
=1时有一位错：由S
4
S
3
S
2
S
1
的二进制编码指出出错位号。例如S
4
S
3
S
2
S
1
=1001 说明第9位出错，将其取反，即可纠错。
?当S
5
=0时无错或有偶数个错(两个错的可能性比较大)：当
S
4
S
3
S
2
S
1
=0000时，接收的数无错，否则有两个错。
?【例题答案】能指出两个错误并能纠正一位出错位的海明校验逻辑电路如图所示。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
D
7
D
6
D
5
D
4
D
3
D
2
D
1
D
0
无错
一位错
两位错
=1 =1 =1 =1 =1 =1 =1 =1
H
12
H
11
H
10
H
9
H
7
H
6
H
5
H
3
1100 1011 1010 1001 0111 0110 0101 0011 0000
4
：
16
译
码
器
(
设译码器高电平有效
)
S
4
S
3
S
2
S
1
S
5
奇偶形成线路
奇偶形成线路
奇偶形成线路
奇偶形成线路
奇偶形成线路
H
12
H
11
H
10
H
9
H
8
H
12
H
7
H
6
H
5
H
4
H
11
H
10
H
7
H
6
H
3
H
2
H
11
H
9
H
7
H
5
H
3
H
1
所有位
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例：有一个（7，4）码，写出代码0011的海明效验码，画出效验电路
?解答：
(1)求信息码001的海明效验码。
①确定海明效验位的位数因为是（7，4）码，所以N=7，K=4，效验位的位数为3。
②确定效验位的位置：位号（1∽7）为2的权值的那些位，
即：2
0
、2
1
、2
2
的位置作为效验位，即：
1 2 3 4 5 6 7
P1 P2 D
3
P3 D
2
D
1
D
0
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
②
H
7
H
6
H
5
H
4
H
3
H
2
H
1
D
3
D
2
D
1
P3 D
0
P2 P1
第一组（P1） √ √ √ √
第二组（P2） √ √ √ √
第三组（P3） √ √ √ √
0 0 1 1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?④效验位的形成
P1= D
3
⊕D
1
⊕D
0
= 0⊕1⊕1=0
P2= D
3
⊕D
2
⊕D
0
= 0⊕0⊕1=1
P3= D
3
⊕D
2
⊕D
1
= 0⊕0⊕1=1
?所以：信息码0011的海明效验码为：001 1 1 10。
(2)海明效验逻辑电路如图所示。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
D3 D2 D1 D0 =1无错
=0有错
H
7
H
6
H
5
H
3
0011 0101 0110 0111 0000
3：8 译 码 器 （设译码器高电平有效）
S3 S2 S1
奇偶形成线路 奇偶形成线路 奇偶形成线路
H
7
H
6
H
5
H
4
H
7
H
6
H
3
H
2
H
7
H
5
H
3
H
1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码三、循环冗余校验(CRC)码
?二进制信息沿一条线逐位在部件之间或计算机之间传送称为串行传送。CRC(Cyclic Redundancy Check)码可以发现并纠正信息存储或传送过程中连续出现的多位错误。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(1)CRC码的编码
?①模2运算模2运算是指以按位模2相加为基础的四则运算，运算时不考虑进位和借位。
?模2加减：即按位加，可用异或逻辑实现。模2加与模2减的结果相同，即0±0＝0，0±1＝1，1±0＝1，1±1＝0。
?模2乘:按模2加求部分积之和。
?模2除:按模2减求部分余数。上商的原则是：当部分余数的首位为1时，商取l；当部分余数的首位为0时，商取0。当部分的余数的位数小于除数的位数时，该余数即为最后余数
。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?②CRC码的编码方法
CRC码是用多项式M(x)·x
r
除以称为生成多项式的G(x)(产生校验码的多项式)所得余数作为校验位。为了得到r位余数(
校验位)，G(x)必须是r＋1位。
设所得余数表达示为R(x)，商为Q(x)。将余数拼接在信息位左移r位后空出的r位上，就构成这个有效信息的CRC码。这个CRC码可用多项式表示为：
M(x)·x
r
＋R(x)＝[Q(x)·G(x)＋R(x)]＋R(x)
＝[Q(x)·G(x)]＋[R(x)＋R(x)]
＝Q(x)·G(x)
?因此所得CRC码可被G(x)表示的数码除尽。
?将编好的循环校验码称为(n，k)码。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?③CRC码的编码电路
?若G(x)=x
r
＋g
r –1
x
r –1
＋…＋g
2
x
2＋
g
1
x
1
＋1,g
i
∈{0，
1},i∈{r－1，…，2，1},则CRC码的编码电路如下图所示：
k
m
R
g
1
g
2
g
r
－
1
R
0
⊕
R
1
⊕
⊕
R
r
－
1
⊕
信息输入端
(高位在前，低位在后) 码字输出端
k
k
r
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?当g
i
=1时，开关g
i
闭合，当g
i
=0时，开关g
i
断开。开始发送数据时，开关k置于k
m
位置，开关R同时闭合，信息位由输入端从高到低串行输入，一边从码字输出端输出，一边进入编码电路循环运算。当信息发送完毕时，寄存器R
0
，R
1
，…，R
r－1
中的内容即为冗余位的值。此时，开关R断开，
开关k置于k
r
位置，冗余位就紧接在信息位的后面输出。至此发送方编码发送完毕。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例在CRC校验中，已知生成多项式G(x)＝x
4
＋x
3
＋1。要求：①计算信息序列1101101的校验序列。
②画出该G(x)的编码电路。
?分析：
?①对应生成多项式G(x)的二进制序列为：11001
在有效信息后面添4个0。然后用它和G(x)进行模2除法运算，所得的余数即为所求的校验位。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
运算过程如下,
１0 0 1 1 0 1
1１0 0１ １１0 1 1 0 1 0 0 0 0
1１0 0１
1 0 0 1 0
1１0 0１
1 0１１0
1 1 0 0 1
1 1 1 1 0
1 1 0 0 1
1 1 1 0 0
1 1 0 0 1
1 0 1
余数为0101，所求的CRC校验码为：1101101 0101
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?②G(x)= 11001,则CRC码的编码电路如下图所示。
?开始发送数据时，开关k置于k
m
位置，开关R同时闭合，信息位由输入端从高到低串行输入，一边从码字输出端输出
，一边进入编码电路循环运算。当信息发送完毕时，寄存器R
0
，R
1
，R
2
，R
3
中的内容即为冗余位的值。此时，开关
R断开，开关k置于k
r
位置，冗余位就紧接在信息位的后面输出。至此发送方编码发送完毕。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
k
m
0 1 1
R
0
R
1
R
2 ⊕
R
3
⊕
码字输出端
信息输入端
(
高位在前，低位在后
)
k
k
r
R
1 0
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?在实际工作中,接收方一边接收信息，一边利用译码电路进行差错检测。
?若G(x)=x
r
＋g
r –1
x
r –1
＋…＋g
2
x
2＋
g
1
x
1
＋1,g
i
∈{0，1},i∈{r
－1，…，2，1},则译码电路如图2,2所示，当g
i
=1时，开关g
i
闭合，当g
i
=0时，开关g
i
断开。接收方将收到的码字信息逐位送入译码电路计算余数，在码字信息全部进入译码电路后，寄存器R
0
，R
1
，…，R
r－1
中就寄存了余数E(x)。
将余数各位进行或运算。得错误特征位E。若E＝0，则接收正确，将码字中的最末r位去掉，得到原发数据；若E=l，则表示收到的码字有错。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (2) CRC的译码与纠错
?在CRC校验中，发送方已知信息序列M(x)和生成多项式
G(x)，发送方便可利用编码电路形成传输序列T(x)进行发送
。T(x)经信道传输后到达接收方，接收方收到信息T’(x),若
T’(x)＝T(x)，则传输无错，否则就是出错。接收方只是已知G(x)和收到的T’(x),但不知道发送方发送的T(x)。判断
T’(x)是否有错的方法为：将收到的循环校验码用约定的生成多项式G(x)去除，如果码字无误则余数应为0，如有某一位出错，则余数不为0，不同位数出错余数不同。更换不同的待测码字可以证明：余数与出错位的对应关系是不变的
，只与码制和生成多项式有关。对于其他码制或选用其他生成多项式，出错模式将发生变化。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
g1 g2 gr
－
1
R
0 ⊕
R1 ⊕ ⊕ R r
－
1 ⊕
接收码字输入端
≥
1
错误特征位
图
2.2 CRC
的译码电路
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例，求有效信息1010、0111的CRC校验码，并求循环余数，
说明校验原理,画出译码与纠错电路。
?分析：
(1)求有效信息1010的CRC校验码
?①确定校验位的位数设R为校验位的位数，则整个码字的位数应满足不等式：
N=K＋R≤2
R
－1
设R=3，则2
3
－1=7，N=4＋3=7，不等式满足。所以R最小取3。
?②选一个R＋1位的生成多项式G(x),如G(x)=1011
?③在有效信息后面添R个0。然后用它和G(x)进行模2除法运算，所得的余数即为所求的校验位。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
运算过程如下,
１００１
１０１１ １０１００００
１０１１
１０００
１０１１
１１
余数为０１１，所以，所求的CRC校验码为：１０１００１１
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
④求循环余数：在上面１１余数的基础上添０继续进行模２除,如下,
１０１１ １１ 第一个余数
１１０ 第二个余数
１１００ 余数循环次序如下：
１０１１
１１１ 第三个余数
０１１
１１０ １１１
１１１０
１０１１
１０１
１０１ 第四个余数
１０１０
１００
０１０
００１
１０１１
１ 第五个余数
１０ 第六个余数
１００ 第七个余数
１０００
１０１１
１１ 第一个余数
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
(2)
求有效信息
0111
的
CRC
校验码
运算过程如下：
１１０
１０１１
０１１１０００
１０１１
１０１０
１０１１
１０
余数为０１０，所以，所求的
CRC
校验码为：１１０１０１０
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码求循环余数：在上面１余数的基础上添０继续进行模２除,如下,
１０１１ １０ 第一个余数
１００ 第二个余数 余数循环次序如下：
１０００
１０１１ ０１１ １１０ １１１
１１ 第三个余数
１１０ 第四个余数 １０１
１１００
１０１１ １００
０１０ ００１
１１１ 第五个余数
１１１０
１０１１
１０１ 第六个余数
１０１０
１０１１
１ 第七个余数
１０ 第一个余数
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (3)校验原理
?从以上(1)、(2)的余数循环次序来看，其余数是相同的，
实际上只要是4位有效数，他们的余数均相同，而且出错模式也是相同的。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
G (x)=1011
时的
1010(7
，
4)
循环码的出错模式
D1 D2 D3 D4 D5 D6 D7
余 数 出错位
正确
1 0 1 0 0 1 1 0 0 0
无
错误
1
1
1
1
1
1
0
0
0
0
0
0
1
0
1
1
1
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
1
1
7
6
5
4
3
2
1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
G (x)=1011
时的
0111(7
，
4)
循环码的出错模式
D1 D2 D3 D4 D5 D6 D7
余 数 出错位
正确
0 1 1 1 0 1 0 0 0 0
无
错误
1
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
1
1
7
6
5
4
3
2
1
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (4)译码与纠错电路
?校验的原理是根据余数来判断出错位，取反即可纠错,译码与纠错电路如下。接收方将收到的码字信息逐位送入译码电路计算余数，在码字信息全部进入译码电路后，寄存器R
0
，R
1
，R
2
中就寄存了余数。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?余数=0译码器的0输出端为高，表示无错；
?余数=1译码器的1输出端为高，表示有效信息D
1
错，取反即可纠错；
?余数=2译码器的2输出端为高，表示有效信息D
2
错，取反即可纠错；
?余数=4译码器的4输出端为高，表示有效信息D
3
错，取反即可纠错；
?余数=3译码器的3输出端为高，表示有效信息D
4
错，取反即可纠错；
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
R
R
0 ⊕
R
2
R
3 ⊕
接收码字输入端
3
：
8
译
码
器
(
设译码器高电平有效
)
000 001 010 100 011
D
1
’
D
2
’
D
3
’
D
4
’
⊕
⊕
⊕
⊕
=1
有错
D
1
D
2
D
3
D
4
=0
无错
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
? (3)关于生成多项式并不是任何一个(r＋1)位多项式都可以作为生成多项式的。从检错及纠错的要求出发，生成多项式应能满足下列要求：
?①任何一位发生错误都应使余数不为0。
?②不同位发生错误应当使余数不同。
?③对余数继续作模2除，应使余数循环。
将这些要求反映为数学关系是比较复杂的，对一个(n，k)码来说，可将(x
n
－1)分解为若干质因子，根据编码所要求的码距选取其中的因式或若干因式的乘积作为生成多项式。
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?例：有一个（7，3）码，生成多项式为G(x)= x
4
+ x
3
+ x
2
+ 1,写出代码001的效验码和循环余数。
?解：生成多项式为11101，在有效信息后面添４个0，然后用它和
G(x)进行模2除法运算。
计算机学院(XBXU)
运算过程如下,
１００１
１１１０１ ００１００００
１１１０１
１１０１
余数为１１０１，所以，所求的CRC效验码为：
００１１１０１
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码求循环余数的过程如下,
１１１０１ １１０１ 第一个余数
１１０１０
１１１０１ 余数循环次序如下：
１１１ 第二个余数
１１１０ 第三个余数 １１０１ ０１１１ １１１０
１１１００
１１１０１ ０００１
１ 第四个余数
１０ 第五个余数 １０００ ０１００ ００１０
１００ 第六个余数
１０００ 第七个余数
１００００
１１１０１
１１０１第一个余数
计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码计算机学院(XBXU)
3.7
3.7
数据校验码数据校验码
?第三章习题
? P.103,3.9；
? P.104,3.25;3.26;3.27;3.31
END
