计算机组成与系统结构-第3章 运算方法和运算部件 上

标签：运算 符号 补码 系统结构 部件 加法器 余数 进位

文章目录

• 3.1高级语言和机器指令中的运算
• • 3.1.1C语言程序中涉及的运算
  • • 数据的运算
  • 3.1.2MIPS 指令中涉及的运算
• 3.2基本运算部件
• • 3.2.1全加器和加法器
  • • 全加器（Full Adder，简称FA）
    • 串行进位加法器/行波进位加法器(carry ripple adder,CRA)。
  • 3.2.2并行进位加法器
  • 3.2.3带标志加法器
  • 3.2.4 算术逻辑部件（ALU）
  • • 例：实现某11条MIPS指令的ALU
• 第二讲：定点数运算
• 3.3定点数运算
• • 3.3.1 补码加减运算
  • • 整数减法举例
    • 整数加法
  • 3.3.2 原码加减运算（不要求）
  • 移码加减运算（不要求）
  • 无符号数的乘法运算
  • • 无符号乘法运算的算法推导
    • 32位乘法运算的硬件实现
    • Example：无符号整数乘法运算
  • 3.3.3 原码乘法运算
  • • 原码两位乘法举例
  • 3.34 补码乘法运算
  • • 如何求补码的真值
    • Booth’s 算法实质
    • 布斯算法举例
    • 补码两位乘法举例
  • 3.3.5 快速乘法器
  • • 流水线方式的快速乘法器
    • 阵列乘法器的实现
  • 3.3.6 原码除法运算
  • • Divide Algorithm example
    • 第一次试商为1时的情况
    • 无符号数除法算法的硬件实现
    • Divide Algorithm example
    • 不恢复余数除法(加减交替法)
    • 带符号数除法
    • 原码除法举例
  • 3.3.7 补码除法运算
  • • 实现补码除法的基本思想
    • 补码恢复余数法
    • 补码不恢复余数法
    • 举例：-9/2
    • 定点运算器芯片举例-AM2901A芯片框图
• 3.4整数乘除运算
• 3.5 浮点数运算
• • [计算机组成与系统结构-第3章 运算方法和运算部件 下](https://blog.csdn.net/rc4gyyc/article/details/137186577)

3.1高级语言和机器指令中的运算

• 主要内容
  • 高级语言程序中涉及的运算（以C语言为例）
    • 整数算术运算、浮点数算术运算
    • 按位、逻辑、移位、位扩展和位截断
  • 串行进位加法器
  • 并行进位加法器
    • 全先行进位加法器
    • 两级/多级先行进位加法器
  • 带标志加法器
  • 算术逻辑部件（ALU）

3.1.1C语言程序中涉及的运算

• C语言程序中的基本数据类型及其基本运算类型
  • 基本数据类型
    • 无符号数、带符号整数、浮点数、位串、字符（串）
  • 基本运算类型
    • 算术、按位、逻辑、移位、扩展和截断、匹配
• 计算机如何实现高级语言程序中的运算？
  • 将各类表达式编译（转换）为指令序列
  • 计算机直接执行指令来完成运算
• 例：C语句“f = (g+h) – (i+j);”中变量i、j、g、h由编译器分别分配在RISC-V寄存器t3~ t6中，寄存器t3~ t6的编号对应28~31，f分配在t0（编号5），则对应的RISC-V机器代码和汇编表示（#后为注释）如下：
  0000000 11111 11110 000 00101 0110011 add t0, t5, t6 # g+h
  0000000 11101 11100 000 00110 0110011 add t1, t3, t4 # i+j
  0100000 00110 00101 000 00101 0110011 sub t0, t0, t1 # f=(g+h)–(i+j)

数据的运算

• 高级语言程序中涉及的运算（以C语言为例）
  • 整数算术运算、浮点数算术运算
  • 按位、逻辑、移位、位扩展和位截断
    • 考虑以下C语言程序代码：
      1 short si=-32768;
      2 unsigned short usi=si;
      3 int i=si;
      4 unsigned ui=usi;
      执行上述程序段，并在32位大端方式机器上输出变量si、usi、i、ui的十进制和十六进制值，可得到各变量的输出结果为：
      si=-32768 8000
      usi=32768 8000
      i = -32768 FF FF 80 00
      ui = 32768 00 00 80 00
    • 位截断发生在将长数转换为短数时，例如，对于下列代码：
      1 int i=32768;
      2 short si=(short) i;
      3 int j=si;
      i = 32768 00008000
      si=-32768 8000
      j = -32768 FF FF 80 00
    • 类型转换时可能需要数据扩展或截断
• 指令集中涉及的运算（如RISC-V指令系统提供的运算类指令）
  • 涉及的定点数运算
    • 算术运算
      • 带符号整数：取负 / 符号扩展 / 加 / 减 / 乘 / 除 / 算术移位
      • 无符号整数：0扩展 / 加 / 减 / 乘 / 除
    • 逻辑运算
      • 逻辑操作：与 / 或 / 非 / …
      • 移位操作：逻辑左移 / 逻辑右移
      • 涉及的浮点数运算：加、减、乘、除
• 所有运算都可由ALU或加法器+移位器+多路选择器+控制逻辑实现！
  以下介绍基本运算部件：加法器（串行→并行 ）→ 带标志加法器 → ALU

3.1.2MIPS 指令中涉及的运算

3.2基本运算部件

3.2.1全加器和加法器

全加器（Full Adder，简称FA）

• 输入为加数A、被加数B和低位进位Cin，输出为和F、进位Cout
  化简后：
  逻辑上：Sum =A XOR B XOR Carryln
  CarryOut =B&Carryln | A&Carryln | A&B
  

  • 式中，F、Cout被分别称为“全加和”和“全加进位”。图3.1和图3.2分别是“全加和”和“全加进位”生成电路。从图3.2可看出，进位Ci-1到Ci的延迟是两级门。 F延迟为6ty；Cout延迟为2ty。
    

串行进位加法器/行波进位加法器(carry ripple adder,CRA)。

• 将n个全加器相连可得n位加法器，如图3.4 所示的加法器实现了两个n位二进制数X=XnXn-1…X1和Y=YnYn-1…Y1逐位相加的功能，得到的二进制和为F=FnFn-1,…F1,进位输出为Cn。
  
• 串行加法器的缺点：进位按串行方式传递，速度慢！
• 这种结构所用元件较少，但进位传递时间较长。
  • 全加器内从进位输入到进位输出，共经过2级门延迟
  • 所以，n位串行加法器从C0到Cn的延迟时间为2n级门延迟。
  • 假定一个异或门为3级门延迟，
  • 则最后一位和数Fn的延迟时间为2n+1级门延迟。(2(n-1)+3)
• 加法运算时间随两个加数位数n的增加而增加。当n较大时，串行进位的加法器速度将显著变慢。
  • 几乎所有的算术运算都要用到ALU或加法器，ALU 的核心还是加法器
  • 由于串行进位加法器速度慢的主要原因是进位按串行方式传递，高位进位依赖低位进位。为了提高加法器的速度，必须尽量避免进位之间的依赖关系。

3.2.2并行进位加法器

• 为什么用先行进位方式？
  串行进位加法器采用串行逐级传递进位，电路延迟与位数成正比关系。
  因此，现代计算机采用一种先行进位(Carry look ahead)方式。
• 如何产生先行进位？
  • 定义辅助函数：
    Gi=AiBi…进位生成函数
    Pi=Ai+Bi…进位传递函数
    • 通常把实现上述逻辑的电路称为进位生成/传递部件
• 全加逻辑方程：Si=Ai⊕Bi⊕Ci　 C_i+1=Gi+PiCi (i=0,1,…n)
  设n=4,则：C1=G0+P0C0
  　　 　 　 C2=G1+P1C1=G1+P1G0+P1P0C0
  　 　　 　 C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0
  　 　　 　 C4=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0
  • 由上式可知:从上述表达式可以看出，Ci仅与Xi、Yi和C₀有关，相互间的进位没有依赖关系。各进位之间无等待，相互独立并同时产生。
  • 通常把实现上述逻辑的电路称为4位先行进位部件（4位CLU）
    通过这种进位方式实现的加法器称为全先行进位加法器(carry lookahead adder,CLA)
    因为各个进位是并行产生的，所以是一种并行进位加法器。
• 图3.5为4位CLU和4位CLA示意图。
  
• Gi=XiYi
  Pi=Xi+Yi（或 Pi=Xi⊕Yi ）
  Ci=Gi+PiCi-1
  Fi=Xi⊕Yi ⊕Ci-1
  由图3.5可看出，从Xi、Yi到产生Pi、Gi需要1级门延迟，从Pi、Gi、C₀到产生所有进位C1～C4需要2级门延迟，从Xi、Yi 、Ci-1到产生Fi需要3级门延迟。产生全部和需要1+2+3=6级门延迟(假定一个异或门等于3级门延迟)。所以4位全先行进位加法器的关键路径长度为6级门延迟。
• 虽然更多位数的CLA只会增加逻辑门的输入端个数，而不会增加门的级数。但是使用全先行进位实现方式不太现实。
• 更多位数的加法器可通过将CLU或全先行进位加法器串接起来实现，
  • 例如，对于16位加法器，可以分成4位一组，组内为4位先行进位，组间串行进位。
  • 也可以进一步采用组内和组间都并行的进位方式
  • 因为两级先行进位加法器组内和组间都采用先行进位方式，其延迟和加法器的位数没有关系，不会随着位数的增加而延长时间。
  • 计算机内部大多采用两级或多级先行进位加法器。

3.2.3带标志加法器

• n位无符号数加法器无法用于两个n位带符号整数（补码）相加，无法判断是否溢出。不能进行无符号整数的减运算，也不能进行带符号整数的加/减运算。
• 还需要在增加相应的逻辑门电路。使得加法器不仅能计算和/差，还要能够生成相应的标志信息
• 程序中经常需要比较大小，通过（在加法器中）做减法得到的标志信息来判断
  
• 标志

  • 溢出标志OF：OF=Cn⊕Cn-1

    • 如果最高位有进位（符号位进位）/次高位有进位（符号位被进位），符号位都改变，则CF=1，否则为0
      

  • 符号标志SF：SF=F_n-1

  • 零标志ZF=1当且仅当F=0；
    

  • 进位/借位标志CF：CF=Cout⊕Cin，即当Cin=0时，CF为进位C_out,当Cin=1时，CF为进位C_out取反。

  • 需要说明的是，为了加快加法运算的速度，真正的电路一定使用多级先行进位方式，图3.6(b)主要是为了说明如何从加法运算结果中获得标志信息，因而使用全加器简化了加法器电路。

3.2.4 算术逻辑部件（ALU）

• ALU 是一种能进行多种算术运算与逻辑运算的组合逻辑电路，其核心部件是带标志加法器，多采用先行进位方式
  

• 进行基本算术运算与逻辑运算

  • 无符号整数加、减
  • 带符号整数加、减
  • 与、或、非、异或等逻辑运算
  • 实际的ALU中还包括算术移位、逻辑移位等其他运算功能

• 核心电路是整数加/减运算部件

• 输出除和/差等，还有标志信息

• 有一个操作控制端（ALUop），用来决定ALU所执行的处理功能。ALUop的位数k决定了操作的种类例如，当位数k为3时，ALU最多只有23=8种操作。
  

module ALU (
      input [3:0] a, b,
      input [1:0] aluop,
      input cin,
      output [3:0] f,
      output OF, SF, ZF, CF,
      output cout
);
      wire [3:0] sum;
      CLA_FLAGS(a, b, cin, sum, OF, SF, ZF, CF, cout);
      always @(*) begin
          case(aluop)
              2’b00: f = a & b;
              2’b01: f = a | b;
              2’b10: f = sum;
              default: f = 0;
          endcase
      end
endmodule

例：实现某11条MIPS指令的ALU

第二讲：定点数运算

主 要 内 容

• 定点数加减运算
  • 补码加减运算
  • 原码加减运算
  • 移码加减运算
• 定点数乘法运算
  • 原码乘法运算
  • 补码乘法运算
  • 快速乘法器
• 定点数除法运算
  • 原码除法运算
  • 补码除法运算

3.3定点数运算

3.3.1 补码加减运算

• 补码的定义
  假定补码有n位，则：
  [X]补=2ⁿ +X （-2ⁿ≤X＜2ⁿ ,mod 2ⁿ）
• 先看一个C程序段：
  int x=9, y=-6, z1, z2;
  z1=x+y;
  z2=x-y;
  • 问题：上述程序段中，x和y的机器数是什么？z1和z2的机器数是什么？
  • 回答：x的机器数为[x]_补， y的机器数为[y]_补;
    z1的机器数为[x+y]_补;
    z2的机器数为[x-y]_补。
  • 因此，计算机中需要有一个电路，能够实现以下功能：
    已知 [x]_补 和 [y]_补 ，计算[x+y]_补 和 [x-y]_补 。
• 补码加减运算公式
  [A+B]_补= [A]_补+ [B] _补 ( mod 2ⁿ )
  [A–B]_补= [A]_补+ [–B] _补 ( mod 2ⁿ )
  – 实现减法的主要工作在于：求[–B] 补
  • [A]_补 和[B]_补 的符号位(最高有效位)可以和数值位一起参与运算，加、减运算结果的符号位也在求和运算中直接得出
  • 最终运算结果的高位丢弃，保留低n位，相当于对和数取模2ⁿ。
  • 问题：如何 求[–B]_补 ？
    
• 利用带标志加法器，可构造整数加/减运算器，进行以下运算：
  无符号整数加、无符号整数减
  带符号整数加、带符号整数减
  
  • 2选1多路选择器
    用一个控制端 Sub来控制选择将原码B输入到加法器还是将反码B输入到加法器，并将控制端 Sub同时作为低位进位送到加法器，
  • 当Sub为1时，做减法
    当Sub为0时，做加法
  • 在整数加/减运算部件基础上，加上寄存器、移位器以及控制逻辑，就可实现ALU、乘/除运算以及浮点运算电路
• 零标志 ZF=1表示结果F为0。不管作为无符号整数还是带符号整数来运算，ZF 都有意义。
  符号标志SF表示结果的符号，即F的最高位。对于无符号数运算，SF没有意义。
  进/借位标志CF表示无符号数加/减运算时的进/借位。加法时，若CF=1则表示无符号数加法溢出；减法时，若CF=1则表示有借位，即不够减。因此，加法时CF就应等于进位输出Cout;减法时 CF 就应将进位输出Cout取反来作为借位标志。综合起来，可得CF=Sub⊕Cout。对于带符号整数运算，CF 没有意义。
  溢出标志OF=1表示带符号整数运算时结果发生了溢出。对于无符号整数运算，OF没有意义。

整数减法举例

• -7- 6 = -7 + (-6) = +3 　　　 发生了溢出，是一个错误的值
  
  • OF=1、ZF=0、SF=0、借位CF=0
  • 可以发现以下两种溢出现象：(1) 最高位和次高位的进位不同
    (2) 和的符号位和加数的符号位不同
• -3 - 5 = - 3 + (- 5) = - 8　　　　是一个正确的值。
  
  • OF=0、ZF=0、SF=1、借位CF=0
  • 此时，最高位的进位和次高位的进位都是1,没有发生第(1)种现象，而且和的符号和加数的符号都是1,因而也没有发生第(2)种现象。
• 通常根据上述两种现象是否发生来判断有无溢出。因此，有以下两种溢出判断逻辑表达式。
  (1)若符号位产生的进位C。与最高数值位向符号位的进位C。,不同，则产生溢出，即
  OF=C_n-1⊕Cn
  (2)若两个加数的符号位X。-和Y,相同，且与和的符号位F,-不同，则产生溢出，即
  
• 做减法以比较大小，规则：
  Unsigned: CF=0时，大于
  Signed：OF=SF时，大于
  验证：9>6，故CF=0；13>5，故CF=0
  验证：-7<6，故OF≠SF
  　　　-3<5，故OF≠SF
• Ex2:用8位补码计算107+46=7
  结果错误：107+46=-103，
  
  • 若采用变形补码结果怎样？
    变形补码（有多个相同的符号位）可保留运算中间结果，最后结果都是补码，变形补码只是在过程中间结果的表示
    从乘除运算过程可看出这点
    采用变形补码（假设有两个符号位）时“溢出”判断条件：结果的两个符号位不同

整数加法

unsigned int x=134;
unsigned int y=246;
int m=x;
int n=y;
x和m的机器数一样：1000 0110，y和n的机器数一样：1111 0110
unsigned int z1=x-y;
unsigned int z2=x+y;
int k1=m-n;
int k2=m+n;
z2和k2的机器数一样：0111 1100，CF=1，OF=1，SF=0
z2的值为124（=134+246-256，x+y>256）
k2的值为124（=-122+(-10)+256，m+n<-128，即负溢出）

3.3.2 原码加减运算（不要求）

• 用于浮点数尾数运算
• 符号位和数值部分分开处理
• 仅对数值部分进行加减运算，符号位起判断和控制作用
• 规则如下：
  • 比较两数符号，对加法实行“同号求和，异号求差”，对减法实行“异号求和，同号求差”。
  • 求和：数值位相加，和的符号取被加数（被减数）的符号。若最高位产生进位，则结果溢出。
  • 求差：被加数（被减数）加上加数（减数）的补码。
    a) 最高数值位产生进位表明加法结果为正，所得数值位正确。
    b) 最高数值位没产生进位表明加法结果为负，得到的是数值位的补码形式，需对结果求补，还原为绝对值形式的数值位。
  • 差的符号位：a)情况下，符号位取被加数（被减数）的符号；
    b)情况下，符号位为被加数（被减数）的符号取反。
• 例1：已知 [X]原 = 1.0011，[Y]原 = 1.1010，要求计算[X+Y]原
  解：由原码加减运算规则知：同号相加，则求和，和的符号同被加数符号。
  所以：和的数值位为：0011 + 1010 = 1101 （ALU中无符号数相加）
  和的符号位为：1
  [X+Y]原 = 1.1101
  • 求和：直接加，有进位则溢出，符号同被
• 例2 ：已知 [X]原 = 1.0011，[Y]原 = 1.1010，要求计算[X–Y]原
  解：由原码加减运算规则知：同号相减，则求差（补码减法）
  差的数值位为：0011+(1010)_补= 0011 + 0110 = 1001
  最高数值位没有产生进位，表明加法结果为负，需对1001求补，还
  原为绝对值形式的数值位。即：(1001)补= 0111
  差的符号位为[X]原的符号位取反，即：0
  [X–Y]原 = 0.0111
  • 求差：加补码，不会溢出，符号分情况

移码加减运算（不要求）

• 用于浮点数阶码运算
• 符号位和数值部分可以一起处理
• 运算公式（假定在一个n位ALU中进行加法运算）
  [E1]_移+[E2]_移=2^n-1+E1+2^n-1+E2=2ⁿ+E1+E2=[E1+E2]_补 （mod 2ⁿ）
  [E1]_移–[E2]_移=[E1]_移+[–[E2]_移]_补=2^n-1+E1+2ⁿ–[E2]_移
  =2^n-1+E1+2ⁿ–2^n-1–E2
  = 2ⁿ+E1–E2 = [E1–E2]_补 （mod 2ⁿ）
  结论：移码的和、差等于和、差的补码！
• 运算规则
  ① 加法：直接将[E1]_移和[E2]_移进行模2ⁿ加，然后对结果的符号取反。
  ② 减法：先将减数[E2]_移求补（各位取反，末位加1），然后再与被减数 [E1]_移进行模2ⁿ相加，最后对结果的符号取反。
  ③ 溢出判断：进行模2ⁿ相加时，如果两个加数的符号相同，并且与和数的符号也相同，则发生溢出。
• 例1： 用四位移码计算“–7+（– 6）”和“–3 + 6”的值。
  解：[–7]_移 = 0001 [– 6]_移= 0010 [–3]_移= 0101 [6]_移= 1110
  [–7]_移 + [–6]_移 = 0001 + 0010 = 0011 （两个加数与结果符号都为0，溢出）
  [–3]_移 + [6]_移 = 0101 + 1110 = 0011， 符号取反后为 1011，其真值为+3
  问题：[–7+(–6)]_移=? [–3+(6)]_移 =？
  -2 +（-3）=？
• 例2： 用四位移码计算“–7 –（– 6）”和“–3 – 5”的值。
  解：[–7]_移 = 0001 [– 6]_移= 0010 [–3]_移= 0101 [5]_移= 1101
  [–7]_移 – [–6]_移 = 0001 + 1110 = 1111， 符号取反后为 0111，其真值为–1。
  [–3]_移 – [5]_移 = 0101 + 0011 = 1000，符号取反后为 0000，其真值为– 8。
• 实现某11条MIPS指令的ALU
  • 顶点整数ALU，浮点的运算需要别的ALU
    

无符号数的乘法运算

• 假定：[X]原=x0.x1…xn，[Y]原=y0.y1…yn ，求[x×Y]原
  数值部分 z1…z2n = (0.x1…xn ) × (0. y1…yn)
  (小数点位置约定，不区分小数还是整数)
  
• 整个运算过程中用到两种操作：加法 + 左移
  因而，可用ALU和移位器来实现乘法运算
  
• 手工乘法的特点：
  ① 每步计算：X×y_i，若y_i = 0，则得0；若y_i = 1，则得X
  ② 把①求得的各项结果X× y_i 逐次左移，可表示为X× y_i×2^-i③ 对②中结果求和，即 Σ(X× y_i×2^-i)，这就是两个无符号数的乘积
• 计算机内部稍作以下改进：
  ① 每次得X×y_i后，与前面所得结果累加，得到Pi，称之为部分积。因为不等到最后一次求和，减少了保存各次相乘结果X×y_i的开销。
  ② 每次得X×y_i后，不将它左移与前次部分积Pi相加，而将部分积Pi右移后与X×y_i相加。因为加法运算始终对部分积中高n位进行。故用n位加法器可实现二个n位数相乘。
  ③ 对乘数中为 “1”的位执行加法和右移，对为“0”的位只执行右移，而不执行加法运算。

无符号乘法运算的算法推导

• 上述思想可写成如下数学推导过程：
  
  • 上述推导过程具有明显的递归性质，因此，无符号数乘法过程可归结为循环计算下列算式的过程：设P0 = 0，每步的乘积为：
    P₁ = 2^-1 (P₀+ X × y_n)
    P₂ = 2^-1 (P₁+ X × y_n-1)
    …… ……
    P_n = 2^-1 (P_n-1+ X × y₁)
  • 其递推公式为：P_i+1 = 2^-1 (P_i + X×y_n-i) ( i = 0, 1, 2, 3, … , n-1 )
    最终乘积P_n = X×Y
• 迭代过程从乘数最低位y_n和P₀=0开始，经n次“判断–加法–右移”循环，直到求出P_n为止

32位乘法运算的硬件实现

• 每次循环都要对进位位C、乘积寄存器P和乘数寄存器实现同步逻辑“右移”
• 被乘数寄存器X：存放被乘数
• 乘积寄存器P：开始置初始部分积P0 = 0；结束时，存放的是64位乘积的高32位
• 乘数寄存器Y：开始时置乘数；结束时，存放的是64位乘积的低32位
• 进位触发器C：保存加法器的进位信号
• 循环次数计数器Cn：存放循环次数。初值32，每循环一次，Cn减1，Cn=0时结束
• ALU：乘法核心部件。在控制逻辑控制下，对P和X的内容“加”，在“写使能”控制下运算结果被送回P，进位位在C中
• 乘积和乘数被放在一个寄存器里，右移时会一起进行

Example：无符号整数乘法运算

• 举例说明：若需计算z=x* y; x、y和z都是unsigned类型。
  设x=1110 y=1101 应用递推公式： Pi=2-1(x*yi+ Pi-1)
  

3.3.3 原码乘法运算

• 用于浮点数尾数乘运算

• 符号与数值分开处理：积符异或得到，数值用无符号乘法运算

  • 例：设[x]原=0.1110 ，[y]原=1.1101，计算 [x×y]原
    解：数值部分用无符号数乘法算法计算：1110×1101= 1011 0110
    符号位：0  1=1，所以： [x×y]原=1. 10110110

• 一位乘法：每次只取乘数的一位判断，需n次循环，速度慢。

• 两位乘法：每次取乘数两位判断，只需n/2次循环，快一倍。

• 两位乘法递推公式：
  00：P_i+1=2^-2Pi
  01：P_i+1=2^-2(Pi +X)
  10：P_i+1=2^-2(Pi +2X)
  11：P_i+1=2^-2(Pi +3X)=2^-2(Pi+4X-X) = 2^-2(Pi -X) +X

  • 3X时，可以本次-X，下次再+X ！。部分积右移两位，相当于4X,可以减少一次X运算

• T触发器用来记录下次是否要执行“+X”“–X”（运算用“+[-X]补”实现）！
  

原码两位乘法举例

• 已知 [X]_原=0.111001， [Y]_原= 0.100111，用原码两位乘法计算[X×Y]原
  解： 先用无符号数乘法计算111001×100111，原码两位乘法过程如下：
  乘积P 乘数Y 触发器T
  
• Y的后两位和T用来判断执行+X、-X
• 采用补码算术右移，与一位乘法不同，Why？
  为模8补码形式(三位符号位)，Why？
  若用模4补码，则P和Y同时右移2位时，(符号位可能改变) 得到的P3是负数，这显然是错误的！需要再增加一位符号。

3.34 补码乘法运算

• 用于对什么类型的数据计算？已知什么？求什么？
  带符号整数！如int型
  如C语句：int x=-5，y=-4，z=x*y;
• 问题：已知[x]_补和[y]_补，求[x*y]_补
  因为[x*y]_补 ≠ [x]_补*[y]_补 ，故不能直接用无符号整数乘法计算。例如，若x=-5，求x*x=？： [-5]_补=1011
  [x*x]_补： [25]_补=0001 1001
  [x]_补*[x]_补：[-5]_补* [-5]_补=1111 1001
• 思路：根据[y]_补求y，将y的计算公式代入[x*y]_补
  令：[y]_补= y_n-1y_n-2…… y₁y₀
  则： y= - y_n-1.2^n-1+y_n-2 .2^n-2+ …… y₁ .2¹+ y₀ .2⁰
  因为[A+B]_补= [A]_补+[B]_补 ，只要将[x*y]_补转换为对若干数的和求补即可
  

如何求补码的真值

• 令：[y]_补= y_n-1y_n-2…… y₁y₀
  则： y= - y_n-1.2^n-1+y_n-2 .2^n-2+ …… y₁ .2¹+ y₀ .2⁰
  
• 符号为0， 则为正数，数值部分同
  符号为1，则为负数，数值各位取反，末位加1
  例如：补码“11010110”的真值为：-0101010=-(32+8+2)=-42

Booth’s 算法实质

同前面算法一样，将乘积寄存器右移一位。（这里是算术右移）

布斯算法举例

已知 [X]_补= 1 101，[Y]_补= 0 110，计算[X×Y]补，[-X]_补= 0011
X=-3，Y=6，X×Y=-18，[X×Y]补应等于11101110或结果溢出

• 补码两位乘可用布斯算法推导如下：
• [P_i+1]_补= 2^-1 ( [Pi]_补+ ( y_i-1– yi ) [X]_补)
• [P_i+2]_补= 2^-1 ( [Pi+1]_补+ ( y_i – y_i+1) [X]_补)
  = 2^-1 (^2-1 ( [Pi]_补+ ( y_i-1– y_i ) [X]_补) + ( y_i – y_i+1) [X]_补)
  = 2^-2 ( [Pi]_补+ (y_i-1 + y_i – 2y_i+1) [X]_补)
• 开始置附加位y-1为0，乘积寄存器最高位前面添加一位附加符号位0。
• 最终的乘积高位部分在乘积寄存器P中，低位部分在乘数寄存器Y中。
• 因为字长总是8的倍数，所以补码的位数n应该是偶数，因此，总循环次数为n/2。
  

补码两位乘法举例

3.3.5 快速乘法器

• 前面介绍的乘法部件的特点
  通过一个ALU多次做“加/减+右移”来实现

  • 一位乘法：约n次“加+右移”
  • 两位乘法：约n/2次“加+右移”

  所需时间随位数增多而加长，由时钟和控制电路控制

• 设计快速乘法部件的必要性
  大约1/3是乘法运算

• 快速乘法器的实现（由特定功能的组合逻辑单元构成）
  流水线方式
  硬件叠加方式（如：阵列乘法器）

流水线方式的快速乘法器

阵列乘法器的实现

3.3.6 原码除法运算

• 手算除法的基本要点
  ① 被除数与除数相减，够减则上商为1；不够减则上商为0。
  ② 每次得到的差为中间余数，将除数右移后与上次的中间余数比较。用中间余数减除数，够减则上商为1；不够减则上商为0。
  ③ 重复执行第②步，直到求得的商的位数足够为止。
• 除前预处理
  ①若被除数=0且除数≠0，或定点整数除法时|被除数|<|除数|，则商为0，不再继续
  ②若被除数≠0、除数=0，则发生“除数为0”异常（浮点数时为∞）
  （若浮点除法被除数和除数都为0，则有些机器产生一个不发信号的NaN，即“quiet NaN”
  只有当被除数和除数都≠ 0，且商≠ 0时，才进一步进行除法运算。
• 计算机内部无符号数除法运算
  • 与手算一样，通过被除数（中间余数）减除数来得到每一位商够减上商1；不够减上商0（从msb→lsb得到各位商）并将除数加回去
  • 基本操作为减（加）法和移位，故可与乘法合用同一套硬件
    • 两个n位数相除的情况：
      (1)定点正整数（即无符号数 ）相除：在被除数的高位添n个0
      (2)定点正小数（即原码小数）相除：在被除数的低位添加n个0
    • 这样，就将所有情况都统一为：一个2n位数除以一个n位数\
• 手工Divide Algorithm
  • 余数 - 除数 = 新余数
    新余数>=0.商左移上1
    新余数<0，商左移上0，恢复余数
    除数右移

Divide Algorithm example

1. • 被除数不变，除数进行右移
     Q：商；R：被除数（中间余数）; D：除数；–D = 1110
     
   • Q的第一个0是判断结果是否溢出的，0说明没有溢出，它不是真正的商，最后的商不需要第一个0
   • 每次减除数后，如果R中间余数第一位是0，商为1，反之为0

第一次试商为1时的情况

• 问题：第一次试商为1，说明什么？
  商有n+1位数，因而溢出！
• 若是2n位除以n位的无符号整数运算，则说明将会得到多于n+1位的商，因而结果“溢出”（即：无法用n位表示商）。
  例：1111 1111/1111 = 1 0001
  若是两个n位数相除，则第一位商为0，且肯定不会溢出，为什么？
  最大商为:0000 1111/0001=1111
  若是浮点数中尾数原码小数运算，第一次试商为1，则说明尾数部分有“溢出”，可通过浮点数的**“右规”消除“溢出”**。所以，在浮点数运算器中，第一次得到的商“1” 要保留。
  例：0.11110000/0.1000=+1.1110

无符号数除法算法的硬件实现

• 除数寄存器Y：存放除数。
• 余数寄存器R：初始时高位部分为高32位被除数；结束时是余数。
• 余数/商寄存器Q：初始时为低32位被除数；结束时是32位商。
• 循环次数计数器Cn：存放循环次数。初值是32，每循环一次，Cn减1，当Cn=0时，除法运算结束。
• ALU：除法核心部件。在控制逻辑控制下，对于寄存器R和Y的内容进行“加/减”运算，在“写使能”控制下运算结果被送回寄存器R。
  • R和Q同步“左移”，Q空出位上“商”，商的各位逐次左移到Q中。
  • 由控制逻辑根据加减结果决定商为0还是1
  • 减----试商，加----恢复余数。

Divide Algorithm example

2. 改进
   • 每次被除数左移，除数不动，中间余数和商一起放在R
     R：被除数（中间余数）; D：除数；–D = 1110
     
   • 从例子可看出：
     每次上商为0时，需做加法以“恢复余数” 。所以，称为“恢复余数法
   • 也可在下一步运算时把当前多减的除数补回来。这种方法称为“不恢复余数法”，又称“加减交替法”。

不恢复余数除法(加减交替法)

• 恢复余数法可进一步简化为“加减交替法”
• 根据恢复余数法(设B为除数，R_i为第i次中间余数)，有：
  • 若R_i<0,则商上“0”，并做加法恢复余数，即：
    R_i+1=2(R_i+2ⁿ|B|)-2ⁿ|B|=2R_i + 2ⁿ|B| (“负，０，加”)
  • 若R_i>=0,则商上“1”，不需恢复余数，即：
    R_i+1=2R_i - 2ⁿ|B| (“正，１，减”)
  • 将做加法恢复余数的步骤放到下一次进行可以直接省略下次的减除数运算
• 省去了恢复余数的过程
  注意：最后一次上商为“0”的话，需要“纠余”处理，即把试商时被减掉的除数加回去，恢复真正的余数。
  不恢复余数法也称为加减交替法

带符号数除法

• 原码除法
  • 商符和商值分开处理
    • 商的数值部分由无符号数除法求得
    • 商符由被除数和除数的符号确定：同号为0，异号为１
  • 余数的符号同被除数的符号
• 补码除法
  • 方法1：同原码除法一样，先转换为正数，先用无符号数除法，然后修正商和余数。
  • 方法2：直接用补码除法，符号和数值一起进行运算，商符直接在运算中产生。
• 若是两个n位补码整数除法运算，则被除数进行符号扩展。
• 若被除数为2n位，除数为n位，则被除数无需扩展。

原码除法举例

• 已知 [X]原 = 0.1011
  [Y]原 = 1.1101
  用恢复余数法计算[X/Y]原
  • 解：商的符号位：0 ⊕ 1 = 1
    减法操作用补码加法实现，是否够减通过中间余数的符号来判断，所以中间余数要加一位符号位。
    [|X|]补 = 0.1011
    [|Y|]补 = 0.1101
    [–|Y|]补 = 1.0011
    
  • 若求[Y/X]原结果如何？
  • 思考：若实现无符号数相除，即1011除以1101，则有何不同？结果是什么？
    被除数高位补0，1011除以1101，结果等于0
• 已知 [X]原 = 0.1011
  [Y]原 = 1.1101
  用加减交替法计算[X/Y]原
  • 解：[|X|]补 = 0.1011
    [|Y|]补 = 0.1101
    [–|Y|]补 = 1.0011
    
  • 用被除数（中间余数）减除数试商时，怎样确定是否“够减”？
    中间余数的符号！（正数-正数）
  • 补码除法能否这样来判断呢？
    不能，因为符号可能不同！

3.3.7 补码除法运算

• 补码除法判断是否“够减”的规则
  （1）当被除数（或中间余数）与除数同号时，做减法，若新余数的符号与除数符号一致（正(负)-正(负)=正(负)）表示够减，否则为不够减
  （2）当被除数（或中间余数）与除数异号时，做加法，若新余数的符号与除数符号一致表示不够减，否则（正(负)+负(正)=正(负) ）为够减
  • 总结：余数变号不够减，不变号够减
    

实现补码除法的基本思想

• 从上表可得到补码除法的基本算法思想：
  • （1）运算规则：
    当被除数（或中间余数）与除数同号时，做减法；
    　　　　　　　　　　　　　　异号时，做加法。
  • （2）上商规则：
    　　 若余数符号不变，则够减，商1；否则不够减，商0 。
  • （3）修正规则：
    • 若被除数与除数符号一致，则商为正。 此时，应“够减，商1；
      不够减，商0”，故上商规则正确，无需修正
    • 若被除数与除数符号不一致，则商为负。此时，应 “够减，商0；
      不够减，商1”，故上商规则相反，需修正
  • 即：若商应为负数，则需要“各位取反，末位加1”来得到真正的商
  • 补码除法也有：恢复余数法和不恢复余数法

补码恢复余数法

• 两个n位带符号整数相除算法要点：
  • (1) 操作数的预置：
    除数装入除数寄存器Y，被除数经符号扩展后装入余数寄存器R和余数/商寄存器Q
  • (2) R和Q同步串行左移一位。
  • (3) 若R与Y同号，则R = R–Y；否则R = R+Y，并按以下规则确定商值q₀：
    ① 若中间余数R=0或R操作前后符号未变，表示够减，则q₀置１，转下一步；（这里可以比较R操作前后符号还不是比较R和余数是因为用的是恢复余数法）
    ② 若操作前后R的符号已变，表示不够减，则q₀置0，恢复R值后转下一步；
  • (4) 重复第(2)和第(3)步，直到取得n位商为止。
  • (5) 若被除数与除数同号，则Q中就是真正的商；否则，将Q求补后是真正的商。
    （即：若商应为负数时，则需要“各位取反，末位加1”来得到真正的商）
  • (6) 余数在R中。
• 问题：如何恢复余数？通过“做加法”来恢复吗？
  • 无符号数（或原码）除法通过“做加法”恢复余数，但补码不是!
  • 补码：若原来是 R = R–Y，则执行R = R+Y 来恢复余数；
    若原来是 R = R+Y，则执行R = R–Y 来恢复余数。
    

补码不恢复余数法

判断是否同号与恢复余数法不同，不是新老余数之间！而是余数和除数之间

• 算法要点：
  • (1) 操作数的预置：
    除数装入除数寄存器Y，被除数经符号扩展后装入余数寄存器R和余数/商寄存器Q。
  • (2) 根据以下规则求第一位商q_n：
    若被除数X与Y同号，则R₁=X–Y；否则R₁ =X+Y，并按以下规则确定商值q_n：
    ① 若新的中间余数R₁与Y同号，则q_n置１，转下一步；（这里可以只能比较R和余数是因为用的是不恢复余数法，中间余数上商0没有恢复）
    ② 若新的中间余数R₁与Y异号，则q_n置0，转下一步；
    q_n用来判断是否溢出，而不是真正的商。以下情况下会发生溢出：
    若X与Y同号且上商q_n=1，或者，若X与Y异号且上商q_n = 0。
  • (3) 对于i =1到n ，按以下规则求出n位商：
    ① 若Ri与Y同号，则q_n-i置１，R_i+1 = 2R_i –[Y]_补，i = i +1；
    ② 若Ri与Y异号，则q_n-i置0，R_i+1 =2R_i+[Y]_补，i = i +1；
  • (4) 商的修正：最后一次Q寄存器左移一位，将最高位q_n移出，最低位置上商q₀。若被除数与除数同号， Q中就是真正的商；否则，将Q中商的末位加1。
  • (5) 余数的修正：若余数符号同被除数符号，则不需修正，余数在R中；否则，按下列规则进行修正：当被除数和除数符号相同时，最后余数加除数；否则，最后余数减除数。
• 补码不恢复余数法也有一个六字口诀“同、1、减；异、0、加”。
• 其运算过程也呈加/减交替方式，因此也称为“加减交替法”。

举例：-9/2

• 将X=-9和Y=2分别表示成5位补码形式为：
  [X]补 = 1 0111
  [Y]补 = 0 0010
  被除数符号扩展为：
  [X]补=11111 10111
  [–Y] 补 = 1 1110
• 若Ri与Y同号，则q_n-i置１，R_i+1 = 2R_i –[Y]_补，
  若Ri与Y异号，则q_n-i置0，R_i+1 =2R_i+[Y]_补，
  • 同、1、减
    异、0、加
    
• X/Y= – 0100B = – 4
  余数为 –0001B = –1
  将各数代入公式:
  “除数×商+余数= 被除数”进行验证，得
  2×(–4) +(–1) = –9
• 编译器遇到x/2时会如何做？
  右移一位吗！

定点运算器芯片举例-AM2901A芯片框图

运算部件通常指ALU、移位器、寄存器组，加上用于数据选择的多路选择器和实现数据传送的总线等构成的一个运算数据通路。
"运算器(Operate Unit）、“运算部件(Operate Unit)”、"功能部件(Function Unit）w“执行部件（Execution Unit)”和“数锯通路(DataPath)”的含义基本上一样，只是强调的侧重不同。
定点部件：
ALU、GRS、MUX、Shifters、Q寄存器等，CU控制执行。

3.4整数乘除运算

3.5 浮点数运算

计算机组成与系统结构-第3章 运算方法和运算部件 下

标签：运算,符号,补码,系统结构,部件,加法器,余数,进位
From： https://blog.csdn.net/rc4gyyc/article/details/136901925