第3章-kuaisu数据表示与运算算法分析

第3章-kuaisu数据表示与运算算法分析第一页，共81页。本章主要内容3.1信息编码概念、码制转换3.2数据表示——常用的信息编码3.3二进制数值数据的编码与运算算法第一页第二页，共81页。数字化编码二要素数值、文字、符号、语音、图形、图像等统称数据，在计算机内部，都必须用数字化编码的形式被存储、加工和传送。数字化编码二要素:少量简单的基本符号一定的组合规则用以表示大量复杂多样的信息第二页第三页，共81页。基二码（二进制码）只使用两个基本点符号：１

０符号个数最少，物理上容易实现与二值逻辑的真

假

两个值对应简单用二进制码表示数值数据运算规则简单第三页第四页，共81页。进位记数法与进制转换进位记数法：N=Dm-1Dm-2Dm-3…D1D0D-1D-2…D-k每个Di的单位值都赋以固定的权值ri（r称为基），则上式可写成：例如：十进制数1234，可写成：1234=1*10^3+2*10^2+3*10^1+4*10^0第四页第五页，共81页。十进制转二进制整数部分除2取余小数部分乘2取整211222521011010.625*210.25*200.5*210.0除尽为止

求得位数满足要求为止低高高低从二进制数求其十进制的值，逐位码权累加求和第五页第六页，共81页。二到八或十六进制转换二到八从小数点向左右三位一分组（10011100.01)2=(234.2)8010

二到十六从小数点向左右四位一分组（10011100.01)2=(9C.4)16

0100

说明：整数部分不足位数对转换无影响，

小数部分不足位数要补零凑足，否则出错。第六页第七页，共81页。二进制数据算术运算规则(1)加法运算规则0+0=0例如：01010+1=1+)00011+0=101101+1=0并产生进位(2)减法运算规则0-0=0例如：10110-1=1并产生借位-)01011-0=101101-1=0第七页第八页，共81页。二进制数据算术运算规则乘法运算规则例如：11010X0=0X)01010X1=011011X0=0+1101001X1=11000001除法运算规则1101例如：1110101/100110011110101

10011011

10010010011001

0

第八页第九页，共81页。本章主要内容3.1信息编码概念、码制转换3.2数据表示——常用的信息编码3.3二进制数值数据的编码与运算算法第九页第十页，共81页。数据表示逻辑型数据字符型数据西文字符汉字字符串多媒体信息图像/图形声音视频数值型数据定点小数整数浮点数十进制数（BCD码）检错纠错码 奇偶校验海明校验循环冗余校验第十页第十一页，共81页。逻辑型数据逻辑型数据只有两个值：真和

假， 正好可以用二进制码的两个符号分别表示。 例如1表示真

0

表示假对逻辑型数据可以执行逻辑的与或

非等基本逻辑运算。其规则如下：X

Y

X与YX或YX的非

0

0001

0

1011

1

0010

1

1

110

第十一页第十二页，共81页。字符型数据字符是最重要的数据类型之一，编码规则很多，一些常见编码或术语：ASCII编码扩展ASCII码EBCDIC码ANSI编码（MBCS编码）GB2312码、GBK码、BIG5码Unicode编码UTF-8码AmericanStandardCodeforInformationInterchange，美国信息互换标准代码，主要用于显示现代英语和其他西欧语言，是最通用的单字节编码系统，包含控制字符（如回车键、退格、换行键等）和可显示字符（如英文大小写字符、阿拉伯数字和西文符号）用7位表示一个字符，共128字符。见P49表3.4。为表示更多的欧洲常用字符，对ASCII进行了扩展，使用8位表示一个字符，共256字符，扩充出来的符号包括表格符号、计算符号、希腊字母和特殊的拉丁符号。ExtendedBinaryCodedDecimalInterchageCode，是IBM公司为大型操作系统开发的，根据早期打孔机式的BCD排列而成，使用8位表示一个字符，共256个字符。但英文字母不连续。为扩充ASCII码，以显示本国语言，各国家和地区制定的标准，如GB2312,BIG5,JIS等，称为ANSI编码，又称为MBCS（Muilti-BytesCharecterSet，多字节字符集），多为2字节。简体中文中ANSI编码代表GB2312编码，日文中ANSI编码代表JIS编码。GB2312是一个简体中文字符集，由6763个常用汉字和682个全角的非汉字字符组成，排列成94行94列，用区位号表示一个字符编码.GBK是对GB2312的扩充，增加了对人名、古汉语等方面出现的罕用字。BIG5是一个繁体中文字符集，在台湾、香港与澳门地区及其他海外华人中普遍使用。各种ANSI编码不兼容，易出现乱码，Unicode编码将所有符号都纳入其中（现在可容纳100多万个符号）。但编码效率不高，比如UCS-4标准)规定用4个字节存储一个符号，每个英文字母前3个字节为0，对存储和传输都很耗资源。为提高Unicode编码的效率，推出了UTF-8码，它可以根据不同的符号自动选择编码的长度，如英文字母采用1个字节就够了。第十二页第十三页，共81页。字符串的表示与存储字符串是指连续的一串字符，占据主存中连续字节，每个字节存放一个字符，表示字符串数据要给出串存放的主存起始地址和串的长度。对一个主存字的多个字节，有按从低位到高位字节次序存放的，也有按从高位到低位字节次序存放的。例如：IFA>BTHENREAD(C)存放方式有：IFAAFI>BTTB>假定每个字4个字节HENNEHREADDAER(C))C(第十三页第十四页，共81页。多媒体信息编码1图图像图形2声音语音：采集→AD转换→编码音乐：把乐谱、弹奏的乐器类型、击键力度等用符号记录效果声3视频信息由像素点阵构成的位图，色彩丰富、过渡自然，图像像素点越多（分辨率高），图像越清晰，文件就越大。一般通过照相、扫描、摄像得到图形都是位图图像，如bmp、jpg等。由数学公式表达的轮廓线条构成矢量图；放大后图形不失真，占用空间较小。工程设计图、图表、插图经常以矢量图形曲线来表示，如photoshop中的PSD文件。把声音的波形进行编码---波形法把数字式电子乐器的弹奏过程记录下来---合成法第十四页第十五页，共81页。数值数据在计算机内的格式定点小数:N=NNN……...Ns-1-n-2整数:N=NNN...NN01snn-1浮点数:N=M

EE...EE

MM...M

ssm-110-1-2-n符号位

阶码位

尾数数码位

总位数短浮点数:

1

8

2332长浮点数:1

11

5264临时浮点数:1

15

64

80IEEE标准：阶码用移码，尾数用原码基为2第十五页第十六页，共81页。

8421码余3码循环码84-2-100000001100000000100010100000101112001001010011011030011011000100101401000111011001005010110001110101160110100110101010701111010100010018100010111100100091001110001001111十进制数的编码（BCD编码）用4位二进制表示1位十进制，从16个编码中选10个，有多种方案，例如：8421码，余3码，循环码8421和84-2-1为有权码，即每位上的1代表确定的值，如：8421码中4个位分别表示8、4、2、1，故编码0111=0*8+1*4+1*2+1*1=784-2-1码中4个位分别表示8、4、-2、-1，故编码0111=0*8+1*4+1*(-2)+1*(-1)=1余3码和循环码为无权码：无法确定每位上的1代表的值第十六页第十七页，共81页。检错纠错码为了提高计算机的可靠性，除了采取选用更高可靠性的器件、更好的生产工艺等措施之外，还可以从数据编码上想一些办法，即采用一点冗余的线路，在原有数据位之外再增加一到几位校验位，使新得到的码字带上某种特性，之后通过检查该码字是否仍保持这种特性，来发现是否出现了错误，甚至自动改正错误，这就是检错纠错编码技术。第十七页第十八页，共81页。三种常用的检错纠错码奇偶检错码，用于并行数据传送中海明检错与纠错码，用于并行数据传送中循环冗余码，用于串行数据传送中编码译码传送原始数据码字结果数据形成校验位的值，加进特征检查接送的码字，发现/改正错误第十八页第十九页，共81页。奇偶校验码校验位用于并行数据检错原理：在k位数据码之外增加1位校验位，使K+1位码字中取值为1的位数保持为偶数(偶校验)或奇数(奇校验)。例如： 00011000100001 01010010110101原始信息两个新的码字

偶校验奇校验第十九页第二十页，共81页。奇偶校验码的实现电路出错指示⊕编码电路译码电路P(校验位)0D6D5D4D3D2D1D0p⊕编码电路⊕⊕⊕⊕⊕⊕P奇=D6⊕D5⊕D4⊕D3⊕D2⊕D1P偶=D6⊕D5⊕D4⊕D3⊕D2⊕D1E奇=D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕P奇当E奇=1时为合法码E偶=D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕P偶当E偶=0时为合法码奇较验偶校验7位数据位第二十页第二十一页，共81页。奇偶检验码练习--教材P75：4解：数据01010111中有5个1，故：奇校验：001010111 偶校验：101010111数据11010100中有4个1，故：奇校验：111010100 偶校验：011010100第二十一页第二十二页，共81页。海明校验码用于并行数据检错纠错，如主存的ECC(ErrorCorrectingCode)是海明校验码的一种典型应用。实现原理：在k个数据位中加入r个校验位，将数据代码的码距比较均匀地拉开，并把每数据位分配在几个奇偶校验组中。当某位出错时，就会引起相关的几个校验位值发生变化，这不仅可发现错误，还能指出哪一位出错，为进一步自动纠借提供了依据。第二十二页第二十三页，共81页。海明校验码构成r个位可表示2r个码，用其中一个码表示是否出错，用其余2r-1个码指示出错位置，则最多可指示2r-1个位，数据位和检验位都有可能出错，故校验位数r和数据位数k应满足不等式：2r-1≥k＋r，也即k≤2r-1-rk值 最小r值1～4 35～11 412～26 527～57 658～119 7例如，校验位数r=4，可表示16个码，可用于纠正被传送的最多有效数据位k=16-1-4=11。第二十三页第二十四页，共81页。(1)校验位分布若由k个数据码DkDk-1…D1和r个校验码PrPr-1…P1构成的海明码格式为HmHm-1…H3H2H1,m=k+r，则：PrPr-1…P1依次分布在H2r-1、H2r-2、…、H4、H2、H1上，DkDk-1…D1按序分布在剩余位置上。例如：5位信息码D5D4D3D2D1，需4位检验码P4P3P2P1，则9位海明码为：H9H8H7H6H5H4H3H2H1D5

P4

D4D3D2

P3

D1

P2

P1海明码编码规则-1第二十四页第二十五页，共81页。(2)校验关系指海明码中每个Hi由哪些P?来校验，关系为：被校验位位号=校验位位号之和。例如：H3对应H2、H1(3=2+1)，故H3处的D1由P2、P1校验H5对应H4、H1(5=4+1)，故H5处的D2由P3、P1校验H6对应H4、H2(6=4+2)，故H6处的D3由P3、P2校验H7对应H4、H2、H1(7=4+2+1)，故D4由P3、P2、P1校验H9对应H8、H1(9=8+1)，故D5在由P4、P1检验注意：由于H1、H2、H4、H8、H16…本身是检验位，因此不再由其他检验位进行检验。海明码编码规则-2第二十五页第二十六页，共81页。海明码编码规则-3(3)校验位的取值H9D5H8P4H7D4H6D3H5D2H4P3H3D1H2P2H1P1P4√√P3√√√√P2√√√√P1√√√√√按行采用偶校验，各校验位计算公式如下： P4=D5 P3=D4⊕D3⊕D2 P2=D4⊕D3⊕D1 P1=D5⊕D4⊕D2⊕D1第二十六页第二十七页，共81页。海明码解码在收到数据解码时，按奇偶校验码解码方式处理： S4=D5⊕P4 S3=D4⊕D3⊕D2⊕P3 S2=D4⊕D3⊕D1⊕P2 S1=D5⊕D4⊕D2⊕D1⊕P1若S4S3S2S1=0，说明传送无错,接收到的代码无错;若S4S3S2S1≠0,说明传送有错,此时S4S3S2S1代表的十进制数值就是出错的位号,故将SS3S2S1称为指误字(Symptom)。第二十七页第二十八页，共81页。海明码举例---一位出错例：假设海明码数据在传送时第5位发生错误。H9H8H7H6H5H4H3H2H1D5P4D4

D3

D2

P3

D1

P2

P1发送海明码00

0

1

0

1

0

1

0(如数字4,00100)接收的海明码0

0

0

1

1

1

0

1

0

出错则：S4=D5⊕P4=0 S3=D4⊕D3⊕D2⊕P3=0⊕1⊕1⊕1=1 S2=D4⊕D3⊕D1⊕P2=0⊕1⊕0⊕1=0 S1=D4⊕D2⊕D1⊕P1=0⊕1⊕0⊕0=1从而得到指误字S4S3S2S1=0101，说明H5(数据位D2)出错,将D2取反即可。第二十八页第二十九页，共81页。海明码举例---两位出错例：假设海明码数据在传送时第5、6位同时发生错误。H9H8H7H6H5H4H3H2H1D5P4D4

D3

D2

P3

D1

P2

P1发送海明码00

0

1

0

1

0

1

0(如数字4,00100)接收的海明码0

0

0

0

1

1

0

1

0

出错则：S4=D5⊕P4=0 S3=D4⊕D3⊕D2⊕P3=0⊕0⊕1⊕1=0 S2=D4⊕D3⊕D1⊕P2=0⊕0⊕0⊕1=1 S1=D4⊕D2⊕D1⊕P1=0⊕1⊕0⊕0=1从而得到指误字S4S3S2S1=0011，说明H3(数据位D1)出错，与事实不符。结论:海明码能查出2位以上的错误，但不能定位和纠错。第二十九页第三十页，共81页。海明码改进---纠一检两增加一个检验位，用于区分是一位错还是两位错。仍以5位数据为例，此时检验码需增加到5位，则P4P3P2P1编解码同前面方案，而P5位于H10，海明码格式如下：H10H9H8H7H6H5H4H3H2H1

P5D5P4D4

D3

D2

P3

D1

P2

P1且P5的编码为：P5=H1⊕H2⊕…⊕H9P5的解码为：S5=H1⊕H2⊕…⊕H9⊕H10(即P5)结论：当Si(i=1~5)全为0，表示接收无误；当S5=1，S4S3S2S1=0000，表示P5出错；当S5=1，S4S3S2S1≠0000，表示一位错，其值为出错位置；当S5=0，S4S3S2S1≠0000，表示两位错，错误位置不确定。第三十页第三十一页，共81页。检错纠错码小结(1)K位码有2K个编码状态，若全用于表示合法码，则任何一位出错，均会变成另一个合法码，不具有检错能力。(2)从一个合法码变成另一个合法码，至少要改变几位码的值，称为最小码距(码距)。(3)K+1位码，只用其2K个状态，可使码距为2,如果一个合法码中的一位错了，就成为非法码，通过检查码字的合法性，就得到检错能力，这就是奇偶校验码。第三十一页第三十二页，共81页。检错纠错能力(4)对k

位数据位，当给出r位校验位时，要发现并改正一位错，须满足如下关系：

2r>=k+r+1；

要发现并改正一位错，也能发现两位错,则应：

2r-1>=k+r

,此时码距为4。(5)若最小码距为d(d>=2), 能发现d-1位错，或改正(d-2)/2(取整)位错, 要发现l位错,并改正t位错，应满足如下条件:

d>=

l+t+1(l>=t)

第三十二页第三十三页，共81页。海明码练习---教材P75：7对8位数据进行检1纠1需4位校验位，检2纠1则需5位。H12D8H11D7H10D6H9D5H8P4H7D4H6D3H5D2H4P3H3D1H2P2H1P1P4√√√√√P3√√√√√P2√√√√√√P1√√√√√√数据01010111的5个校验位取值如下：P1=D7⊕D5⊕D4⊕D2⊕D1=1⊕1⊕0⊕1⊕1=0P2=D7⊕D6⊕D4⊕D3⊕D1=1⊕0⊕0⊕1⊕1=1P3=D8⊕D4⊕D3⊕D2=0⊕0⊕1⊕1=0P4=D8⊕D7⊕D6⊕D5=0⊕1⊕0⊕1=0P5=∑Hi=0海明码为：001010011011

0数据00000000，5个校验位取值如下：P1=D7⊕D5⊕D4⊕D2⊕D1=0P2=D7⊕D6⊕D4⊕D3⊕D1=0P3=D8⊕D4⊕D3⊕D2=0P4=D8⊕D7⊕D6⊕D5=0P5=∑Hi=0海明码为：00000000000数据01010111第三十三页第三十四页，共81页。海明码练习---教材P75：7若01010111的最低数据位由1变成0，即变成01010110，则： 原海明码001010011011

0 变成0010100110

1

1

0译码过程：S1=D7⊕D5⊕D4⊕D2⊕D1⊕P1=1⊕1⊕0⊕1⊕0⊕0=1S2=D7⊕D6⊕D4⊕D3⊕D1⊕P2=1⊕0⊕0⊕1⊕0⊕1=1S3=D8⊕D4⊕D3⊕D2⊕P3=0⊕0⊕1⊕1⊕0=0S4=D8⊕D7⊕D6⊕D5⊕P4=0⊕1⊕0⊕1⊕0=0S5=∑Hi=1根据译码结果知S5=1，表示1位错，错误位置在0011，即H3，故D1位错。第三十四页第三十五页，共81页。海明码练习---教材P75：7若00000000的最低、最高数据位由0变成1，即变成10000001，则原海明码000000000000

0 变成0

100000000

1

0

0译码过程：S1=D7⊕D5⊕D4⊕D2⊕D1⊕P1=0⊕0⊕0⊕0⊕1⊕0=1S2=D7⊕D6⊕D4⊕D3⊕D1⊕P2=0⊕0⊕0⊕0⊕1⊕0=1S3=D8⊕D4⊕D3⊕D2⊕P3=1S4=D8⊕D7⊕D6⊕D5⊕P4=1⊕0⊕0⊕0⊕0=1S5=∑Hi=0根据译码结果知S5=0，S4S3S2S1≠0000，故两位错，具体哪两位不知。第三十五页第三十六页，共81页。循环冗余校验(CyclicRedundancyCheck,CRC)码，简称CRC码，是一种检错、纠错能力很强的数据校验码，主要用于网络、同步通信及磁表面存储器等场合。CRC码格式CRC码的左边为信息位，右边为校验位。若信息位为n位，校验位为r位，则该校验码被称为(n+r,r)循环码。循环冗余校验码信息位校验位n位r位循环冗余校验码的格式第三十六页第三十七页，共81页。CRC编码步骤如下：(1)将待编码的n位有效信息位表示为一个n-1阶多项式M(x)。(2)将M(x)左移r位，得到M(x).xr（r由预选的r+1阶生成多项式G(x)决定）。(3)用预选的r+1阶生成多项式G(x)对M(x).xr作模2除法。(4)把左移r位后的的有效信息位与余数作模2加法，形成长度为n+r的CRC码。M(x).xr+R(x)＝Q(x).G(x)CRC编码方法M(x)·xrG(x)＝Q(x)＋R(x)G(x)第三十七页第三十八页，共81页。模2运算模2加减运算是指不考虑进/借位，即： 0±0＝0,0±1＝1,1±0＝1,1±1＝0， 实际是异或操作。模2除法的上商原则是当部分余数首位是1时，商取1，即使比除数小，反之商取0；然后按模2减求余数。当被除数除完时的余数就是校验位（比除数少一位）。

第三十八页第三十九页，共81页。CRC编码举例例：使用生成多项式为G(X)＝X3＋X＋1，把4位信息1100编成CRC码。解：步骤1：由于G(X)为3次多项式，故r取3，将信息码1100左移3位得11000000（相当于M(X)=X3+X2，M(X)·X3=X6+X5）步骤2：由于G(X)多项式系数对应1011，计算模2除法：1100000/1011，得商为1110，余数为010（相当于计算M(X)·X3/G(X)=(X6+X5)/(X3+X+1)，得Q(X)=X3+X2+X1，R(X)=X）步骤3：将1100000与余数010进行模2加，即1100000+010=1100010，1100010即为所求的CRC码（相当于计算M(X)·X3+R(X)）第三十九页第四十页，共81页。CRC码的纠错原理由于M(X).Xr＝Q(X).G(X)+R(X)，根据模2加的规则M(X).Xr+R(X)=Q(X).G(X)+R(X)+R(X)＝Q(X).G(X)上式表明,合法的CRC码应当能被生成多项式整除。若CRC码不能被生成多项式整除，说明出现差错。当出现信息的传送差错时，CRC码被生成多项式整除所得到的余数与出错位之间有唯一的对应关系,根据这一关系便可立即确定出错位的位置。若某位出错，则余数不为0，对此余数补0后继续作模2除法,此后余数将按一定顺序循环。对前例，形成010、100、011、110、111、101、001、010的循环，反复循环，这就是“循环码”一词的来源。第四十页第四十一页，共81页。CRC生成多项式的选择被用来生成CRC码的多项式一般满足下列要求：（1）任何一位出错都应使余数不为0。（2）不同位出错应使余数不同。（3）对余数继续作模2除法，应使余数循环。（4）必须是r次多项式，且Xr和X0的系数为1。生成多项式的选择主要靠经验，但已有几种多项式具有极高的检错率，被广泛运用，分别是:CRC12＝X12＋X11＋X3＋X2＋X＋1CRC16＝X16＋X15＋X2＋1CRCCCITT＝X16＋X12＋X5＋1第四十一页第四十二页，共81页。本章主要内容3.1信息编码、码制转换与检错纠错码3.2数据表示——常用的信息编码3.3二进制数值数据的编码与运算算法第四十二页第四十三页，共81页。+0.1011+1100–

1100–0.1011带符号的数符号数字化的数真值机器数

01011

11011

01100

11100小数点的位置数据的实际值被称为真值。数据在机器内要用规定的编码来表示，这种表示被称为机器数。机器数与真值第四十三页第四十四页，共81页。定点小数原码定义：[X]

原=实例：X=0.10110-0.101100.0000[X]原=0101101101100000010000

X1-X-1<X≤0

0≤X<1结论：原码为符号位加数的绝对值，0正1负原码零有两个编码，+0和-0编码不同原码难以用于加减运算，但乘除方便(原因?)第四十四页第四十五页，共81页。定点原码特点原码加减法困难：要比较参与加减运算的两个数的符号，还要比较它们的绝对值的大小，才能确定运算结果的数值和符号。原码乘除法方便：两个数的符号异或，数值相乘除即可。第四十五页第四十六页，共81页。定点小数反码定义：[X]反=实例：X=0.10110-0.101100.0000[X]反

=01011010100100000

11111X(2-2-n)+X-1<X≤0MOD(2-2-n)

0≤

X<1结论：负数反码为符号位跟每位数值位取反，0正1负

反码零有二个编码，分+0和-0

反码难以用于加减运算，有循环进位问题(举例?)第四十六页第四十七页，共81页。定点反码循环进位问题如：X=+0.1011，Y=-0.0100，[X]反=01011，[Y]反=11011[X]反+[Y]反=01011+11011=1

00110有进位，结果再加1，即00110+1=

00111又如：X=+0.1011，Y=0.0100，[X]反=01011[Y]反=00100[X]反+[Y]反=01011+00100=01111没有进位，01111就是最后结果。第四十七页第四十八页，共81页。定点小数模2补码定义：[X]补=实例：X=0.10110-0.101100.0000[X]补

=01011010101000000X2+X-1≤X≤0MOD2

0≤X<1结论：补码最高位是符号位，0正1负

补码表示为：2*符号位+数的真值

补码零只有一个编码，故能表示-1

补码能很好地用于加减（乘除）运算（举例？)第四十八页第四十九页，共81页。补码加减方便--示例X=+0.1010，Y=-0.0101，则[X]补=01010，[Y]补=11011

[X]补+[Y]补????

01010+11011

1001011丢掉(成进位C)00101是+0.0101的补码，而X+Y的结果为+0.0101结论：[X+Y]补=[X]补+[Y]补第四十九页第五十页，共81页。负数的[X]原、[X]反、[X]补之间的关系负数的[X]补与[X]反的关系根据定义：[X]补=2+X，[X]反

=(2–2-n)+X得：[X]补=[X]反

+2-n即：求负数补码的简便方法：[X]反加1；也即符号位取1，数值位取反，再加1。负数的[X]补与[X]原的相互转换简便方法均是符号位不变，数值位取反，再加1。第五十页第五十一页，共81页。补码与真值之间的关系假设：[X]补=X0.X1X2…Xn,则：当X>=0时，X0=0，[X]补=0.X1X2…Xn=X有：当X<0时，X0=1,[X]补=1.X1X2…Xn=2+X所以：X=1.X1X2…Xn–2=-1+0.X1X2…Xn=-X0+0.X1X2…Xn也有：结论：[X]补的负系数加数值部分，等于真值X例：[X]补=10110，则：X=-1+0.0110=-(1-0.0110)=-0.1010第五十一页第五十二页，共81页。<Ⅰ>[y]补=0y1

y2

yn…y=0.y1y2

yn…y=0.y1

y2

yn…[y]补=1y1

y2

yn+2-n…<Ⅱ>[y]补=1y1

y2

yn…[y]原=1y1y2

yn+2-n…

y=（0.y1y2

yn

+2-n）…

y=0.y1y2

yn+2-n……[y]补=0y1

y2

yn+2-n每位取反，即得[y]补[y]补连同符号位在内，末位加1每位取反，即得[y]补[y]补连同符号位在内，末位加1已知[y]补如何简单求[-y]补第五十二页第五十三页，共81页。整数的编码表示整数的原码

反码

补码表示与小数的三种表示基本相同，小数点在最低数值位的右侧N=NsNnNn-1……N2N1因此整数的取值范围与整数位数有关。(定点小数的取值范围与位数无关，精度与位数有关)例如：整数六位编码X=+01110[X]原=001110[X]补=001110X=-01110[X]原=101110[X]补=110010第五十三页第五十四页，共81页。原反补码表示小结正数的原码、反码、补码表示均相同，符号位为0，数值位同真值。零的原码和反码均有2个编码，补码只有1个负数的原码，反码，补码表示均不同，符号位为1，数值位：原码为数的绝对值反码为每一位均取反补码为反码再加1由[X]补求[-X]补：每一位取反后,再在最低位+1n由[X]补求X的真值：X=-X0+Xi*2-ii=1第五十四页第五十五页，共81页。补码加减法[X+Y]补=[X]补+[Y]补[X-Y]补=[X]补-[Y]补[X-Y]补=[X]补+[-Y]补说明减法可用加法实现如何求[-Y]补？对[Y]补逐位取反，末位再加1，得[-Y]补例：X=+0.1011y=-0.0101，求X+Y和X-Y。解：[X]补=01011,[Y]补=11011，[-Y]补=00101

01011+1101100110则[X+Y]补=00110故X+Y=0.0110

01011+00101

10000则[X-Y]补=10000故X-Y=-1.0000结果竟为负数？溢出了!0.1011-0.01010.01100.1011+0.01011.0000故X+Y=+0.0110X-Y=+1.0000人工算第五十五页第五十六页，共81页。补码加减法溢出判断(1)正+正得负或负+负得正(2)数字位向符号位有进位，但符号位不产生向更高位的进位(3)双符号位的值为01

或10前例：X=+0.1011，Y=-0.0101，采用双符号位（模4补码）[X]补=001011,[Y]补=111011 [-Y]补=000101

001011+000101

010000X-Y(溢出)

001011+1110111000110则[X+Y]补=000110故X+Y=0.0110[X]补+[Y]补[X]补+[-Y]补第五十六页第五十七页，共81页。FX实现补码加减运算的逻辑电路FsFALU目的寄存器源寄存器选通门二选通门选通门F1XYFYXF0101F/YFsOVRZC累加器减法：X

X-YＦ

ＸＦ

ＹＸ

ＦＦ

ＸＦ

/ＹＦ

1Ｘ

Ｆ加法：X

X+Y第五十七页第五十八页，共81页。溢出判断电路单符号位判断：正加正得负或负加负得正表明溢出第五十八页第五十九页，共81页。补码表示中的符号位扩展由[X]补求[X/2]补：

原符号位不变，且符号位与数值位均右移一位，例如，[X]补=10010则[X/2]补=110010不同位数的整数补码相加减时，位数少的补码数的符号位向左扩展，

0101101011+1

+0

0111101111第五十九页第六十页，共81页。补码计算练习教材P75：10、11第六十页第六十一页，共81页。第六十一页第六十二页，共81页。原码一位乘法

例如：X=0.1101Y=-0.10110.1101问题：*0.10111.加法器只有两个数据输入端11012.加法器与乘运算数据位数相同1101解决方案：00001.每次求出部分积，而不是一次总累加+1101变每次左移被乘数为右移部分积0.100011112.判乘数每一位的值用固定的一位线路

手工运算过程第六十二页第六十三页，共81页。

例如：X=0.1101Y=-0.10110.1101*0.1011

1101

11010000+11010.10001111

手工运算过程原码一位乘运算[X*Y]原=(XＳ⊕YＳ)(|X|*|X|)００００００累加器初值取零值+００１１０１００１１０１初值０加被乘数０００１１０１部分积右移+００１１０１０１００１１１前次部分积加被乘数００１００１１

１部分积右移+００００００００１００１１１前次部分积加０+００１１０１０００１００１１

１部分积右移０１０００１１１１前次部分积加０００１００１１１１１部分积右移两数符号再异或求积的符号，最终：X*Y=-0.10001111第六十三页第六十四页，共81页。实现原码一位乘法的逻辑线路图加法器部分积被乘数乘数

F最低位加运算移位线路每位1套

第i位第i位第i+1位第i-1位F/2→XF→XF*2→X移位电路把乘数放在一个移位寄存器中，该寄存起又用来接受加法器的移位输出，则判乘数的某一位也更方便第六十四页第六十五页，共81页。原码一位乘法0000001011加法器部分积被乘数乘数

F最低位加运算移位线路每位1套0000000011011011001101001101000110110110110100110100111101101111110010000010010001100010011011001001001001000100101100010011111101111111110100010100010010001111低位积

第六十五页第六十六页，共81页。已知：X=0.1001，Y=0.1101，计算X*Y。原码一位乘法运算例2部分积乘数００００００１１０１＋X

００

１００１

００１００１

１１０１右移一位

０００１００

１１１０＋0

００００００

０００１００

１１１０右移一位

００００１０

０１１１

＋X

００１００１００１０１１

０１１１右移一位

０００１０１

１０１１＋X

００１００１

００１１１０

１０１１右移一位

０００１１１

０１０１

乘积高位乘积低位

XY=０.０１１１０１０１

第六十六页第六十七页，共81页。除法运算在计算机内实现除运算时，存在与乘法运算类似的几个问题：加法器与寄存器的配合，被除数位数更长，商要一位一位地计算出来等。这可以用左移余数得到解决，且被除数的低位部分可以与最终的商合用同一个寄存器，余数与上商同时左移。第六十七页第六十八页，共81页。原码一位除运算 [Y/X]原=(XＳ⊕YＳ)(|Y|/|X|)原码一位除是指用原码表示的数相除，求出原码表示的商。除操作的过程中，每次求出一位商。恢复余数除法：确定上商应为１还是为０时，用被除数或中间余数减去除数，若求出一个为负的余数来，通常应首先恢复其值为正，再求下一位商。不恢复余数除法：但计算机内一般不用恢复余数除法，而是直接用求得的负余数求下一位商。

可以吗？为什么？第六十八页第六十九页，共81页。加减交替除法原理证明1.若第i-1次求商余数为+Ri-1，则商1，余数左移得2Ri-1。2.则第i次求商Ri=2Ri-1-Y3.则第i+1次求商Ri+1=2(Ri+Y)-Y

=2Ri+Y实质是:对上次负差直接左移,本次用+Y求商即可。若Ri

≥0则重复步1若Ri<0商0先恢复余数：Ri+Y，再左移：2(Ri+Y)第六十九页第七十页，共81页。00101111001111111011110000110100100101001011001100010100101011001111110111101000110100011100000开始情形-Y00000

<0,商000000左移1位+Y00001

>0,商100010左移1位-Y00011>0,商100110左移1位-Y00110<0,商001100左移1位+Y0110

1>0,商1被除数(余数)商+[-Y]补)X=0.1011Y=0.1101X/Y=?[|Y|]补=001101[-|Y|]补=110011原码一位除运算两数符号相同，故：X/Y=0.1101+[Y]补)+[-Y]补)+[-Y]补)+[Y]补)第七十页第七十一页，共81页。

F加法器A被除数(余数)B除数10与或门与或门2F→AF→AB→F/B→F

1→FC乘商寄存器上商与或门2C→C计数器Cd实现原码一位除法运算的原理逻辑图第七十一页第七十二页，共81页。教材P76：14、15乘除法练习第七十二页第七十三页，共81页。第七十三页第七十四页，共81页。补码一位乘法1.补码[X]补与真值X的转换公式设[X]补=X0.X1X2…Xn，有2.补码的右移[X]补扩展右移1位（即符号位右移且符号位取值不变），可得到[X/2]补。证明：即[X/2]补=X0X0X1X2…Xn第七十四页第七十五页，共81页。3.补码乘法规则设[X]补=X0X1X2…Xn，[Y]补=Y0Y1Y2…Yn，则证明略。将上式展开加以变换:[X*Y]补=[X]补*[-Y0+Y12-1+Y22-2+…+Yn2-n]=[X]补*[-Y0+(Y1-Y12-1)+(Y22-1-Y22-2)+…+(Yn2-(n-1)-Yn2-n)]=[X]补*[(Y1-Y0)+(Y2-Y1)2-1+…+(Yn-Yn-1)2-(n-1)+(0-Yn)2-n]

第七十五页第七十六页，共81页。写成递推公式如下：[Z0]补=0[Z1]补=2-1{[Z0]补+(Yn+1-Yn)[X]补}(yn+1=0)[Z2]补=2-1{[Z1]补+(Yn-Yn-1)[X]补}┇[Zi]补=2-1{[Zi-1]补+(Yn-i+2-Yn-i+1)[X]补}┇[Zn]补=2-1{[Zn-1]补+(Y2-Y1)[X]补}[Zn+1]补=[Zn]补+(Y1-Y0)[X]补=[X*Y]补Booth算法初始，部分积为0