下载文档原格式
补码一位乘法校正法补码一位乘法校正法是一种用于检测和纠正乘法器误差的方法。
在数字电路中，乘法器是一种非常重要的组件，负责执行数字信号的乘法运算。
然而，由于硬件设计和制造的不完美，乘法器可能会产生误差，导致输出结果不准确。
补码一位乘法校正法就是一种常用的解决方案。
在理解补码一位乘法校正法之前，我们首先需要了解补码的概念。
补码是一种用于表示有符号整数的编码方式。
在计算机中，负数一般使用补码表示，这样可以简化运算。
补码的计算方法是将原码的符号位保持不变，其余位按位取反后加1。
例如，-5的原码为10000101，补码为11111011。
补码一位乘法校正法的基本思想是将乘法器的输出结果与真实的乘法结果进行比较，并根据比较结果来调整乘法器的输出。
具体步骤如下：1. 乘法器的输入为两个n位的补码数字，输出为一个2n位的补码数字。
2. 将乘法器的输出结果与真实的乘法结果进行比较。
如果两者相等，则乘法器的输出是正确的；如果不相等，则说明乘法器存在误差。
3. 根据乘法器输出的最高位进行判断。
如果最高位为1，说明乘法器的输出是负数，需要对乘法器的输出进行补码取反操作；如果最高位为0，则不需要进行操作。
4. 将乘法器的输出与校正后的结果进行比较。
如果两者相等，则乘法器的输出是正确的；如果不相等，则说明乘法器的误差无法通过补码一位乘法校正法进行修复。
补码一位乘法校正法的原理是通过对乘法器输出结果的最高位进行判断，来确定是否需要对乘法器的输出进行补码取反操作。
通过这种方法，可以有效地检测和纠正乘法器误差，提高乘法器的准确性和可靠性。
然而，补码一位乘法校正法只能处理一位乘法误差，对于多位乘法误差无法进行有效的修复。
在实际应用中，补码一位乘法校正法通常与其他纠错技术结合使用，以进一步提高乘法器的准确性。
例如，可以将补码一位乘法校正法与冗余校验码相结合，通过对乘法器输出结果进行校验和校正，来实现更可靠的乘法运算。
总结起来，补码一位乘法校正法是一种用于检测和纠正乘法器误差的方法。
二进制补码一位乘法规律的推导作者：孙启良来源：《电脑知识与技术》2009年第25期摘要:计算机采用补码运算,速度快效率高,但其递推公式推导复杂。
补码乘法也是《计算机组成原理》课程的难点。
文章从补码与真值的关系出发,首先推导出补码的右移公式,最终给出了二进制补码一位乘法规则的较全面的推导过程。
关键词:机器数;真值;补码;补码阵列乘法器中图分类号:TP332文献标识码:A文章编号:1009-3044(2009)25-7278-03A Detailed Derivation of the Rules about Two's Complement MultiplicationSUN Qi-liang(University of Ji'nan, Ji'nan 250022, China)Abstract: The computer using two's complement is faster and more efficient,but the derivation of the rules about two's complement multiplication is Complex.Two's complement multiplication is also a difficulty of the course "Principles of Computer Organization".This article starts from the relations of two's complement and the true value.First,it deduces a formula about the shifting to right of two's complement.Finally,it gives the detailed rules about two's complement multiplication.Key words: machine number; true value; two's complement; two's complement array multiplier在计算机中表示的带符号的二进制数称为“机器数”。
定点补码一位乘的运算方法定点补码一位乘的运算方法:按乘数为正、负两种情况讨论:1.被乘数[x]补符号任意,乘数[y]补为正设[x]补=x0.x1x2…x n[y]补=y0.y1y2…y n根据补码定义可推得: [x]补=2+x=2n+1+x (MOD2)[y]补=y=0.y1y2...y n其中x,y为真值.故: [x]补[y]补=(2n+1+x)*y=2n+1+xy=21*2n(0.y1y2...y n)+xy=2(y1y2...y n)+xy注意0.y1y2...y n被2n乘已成为正整数.根据模的运算性质有:2(y1y2...y n)=2 (mod 2)所以 [x]p*[y]p=2+x*y=[x*y]补(mod 2)即 [x*y]p=[x]p*[y]p=[x]p*y(因为y s=0为正) =[x]p* (0.y1y2...y n) (1) 当乘数y>0,不管x的符号如何,将[x]p*y=[x*y]p2.被乘数[x]p符号任意,乘数y为负[x]补=x0.x1x2…x n[y]补=1.y1y2…y n =2+y (mod 2)该项得: y=[y]补-2=1.y1y2…y n -2=1+0.y1y2...y n-2=0.y1y2...y n-1 所以 x*y=x*(0.y1y2...y n-1)=x*(0.y1y2...y n)-x将上式两边取补所以有: [x*y]p=[x(0.y1y2...y n)-x]p=[x(0.y1y2...y n)]p-[x]p=[ x(0.y1y2...y n)]p+ [-x]p因为 (0.y1y2...y n)>0 正数的补码 = 本身所以 [x(0.y1y2...y n)]p= [x]p*(0.y1y2...y n)所以 [x*y]p= [x]p*(0.y1y2...y n) -[x]p (2)将(1)和(2)综合起来:得统一的算式[x*y]p= [x]p*(0.y1y2...y n) -[x]p*y0 (3)=[x]p*(-y0+0.y1y2...y n)分析:右边第二项[x]p*y0当y为正 y0=0 该项不存在 (1)y为负 y0=1 该项为[x]p (2)将(3)式展开,推出逻辑实现分步算法:获得各项部分积的累加形式.[x*y]p= [x]p*(0.y1y2...y n) -[x]p*y0= [x]p*(2-1y1+2-2y2+…+2-n y n) -[x]p*y0=[x]p*[-y0+ (y1-2-1y1)+( y22-1-2-2y2)+…+(2-(n-1)y n-2-n y n) =[x]p*[(y1-y0)+(y2-y1)2-1+…+(y n-y n-1)2-(n-1)+(y n+1-y n) 2-n] 说明:(1) 0.y1y2...y n可写成2-1y1+2-2y2+…+2-n y n(2)提公因式[x]p将 -y0 提前(3)去括号重新组合(4) y1-2-1y1=(20-2-1)y1=(1-1/2) y1=0.5yy22-1-y22-2=(2-1-2-2)*y2=2-2y2[x*y]补= [x]补*(0.y1y2...y n) -[x]补*y0= [x]补*(2-1y1+2-2y2+…+2-n y n) -[x]补*y0=[x]补*[-y0+ (y1-2-1y1)+( y22-1-2-2y2)+…+(2-(n-1)y n-2-n y n)=[x]补*[(y1-y0)+(y2-y1)2-1+…+(y n-y n-1)2-(n-1)+(y n+1-y n) 2-n]将[x]p乘进去,然后从第2项开始,每次提2-1=(y1-y0)[x]p+(y2-y1)2-1[x]p+…+(y n+1-y n)2-n[x]p=(y1-y0)[x]p+2-1[(y2-y1)[x]p+(y3-y2)2-1[x]p+(y4-y3) 2-2[x]p…+(y n+1-y n) 2-(n-1) [x]p]1=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1[(y3-y2)[x]p+(y4-y3)2-1[x]p…+(y n+1-y n) 2-(n-2)[x]p]2}1=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1{(y3-y2)[x]p+2-1[(y4-y3)[x]p…+(y n+1-y n) 2-(n-3)[x]p]3}2}1…………………=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1{(y3-y2)[x]p+2-1{(y4-y3)[x]p…+2-1 {(y n-y n-1)[x]p +2-1 [(y n+1-y n)[x]pn]n}n-1…}3}2}1说明:式中y n+1是增设的附加位,初始值位0.a i取决于相邻两位乘数的比较结果显然(4)式就是部分积累加的形式若定义[p0]补位初始部分积=0. [p1]补……[p n]补依次位各步求得的累加并右移后的部分积.将(4)改写:更接近于分步运算逻辑实现[x*y]p=[x]p*[(y1-y0)+(y2-y1)2-1+…+(y n-y n-1)2-(n-1)+(y n+1-y n) 2-n]将[x]p乘进去,然后再次提2-1=(y1-y0)[x]p+(y2-y1)2-1[x]p+…+(y n+1-y n)2-n[x]p=(y1-y0)[x]p+2-1[(y2-y1)[x]p+(y3-y2)2-1[x]p+(y4-y3) 2-2[x]p…+(y n+1-y n) 2-(n-1) [x]p]1=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1[(y3-y2)[x]p+(y4-y3)2-1[x]p…+(y n+1-y n) 2-(n-2)[x]p]2}1=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1{(y3-y2)[x]p+2-1[(y4-y3)[x]p…+(y n+1-y n) 2-(n-3)[x]p]3}2}1…………………=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1{(y3-y2)[x]p+2-1{(y4-y3)[x]p…+2-1 {(y n-y n-1)[x]p +2-1 [(y n+1-y n)[x]pn]n}n-1…}3}2}1y>0 [x*y]p= [x]p*(0.y1y2...y n) (1)y<0 [x*y]p= [x]p*(0.y1y2...y n) -[x]p (2)统一算式: [x*y]p= [x]p*(0.y1y2...y n) -[x]p*y0 (3)=[x]p*(-y0+0.y1y2...y n)化简: =[x]p*[(y1-y0)+(y2-y1)2-1+…+(y n-y n-1)2-(n-1)+(y n+1-y n) 2-n] (4)将[x]p乘进去从第二项开始,每次提2-1 ==(y1-y0)[x]p+2-1[(y2-y1)[x]p+(y3-y2)2-1[x]p+(y4-y3)2-2[x]p…+(y n+1-y n) 2-(n-1) [x]p]1……………………=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1{(y3-y2)[x]p+2-1{(y4-y3)[x]p…+2-1{(y n-y n-1)[x]p +2-1 [(y n+1-y n)[x]pn]n}n-1…}3}2}1=(y1-y0)[x]p+2-1{(y2-y1)[x]p+2-1{(y3-y2)[x]p+2-1{(y4-y3)[x]p…+2-1{(y n+1-y n)[x]p +[[P0]补]n}n-1…}3}2}1[P1]补写成递推公式:[P0]补=0[P1]补=2-1{(y n+1-y n)[x]p +[[P0]补]n} 令y n+1=0[P2]补=2-1{(y n-y n-1)[x]p +[[P1]补]n}………………[P i]补=2-1{(y n-i+2-y n-i+1)[x]p +[[P i-1]补]n}………………[P n]补=2-1{(y2-y1)[x]p +[[P n-1]补]n}所以: [ x*y]补=[[P n+1]补]= (y1-y0)[x]p+[P n]补<4> 注意:(1)y0 是乘数y的符号位.y n+1是人为附加位 =0.使式子规范整齐.(2)开始运算时p0=0 , y n+1=0部分积※新部分积获得的方法:1、乘数相邻的两位求差。
![定点补码一位乘法的实现算法 用[x]补×[y]补直接求[x×y]补](https://img.taocdn.com/s1/m/941c3a6daf1ffc4ffe47ac2f.png)
[计算机组成原理]Booth算法——补码⼀位乘法x * y = z运算规则：1.和原码⼀位乘法不同，补码⼀位乘法的符号位是参加运算的，且运算结果和所有参加运算的数都是补码形式。
2.乘数 x 取双符号位参与运算，部分积的初始值为0；乘数 y 取单符号位参与运算。
3.乘数 y ⾸先在末尾添加⼀个辅助位 0 ，每次讨论都是取 y 的最后两位，但每次移动仅移动⼀位。
4.判断 y 的最后两位是规则如下：00 或者 11 时，直接右移⼀位；01时，先加 x的补，然后右移⼀位；10时，先加 -x的补，然后右移⼀位。
5.有个特例，最后⼀步不⽤右移了。
举个栗⼦：设 x = -0.1101 , y = 0.1011则 [x]补 = 11.0011 ，[-x]补 = 00.1101⼀开始部分积初始值：00.0000先给y补⼀个辅助位0，得到 y = 0.10110⾸先，从y的最后两位开始看，0.10110 ，为 10 ，对应规则 “先加[-x]补，再右移⼀位” ：部分积 00.0000 + 00.1101 = 00.1101 ，右移⼀位得到 00.01101接着，y 右移⼀位再看，0.10110，为 11 ，对应规则“直接右移⼀位”：部分积 00.001101然后，y再右移⼀位再看，0.10110 ，为 01 ，对应规则“先加[x]补，再右移⼀位”：00.001101 部分积+ 11.0011 [x]补--------------------= 11.011001 部分积部分积 00.001101 + 11.0011 = 11.011001 ，右移⼀位得到11.1011001 （注意这⾥符号位移动后，仍然保持为 11）接着，y再右移⼀位再看，0.10110 ，为 10 ，对应规则“先加[-x]补，再右移⼀位”：部分积 11.1011001 + 00.1101 = 00.1000001 ，右移⼀位得到 00.01000001最后，y再右移⼀位再看，0.10110 ，为 01 ，对应规则“先加[x]补，再右移⼀位”：部分积 00.01000001 + 11.0011 = 11.01110001 ，但这已经是最后⼀步，不⽤再右移了，所以最后结果是 1.01110001 （注意：这是x*y的补码）。
定点补码一位乘的运算方法
定点补码是一种表示有符号整数的方法，其中最高位为符号位，表示
正负。
一位乘是指使用一位数与多位数进行乘法运算。
一位乘的运算方法可以通过以下步骤进行：
1.将乘数和被乘数转换为定点补码表示。
如果乘数和被乘数是十进制数，首先用二进制表示，然后将其转换为定点补码。
对于正数，最高位为0；对于负数，最高位为1，其余位取反加1
2.确定乘法操作中的最高位。
根据定点补码表示，最高位是符号位。
将乘数和被乘数的符号位相乘，得到结果的符号位。
3.将乘数的符号位扩展到与被乘数的位数相同，并将结果的符号位放
在最高位。
4.对每一位进行乘法运算。
对于每一位，将乘数与被乘数的对应位相乘，得到一个部分乘积。
5.将所有部分乘积相加，得到最终结果。
对于每一位，将所有部分乘
积相加，得到该位的结果。
如果有进位，要将进位加到下一位的运算结果中。
需要注意的是，一位乘的运算方法是逐位运算的，所以需要对每一位
进行乘法运算，然后将结果相加。
在相加的过程中，需要考虑进位的情况。
此外，定点补码表示的补码运算方法也需要掌握，以正确进行符号位的计算。
以上是一位乘的运算方法的简要介绍，详细的运算步骤可以通过具体
的例子进行演示和说明。
在定点乘法运算中，补码乘法分为补码一位乘法和补码两位乘法。
而补码一位乘法又分为较正法和比较法（Booth算法）两种。
其中，较正法是比较法的基础。
因此，掌握较正法是学习补码一位乘法的关键。
下面，我们就对较正法进行深入分析。
一、较正法公式[XY]补= [X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0其中，X、Y是两个定点数的真值，[Y]补=Y0.Y1,Y2, … ,Y n，Y0是符号位。
为了推导出此公式，我们分情况来进一步分析。
1、Y=0在这种情况下，[Y]补=Y=0.0,0, … ,0=0。
[XY]补=0=[X]补*(0.0,0, … ,0)+[-X]补*0=[X]补*(0.Y1,Y2, … ,Y n)+[-X]补*Y02、X>=0, Y>0在这种情况下，[X]补=X，[Y]补=Y，且Y0=0。
不难看出，[XY]补=XY=[X]补*Y=[X]补*(Y0.Y1,Y2, … ,Y n)+[-X]补*0=[X]补*(0.Y1,Y2, … ,Y n)+[-X]补*Y0到此为止，我们还有两种情况尚未讨论，一种情况是X<0, Y>0，一种情况是Y<0。
前一种情况是本文讨论的重点。
与很多教材上的推导方法不同，本文采用与原码一位乘法相对照来证明此种情况。
此方法用到的知识点有原码一位乘法和补码移位规则。
首先，我们先来回顾一下这两个知识点。
二、原码一位乘法原码一位乘法基本上是从手算法则演变过来的。
我们知道，两个数相乘的手算法则是“绝对值相乘；同号得正，异号得负”。
原码一位乘法也采用这种方法。
设[X]原=X s.X1,X2, … ,X n[Y]原=Y s.Y1,Y2, … ,Y n因为[X]原=X，[Y]原=Y，[XY]原=XY所以[XY]原=[X]原*[Y]原则P=|[XY]原|=|[X]原|*|[Y]原|符号位P s=X s⊕Y s下面，我们对P进一步分析。
设A=|[X]原|则P=|[X]原|*|[Y]原|=A*( 0.Y1,Y2, … ,Y n)=0.1{ Y1A+(0. Y2, … ,Y n)}=0.1{ Y1A +0.1{ Y2 A +(0.Y3, … , Y n)}}=0.1{ Y1A +0.1{ Y2 A + … +0.1{Y n (A+0)}…}}这样，我们就得到了原码一位乘法的公式：P=0.1{ Y1A +0.1{ Y2 A + … +0.1{Y n (A+0)}…}}P s=X s⊕Y s其中，P=|[XY]原|，P s为乘积的符号位，A=|[X]原|，[X]原=X s.X1,X2, … ,X n，[Y]原=Y s.Y1,Y2, … ,Y n，X s和Y s是符号位。
三、补码移位规则对于一个数的补码来说，左移一位相当于该数真值乘以2，右移一位相当于该数真值乘以1/2。
1、非负数补码移位规则：除符号位外剩余部分作相应移位后空位补0。
因为非负数补码与原码相同，所以其移位规则也相同，这很容易理解。
2、负数移位规则：除符号位外剩余部分作相应移位后，左移空位补0，右移补1。
因为补码一位乘法只涉及到补码右移，所以这里只给出负数补码右移规则证明。
证明如下：设[X]补＝X0.X1,X2, … ,X n因为[X]补＝2+X则X＝[X]补－2＝X0.X1,X2, … ,X n－2因为X为负数，所以X0＝1，则X＝－X0+0.X1,X2, … ,X n （注1）1/2X＝－1/2 X0+1/2（0.X1,X2, … ,X n）＝－X0+1/2 X0+1/2（0.X1,X2, … ,X n）＝－X0+1/2（X0.X1,X2, … ,X n）＝－X0+0.X0, X1,X2, … ,X n-1写成补码形式，即得[1/2X]补＝X0.X0, X1,X2, … ,X n-1即[1/2X]补＝0.1[X]补（0.1可以看成是右移一位操作）四、较正法公式（续）3、X<0, Y>0证法1：前面已经讲过，原码一位乘法的公式为P=0.1{ Y1A +0.1{ Y2 A + … +0.1{Y n (A+0)}…}}不难发现，这个式子里包含着一个递归操作，递归因子是R＝0.1{Y m (A+Z)}所以，我们只需证明下面这个式子即可：0.1{Y m ([B]补+[Z]补)}＝[ 0.1{Y m (B+Z)}]补证明如下：0.1{Y m ([B]补+[Z]补)}＝0.1{Y m ([B+Z]补)}＝0.1{[Y m (B+Z)]补} （Y m只有0、1这两种可能）＝[ 0.1{Y m (B+Z)}]补（补码右移一位）这里需要注意一点，如果两个数相加得到的结果发生溢出，若结果向右移动一位，则原码空位补1，补码空位补0。
对上面式子的两端进行同等递归后可得[X]补*Y=[XY]补所以[XY]补= [X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0证法2：[X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0＝[X]补*(0.Y1,Y2, … ,Y n)＝0.1Y1[X]补+0.01Y2[X]补+ … +0.00 … 01Y n[X]补＝[0.1Y1X]补+[0.01Y2X]补+ … +[0.00 … 01Y n X]补（0.00 … 01可以看成是右移n位操作）＝[XY]补简单来说，因为补码和原码一样支持相加和右移操作，所以补码也支持非负乘操作。
4、Y<0前面已经证明X＝－X0+0.X1,X2, … ,X n所以，当Y<0时，Y＝0.Y1,Y2, … ,Y n－1XY＝X（0.Y1,Y2, … ,Y n）－X[XY]补＝[X（0.Y1,Y2, … ,Y n）－X]补＝[X]补（0.Y1,Y2, … ,Y n）+[－X]补＝[X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0证毕。
五、常见证法存疑与解惑在证明X<0, Y>0的情况时，有些书上是这样证明的：因为[X]补＝2+X＝2n+1+X （mod 2）所以[X]补*[Y]补＝[X]补*Y＝（2+X）*Y （mod 2）＝（2n+1+X）*Y （mod 2）＝2n+1Y+XY （mod 2）＝2n+1（0.Y1,Y2, … ,Y n）+XY （mod 2）因为2n（0.Y1,Y2, … ,Y n）是个大于或等于1的正整数，所以2n+1（0.Y1,Y2, … ,Y n）＝2 （mod 2）所以[X]补*[Y]补＝2+XY （mod 2）＝[XY]补我的第一个疑问是：当2+X＝2n+1+X （mod 2）时，（2+X）*Y≡（2n+1+X）*Y （mod 2）吗？显然，左右两边不是恒等的。
因为Y为小数，所以在模2的情怳下，2Y不恒等于2n+1 Y，所以上式不成立。
我的第二个疑问是：[X]补*Y＝（2+X）*Y （mod 2）吗？我们很容易产生这样的误区，认为上式是相等的。
但是仔细推敲一下，便会发现，上式左边是补码运算，遵守补码运算法则。
而右边是真值运算，可以看作原码运算，遵守原码运算法则。
更细一步说，在进行右移运算时，上式左边空位补1，右边空位补0。
所以，上式不成立。
我的第三个疑问是：[X]补*Y到底等于什么呢？下面我们就来解决这一疑问。
设[X]补＝（11…1）X0.X1,X2, … ,X n设2+X＝（00..0）X0.X1,X2, … ,X n上面括号里的1或0是为该数右移时补空位用的，遵守原码空位补0、补码空位补1原则。
因为X是负数，所以X0＝1，对于原码范畴的2+X来讲，发生溢出，右移一位时空位补1。
所以：右移1位时，[X]补＝（11…1）1.X0,X1,X2, … ,X n2+X＝（00..0）0.X0,X1,X2, … ,X n两者相差1。
右移2位时，[X]补＝（11…1）1.1,X0,X1,X2, … ,X n2+X＝（00..0）0.0,X0,X1,X2, … ,X n两者相差1.1。
……又[X]补*Y＝0.1Y1[X]补+0.01Y2[X]补+ … +0.00 … 01Y n[X]补（2+X）*Y＝0.1Y1（2+X）+0.01Y2（2+X）+ … +0.00 … 01Y n （2+X）两者相差1 Y1+1.1 Y2+1.11 Y3+……所以[X]补*Y＝（2+X）*Y+1 Y1+1.1 Y2+1.11 Y3+……（mod 2）＝2（0.Y1,Y2, … ,Y n）+XY+1 Y1+1.1 Y2+1.11 Y3+……（mod 2）＝2（Y1+Y2+ … +Y n）+XY （mod 2）因为Y1+Y2+ … +Y n是大于或等于1的正整数，所以上式＝2+XY （mod 2）＝[XY]补这里需要说明一下，因为[X]补*Y过程中一直在进行模2运算，所以后面必须有模2操作。
六、结束语由于本文采用Word2003格式编写，不便举例，还望谅解。
注1：这是补码的真值表示公式，同样适用于非负数，这里不再证明。
参考文献1、计算机组成原理PPT－刘子良2、补码一位乘法的证明－quzy。
