浮点数计算方法.ppt

第二章运算方法和运算器 2 1数据与文字的表示方法2 2定点加法 减法运算2 3定点乘法运算2 4定点除法运算2 5定点运算器的组成2 6浮点运算方法和浮点运算器 2 1数据与文字的表示方法2 1 1数据格式 计算机中常用的数据表示格式有两种 1定点格式2浮点格式一般来说 定点格式容许的数值范围有限 但要求的处理硬件比较简单 而浮点格式容许的数值范围很大 但要求的处理硬件比较复杂 1 定点数的表示方法 定点表示 约定机器中所有数据的小数点位置是固定不变的 由于约定在固定的位置 小数点就不再使用记号 来表示 通常将数据表示成纯小数或纯整数 定点数 0 1 2 n在定点机中表示如下 0 符号位 0代表正号 1代表负号 纯小数的表示范围为 0 1 2 n各位均为0时最小 各位均为1时最大 0 1 2 n 2 1 纯整数的表示范围为0 2n 1 2 2 目前计算机中多采用定点纯整数表示 因此将定点数表示的运算简称为整数运算 电子的质量 9 10 28克 和太阳的质量 2 1033克 相差甚远 在定点计算机中无法直接来表示这个数值范围 要使它们送入定点计算机进行某种运算 必须对它们分别取不同的比例因子 使其数值部分绝对值小于1 即 9 10 28 0 9 10 272 1033 0 2 1034这里的比例因子10 27和1034要分别存放在机器的某个存储单元中 以便以后对计算结果按这个比例增大 显然这要占用一定的存储空间和运算时间 因此得到浮点表示法如下 2 浮点数的表示方法 浮点表示法 把一个数的有效数字和数的范围在计算机的一个存储单元中分别予以表示 这种把数的范围和精度分别表示的方法 相当于数的小数点位置随比例因子的不同而在一定范围内自由浮动 称为浮点表示法 任意一个十进制数 可以写成 10E 2 3 同样在计算机中一个任意进制数 可以写成 e 2 4 尾数 是一个纯小数 e 比例因子的指数 称为浮点数的指数 是一个整数 R 比例因子的基数 对于二进计数值的机器是一个常数 一般规定 为2 8或16 一个机器浮点数由阶码和尾数及其符号位组成 尾数 用定点小数表示 给出有效数字的位数决定了浮点数的表示精度 阶码 用整数形式表示 指明小数点在数据中的位置 决定了浮点数的表示范围 32位浮点数的IEEE754标准格式为 64位浮点数的IEEE754标准格式为 在IEEE754标准格式表示的32位浮点数中 浮点数的符号位 1位 0表示正数 1表示负数 尾数 23位 用小数表示 小数点放在尾数域的最前面 阶码 8位阶符采用隐含方式 即采用移码方式来表示正负指数 移码方法对两个指数大小的比较和对阶操作都比较方便 因为阶码域值大者其指数值也大 采用这种方式时 将浮点数的指数真值e变成阶码 时 应将指数e加上一个固定的偏移值127 01111111 即 e 127 IEEE754标准中 一个规格化的32位浮点数 的真值可表示为 1 s 1 2 127e 127一个规格化的64位浮点数 的真值为 1 s 1 2 1023e 1023为提高数据的表示精度 当尾数的值不为0时 尾数域的最高有效位应为1 否则以修改阶码同时左右移小数点的办法 使其变成这一表示形式 这称为浮点数的规格化表示 当浮点数的尾数为0 不论其阶码为何值 或者当阶码的值遇到比它能表示的最小值还小时 不管其尾数为何值 计算机都把该浮点数看成零值 称为机器零 当阶码E为全0且尾数M也为全0时 表示的真值x为零 结合符号位S为0或1 有正零和负零之分 当阶码E为全1且尾数M为全0时 表示的真值x为无穷大 结合符号位S为0或1 也有 和 之分 这样在32位浮点数表示中 要除去E用全0和全1 255 10表示零和无穷大的特殊情况 指数的偏移值不选128 10000000 而选127 01111111 对于规格化浮点数 E的范围变为1到254 真正的指数值e则为 126到 127 因此32位浮点数表示的绝对值的范围是10 38 1038 以10的幂表示 浮点数所表示的范围远比定点数大 一台计算机中究竟采用定点表示还是浮点表示 要根据计算机的使用条件来确定 一般在高档微机以上的计算机中同时采用定点 浮点表示 由使用者进行选择 而单片机中多采用定点表示 例1 若浮点数 的754标准存储格式为 41360000 16 求其浮点数的十进制数值 例2 将 20 59375 10转换成754标准的32位浮点数的二进制存储格式 例1 若浮点数 的754标准存储格式为 41360000 16 求其浮点数的十进制数值 解 将十六进制数展开后 可得二进制数格式为指数e 阶码 127 10000010 01111111 00000011 3 10包括隐藏位1的尾数1 M 1 01101100000000000000000 1 011011于是有 1 s 1 M 2e 1 011011 23 1011 011 11 375 10 例2 将 20 59375 10转换成754标准的32位浮点数的二进制存储格式 解 首先分别将整数和分数部分转换成二进制数 20 59375 10100 10011然后移动小数点 使其在第1 2位之间10100 10011 1 010010011 24e 4于是得到 S 0 E 4 127 131 M 010010011最后得到32位浮点数的二进制存储格式为 01000001101001001100000000000000 41A4C000 16 3 十进制数串的表示方法 目前 大多数通用性较强的计算机都能直接处理十进制形式表示的数据 十进制数串在计算机内主要有两种表示形式 1 字符串形式 一个字节存放一个十进制的数位或符号位 为了指明这样一个数 需要给出该数在主存中的起始地址和位数 串的长度 2 压缩的十进制数串形式 一个字节存放两个十进制的数位 它比前一种形式节省存储空间 又便于直接完成十进制数的算术运算 是广泛采用的较为理想的方法 4 自定义数据表示 在传统的计算机体系结构中 用指令本身来说明操作数据的类型 如定点加法表示操作数是纯小数或纯整数 浮点加法表示操作数是浮点数 十进制加法表示操作数是BCD数 由于操作数据类型不同 要设三种不同的指令 操作码 来加以区分 自定义数据表示则用数据本身来说明数据类型 表示形式有两种 即标志符数据表示和描述符数据表示 描述符数据表示主要用来描述多维结构的数据类型 如向量 矩阵 记录等 描述符标志位部分指明这是一个数据描述符 特征标记部分指明数据的各种特征 长度部分指明数组中元素个数 起始地址部分指明数据块的首地址 其格式为 标志符数据表示要求对每一个数据都附加标志符 其指明后面的数据所具有的类型 如整数 浮点数 BCD数 字符串等 其格式如下 2 1 2数的机器码表示 在计算机中对数据进行运算操作时 为了妥善的处理好符号位问题 就产生了把符号位和数字位一起编码来表示相应的数的各种表示方法 如原码 补码 反码 移码等 为了区别一般书写表示的数和机器中这些编码表示的数 通常将前者称为真值 后者称为机器数或机器码 常用的机器码表示法 1 原码表示法2 补码表示法3 反码表示法4 移码表示法 1 原码表示法 若定点小数的原码形式为 0 1 2 n 则原码表示的定义是 1 0 原 1 1 0 1式中 原是机器数 是真值若定点整数的原码形式为 0 1 2 n 则原码表示的定义是 2n 0 原 2n 2n 0 2n 对于0 原码机器中往往有 0 0 之分 故有两种形式 0 原 0 000 0 0 原 1 000 0采用原码表示法简单易懂 但它的最大缺点是加法运算复杂 这是因为 当两数相加时 如果是同号则数值相加 如果是异号 则要进行减法 而在进行减法时还要比较绝对值的大小 然后大数减去小数 最后还要给结果选择符号 为了解决这些矛盾 人们找到了补码表示法 2 补码表示法 我们先以钟表对时为例说明补码的概念 假设现在的标准时间为4点正 而有一只表已经7点了 为了校准时间 可以采用两种方法 一是将时针退7 4 3格 一是将时针向前拨12 3 9格 这两种方法都能对准到4点 由此可以看出 减3和加9是等价的 就是说9是 3 对12的补码 可以用数学公式表示 3 9 mod12 mod12的意思就是12模数 这个 模 表示被丢掉的数值 上式在数学上称为同余式 上例中其所以7 3和7 9 mod12 等价 原因就是表指针超过12时 将12自动丢掉 最后得到16 12 4 从这里可以得到一个启示 就是负数用补码表示时 可以把减法转化为加法 这样 在计算机中实现起来就比较方便 7 3 47 9 4以12取模数 mod12 3 9 mod12 采用补码表示法进行减法运算就比原码方便得多了 因为不论数是正还是负 机器总是做加法 减法运算可变为加法运算 关键是我们需要换算出两个操作数的补码表示 若定点小数补码形式为 0 1 2 n 则补码表示的定义是 1 0 补 2 2 0 1 mod2 若定点整数补码形式为 0 1 2 n 则补码表示的定义是 2n 0 补 2n 1 2n 1 0 2n mod2n 1 根据补码定义 求负数的补码要从2减去 x 为了用加法代替减法 结果还得在求补码时作一次减法 这显然是不方便的 下面介绍的反码表示法可以解决负数的求补问题 3 反码表示法 所谓反码 就是二进制的各位数码0变为1 1变为0 也就是说 若Xi 1 则反码为xi 0 若xi 0 则反码xi 1 数值上面的一横表示反码的意思 在计算机中用触发器寄存数码 若触发器Q端输出表示原码 则其Q端输出就是反码 由此可知 反码是容易得到的 若定点小数反码形式为 0 1 2 n 则反码表示的定义是 1 0 反 2 2 n 0 1一般情况下 对正数和负数的 值 0 1 2 n 则 反 0 1 2 n 0 1 2 n 则 反 1 1 2 n若定点整数反码形式为 0 1 2 n 则反码表示的定义是 2n 0 反 2n 1 1 0 2n 我们比较反码与补码的公式 对于负数有 定点小数 反 2 2 n 补 2 可得到 补 反 2 n定点整数 反 2n 1 1 补 2n 1 可得到 补 反 1这就是通过反码求补码的重要公式 这个公式告诉我们 若要一个负数变补码 其方法是符号位置1 其余各位0变1 1变0 然后在最末位 2 n 上加1 4 移码表示法 移码通常用于表示浮点数的阶码 由于阶码是个n位的整数 假定定点整数移码形式为 0 1 2 n时 对定点整数移码的传统定义是 移 2n 2n 2n若阶码数值部分为5位 以 表示真值 则 移 25 25 25 小结 上面的数据四种机器表示法中 移码表示法主要用于表示浮点数的阶码 由于补码表示对加减法运算十分方便 因此目前机器中广泛采用补码表示法 在这类机器中 数用补码表示 补码存储 补码运算 也有些机器 数用原码进行存储和传送 运算时改用补码 还有些机器在做加减法时用补码运算 在做乘除法时用原码运算 例5 设机器字长16位 定点表示 尾数15位 数符1位 问 1 定点原码整数表示时 最大正数是多少 最小负数是多少 2 定点原码小数表示时 最大正数是多少 最小负数是多少 解 1 定点原码整数表示最大正数值 215 1 10 32767 10最小负数值 215 1 10 32767 10 2 定点原码小数表示最大正数值 1 2 15 10 0 111 11 2最小负数值 1 2 15 10 0 111 11 2 例6 假设由S E M三个域组成的一个32位二进制数所表示的非零规格化浮点数 真值表示为 1 s 1 M 2E 128问 它所表示的规格化的最大正数 最小正数 最大负数 最小负数是多少 解 1 最大正数 1 1 2 23 2127 2 最小正数 1 0 2 128 3 最小负数 1 1 2 23 2127 4 最大负数 1 0 2 128 例7 若机器使用8位表示定点数 将数x 100 100 y 0 59375 0 59375分别转换为各种机器码形式 解 已知数据位数为8位 最高位为符号位 数据表示范围可用7位 那么定点整数的范围是 0 127 27 1 定点小数的范围是 0 0 9921875 1 2 7 100 10 1100100 2 0 59375 10 0 10011 2 1100100 原 01100100 1100100 原 11100100 1100100 反 01100100 1100100 反 10011011 1100100 补 01100100 1100100 补 10011100 0 10011 原 01001100 0 10011 原 11001100 0 10011 反 01001100 0 10011 反 10110011 0 10011 补 01001100 0 10011 补 10110100 2 1 3字符与字符串的表示方法 1 字符的表示方法现代计算机不仅处理数值领域的问题 而且处理大量非数值领域的问题 这样一来 必然要引入文字 字母以及某些专用符号 以便表示文字语言 逻辑语言等信息 目前国际上普遍采用的字符系统是七单位的ASCII码 美国国家信息交换标准字符码 它包括10个十进制数码 26个英文字母和一定数量的专用符号 如 等 共128个元素 因此二进制编码需7位 加一位偶校验位 共8位一个字节 参见书中表2 1的ASCII码字符编码表 2 字符串字符串是指连续的一串字符 通常方式下 它们占用主存中连续的多个字节 每个字节存一个字符 当主存字由2个或4个字节组成时 在同一个主存字中 既可按从低位字节向高位字节的顺序存放字符串的内容 也可按从高位字节向低位字节的次序顺序存放字符串的内容 例 将下面字符串从高位字节到低位字节依次存在主存中 IF A B THEN READ C 2 1 4汉字的表示方法 1 汉字的输入编码当前采用的方法主要有以下三类 数字编码常用的是国标区位码 用数字串代表一个汉字输入 区位码是将国家标准局公布的6763个两级汉字分为94个区 每个区分94位 实际上把汉字表示成二维数组 每个汉字在数组中的下标就是区位码 区码和位码各两位十进制数字 因此输入一个汉字需按键四次 数字编码输入的优点是无重码 且输入码与内部编码的转换比较方便 缺点是代码难以记忆 拼音码拼音码是以汉字拼音为基础的输入方法 使用简单方便 但汉字同音字太多 输入重码率很高 同音字选择影响了输入速度 字形编码字形编码是用汉字的形状来进行的编码 把汉字的笔划部件用字母或数字进行编码 按笔划的顺序依次输入 就能表示一个汉字 2 汉字内码汉字内码是用于汉字信息的存储 交换 检索等操作的机内代码 一般采用两个字节表示 英文字符的机内代码是七位的ASCII码 当用一个字节表示时 最高位为 0 为了与英文字符能相互区别 汉字机内代码中两个字节的最高位均规定为 1 注意 有些系统中字节的最高位用于奇偶校验位 这种情况下用三个字节表示汉字内码 3 汉字字模码字模码是用点阵表示的汉字字形代码 它是汉字的输出形式 字模点阵只能用来构成汉字库 用于汉字的显示输出或打印输出 注意 汉字的输入编码 汉字内码 字模码是计算机中用于输入 内部处理 输出三种不同用途的编码 不要混为一谈 图2 1汉字的字模点阵及编码 2 1 5校验码 元件故障 噪声干扰等各种因素常导致计算机在处理信息过程中出现错误 为了防止错误可将信号采用专门的逻辑线路进行编码以检测错误 甚至校正错误 通常的方法是在每个字上添加一些校验位 用来确定字中出现错误的位置 最简单且应用广泛的检错码是采用一位校验位的奇校验或偶校验 设 0 1 n 1 是一个n位字 则奇校验位 定义为C 0 1 n 1同理偶校验位 定义为C 0 1 n 1 2 2定点加法 减法运算2 2 1补码加法 负数用补码表示后 可以和正数一样来处理 这样 运算器里只需要一个加法器就可以了 不必为了负数的加法运算 再配一个减法器 补码加法的公式是 补 补 补 mod2 现分四种情况来证明 假设采用定点小数表示 因此证明的先决条件是 1 1 1 1 0 0 则 0 相加两数都是正数 故其和也一定是正数 正数的补码和原码是一样的 可得 补 补 补 mod2 2 0 0 则 0或 0时 2 2 进位2必丢失 又因 0 故 补 补 补 mod2 当 0时 2 2 又因 0 故 补 补 2 补 mod2 3 0 则 0或 0 这种情况等同于第2种情况 4 0 0 则 0 相加两数都是负数 则其和也一定是负数 补 2 补 2 补 补 2 2 2 2 上式右边分为 2 和 2 两部分 既然 是负数 而其绝对值又小于1 那么 2 就一定是小于2而大于1的数 进位 2 必丢失 又因 0 所以 补 补 2 补 mod2 至此我们证明了 在模2意义下 任意两数的补码之和等于该两数之和的补码 这是补码加法的理论基础 其结论也适用于定点整数 例8 0 1001 0 0101 用补码求 解 补 0 1001 补 0 0101 补0 1001 补0 0101 补0 1110所以 0 1110 例9 0 1011 0 0101 用补码求 解 补 0 1011 补 1 1011 补0 1011 补1 1011 补10 0110所以 0 0110由以上两例看到 补码加法的特点 一是符号位要作为数的一部分一起参加运算 二是要在模2的意义下相加 即超过2的进位要丢掉 2 2 2补码减法 负数的减法运算也要设法化为加法来做 其所以使用这种方法而不使用直接减法 是因为它可以和常规的加法运算使用同一加法器电路 从而简化了计算机的设计 数用补码表示时 减法运算的公式为 补 补 补 补 补只要证明 补 补 上式即得证 现证明如下 补 补 补 mod2 补 补 补 2 19a 补 补 补 补 补 补 补 2 19a 将式 2 19a 与 2 19b 相加 得 补 补 补 补 补 补 补 补 补 补 补 补 0故 补 补 mod2 从 补求 补的法则是 对 补包括符号位 求反且最末位加1 即可得到 补 写成运算表达式 则为 其中符号 表示对 补作包括符号位在内的求反操作 2 n表示最末位的1 例10 已知 1 0 1110 2 0 1101 求 1 补 1 补 2 补 2 补 解 1 补 1 0010 1 补 1 补 2 4 0 1101 0 0001 0 1110 2 补 0 1101 2 补 2 补 2 4 1 0010 0 0001 1 0011 例11 0 1101 0 0110 求 解 补 0 1101 补 0 0110 补 1 1010 补0 1101 补1 1010 补10 0111所以 0 0111 2 2 3溢出概念与检测方法 在定点小数机器中 数的表示范围为 1 在运算过程中如出现大于1的现象 称为 溢出 在定点机中 正常情况下溢出是不允许的 两个正数相加 结果大于机器所能表示的最大正数 称为上溢 而两个负数相加 结果小于机器所能表示的最小负数 称为下溢 机器定点小数表示 例12 0 1011 0 1001 求 解 补 0 1011 补 0 1001 补0 1011 补0 1001 补1 0100两个正数相加的结果成为负数 这显然是错误的 例13 0 1101 0 1011 求 解 补 1 0011 补 1 0101 补1 0011 补1 0101 补0 1000两个负数相加的结果成为正数 这同样是错误的 为了判断 溢出 是否发生 可采用两种检测的方法 第一种方法是采用双符号位法 这称为 变形补码 或 模4补码 从而可使模2补码所能表示的数的范围扩大一倍 第二种溢出检测方法是采用单符号位法 从上例中看到 当最高有效位产生进位而符号位无进位时 产生上溢 当最高有效位无进位而符号位有进位时 产生下溢 在定点机中当运算结果发生溢出时 机器通过逻辑电路自动检查出溢出 并进行中断处理 2 2 4基本的二进制加法 减法器 首先我们来讨论最简单的一位全加器的结构 设定两个二进制数字Ai Bi和一个进位输入Ci相加 产生一个和输出Si 以及一个进位输出Ci 1 Ai BiCiCi 1Si下表列出一位全加器进行加法运算的输入输出真值表 表2 2一位全加器真值表 根据表2 2所示的真值表 三个输入端和两个输入端可按如下逻辑方程进行联系 Si Ai Bi CiCi 1 AiBi BiCi CiAi按此表达式组成的一位全加器下图示2 2 a 由上图看到 n个1位的全加器 FA 可级联成一个n位的行波进位加减器 M为方式控制输入线 当M 0时 作加法 A B 运算 当M 1时 作减法 A B 运算 在后一种情况下 A B运算转化成 A 补 B 补运算 求补过程由B 1来实现 因此图中最右边的全加器的起始进位输入端被连接到功能方式线M上 作减法时M 1 相当于在加法器的最低位上加1 另外图中左边还表示出单符号位法的溢出检测逻辑 当Cn Cn 1时 运算无溢出 而当Cn Cn 1时 运算有溢出 经异或门产生溢出信号 对一位全加器 FA 来说 Si的时间延迟为6T 每级异或门延迟3T Ci 1的时间延迟为5T 其中T被定义为相应于单级逻辑电路的单位门延迟 T通常采用一个 与非 门或一个 或非 门的时间延迟来作为度量单位 现在我们计算一个n位的行波进位加法器的时间延迟 假如采用图2 2 a 所示的一位全加器并考虑溢出检测 那么n位行波进位加法器的延迟时间ta为ta n 2T 9T 2n 9 T9T为最低位上的两极 异或 门再加上溢出 异或 门的总时间 2T为每级进位链的延迟时间 当不考虑溢出检测时 有ta n 1 2T 9Tta意味着加法器的输入端输入加数和被加数后 在最坏情况下加法器输出端得到稳定的求和输出所需的最长时间 显然这个时间越小越好 注意 加数 被加数 进位与和数都是用电平来表示的 因此 所谓稳定的求和输出 就是指稳定的电平输出 注意 第一种情况下 是最低的两个异或门加上溢出的异或门共3 3T 第二种情况下 是最低的两个异或门加上最后一个FA的输出异或门共3 3T 2 2 5十进制加法器 十进制加法器可由BCD码 二 十进制码 来设计 它可以在二进制加法器的基础上加上适当的校正逻辑来实现 该校正逻辑可将二进制的和改变成所要求的十进制格式 n位BCD码行波式进位加法器的一般结构如下图2 3 a 所示 它由n级组成 每一级将一对4位的BCD数字相加 并通过一位进位线与其相邻级连接 而每一位十进制数字的BCD加法器单元的逻辑结构示于图2 3 b 在十进制运算时 当相加二数之和大于9时 便产生进位 可是用BCD码完成十进制数运算时 当和数大于9时 必须对和数进行加6修正 这是因为 采用BCD码后 在二数相加的和数小于等于9时 十进制运算的结果是正确的 而当相加的和数大于9时 结果不正确 必须加6修正后才能得出正确的结果 2 3定点乘法运算2 3 1原码乘法1 人工算法与机器算法的同异性 设 0 1101 0 1011 下面让我们先用习惯方法求其乘积 其过程如下 上述的运算过程与十进制乘法相似 从乘数 的最低位开始 若这一位为 1 则将被乘数 写下 若这一位为 0 则写下全0 然后在对乘数 的次高位进行乘法运算 其规则同上 不过这一位乘数的权与最低位乘数的权不一样 因此被乘数 要左移一位 以此类推直到乘数个位乘完为止 最后将它们统统加起来便得到最后乘积 同理 如果被乘数和乘数用定点整数表示 我们也会得到同样的结果 数值部分的运算方法与普通的十进制小数乘法类似 不过对于用二进制表达式的数来说 其乘法规则更为简单一些 在定点计算机中 两个原码表示的数相乘的运算规则是 乘积的符号位由两数的符号位按异或运算得到 而乘积的数值部分则是两个正数相乘之积 设n位被乘数和乘数用定点小数表示被乘数 原 f n 1 1 0乘数 原 f n 1 1 0则两数的乘积 原 f f 0 n 1 1 0 0 n 1 1 0 式中 f为被乘数符号 f为乘数符号 人们习惯的算法对机器并不完全适用 原因之一 机器通常只有n位长 两个n位数相乘 乘积可能为2n位 原因之二 只有两个操作数相加的加法器难以胜任将n各位积一次相加起来的运算 早期计算机中为了简化硬件结构 采用串行的1位乘法方案 即多次执行 加法 移位 操作来实现 这种方法并不需要很多器件 然而串行方法毕竟太慢 自从大规模集成电路问世以来 出现了各种形式的流水式阵列乘法器 它们属于并行乘法器 2 不带符号的阵列乘法器 设有两个不带符号的二进制整数 A am 1 a1a0B bn 1 b1b0它们的数值分别为a和b 即m 1n 1a ai2ib bj2ji 0j 0在二进制乘法中 被乘数A与乘数B相乘 产生m n位乘积P P pm n 1 p1p0乘积P的数值为 实现这个乘法过程所需要的操作和人们的习惯方法非常类似 上述过程说明了在m位乘n位不带符号整数的阵列乘法中 加法 移位 操作的被加数矩阵 每一个部分乘积项 位积 aibj叫做一个被加数 这m n个被加数 aibj 0 i m 1和0 j n 1 可以用m n个 与 门并行地产生 由此说明设计高速并行乘法器的基本问题 就在于缩短被加数矩阵中每列所包含的1的加法时间 下图是一个5 5 m n 不带符号的阵列乘法器的逻辑电路图 这种乘法器要实现n位 n位时 需要n n 1 个全加器和n2个 与 门 该乘法器的总的乘法时间可以估算如下 令Ta为 与门 的传输延迟时间 Tf为全加器 FA 的进位传输延迟时间 假定用2级 与非 逻辑来实现FA的进位链功能 那么我们就有 Ta Tf 2T从上图可知 最坏情况下延迟途径 即是沿着矩阵最右边的对角线和最下面的一行 因而得n位 n位不带符号的阵列乘法器总的乘法时间为 tm Ta n 1 6T n 1 Tf 2T n 1 6T n 1 2T 8n 6 T 例16 已知两个不带符号的二进制整数A 11011 B 10101 求每一部分乘积项aibj的值与p9p8 p0的值 解 P p9p8p7p6p5p4p3p2p1p0 1000110111 56710 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 1 3 带符号的阵列乘法器 1 对2求补器电路 我们先来看看算术运算部件设计中经常用到的求补电路 下图示出一个具有使能控制的二进制对2求补器电路 其逻辑表达式如下 C 1 0 Ci ai Ci 1ai ai ECi 1 0 i n 在对2求补时 要采用按位扫描技术来执行所需要的求补操作 令A an a1a0是给定的 n 1 为带符号的数 要求确定它的补码形式 进行求补的方法就是从数的最右端a0开始 由右向左 直到找出第一个 1 例如ai 1 0 i n 这样 ai以左的每一个输入位都求反 即1变0 0变1 最右端的起始链式输入C 1必须永远置成 0 当控制信号线E为 1 时 启动对2求补的操作 当控制信号线E为 0 时 输出将和输入相等 显然 我们可以利用符号位来作为控制信号 例如 在一个4位的对2求补器中 如果输入数为1010 那么输出数应是0110 其中从右算起的第2位 就是所遇到的第一个 1 的位置 用这种对2求补器来转换一个 n 1 位带符号的数 所需的总时间延迟为tTC n 2T 5T 2n 5 T其中每个扫描级需2T延迟 而5T则是由于 与 门和 异或 门引起的 2 带符号的阵列乘法器 下图是 n 1 n 1 位带求补器的阵列乘法器逻辑方框图 通常 把包括这些求补级的乘法器又称为符号求补的阵列乘法器 在这种逻辑结构中 共使用三个求补器 其中两个算前求补器的作用是 将两个操作数A和B在被不带符号的乘法阵列 核心部件 相乘以前 先变成正整数 而算后求补器的作用则是 当两个输入操作数的符号不一致时 把运算结果变成带符号的数 上面所示的带求补级的阵列乘法器既适用于原码乘法 也适用于间接的补码乘法 不过在原码乘法中 算前求补和算后求补都不需要 因为输入数据都是立即可用的 而间接的补码阵列乘法却需要增加三个硬件求补器 为了完成所必需的求与乘法操作 时间大约比原码阵列乘法增加1倍 实际上我们可以看到带符号的阵列乘法器其内部仍是一个基本的源码阵列乘法器 只是对输入的补码数据在乘前进行了值还原 同时在乘后再次将乘积数转换为补码形式输出 例17 设 15 13 用带求补器的原码阵列乘法器求出乘积 解 设最高位为符号位 则输入数据为 补 01111 补 10011符号位单独考虑 经过算前求补级后 1111 1101 算后经求补级输出并加上乘积符号位1 乘积的补码值为100111101 则原码乘积值为111000011 换算成二进制数真值是 11000011 2 195 10十进制数验证 15 13 195相等 2 3 2补码乘法1 补码与真值的转换公式 补码乘法因符号位参与运算 可以完成补码数的 直接 乘法 而不需要求补级 这种直接的方法排除了较慢的对2求补操作 因而大大加速了乘法过程 首先说明与直接的补码乘法相联系数学特征 对于计算补码数的数值来说 一种较好的表示方法是使补码的位置数由一个带负权的符号和带正权的系数 今考虑一个定点补码整数 N 补 an 1an 2 a1a0 这里an 1是符号位 根据 N 补的符号 补码数 N 补和真值N的关系可以表示成 n 2 ai2i当an 1 0 N 补为正 N i 0n 2 1 1 ai 2i 当an 1 1 N 补为负 i 0 如果我们把负权因数 2n 1强加到符号位an 1上 那么就可以把上述方程组中的两个位置表达式合并成下面的统一形式 n 2N an 12n 1 ai2ii 0n 2 N 1 an 1 2n 1 1 ai 2i 1i 0 2 一般化的全加器形式 常规的一位全加器可假定它的3个输入和2个输出都是正权 这种加法器通过把正权或负权加到输入 输出端 可以归纳出四类加法单元 如下表 0类全加器没有负权输入 1类全加器有1个负权输入和2个正权输入 依次类推 对0类 3类全加器而言有 对1类 2类全加器 则有 表2 3四类一般化全加器的名称和逻辑符号 注意 0类和3类全加器是用同一对逻辑方程来表征的 它和普通的一位全加器 0类 是一致的 这是因为3类全加器可以简单地把0类全加器的所有输入输出值全部反向来得到 反之亦然 1类和2类全加器之间也能建立类似的关系 由于逻辑表达式具有两级与 或形式 可以用 与或非 门来实现 延迟时间为2T 3 直接补码阵列乘法器 利用混合型的全加器就可以构成直接补码数阵列乘法器 设被乘数A和乘数B是两个5位的二进制补码数 即A a4 a3a2a1a0B b4 a3a2a1a0它们具有带负权的符号位a4和b4 并用括号标注 如果我们用括号来标注负的被加项 例如 aibJ 那么A和B相乘过程中所包含的操作步骤如下面矩阵所示 A a4 a3a2a1a0B b4 b3b2b1b0 a4b0 a3b0a1b0a1b0a0b0 a4b1 a3b1a2b1a1b1a0b1 a4b2 a3b2a2b2a1b2a0b2 a4b3 a3b3a2b3a1b3a0b3 a4b4 a3b4 a2b4 a1b4 a0b4 P p9p8p7p6p5p4p3p2p1p0 上图所示是5位乘5位的直接补码阵列乘法器逻辑原理 其中使用不同的逻辑符号来代表0类 1类 2类 3类全加器 2类和1类全加器具有同样的结构 但是使用不同的逻辑符号可使乘法阵列的线路图容易理解 该实现方式称为三段阵列乘法器 其中右上角的三角形中只用0类全加器 左上角的三角形只用1类全加器 阵列的最后两行只用2类全加器 其中使用不同的逻辑符号来代表0类 1类 2类 3类全加器 2类和1类全加器具有同样的结构 但是使用不同的逻辑符号可使乘法阵列的线路图容易理解 在n位乘n位的一般情况下 该乘法器需要 n 2 2个0类全加器 n 2 个1类全加器 2n 3 个2类全加器 1个3类全加器 总共是n n 1 个全加器 故所需的总乘法时间是 tp Ta 2 n 1 Tf 2T 2n 2 2T 4n 2 T 2 31 例20 设 A 补 01101 2 B 补 11011 2 求 A B 补 解 0 1101 13 1 1011 5 0 1101 0 1101 0 0000 0 11010 1 1 0 1 0 1 0111111 1 10111111 65扩展符号位符号位验证 1 27 0 26 1 25 1 24 1 23 1 22 1 21 1 20 128 32 16 8 4 2 1 65 13 5 65 2 4定点除法运算2 4 1原码除法运算原理 两个原码表示的数相除时 商的符号由两数的符号按位相加求得 商的数值部分由两数的数值部分相除求得 设有n位定点小数 定点整数也同样适用 被除数 其原码为 原 f n 1 1 0除数 其原码为 原 f n 1 1 0则有商q 其原码为 q 原 f f 0 n 1 1 0 0 n 1 1 0 商的符号运算qf f f与原码乘法一样 用模2求和得到 商的数值部分的运算 实质上是两个正数求商的运算 根据我们所熟知的十进制除法运算方法 很容易得到二进制数的除法运算方法 所不同的只是在二进制中 商的每一位不是 1 就是 0 其运算法则更简单一些 下面仅讨论数值部分的运算 设被除数 0 1001 除数 0 1011 模仿十进制除法运算 以手算方法求 的过程如下 得 的商q 0 1101 余数为r 0 00000001 上面的笔算过程可叙述如下 1 判断 是否小于 现在 2 1 表示够减 小数点后第一位商 1 作r0 2 1 得余数r1 3 比较r1和2 2 因r1 2 2 表示够减 小数点后第二位商 1 作r1 2 2 得余数r2 4 比较r2和2 3 因r22 4 表示够减 小数点后第四2位商 1 作r3 2 4 得余数r4 共求四位商 至此除法完毕 在计算机中小数点是固定的 不能简单地采用手算的办法 为便于机器操作 使 除数右移 和 右移上商 的操作统一起来 事实上机器与人运算过程不同 人会心算一看就知道够不够减 但机器却必须先作减法 若余数为正才知道够减 若余数为负才知道不够减 不够减时必须恢复原来的余数以便再继续往下运算 这种方法称为恢复余数法 要恢复原来的余数 只要当前的余数加上除数即可 但由于要恢复余数 使除法进行过程的步数不固定 因此控制比较复杂 实际中常用不恢复余数法又称加减交替法 其特点是运算过程中如出现不够减则不必恢复余数 根据余数符号 可以继续往下运算 因此步数固定 控制简单 早期计算机中 为了简化结构 硬件除法器的设计采用串行的1位除法方案 即多次执行 减法 移位 操作来实现 并使用计数器来控制移位次数 由于串行除法器速度太慢 目前已被淘汰 不恢复余数除法即加减交替法的实现方式 设被除数为 除数为 1 x y 补 x 补 y 补若 x y 0则商数为1 并进行第二步减 即 x y 补 2 1y 若 x y 0则商数为0 还原减法操作 在进行第二步减 即 x 2 1y 补 x 补 2 1y 补上面过程也就是 x y y 2 1y 补 x y 补 y 2 1y 补 x y 补 2 1y 补步骤2同理 从而用加减交替法实现除法操作 2 4 2并行除法器1 可控加法 减法 CAS 单元 和阵列乘法器非常相似 阵列式除法器也是一种并行运算部件 采用大规模集成电路制造 与早期的串行除法器相比 阵列除法器不仅所需的控制线路少 而且能提供令人满意的高速运算速度 阵列除法器有多种多样形式 如不恢复余数阵列除法器 补码阵列除法器等等 先介绍可控加法 减法 CAS 单元 它将用于并行除法流水逻辑阵列中 它有四个输出端和四个输入端 当输入线P 0时 CAS作加法运算 当P 1时 CAS作减法运算 逻辑结构图 CAS单元的输入与输出的关系可用如下一组逻辑方程来表示 Si Ai Bi P CiCi 1 Ai Ci Bi P AiCi 2 32 当P 0时 方程式 2 32 就等于我们前面学习的一位全加器 FA 的公式 Si Ai Bi CiCi 1 AiBi BiCi AiCi当P 1时 则得求差公式 Si Ai Bi CiCi 1 AiBi BiCi AiCi 2 33 其中Bi Bi 1 在减法情况下 输入Ci称为借位输入 而Ci 1称为借位输出 为说明CAS单元的实际内部电路实现 将方程式 2 32 加以变换 可得如下形式 Si Ai Bi P Ci AiBiCiP AiBiCiP AiBiCiP AiBiCiP AiBiCiP AiBiCiP AiBiCiP AiBiCiPCi 1 Ai Ci Bi P AiCi AiBiP AiBiP BiCiP BiCiP AiCi在这两个表达式中 每一个都能用一个三级组合逻辑电路 包括反向器 来实现 因此每一个基本的CAS单元的延迟时间为3T单元 2 不恢复余数的阵列除法器 先假定所有被处理的数都是正的小数 不恢复余数的除法也就是加减交替法 在不恢复余数的除法阵列中 每一行所执行的操作究竟是加法还是减法 取决于前一行输出的符号与被除数的符号是否一致 当出现不够减时 部分余数相对于被除数来说要改变符号 这时应该产生一个商位 0 除数首先沿对角线右移 然后加到下一行的部分余数上 当部分余数不改变它的符号时 即产生商位 1 下一行的操作应该是减法 下图是4位除4位的不恢复余数阵列除法器的逻辑原理图 其中被除数 0 1 2 3 4 5 6 双倍长 除数 0 1 2 3商数 0 q1q2q3余数 0 00r3r4r5r6字长n 1 4由上图看出 该阵列除法器是用一个可控加法 减法 CAS 单元所组成的流水阵列来实现的 推广到一般情况 一个 n 1 位除 n 1 位的加减交替除法阵列由 n 1 2个CAS单元组成 其中两个操作数 被除数与除数 都是正的 最上面一行所执行的初始操作经常是减法 因此最上面一行的控制线P固定置成 1 减法是用2的补码运算来实现的 这时右端各CAS单元上的反馈线用作初始的进位输入 每一行最左边的单元的进位输出决定着商的数值 将当前的商反馈到下一行 我们就能确定下一行的操作 由于进位输出信号指示出当前的部分余数的符号 因此 它将决定下一行的操作将进行加法还是减法 对不恢复余数阵列除法器来说 在进行运算时 沿着每一行都有进位 或借位 传播 同时所有行在它们的进位链上都是串行连接 而每个CAS单元的延迟时间为3T单元 因此 对一个2n位除以n位的不恢复余数阵列除法器来说 单元的数量为 n 1 2 考虑最大情况下的信号延迟 其除法执行时间为td 3 n 1 2T其中n为尾数位数 例20 0 101001 0 111 求 解 补 1 001被除数 0 101001减 1 001余数为负1 110001 0q0 0余数左移1 10001加 0 111余数为正0 01101 0q1 1余数左移0 1101减 1 001余数为负1 1111 0q2 0余数左移1 111加 0 111余数为正0 110 0q3 1故得商q q0 q1q2q3 0 101余数r 0 00r3r4r5r6 0 000110 2 5定点运算器的组成2 5 1逻辑运算 计算机中除了进行加 减 乘 除等基本算术运算外 还可对两个或一个逻辑数进行逻辑运算 所谓逻辑数 是指不带符号的二进制数 利用逻辑运算可以进行两个数的比较 或者从某个数中选取某几位等操作 计算机中的逻辑运算 主要是指逻辑非 逻辑加 逻辑乘 逻辑异四种基本运算 1 逻辑非运算逻辑非也称求反 对某数进行逻辑非运算 就是按位求它的反 常用变量上方加一横来表示 2 逻辑加运算两数进行逻辑加 就是按位求它们的 或 所以逻辑加又称逻辑或 常用记号 V 或 来表示 3 逻辑乘运算两数逻辑乘 就是按位求它们的 与 所以逻辑乘又称 逻辑与 常用记号 或 来表示 4 逻辑异运算对两数进行异或就是按位求它们的模2和 所以逻辑异又称 按位加 常用记号 表示 2 5 2多功能算术 逻辑运算单元 ALU 由一位全加器 FA 构成的行波进位加法器 它可以实现补码数的加法或减法运算 但是这种加法 减法器存在两个问题 一是由于串行进位它的运算时间很长 假如加法器由n位全加器构成 每一位的进位延迟时间为20ns 那么最坏情况下 进位信号从最低位传递到最高位而最后输出稳定至少需要n 20ns 这在高速计算中显然是不利的 二是就行波进位加法器本身来说 它只能完成加法或减法两种操作而不能完成逻辑操作 本节我们介绍的多功能算术 逻辑运算单元 ALU 不仅具有多种算术运算和逻辑运算的功能 而且具有先行进位逻辑 从而能实现高速运算 图2 10ALU的逻辑结构原理框图 1 基本思想 一位全加器 FA 的逻辑表达式为Fi Ai Bi CiCi 1 AiBi BiCi CiAi我们将Ai和Bi先组合成由控制参数S0 S1 S2 S3控制的组合函数Xi和Yi 然后再将Xi Yi和下一位进位数通过全加器进行全加 这样 不同的控制参数可以得到不同的组合函数 因而能够实现多种算术运算和逻辑运算 一位算术 逻辑运算单元的逻辑表达式为 Fi Xi Yi Cn ICn i 1 XiYi YiCn i Cn iXi上式中进位下标用n i代替原来一位全加器中的i i代表集成在一片电路上的ALU的二进制位数 对于4位一片的ALU i 0 1 2 3 n代表若干片ALU组成更大字长的运算器时每片电路的进位输入 例如当4片组成16位字长的运算器时 n 0 4 8 12 2 逻辑表达式 控制参数S0 S1 S2 S3分别控制输入Ai和Bi 产生Y和X的函数 其中Yi是受S0 S1控制的Ai和Bi的组合函数 而Xi是受S2 S3控制的Ai和Bi组合函数 其函数关系如下表2 4所示 表2 4Xi Yi与控制参数和输入量的关系 根据上面所列的函数关系 即可列出Xi和Yi的逻辑表达式Xi S2S3 S2S3 Ai Bi S2S3 Ai Bi S2S3AiYi S0S1Ai S0S1AiBi S0S1AiBi进一步化简并代入前面的求和与进位表达式 可得ALU的某一位逻辑表达式如下 2 36 4位之间采用先行进位公式 根据上式 2 36 每一位的进位公式可递推如下 第0位向第1位的进位公式为Cn 1 Y0 X0Cn其中Cn是向第0位 末位 的进位 第1位向第2位的进位公式为Cn 2 Y1 X1Cn 1 Y1 Y0X1 X0X1Cn第2位向第3位的进位公式为Cn 3 Y2 X2Cn 2 Y2 Y1X2 Y0X1X2 X0X1X2Cn第3位的进位输出 即整个4位运算进位输出 公式为Cn 4 Y3 X3Cn 3 Y3 Y2X3 Y1X2X3 Y0X1X2X3 X0X1X2X3Cn设G Y3 Y2X3 Y1X2X3 Y0X1X2X3P X0X1X2X3则Cn 4 G PCn 2 37 这样对一片ALU来说 可有三个进位输出 其中G称为进位发生输出 P称为进位传送输出 在电路中多加这两个进位输出的目的 是为了便于实现多片 组 ALU之间的先行进位