第二章运算方法和运算器

第二章运算方法和运算器PrinciplesofComputerOrganization主讲教师：黄艺美UniversityofJinan12.1数据与文字的表示方法2.4定点除法运算2.3定点乘法运算2.2定点加法、减法运算2.5定点运算器的组成主要内容2.6浮点运算方法和浮点运算器2一、数据编码三、数的定点、浮点表示二、数的机器码表示2.1数据与文字的表示方法四、字符与字符串的表示方法五、汉字的表示方法六、校验码3数据编码计算机数据编码需要考虑的因素:数的类型(小数、整数、实数和复数）数值范围

数值精确度

数值存储和处理所需的硬件代价

日常生活：十进制计算机：二进制天生十个手指头0/1（开/关、低/高、真/假）0+1=1+0=11+1=00+0=0（用异或门实现）4几个概念长度：在同一计算机中，长度统一，不足补0。正负：最高位符号位（0:正、1:负）真值数：带正负号如：–0101100机器码：符号位和数值位一起编码如：10101100小数点：隐含的小数点位置可以固定，也可以可变。固定：定点数一般表示纯小数或纯整数可变：浮点数数值范围很大，硬件较复杂原码、反码、补码、移码5数的机器码表示正负问题计算机中数的表示：原码、反码、补码、移码机器数或机器码真值+0.1011+1100–

1100–0.10110

1011小数点的位置0

1100小数点的位置1

1100小数点的位置1

1011小数点的位置一般书写表示机器中编码表示6原码表示法整数x为真值n为整数的位数如x=+1110[x]原=01110[x]原=24+1110=11110x=1110[x]原=x0≤x＜2n2n

－x=2n＋|x|

－2n＜x≤0[x]原为机器数x=+0000[x]原=00000（正零）[x]原=24+0000=10000（负零）x=00007原码表示法小数x为真值如x=+0.1101[x]原=0.1101x=0.1101[x]原=1(0.1101)=1.1101x0≤x＜1[x]原=1－x=1＋|x|－1＜x≤0x=0.1000000[x]原=1(0.1000000)=1.1000000x=+0.1000000[x]原=0.1000000[x]原为机器数[+0]原=0.000…0[-0]原=1.000…08原码表示法原码为符号位加上数的绝对值，0正1负。简单、直观但是用原码作加法时，会出现如下问题：能否只作加法?

找到一个与负数等价的正数

来代替这个负数加法正正加加法正负加法负正加法负负减减加正可正可负可正可负负

要求

数1数2

实际操作结果符号9补码的概念假设要校准的时间为1点整。逆时针10－9＝1顺时针10＋3＝13两种方法：可见，减9和加3是等价的，即3是(-9)对12的补码，可以用数学公式表示：－9＝＋3(mod12)结论：负数用补码表示时,可以把减法转化为加法。同理：－4＝＋8(mod12)－5＝＋7(mod12)10模的概念一个负数加上“模”即得该负数的补数时钟的模数为12，可以把模定义为一个计量器的容量。例如：一个4位的计数器，它的计数值为0∼15。当计数器计满15之后再加1，这个计数器就发生溢出，其溢出量为16，也就是模等于16（即24，10000）。小数的溢出量为2，即以2为模。一个字长为n+1位的定点整数的溢出量为2n+1，即以2n+1为模。11补码表示法整数（mod

2n+1）如x=+1010[x]补=01010[x]补=27+1+（－1011000）=100000000－1011000

=10101000x=1011000[x]补=x0≤x＜2n2n+1

＋x=2n+1

－|x|

－2n≤x≤0对于0，[+0]补＝[-0]补＝0000

(mod

2n+1)

注意：0的补码表示只有一种形式。12补码表示法小数如x=+0.1011[x]补=0.1011x=0.1011[x]补=10＋(－0.1011)=1.0101x0≤x＜1[x]补=2＋

x=2－

|x|－1≤x≤0[+0]补＝[-0]补＝0.0000

(mod2)（mod

2）13求补码的快捷方式=100000=1011010101+1=10110又[x]原=11010则[x]补=24+11010=11111+11010=1111110101010当真值为负

时，补码

可用原码除符号位外每位取反，末位加1求得+1设x=1010时14举例解：x=+0.0001解：由定义得x=[x]补–2=1.0001–10.0000[x]原=1.11112、已知[x]补=1.0001求x[x]补[x]原

？由定义得1、已知[x]补=0.0001，求x∴x=0.1111–=0.1111–15举例解：x=[x]补–24+1

=11110–100000[x]原=10010[x]补[x]原

？∴x=0010=00103、已知[x]补=11110，求x由定义得x=－1×24＋1×23＋1×22＋1×21＋0×20=－16+14=－24、已知[x]补=01110，求x解：x=+1110由定义得x=0×24＋1×23＋1×22＋1×21＋0×20=1416反码表示法整数[x]反=x0≤x＜2n(2n+1

－1)＋x

－2n＜x≤0如x=+1101[x]反=01101=10010x=1101[x]反=(24+1－1)－1101=11111－110117反码表示法小数x=+0.1101[x]反=0.1101x=0.1010[x]反=(2–2-4)–0.1010=1.1111–0.1010=1.0101如[x]反=x0≤x＜1(2–2-n)+x－1＜x≤0[+0.0000]反=0.0000[+0]反=00000[

0.0000]反=1.1111[0]反=11111∴[+0]反≠[0]反

18小结对于正数，原码=补码=反码对于负数

，符号位为1，其数值部分原码除符号位外每位取反反码原码除符号位外每位取反末位加1补码原码为符号位加上数的绝对值，0正1负;[+0]原≠[0]原[+0]补＝[-0]补[+0]反≠[0]反

原码加减运算复杂。补码能很好用于加减运算。反码表示法可以解决负数的求补问题。19举例x=＋122，y=－122，求x、y的原码、反码、补码。解：x=(＋122)10=(＋1111010)2y=(－122)10=(－1111010)2[x]原=01111010[x]反=01111010[x]补=01111010[y]原=11111010[y]反=10000101[y]补=1000011020移码表示法补码表示很难直接判断其真值大小如十进制x=+21x=–21x=

+31x=–31大大错错010101101011011111100001+10101–

10101+11111–

11111二进制补码x+25+10101+100000+11111+10000010101+10000011111+100000大大正确正确=110101=001011=111111=00000121移码定义x为真值，n为整数的位数移码在数轴上的表示[x]移码2n+1–12n2n

–1–2n00真值如x=10100[x]移=25+10100x=–10100[x]移=25

–10100[x]移=2n+x（2n＞x

≥2n）=110100=00110022移码和补码的比较设x=+1100100[x]移=27+1100100[x]补=01100100设x=–1100100[x]移=27

–1100100[x]补=10011100补码与移码只差一个符号位=11100100=0001110023移码的特点当x=0时[+0]移=25+0当n=5时n=5时，移码的表示范围为000000～111111=100000=100000=000000[+0]移=[0]移[

100000]移=25

100000最小的真值为25=

100000[0]移=250最大的真值为25-1=011111[011111]移=25+011111=11111124小结数据四种机器表示法中：(1)移码表示法主要用于表示浮点数的阶码。(2)补码表示对加减法运算十分方便，因此目前机器中广泛采用补码表示法。(3)在一些机器中,数用补码形式表示、存储、运算。在有些机器中,数用原码进行存储和传送,运算时改用补码。还有些机器在做加减法时用补码运算,在做乘除法时用原码运算。25数的定点、浮点表示小数点问题定点表示（小数点位置固定，不使用“.”）浮点表示（小数点位置浮动）定点小数定点整数一般表示纯整数、纯小数目前多采用定点纯整数表示，称为整数运算26定点小数符号位小数点位置数值部分X0X1X2X3………Xn最低有效位最高有效位最大数值X0111……112-12-22-32-(n-1)2-n最大数值=2-1+2-2…+2-n=1-2-n

数的表示范围：0≤|x|≤1-2-n

最小数值=027定点整数最大数值2n2n-12n-22221最大数值=21+22…+2n=2n-1数的表示范围：0≤|x|≤2n-1最小数值=0符号位小数点位置数值部分X0X1X2X3………Xn最高有效位最低有效位X0X1X2X3………Xn28举例设机器字长16位,定点表示,尾数15位,数符1位,问：定点原码整数表示时,最大正数是多少?最小负数是多少?解：定点原码整数表示：最大正数：0111111111111111x=(215－1)10=(＋32767)10最小负数：1111111111111111x=－(215－1)10=(－32767)1029浮点数通过小数点移动改变数的大小如：0.2×1034=0.02×1035N=M×RE当R=2时，M尾数E阶码R基数（基值）N=11.0101=0.110101×210=1.10101×21=1101.01×2-10

=0.00110101×2100

规格化数二进制表示计算机中M小数、可正可负E整数、可正可负30浮点数ES

E1

E2

Em

MS

M1M2

Mn

……E

阶码M

尾数阶符数符阶码的数值部分尾数的数值部分小数点位置MS代表浮点数的符号n其位数反映浮点数的精度m其位数反映浮点数的表示范围ES和m共同表示小数点的实际位置31浮点数的标准格式IEEE754标准：尾数用原码；阶码用移码，基为2。SEM31302322032位SEM63625251064位S：尾数符号，0正1负；M：尾数,纯小数表示,小数点放在尾数域的最前面。原码。E：阶码，采用移码表示（移码可表示阶符）;阶符采用隐含方式，即采用移码方法来表示正负指数。32浮点数的规格化表示非“0”的有效位最高位为“1”(尾数的绝对值>=1/2)一个浮点数有不同的表示：1.11；0.11121；0.011122；11.12-1规格化表示：如：0.1000101010规格化处理：通过尾数移位和修改阶码实现。隐藏位技术：尾数域最左位总是1，保存时左移去掉。执行运算时恢复。如：0.11000101.10001033规格化浮点数的真值x=

(-1)s

(1.Ｍ)2Ｅ－127e=Ｅ–127一个规格化的32位浮点数ｘ的真值为：32位浮点数格式：移码定义：SEM313023220[x]移=2n+x（2n＞x

≥2n）一个规格化的64位浮点数ｘ的真值为：x=

(-1)s

(1.Ｍ)2Ｅ－1023e=Ｅ–102334举例1、若浮点数x的754标准存储格式为(41360000)16,求其32位浮点数的十进制值。解：01000001

001101100000000000000000包括隐藏位1的尾数：1.M＝1.01101100000000000000000＝1.011011于是有x＝(－1)s×1.M×2e

＝＋(1.011011)×23＝＋1011.011＝(11.375)10指数e＝阶码－127＝10000010－01111111＝00000011=(3)10S阶码(8位)尾数(23位)35举例2、将十进制数20.59375转换成754标准的32位浮点数的二进制格式来存储。解：20.59375＝10100.10011＝1.010010011×24

S＝0，E＝4＋127＝131=10000011，M＝010010011e=4最后得到32位浮点数的二进制存储格式为:01000001101001001100000000000000＝(41A4C000)16

36举例3、假设由S,E,M三个域组成的一个32位二进制字所表示的非零规格化浮点数x,真值表示为：x＝(－1)s×(1.M)×2E－128问：它所表示的规格化的最大正数、最小正数、最大负数、最小负数是多少？(3)最小负数

111111111111

11111111111111111111

x＝－[1＋(1－2－23)]×2127(4)最大负数

100000000000

00000000000000000000

x＝－1.0×2－128

解：(1)最大正数01111111111111111111111111111111

x＝[1＋(1－2-23)]×2127

(2)最小正数

000000000000

00000000000000000000

x＝1.0×2－12837十进制数串的表示方法目前，大多数通用性较强的计算机都能直接处理十进制形式表示的数据。字符串形式：一个字节存放一个十进制的数位或符号位。在主存中，一个十进制数占用连续的多个字节。压缩的十进制数串形式：一个字节存放两个十进制的数位。每个数位占用半个字节(即4个二进制位),其值可用二－十编码(BCD码)或数字符的ASCII码的低4位表示。123C012D+123-1238字符与字符串的表示方法现代计算机处理：数值领域的问题和非数值领域的问题。非数值领域的问题需引入文字、字母以及某些专用符号，以便表示文字语言、逻辑语言等信息。目前，国际上普遍采用的字符系统——ASCII码(美国国家信息交换标准字符码)总共128个元素，7位二进制编码，加上一个偶校验位，共8位一个字节。字符串是指连续的一串字符，通常方式下，占用主存中连续的多个字节，每个字节存放一个字符。39ASCII码字符编码表40汉字的表示方法输入编码

数字编码（国标区位码）、拼音码、字形编码

汉字内码

用于汉字信息的存储、交换、检索等操作，一般采用两个字节。为了能区分汉字与ASCII码，两个字节最高位均规定为1。汉字字模码

用点阵表示的汉字字形代码，是汉字的输出形式。所谓点阵，实际上就是一组二进制数。一个m行n列的点阵共有m×n个点。每个点可以是“黑”(1)点或“白”(0)点。注意：汉字的输入编码、汉字内码、字模码是计算机中用于输入、内部处理、输出三种不同用途的编码，不要混为一谈。41校验码元件故障、噪声干扰等因素常常引发错误。可采用专门的逻辑线路进行编码检测、校正错误。通常的方法：在每个字上添加一些校验位，用来确定字中出现错误的位置。常用方法：奇偶校验码；海明校验与纠错码；循环冗余校验码。42奇偶校验原理：在k位数据码之外增加1位校验位，使k+1位码字中取值为1的位数保持为偶数（偶校验）或奇数（奇校验）偶校验奇校验校验位00010001100010

0101010100101

1原有数据位

两个新的码字例如：43校验码设x＝(x0

x1…xn-1)是一个n位字,则奇校验位Ｃ定义为:C＝x0⊕x1⊕…⊕xn-1按位加x中包含奇数个1时，C=1，C=0。偶校验位Ｃ定义为:C＝x0⊕x1⊕…⊕xn-1x中包含偶数个1时，C=0。44举例已知下表中左面一栏有5个字节的数据。请分别用奇校验和偶校验进行编码。数据偶校验编码Ｃ奇校验编码Ｃ101010100101010000000000011111111111111110101010010101000000000001111111111111111010101001010100000000000111111111111111010101010145校验方法（偶校验）发送：x0

x1…xn-1C（算出C加到需发送字的后面）接收：x0'

x1'

…xn-1

'

C'

计算：F＝x'0⊕x'1⊕…⊕x'n-1⊕C'结果：若F＝1，意味着收到的信息有错；若F＝0，表明x字传送正确。奇偶校验可提供单个错误检测，但无法检测多个错误，更无法识别错误信息的位置及纠正错误。46一、补码加法三、溢出概念与检测方法二、补码减法2.2定点加法、减法运算四、基本的二进制加法/减法器47补码加法整数[x]补+[y]补=[x+y]补（mod2n+1）小数[x]补+[y]补=[x+y]补（mod2）特点：不需要事先判断符号，符号位与码值位一起参加运算。符号位相加后若有进位，则舍去该进位数字。x0≤x＜1[x]补=2＋

x=2－

|x|－1≤x≤0（mod

2）公式证明：（以定点小数为例）证明的先决条件：︱x︱﹤1,︱y︱﹤1,︱x＋y︱﹤1。证明的依据：48公式证明(1)x﹥0,y﹥0,则x＋y﹥0。[x]补＋[y]补＝x＋y＝[x＋y]补(mod2)(2)x﹥0,y﹤0,则x＋y>0或x＋y<0。[x]补＝x,[y]补＝2＋y

[x]补＋[y]补＝x＋2＋y＝2＋(x＋y)

当x+y>0时,2+(x+y)>2,进位2舍去。

[x]补＋[y]补＝x＋y＝[x＋y]补(mod2)当x+y<0时,2+(x+y)<2,又因(x+y)<0，[x]补＋[y]补＝2＋(x＋y)＝[x＋y]补(mod2)49公式证明(3)x<0,y>0,则x＋y>0或x＋y<0。

证明同(2)(4)x<0,y<0,则x＋y<0。

相加两数都是负数,则其和也一定是负数。∵[x]补＝2＋x,[y]补＝2＋y∴[x]补＋[y]补＝2＋x＋2＋y＝2＋(2＋x＋y)

因为|x＋y|<1,1<(2＋x＋y)<2,2＋(2＋x＋y)>2，进位2必丢失。又因x+y<0，故

[x]补＋[y]补＝2＋(x＋y)＝[x＋y]补(mod2)50结论在模2意义下，任意两数的补码之和等于该两数之和的补码。其结论也适用于定点整数。补码加法的特点：

（1）符号位要作为数的一部分一起参加运算；（2）在模2的意义下相加，即大于2的进位要丢掉。51举例1、x＝0.1001,y＝0.0101,求x＋y。解:[x]补＝0.1001,[y]补＝0.0101[x]补0.1001＋[y]补0.0101[x＋y]补0.1110所以x＋y＝＋0.111052举例2、x＝＋0.1011,y＝－0.0101,求x＋y。所以x＋y＝0.0110解:[x]补＝0.1011,[y]补＝1.1011[x]补0.1011＋[y]补1.1011[x＋y]补10.011053举例3、x＝＋1011,y＝－0101,求x＋y。所以x＋y＝＋0110解:[x]补＝01011,[y]补＝11011[x]补01011＋[y]补11011[x＋y]补10011054补码减法x–y=x+(–y

)整数[x

–y]补=[x]补–[y]补=[x]补+[

–

y]补(mod2n+1)小数[x

–y]补=[x]补–[y]补(mod2)公式证明：[–y]补＝–[y]补=[x]补+[

–

y]补[

–

y]补+[y]补=[y+(–y)]补=[0]补=0故[–y]补=–[y]补由[y]补求[

–

y]补的法则是：包括符号位“求反末位加1”。55举例1、已知:x1=–0.1110,x2=+0.1101,求：[x1]补,[–

x1]补,[x2]补,[–

x2]补。解:[x1]补=[–0.1110]补=1.0010

[–

x1]补

=[0.1110]补=0.1110[x2]补=[+0.1101]补=0.1101[–

x2]补=[–0.1101]补=1.001156举例2、x=+0.1101,y=+0.0110,求x–

y。解:[x]补=0.1101[y]补=0.0110,[–

y]补=1.1010[x]补0.1101+[–

y]补1.1010[x–

y]补10.0111所以x–

y=+0.011157举例3、x=–0.1101,y=–0.0110,求x–

y。解:[x]补=1.0011[y]补=1.1010,[–

y]补=0.0110[x]补1.0011+[–

y]补0.0110[x–

y]补1.1001所以x–

y=–

0.011158溢出概念与检测方法在定点小数机器中，数的表示范围为|ｘ|<1。在运算过程中如出现大于1的现象,称为“溢出”。机器定点小数表示上溢下溢例如：x=+0.1011,y=+0.1001,x+y=1.0100；正溢x=–0.1101,y=–0.1011，x+y=0.1000；负溢59溢出的检测方法(1)双符号位法（变形补码/模4补码）[x]补'

=

x1＞x≥04+x0＞x≥–1（mod4）[x]补'+[y]补'=[x+y]补'（mod4）[x

–y]补'=[x]补'+[–

y]补'（mod4）结果的双符号位相同未溢出结果的双符号位不同溢出最高符号位

代表其真正的符号00.×××××11.×××××10.×××××01.×××××60举例1、x=+0.1100,y=+0.1000,求x+y。

解：[x]补=00.1100

[y]补=00.1000[x+y]补=[x]补

+

[y]补

=00.1100+00.1000=01.1000

两个符号位出现“01”，表示已正溢出，即结果大于+1。2、x=–0.1100,y=–0.1000,求x+y。

解：[x]补=11.0100

[y]补=11.1000[x+y]补=[x]补

+

[y]补

=11.0100+11.1000=10.1100

两个符号位出现“10”，表示已负溢出，即结果小于–1。61溢出的检测方法(2)单符号位法硬件实现最高有效位的进位符号位的进位=1溢出[x]补

00.1100+[y]补

00.1000

01.1000[x]补

11.0100+[y]补

11.1000

10.1100溢出：最高有效位溢出（正溢）或符号位溢出（负溢）正数相加为负数或负数相加为正数则产生溢出（结果符号与操作数符号不同）62基本的二进制加法/减法器“1/0”逻辑属性“有/无”、“真/假”、“是/非”逻辑运算：与（全1为1）、或（有1为1）、非交换律：A+B=B+AA·B=B·A结合律：A+(B+C)=(A+B)+CA·(B·C)=(A·B)·C分配律：A+B·C=(A+B)·(A+C)A·(B+C)=A·B+A·C吸收律：A+A·B=AA·(A+B)=A第二吸收律：A+A·B=A+BA·(A+B)=A·B63逻辑运算重叠律：A+A=AA·A=A0-1律：0+A=A1·A=A0·A=01+A=1互补律：A+A=1A·A=0反演律：A+B=A·BA·B=A+B包含律：A·B+A·C+B·C=A·B+A·C(A+B)·(A+C)·(B+C)=(A+B)·(A+C)64逻辑门65一位全加器一位全加器真值表输入输出AiBiCiSiCi＋10000000110010100110110010101011100111111加法运算：Ai+Bi+Ci=Si(Ci+1)加数进位输入和进位输出Si＝Ai⊕Bi⊕CiCi＋1＝AiBi＋BiCi＋CiAiCi＋1=AiBi·(Ci·(Ai⊕Bi))66一位全加器一位全加器逻辑图Si＝Ai⊕Bi⊕CiCi＋1＝AiBi＋BiCi＋CiAiCi＋1=AiBi·(Ci·(Ai⊕Bi))与非门异或门n个1位的全加器(FA)可级联成一个n位的行波进位加减器。一位全加器逻辑符号67n位行波进位加减器加法运算M=0；减法运算M=1,A–B=[A]补+[–B]补；求补过程由B＋1来实现；溢出检测：单符号位法。68时间延迟ta=n·2T+9T=(2n+9)T(1)对一位全加器(FA)来说，Si的时间延迟为6T(每级异或门延迟3T)；Ci＋1的时间延迟为5T。T3T(2)n位行波进位加法器的延迟时间ta为:考虑溢出检测时，有：•9T为最低位上的两极“异或”门再加上溢出“异或”门的总时间；•2T为每级进位链的延迟时间。

ta为在加法器的输入端输入加数和被加数后,在最坏的情况下加法器输出端得到稳定的求和输出所需要的最长时间。越小越好。69时间延迟0Bi,Ai(i=0,1,2,…n-1)C0输入3T所有Bi与M异或完毕进入FA完成必需的第0级FA的A0B0,同时也完成了AiBi(i=1,2,…,n-1)3T2TC1C2C32T2T3T3T3TCn-1Cn2T3TS0S1S2Sn-13T异或门检测输出ta＝n·2T＋9T＝(2n＋9)T70时间延迟C1C2C3Cn-2Cn-10Bi,Ai(i=0,1,2,…n-1)C0输入3T所有Bi与M异或完毕进入FA完成必需的第0级FA的A0B0,同时也完成了AiBi(i=1,2,…,n-1)3T2T2T2T3T3T3T2T3TS0S1S2Sn-1ta＝(n-1)·2T＋9T71一、原码一位乘法三、原码并行乘法二、补码一位乘法2.3定点乘法运算四、补码并行乘法72分析笔算乘法A=–0.1101B=0.1011A×B=–0.100011110.11010.101111011101000011010.10001111符号位单独处理乘数的某一位决定是否加被乘数4个位积一起相加乘积的位数扩大一倍×乘积的符号心算求得

？？73改进A

•B=A

•0.1011=0.1A+0.00A+0.001A+0.0001A=0.1A+0.00A+0.001(A+0.1A)=0.1A+0.01[0•

A+0.1(A+0.1A)]=0.1{A+0.1[0•

A+0.1(A+0.1A)]}=2-1{A

+2-1[0•

A+2-1(A

+

2-1(A+0))]}①②⑧第一步被乘数A

+0第二步右移一位，得新的部分积第八步右移一位，得结果③第三步部分积

+

被乘数…右移一位74改进后的乘法过程0.00000.11010.11010.11010.00000.1101初态，部分积=0乘数为1，加被乘数乘数为1，加被乘数乘数为0，加01.00110.10011.0001乘数为1，加被乘数0.100011111，得结果1011=0.01101，形成新的部分积1101=0.10011，形成新的部分积11

10=0.01001，形成新的部分积111

1=部分积乘数说明＋＋＋＋75小结

被乘数只与部分积的高位相加

由乘数的末位决定被乘数是否与原部分积相加，然后1位形成新的部分积，同时乘数1

位（末位移丢），空出高位存放部分积的低位。硬件3

个寄存器，具有移位功能1

个全加器乘法

运算可用加和移位实现

n=4，加4次，移4次76原码一位乘法以小数为例设[x]原=0.x1x2

xn…[y]原=0.y1y2

yn…x•

y=x(0.y1y2

yn)…=x(y12-1+y22-2++yn2-n)…=2-1(y1x+2-1(y2x+2-1(ynx+0)))……z1znz0=0z1=2-1(ynx+z0)z2=2-1(yn-1x+z1)zn=2-1(y1x+zn-1)……z0每次只要相加两个数再右移一位。77举例0.00000.11100.11100.00000.11100.1110部分积初态z0=0部分积乘数说明0.01111.00011.01100.101101101，得

z41101=0.01111，得

z10

110=0.00111，得

z210

11=0.10001，得

z3110

1=+++++x+0+x+x已知x=–0.1110y=0.1101求x•y=–0.1011011078时间延迟总时间为：tm=n(ta+tr)其中：ta为加法器执行一次加法操作的时间；

tr为执行一次移位操作的时间。

原码一位乘法的主要问题是：符号位不能参与运算，而补码乘法可以实现符号位直接参与运算。采用比较法。比较法是Booth夫妇首先提出来的，又称Booth算法。79补码一位乘法设[x]补=x0.x1x2

xn[y]补=y0.y1y2

yn……真值与补码的关系：x=-x0+[x·y]补=[x]补·y或：[x·y]补=[x]补·有补码乘法算式：80补码一位乘法设[x]补=x0.x1x2

xn[y]补=y0.y1y2

yn……[x

·y]补=[x]补(0.y1

yn)–[x]补

·y0…=[x]补(y12-1+y22-2++yn2-n)–[x]补

·y0…=[x]补(–y0+y1

2-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)]…y12-1++…yn

2-n–[x]补=+[–x]补

2-1=20

–2-12-2=2-1

–2-22-12-2=[x]补[(y1–y0)+(y2–y1)2-1++(yn+1–yn)2-n]…

附加位

yn+181补码一位乘法[z0]补=0[z1]补=2-1{(yn+1–yn)[x]补+[z0]补}yn+1=0[zn]补=2-1{(y2–y1)[x]补+[zn-1]补}…[x

·

y]补=[zn]补+(y1–y0)[x]补最后一步不移位如何实现

yi+1–yi

?000110111+[x]补

1+[–x]补

1101-10yi

yi+1操作yi+1–yi82已知x=+0.0011y=–0.1011求[x·y]补解：00.000011.110111.110100.001111.110100.001111.11011.0101000.0001111.11011100.000111111.11011111

[x]补=0.0011

[y]补=1.0101[–x]补=1.1101+[–x]补11.111011010

11+[x]补00.00001110101+[–x]补11.1110111101100.00001111101+[–x]补+[x]补∴

[x·y]补=1.11011111最后一步不移位6.3补码右移补码右移补码右移补码右移+++++83时间延迟总时间为：tm=(n+1)ta+ntr其中：ta为加法器执行一次加法操作的时间；

tr为执行一次移位操作的时间。串行1位乘法的优劣：不需要很多器件，硬件结构简单；速度太慢，执行一次乘法操作的时间至少是加法操作的n倍；已被淘汰。由于乘法操作大约占全部算术运算的1/3，故采用高速乘法部件是非常必要的。84原码并行乘法不带符号的阵列乘法器设有两个不带符号的二进制整数A＝am－1…a1a0,B＝bn－1…b1b0它们的数值分别为a和b,即：m-1a＝∑ai2ii＝0n-1b＝∑bj2jj＝0在二进制乘法中,被乘数A与乘数B相乘,产生m＋n位乘积P：

P＝pm＋n－1…p1p0

乘积P的数值为:85不带符号的阵列乘法器

am-1am-2···

a1a0

)

bn-1···

b1b0

am-1b0am-2b0···

a1b0a0b0

am-1b1am-2b1···

a1b1a0b1......+)

am-1bn-1am-2bn-1

···

a1bn-1a0bn-1pm+n-1pm+n-2pm+n-3···

pn-1···p1

p0运算过程86不带符号的阵列乘法器m×n位不带符号阵列乘法器逻辑框图n(n－1)个全加器n×n位时n2个与门n×n位时87不带符号的阵列乘法器11011(x)

×10101(y)11011000001101100000+110111000110111(z)例如88不带符号的阵列乘法器2T6T6T6T6T6T6T2T2T2T2T2T2T2T6T6T6T6Ttm＝Ta＋(n-2)×6T＋(n-1)×Tf+6T

2T89时间延迟令Ta为“与门”的传输延迟时间，Tf为全加器(FA)的进位传输延迟时间，假定用2级“与非”逻辑来实现FA的进位链功能，有：

Ta＝Tf＝2T

从演示中可知，最坏情况下延迟途径,即是沿着矩阵P4垂直线和最下面的一行。因而得n位×n位不带符号的阵列乘法器总的乘法时间为：tm＝Ta

＋(n－2)×6T＋

(n-1)

×Tf+6T＝2T＋(n－2)×6T＋

(n-1)

×2T+6T

＝(8n－6)T

90举例已知两个不带符号的二进制整数A＝11011,B＝10101,求每一部分乘积项aibj的值与p9p8……p0的值。11011=A(2710)

10101=B(2110)11011000001101100000+110111000110111=P91举例解:a4b0＝1a3b0＝1a2b0＝0a1b0＝1a0b0＝1a4b1＝0a3b1＝0a2b1＝0a1b1＝0a0b1＝0a4b2＝1a3b2＝1a2b2＝0a1b2＝1a0b2＝0a4b3＝0a3b3＝0a2b3＝0a1b3＝0a0b3＝0a4b4＝1a3b4＝1a2b4＝0a1b4＝1a0b4＝1P＝p9p8p7p6p5p4p3p2p1p0＝1000110111(56710)92带符号的阵列乘法器对2求补：

1100——001110100

101

1——01001

0101方法：从数的最右端a0开始,由右向左,直到找出第一个“1”,例如ai＝1,0≤i≤n。这样,ai以左的每一个输入位都求反,即1变0,0变1。93对2求补器电路图101010110E：符号位3T2T2T时间延迟：tTC=n·2T+5T=(2n+5)T（n+1位数）94带求补级的阵列乘法器95带符号的阵列乘法器包括求补级的乘法器又称为符号求补的阵列乘法器。在这种逻辑结构中，共使用三个求补器:•两个算前求补器作用是：将两个操作数A和B在被不带符号的乘法阵列(核心部件)相乘以前，先变成正整数。•算后求补器作用是：当两个输入操作数的符号不一致时，把运算结果变成带符号的数。结构:96带符号的阵列乘法器设A=anan-1…a1a0和B=bnbn-1…b1b0均为用定点表示的(n＋1)位带符号整数。在必要的求补操作以后，A和B的码值输送给n×n位不带符号的阵列乘法器，并由此产生2n位的乘积，其中P2n为符号位。A·B＝P＝p2n－1…p1p0p2n＝an⊕bn运算:带求补级的阵列乘法器既适用于原码乘法，也适用于间接的补码乘法。在原码乘法中，算前求补和算后求补都不需要，因为输入的数据都是立即可用的。97举例设x=+15，y=–

13，用带求补器的原码阵列乘法求出乘积x·y=？解：设最高位为符号位，输入数据为原码：

[x]原=01111

[y]原=11101因符号单独考虑，所以：|x|=1111，|y|=1101

1111

×

1101

1111

0000

1111

+

1111

11000011符号位运算：0⊕1=1[x×y]原=111000011

x·y=(–11000011)2=(–195)10验证：15×(–13)=19598举例设x=15(+1111B)，y=–

13(–1101B)，用带求补器的补码阵列乘法求出乘积x·y=？

解：设最高位为符号位，输入数据用补码表示：

[x]补=01111

[y]补=10011算前求补器输出为|x|=1111，|y|=1101

1111

×

1101

1111

0000

1111

+

1111

11000011符号位运算：0⊕1=1，乘积为负算后求补：[x·y]补=100111101

x·y=–1×28+1×25+1×24+1×23+1×22+1×20=(–195)10验证15×(–13)=–19599一、原码除法算法原理二、并行除法器2.4定点除法运算100分析笔算除法x=–0.1011y=0.1101求x÷y0.10110.1101⌒0.011010.010010.0011010.0001010.000011010.000001111商符单独处理心算上商余数不动低位补“0”减右移一位的除数上商位置不固定x÷y=–0.1101余数0.00000111商符心算求得00.101000

？？？101原码除法算法原理笔算除法机器除法商符单独处理心算上商符号位异或形成|x|–|y|＞0上商1|x|–|y|＜0上商0余数不动

低位补“0”减右移一位

的除数2倍字长加法器上商位置不固定余数左移一位

低位补“0”减

除数1倍字长加法器在寄存器最末位上商102原码除法算法原理机器不会心算，必须先作减法，若余数为正，才知道够减；若余数为负，才知道不够减。不够减时必须恢复原来的余数，以便再继续往下运算。这种方法称为恢复余数法。要恢复原来的余数，只要当前的余数加上除数即可。但由于要恢复余数，使除法进行过程的步数不固定，因此控制比较复杂。实际中常用不恢复余数法，又称加减交替法。其特点是运算过程中如出现不够减，则不必恢复余数，根据余数符号，可以继续往下运算，因此步数固定，控制简单。103恢复余数法0.10111.00111.00111.00110.0000+[–y*]补01.1110余数为负，上商00.1101恢复余数00.1001余数为正，上商1+[–y*]补1.0110011.0010011+[–y*]补解：被除数（余数）商说明[x]原=1.1011[y]原

=1.1101x=–0.1011

y=–0.1101求[]原

xy10.1011恢复后的余数0+[y*]补[y*]补=0.1101[–y*]补