计算机算法(共102张)

计算机算法第一页，共102页。主要内容二进制整数无符号二进制整数补码表示的带符号二进制整数加减法算法及VerilogHDL实现加法器和减法器设计先行进位加法器设计乘法算法及VerilogHDL实现无符号数乘法器设计带符号数乘法器设计无符号数Wallace树型乘法器设计(略)带符号数Wallace树型乘法器设计(略)除法算法及VerilogHDL实现(略)恢复余数器除法设计不恢复余数器除法设计带符号数不恢复余数除法器设计Goldschmidt除数算法(略)Newton-Raphson除法算法(略)开方算法及VerilogHDL实现(略)逻辑运算(增加)算术逻辑运算单元(ALU)举例(增加)第二页，共102页。3.1二进制整数计算机中所有的信息，包括指令和数据，都是用二进制数表示的。假设有一个32位的二进制数00110011110111100000000100000000它到底表示是什么？指令？数据：整数，浮点数？图形图像？音乐？IP地址？？缺点：读写起来太长，不方便。第三页，共102页。3.1.1无符号二进制整数(略)3.1.2补码表示的带符号二进制整数(略)第四页，共102页。3.2定点整数的加减法算法及VerilogHDL实现影响运算器硬件设计的因素：从数值数据类型区分。定点数、浮点数、BCD码数据。从编码方案区分。原码、补码、反码、移码。从数据运算的算法看，重点是解决运算的高速度与硬软件实现的简便与经济性的矛盾与协调。第五页，共102页。运算器有:定点运算器----用硬件直接完成定点数算术逻辑运算。如果用定点运算器完成浮点数的算术运算，则要由子程序实现，速度慢。浮点运算器----主要用硬件完成浮点数算术运算。第六页，共102页。3.2.1补码数加法器和减法器设计补码定点加减法运规则：

[X+Y]补=[X]补+[Y]补

(mod2)

[X-Y]补=[X]补+[-Y]补

(mod2)例1，，求[X+Y]补.解[X]补，[Y]补

[X]补

+[Y]补

[X]补+[Y]补

所以[X+Y]补注：这里的小数点可以理解为符号与数值的分隔符第七页，共102页。例，用补码加减法规则求X-Y。解[X]补，[Y]补

[-Y]补

[X]补

+[-Y]补

[X]补+[-Y]补

所以[X-Y]补

第八页，共102页。运算器电路的实现补码加减法可用统一的方式处理。用补码实现加减法对运算器有什么要求？公式：

[X+Y]补=[X]补+[Y]补

[X-Y]补=[X]补+[-Y]补

(mod2)由[Y]补求[-Y]补是把[Y]补的每一位取反，再在最低位加1来实现。补码加减法运算逻辑电路框图如下图。

第九页，共102页。图实现补码加减运算的逻辑电路第十页，共102页。A、B、C只是其中的一位。每个框中的1代表Q，0代表/Q。用同一套加法器电路，可以完成[X+Y]补和[X-Y]补的运算。实现[X+Y]补和[X-Y]补的差别：加Y用的是Y→F控制信号有效（‘1’），1→F控制信号无效（‘0’）。减Y用的是/Y→F和1→F两个控制信号都有效（‘1’）。第十一页，共102页。需要增加判别运算结果溢出的功能加法溢出的条件符号相同的两个数相加。减法溢出的条件符号不同的两个数相减。例如[X]补=01011，[Y]补=01000，则[X+Y]补=01011+01000=10011(溢出)例如[X]补=01011，[Y]补=10111

[-Y]补=01001则[X-Y]补=01011+01001=10100(溢出)第十二页，共102页。结论：(1)两个符号相同的补码数相加，如果和的符号与加数符号相反，或者符号相反的两个补码数相减，差的符号与减数符号相同，都表示运算结果溢出。(2)利用进位判断。即两个补码数实现加减法运算时，若最高数值位向符号位的进位值与符号位产生的进位输出值不相同，则表示产生了溢出。表示为：第十三页，共102页。表双符号位溢出判断(3)用双符号位判断溢出如下表。结果符号位溢出情况00无溢出01正溢出10负溢出11无溢出第十四页，共102页。例如[X]补，[Y]补则[X+Y]补例如[X]补，[Y]补，

[-Y]补则[X-Y]补注意：采用双符号方案时，在寄存器和主存中都只要保存一位符号位。第十五页，共102页。Unsignedaddercodemoduleadder(a,b,cin,cout,sum);parameterbit_width=8;output[bit_width-1:0]sum;outputcout;input[bit_width-1:0]a,b;inputcin;assign{cout,sum}=a+b+cin;//singlesignendmodule第十六页，共102页。Unsignedaddertestbenchcode`timescale1ns/1nsmoduleadder_tb;parameterbit_width=4;wire[bit_width-1:0]sum;wirecout;reg[bit_width-1:0]a,b;regcin;//carryintegeri,k;initialbegink=1<<bit_width;cin=0;for(i=0;i<=k*k;i=i+1)begin#100a=i/k;b=i%k;endendadderm(.a(a),.b(b),.cin(cin),.cout(cout),.sum(sum));endmodule修改描述加法器长度,可以得到不同长度的加法器。第十七页，共102页。简单的二进制减法器的实现设计一个n位的二进制减法器。把中的代码略加修改，即可得到减法器的VerilogHDL代码。其符号如下图所示。代码如下一页。第十八页，共102页。Subtractorcodemodulesubtractor(a,b,cin,cout,sum);parameterbit_width=8;output[bit_width-1:0]sum;outputcout;input[bit_width-1:0]a,b;inputcin;//carryassign{cout,sum}=a-b-cin;//singlesignendmodule第十九页，共102页。Substractortestbenchcode`include”subtractor.v”modulesubtractor_tb;parameterbit_width=4;wire[bit_width-1:0]sum;wirecout;reg[bit_width-1:0]a,b;regcin;//carryintegeri,k;initialbegink=1<<bit_width;cin=0;for(i=0;i<=k*k;i=i+1)begin#100a=i/k;b=i%k;endendsubtractorm(.a(a),.b(b),.cin(cin),.cout(cout),.sum(sum));endmodule第二十页，共102页。定点二进制数的补码加减法器设计把补码加减法运算器作为一个功能部件，取名为add_sub，其符号如下图。Add_Subcontrolsumoverflowabcontroloperation0a+b（x+y）1a+/b+1(x+/y+1)说明：(1)a,b均为补码(2)运算结果sum也是补码(3)Overflow溢出标志第二十一页，共102页。add_subcodemoduleadd_sub(a,b,control,cout,overflow,sum);parameterbit_width=4;output[bit_width-1:0]sum;outputcout,overflow;input[bit_width-1:0]a,b;inputcontrol;//carryregoverflow,cout;reg[bit_width-1:0]sum,b1;always@(aorborcontrol)beginif(control==0){cout,sum}=a+b;else{cout,sum}=a+(~b)+control; if((sum[bit_width-1]^sum[bit_width-2])==1)overflow=1;//bit_width-1 elseoverflow=0;endendmodule

if(control==1)b1=~b;elseb1=b;{cout,sum}=a+b1+control; 第二十二页，共102页。Add_subtestbenchcode`include”add_sub.v”moduleadd_sub_tb;parameterbit_width=4;wire[bit_width-1:0]sum;//singlesignwirecout,overflow;reg[bit_width-1:0]a,b;regcontrol;//carry,control==0integeri,k;initialbegink=1<<bit_width;control=0;for(i=0;i<=k*k;i=i+1)begin#100a=i/k;b=i%k;end//adder#100control=1;for(i=0;i<=k*k;i=i+1)begin#100a=i/k;b=i%k;end//subtractorendadd_subm(.a(a),.b(b),.control(control),.cout(cout),.overflow(overflow),.sum(sum));endmodule第二十三页，共102页。3.2.2先行进位加法器设计略第二十四页，共102页。3.3乘法算法及VerilogHDL实现3.3.1无符号数乘法器设计与十进制乘法计算一样，二进制的乘法可以用加法和移位操作来完成，例如:X=1101

Y=10111101(13)101011(11)101101

——位积

1101

——位积

0000

——位积

1101

——位积

10001111(143)10第二十五页，共102页。可以用全加器阵列来实现上述加法，也可以用循环迭代的方法实现。第二十六页，共102页。3带符号数乘法器设计一、原码的乘法器设计十进制乘法规则：积符号：同号相乘为正，异号相乘为负。数值＝|被乘数|*|乘数|原码乘法规则：积符号：同号相乘为正，异号相乘为负。数值＝|被乘数|*|乘数|由此看出，重点在正数的乘法运算。第二十七页，共102页。假设乘数[X]原=Xf.X1X2X3···Xn

被乘数[Y]原=Yf.Y1Y2Y3···Yn

其中Xf，Yf为符号位。则[X*Y]原=[Y]原*[X]原

=(Xf⊕Yf).(Y1Y2Y3···Yn)*(X1X2X3···Xn)第二十八页，共102页。先来看手工乘法的计算过程。

1101

——位积

1101

——位积

0000

——位积

1101

——位积

10001111第二十九页，共102页。存在的问题：①在运算器中是很难实现多个数据同时相加的，通常只能完成对两数的求和运算。②在手工计算时，各加数逐位左移，最终相加位数为相乘二数位数之和，而在计算机中，加法器的位数一般与寄存器位数相同。③如何判断乘数中的某位为1或0？第三十页，共102页。解决①：每求得一个相加数(位积)，就同时完成与上一次部分积相加的操作。解决②：使用两个寄存器，使每次相加得到的部分积右移一位后再与求得的相加数(位积)相加。解决③：在计算机内用乘数寄存器中每一位直接决定相加数是被乘数还是零很不方便，若用该寄存器的最低一位来执行这种判别就简便多了。第三十一页，共102页。设乘数[X]原=Xf.X1X2X3···Xn

被乘数[Y]原=Yf.Y1Y2Y3···Yn则原码乘法的规则为积的符号位=(Xf⊕

Yf)

积的绝对值=|Y|*|X|1X2X3···Xn)=|Y|*(X1*2-1+X2*2-2+X3*2-3+···+Xn*2-n)=|Y|*2-1(X1+2-1(X2+2-1(X3+···+2-1(Xn+0)···)))第三十二页，共102页。则递推公式为：

P0=0P1=2-1(P0+|Y|*Xn)P2=2-1(P1+|Y|*Xn-1)···Pn=2-1(Pn-1+|Y|*X1)=|Y|*|X|乘法规则可表示为：

[Y]原*[X]原=(Yf⊕Xf).Pn其中Pi称为部分积(i=0,1,2,3,···,n)第三十三页，共102页。例，求[Y*X]原。解：[X]原=1.1011，[Y]原

部分积(寄存器)乘数(寄存器)P0

1011+|Y|

P1→

1101P2→

1110第三十四页，共102页。

P3→

1111P4→

1111所以[Y]原*[X]原=(0⊕1).10001111

[Y*X]原原码一位乘法的流程图如下。第三十五页，共102页。原码一位乘法运算的流程图Cn=1？

开始A←0,Cd←nB←Y,C←XＡ←(Ａ)+(Ｂ)(Ａ)、(C)右移一位Cd←(Cd)-1(Cd)=0？Ａ0←Ｂ0⊕C0结束NNYY第三十六页，共102页。用VerilogHDL设计正数的定点小数乘法器算法描述(1)设一个存放部分积的中间变量pp=0，乘数为x，被乘数为y；(2)设一个循环变量i=1；(3)求部分积：

pp←pp+y*xi，

pp右移一位，

i←i+1；(4)如果i<n转(3)；(5)p←pp，算法结束。第三十七页，共102页。设计一个字长8位、最高(符号位)为0的、二进制定点小数的乘法器。其外观图如下。multiplieryxclkstartresetdonep第三十八页，共102页。说明输入端口乘数x(7…0)，6x5x4x3x2x1x0；被乘数y(7…0)，6y5y4y3y2y1y0；异步清零信号reset，当reset=‘0’时，乘法器立即进入初始状态；时钟信号clock，乘法器在时钟信号的驱动下逐步完成乘法运算；启动信号start，乘法器接到该信号后开始工作。第三十九页，共102页。输出端口乘积p(14…0)，p=0.p13p12p11p10p9p8p7p6p5p4p3p2p1p0；乘法完成信号done，当done=‘1’时，输出端口p的数值才是正确的数。根据算法，可以画出该乘法的状态迁移图，如下图所示。第四十页，共102页。该乘法器的VerilogHDL代码如下。第四十一页，共102页。Multipliercodemodulemult(clk,reset,start,x,y,p,done);parameterbit_width=4;inputclk,reset,start;input[bit_width-1:0]x,y;outputdone;output[bit_width*2-1:0]p;reg[bit_width-1:0]ry,temp;reg[bit_width*2-1:0]pp,p;regdone;integerstate;always@(negedgeresetorposedgeclk)begin if(reset==0)beginstate=0;done=0;ry=0;pp=0;end else第四十二页，共102页。 case(state) 0:begin done=0;temp=0<<bit_width;pp={temp,x};ry=y;// if(start==1)state=1; end bit_width:begin if(pp[0]==1)temp=pp[bit_width*2-1:bit_width]+ry; elsetemp=pp[bit_width*2-1:bit_width]; pp={temp,pp[bit_width-1:1]}; p=pp;done=1;state=0; end default: begin if(pp[0]==1) temp=pp[bit_width*2-1:bit_width]+ry; elsetemp=pp[bit_width*2-1:bit_width]; pp={temp,pp[bit_width-1:1]};state=state+1; end endcaseendendmodule第四十三页，共102页。Multipliertestbenchcode`timescale1ns/1nsmodulemult_tb;parameterbit_width=4;wire[bit_width*2-1:0]p;wiredone;reg[bit_width-1:0]a,b;regclk,start,reset;integeri,k;initialbegink=1<<bit_width;clk=0;start=0;reset=1;#100reset=0;#100reset=1;start=1;a=6;b=7;endalways#100clk=~clk;multm(.clk(clk),.reset(reset),.start(start),.x(a),.y(b),.p(p),.done(done));endmodule第四十四页，共102页。3.4.2补码的乘法运算①若计算机中的数是用补码表示的，可以把补码转换成原码，相乘后再把原码转换为补码。缺点：码制变换比较麻烦，造价高，而且影响速度。②直接用补码数据运算而得到乘积。第四十五页，共102页。二、补码一位乘法—校正法补码一位乘法(校正法)是指将[Y]补与[X]补按类似于原码运算规则运算，所得结果再根据情况加以校正而得到[Y*X]补。1、乘数为正数(1)当被乘数为正(Y>=0)时，

[Y]补=[Y]原=Y，[X]补=[X]原=X，所以乘法过程与原码乘法相同，且符号位可以参加运算。第四十六页，共102页。(2)当被乘数为负(Y<0)时，采用模4补码(为什么？)，根据补码定义

[Y]补=22+Y=2n+2+Y

(MOD4)由于X>=0，X0=0故[X]补1X2···Xn=X1*2-1+X2*2-2+X3*2-3+···+Xn*2-n[Y]补*[X]补=[Y]补*X=(2n+2+Y)*X=2n+2*X+Y*X第四十七页，共102页。2n+2*X=2n+2*(X1*2-1+X2*2-2+···+Xn*2-n)=(X1*2n-1+X2*2n-2+···+Xn-1*21+Xn)*22=22

(MOD4)所以[Y]补*[X]补=2n+2*X+Y*X=22+Y*X=[Y*X]补当[Y]补为任意符号数，X>=0时：

[Y*X]补=[Y]补*[X]补=[Y]补*X整数第四十八页，共102页。2、乘数X为负数因X<0，则[X]补1X2···Xn(MOD2)由补码定义，X=[X]补-21X2···Xn-1故[Y·X]补1X2···Xn-1)]补

1X2···Xn)]补-[Y]补

=[Y]补1X2···Xn)-[Y]补综合上述

[Y·X]补=[Y]补1X2···Xn-[Y]补·X0第四十九页，共102页。递推公式：

[P0]补=0[P1]补=2-1([P0]补+[Y]补*Xn)[P2]补=2-1([P1]补+[Y]补*Xn-1)…[Pn]补=2-1([Pn-1]补+[Y]补*X1)[Pn+1]补=[Pn]补-[Y]补*X0第五十页，共102页。补码一位乘法规则：当乘数为正时，与原码乘法类似，只是相加时用两位符号位，右移时按补码规则进行。当乘数为负时，与乘数为正时一样进行计算，最后再进行校正，加上被乘数[-Y]补。第五十一页，共102页。例，求[Y*X]补。解：[Y]补，[X]补[-Y]补所以[Y*X]补第五十二页，共102页。

部分积乘数[P0]补

0101

+[Y]补

[P1]补→1010[P2]补→0101

+[Y]补

[P3]补→0010[P4]补→0001+[-Y]补

0001第五十三页，共102页。三、补码比较乘—BOOTH乘法校正法对乘数为正或为负，其运算规则不统一，控制起来复杂。比较乘法(BOOTH乘法)由补码校正法导出。设被乘数[Y]补=Y0.Y1Y2Y3···Yn

乘数[X]补=X0.X1X2X3···Xn其中X0，Y0为符号位。第五十四页，共102页。

乘积[C]补=[Y*X]补

=[Y]补1X2···Xn)-X0*[Y]补

=[Y]补·(X1*2-1+X2*2-2···+Xn*2-n-X0)=[Y]补·((X1-X0)+(X2-X1)*2-1+(X3-X2)*2-2···+(Xn-Xn-1)*2-(n-1)-Xn*2-n)=[Y]补·((X1-X0)+(X2-X1)*2-1+(X3-X2)*2-2···+(Xn-Xn-1)*2-(n-1)+(Xn+1-Xn)*2-n)

(Xn+1=0)第五十五页，共102页。递推公式：

[P0]补=0，Xn+1=0[P1]补=2-1([P0]补+[Y]补×(Xn+1-Xn))[P2]补=2-1([P1]补+[Y]补×(Xn-Xn-1))…[Pn]补=2-1([Pn-1]补+[Y]补×(X2-X1))[Pn+1]补=[Pn]补+[Y]补×(X1-X0)第五十六页，共102页。BOOTH乘法规则：(1)Xn+1=0(2)当n≠0，判别Xn，Xn+1

n=n-1，转(2)。(3)当n=0，判断XnXn+1，其运算规则同上，只是不移位。XnXn+1新部分积00或11上次部分积加上0，然后右移一位01上次部分积加上[Y]补，然后右移一位10上次部分积加上[-Y]补，然后右移一位第五十七页，共102页。例，，用布斯乘法计算Y*X。解：[Y]补，[X]补

[-Y]补部分积乘数

[P0]补

+[-Y]补

00.1101[P1]补→00.0110110101+[Y]补

11.0011第五十八页，共102页。

[P2]补→11.1100111010+[-Y]补

00.1101[P3]补→00.0100111101+[Y]补

11.0011[P4]补→11.1011111110+[-Y]补

[P５]补

所以[Y*X]补第五十九页，共102页。例Y=-1，X=-1，用布斯乘法计算X*Y解：[Y]补，[X]补[-Y]补

部分积乘数

[P0]补

[P1]补→00.00001000[P2]补→00.00000100[P3]补→00.00000010+[-Y]补

因符号位相异，所以Y*X溢出。第六十页，共102页。图补码一位BOOTH乘法原理框图补码BOOTH乘法的逻辑结构如下图。第六十一页，共102页。BOOTH乘法的流程图如下。pp[1..0]?开始Pp[2n+1:0]←0,i←0,ry[n+1:1],X,temp[n:0]temp=pp[2n+1:n+1]pp←{temp[n+1],temp,pp[n:1]}i←i+1i<n?结束Y00OR11N01启动乘法器，i←1，

ry←y，

ryn+1=ryn，

pp[n:1]=X，pp[0]=0temp=pp[2n+1:n+1]+ry10temp=pp[2n+1:n+1]+ry+1Booth乘法算法流程图p←{temp[n:1],pp[n:2]}第六十二页，共102页。设计实例设计一个二进制定点小数的补码乘法器，其外观图如下。二进制定点小数的补码乘法器的代码如下。complementmultiplieryxclkstartresetdonepoverflow第六十三页，共102页。Complementmultipliercodemodulec_mult( clk,reset,start,x,y,p,done,overflow);parameterbit_width=4;inputclk,reset,start;input[bit_width-1:0]x,y;//x--???y--???outputdone,overflow;output[(bit_width-1)*2:0]p;reg[bit_width:0]ry,temp;reg[bit_width*2+1:0]pp;reg[(bit_width-1)*2:0]p;regdone,overflow;integerstate;always@(negedgeresetorposedgeclk)begin if(reset==0)beginstate=0;done=0;overflow=0;ry=0;pp=0;end elsecase(state) 0:begin done=0;temp=0;pp={temp,x,1'b0};ry={y[bit_width-1],y}; if(start==1)state=1; end第六十四页，共102页。

bit_width:begin case(pp[1:0]) 2'b01:temp=pp[bit_width*2+1:bit_width+1]+ry; 2'b10:temp=pp[bit_width*2+1:bit_width+1]+~ry+1; 2'b00,2'b11:temp=pp[bit_width*2+1:bit_width+1]; endcase p={temp[bit_width-1:0],pp[bit_width:2]}; done=1;overflow=temp[bit_width]^temp[bit_width-1];state=0; end default: begin case(pp[1:0]) 2'b01:temp=pp[bit_width*2+1:bit_width+1]+ry; 2'b10:temp=pp[bit_width*2+1:bit_width+1]+~ry+1; 2'b00,2'b11:temp=pp[bit_width*2+1:bit_width+1]; endcase pp={temp[bit_width],temp,pp[bit_width:1]};//highbitnotmove state=state+1; end endcaseendendmodule第六十五页，共102页。Complementmultipliertestbenchcode`timescale1ns/1nsmodulec_mult_tb;parameterbit_width=4;wire[(bit_width-1)*2:0]p;wiredone,overflow;reg[bit_width-1:0]a,b;regclk,start,reset;integeri,k;initialbegink=1<<bit_width;clk=0;start=0;reset=1;a=1;b=1;#100reset=0;#100reset=1;start=1;endalways#100clk=~clk;always@(posedgedone)begina=a+1;if(a==0)b=b+1;end

c_multm(.clk(clk),.reset(reset),.start(start),.x(a),.y(b),.p(p),.done(done),.overflow(overflow));endmodule第六十六页，共102页。四、阵列乘法器设计—P74设有2个补码表示的8位带符号数A8和B8，试计算Z16=A8*B8。已知[X]补=X0.X1X2···Xn，根据补码性质(3)知：X=[X]补-2X0=X0.X1X2···Xn-2X01X2···Xn-X0若变成正整数，可得：A8=a7a6a5a4a3a2a1a0=-a7*27+a6a5a4a3a2a1a0

=-a7*27+A7B8=b7b6b5b4b3b2b1b0=-b7*27+b6b5b4b3b2b1b0=-b7*27+B7第六十七页，共102页。Z16=A8*B8=(-a7*27+A7)*(-b7*27+B7)=a7*b7*214+(-a7*B7)*27+(-b7*A7)*27+A7*B7其中a7*b7和A7*B7与无符号数乘法相同，其他2项为负。如下图所示。第六十八页，共102页。1514131211109876543210a7b0a6b0a5b0a4b0a3b0a2b0a1b0a0b0a7b1a6b1a5b1a4b1a3b1a2b1a1b1a0b1a7b2a6b2a5b2a4b2a3b2a2b2a1b2a0b2a7b3a6b3a5b3a4b3a3b3a2b3a1b3a0b3a7b4a6b4a5b4a4b4a3b4a2b4a1b4a0b4a7b5a6b5a5b5a4b5a3b5a2b5a1b5a0b5a7b6a6b6a5b6a4b6a3b6a2b6a1b6a0b60a7b7a6b7a5b7a4b7a3b7a2b7a1b7a0b7z15z14z13z12z11z10z9z8z7z6z5z4z3z2z1z0(-a7)*B7*27(-a7)*(-b7)*214A7*(-b7)*27第六十九页，共102页。写成二进制位的形式：a7*B7=00a7b6a7b5a7b4a7b3a7b2a7b1a7b0b7*A7=00b7a6b7a5b7a4b7a3b7a2b7a1b7a0已经知道-X=/X+1。对这2项同时取反再加1后得到：15141312111098700a7b6a7b5a7b4a7b3a7b2a7b1a7b000b7a6b7a5b7a4b7a3b7a2b7a1b7a0000000001000000001第七十页，共102页。化简并1放到适当位置后，得到：15141312111098700a7b6a7b5a7b4a7b3a7b2a7b1a7b000b7a6b7a5b7a4b7a3b7a2b7a1b7a0100000010第七十一页，共102页。把所有乘积项相加后，得到：1514131211109876543210

1a7b0a6b0a5b0a4b0a3b0a2b0a1b0a0b0a7b1a6b1a5b1a4b1a3b1a2b1a1b1a0b1a7b2a6b2a5b2a4b2a3b2a2b2a1b2a0b2a7b3a6b3a5b3a4b3a3b3a2b3a1b3a0b3a7b4a6b4a5b4a4b4a3b4a2b4a1b4a0b4a7b5a6b5a5b5a4b5a3b5a2b5a1b5a0b5a7b6a6b6a5b6a4b6a3b6a2b6a1b6a0b6

1a7b7a6b7a5b7a4b7a3b7a2b7a1b7a0b7z15z14z13z12z11z10z9z8z7z6z5z4z3z2z1z0(-a7)*B7*27(-a7)*(-b7)*214A7*(-b7)*27第七十二页，共102页。阵列乘法的VerilogHDL代码V1modulemul_signed(a,b,z); input[7:0]a,b; output[15:0]z; wire[7:0]ab0=b[0]?a:8’b0; wire[7:0]ab1=b[1]?a:8’b0; wire[7:0]ab2=b[2]?a:8’b0; wire[7:0]ab3=b[3]?a:8’b0; wire[7:0]ab4=b[4]?a:8’b0; wire[7:0]ab5=b[5]?a:8’b0; wire[7:0]ab6=b[6]?a:8’b0; wire[7:0]ab7=b[7]?a:8’b0; assignz=((8’b1,~ab0[7],ab0[6:0])+{7’b0,~ab1[7],ab1[6:0],1’b0})+({6’b0,~ab2[7],ab2[6:0],2’b0}+{5’b0,~ab3[7],ab3[6:0],3’b0})+({4’b0,~ab4[7],ab4[6:0],4’b0}+{3’b0,~ab5[7],ab5[6:0],5’b0})+({2’b0,~ab6[7],ab6[6:0],6’b0}+{1’b1,ab7[7],~ab7[6:0],7’b0}));endmodule第七十三页，共102页。阵列乘法的VerilogHDL代码V2modulemul_signed_v2(a,b,z); input[7:0]a,b; output[15:0]z; reg[7:0]a_bi[7:0];//二维数组

always@*begin integeri,j; for(i=0;i<7;i=i+1) for(j=0;j<7;j=j+1)a_bi[i][j]=a[i]&b[j]; for(i=0;i<7;i=i+1)a_bi[i][7]=~(a[i]&b[7]); for(j=0;j<7;j=j+1)a_bi[7][j]=~(a[7]&b[j]); a_bi[7][7]=a[7]*b[7]; end assignz=((8’b1,a_bi[0][7],a_bi[6:0])+{7’b0,a_bi[1][7],a_bi[1][6:0],1’b0})+({6’b0,a_bi[2][7],a_bi[2][6:0],2’b0}+ {5’b0,a_bi[3][7],a_bi[3][6:0],3’b0})+ ({4’b0,a_bi[4][7],a_bi[4][6:0],4’b0}+ {3’b0,a_bi[5][7],a_bi[5][6:0],5’b0})+ ({2’b0,a_bi[6][7],a_bi[6][6:0],6’b0})+ {1’b0,a_bi[7][7],a_bi[7][6:0],7’b0}));endmodule第七十四页，共102页。3.6逻辑运算定点运算器还用于实现二进制位串的逻辑运算。一、逻辑与运算A、B两个寄存器存放的内容对应位进行逻辑与运算。主要用于数据处理中的“屏蔽”(删去)、“选位置0”操作。例如若将A寄存器的高4位置为全0：

A

00110111BAND0000111100000111第七十五页，共102页。二、逻辑或运算A、B寄存器存放的内容对应位进行逻辑或运算。主要用于数据处理中“选位置1”、插入和拼组等操作。选位置1是指寄存器中某些位要求置1的操作。如要求A寄存器A5、A3、A0被置1，则使B寄存器中与之对应的那些位为1，其余位为0：

A

00110111

B

OR0010100100111111第七十六页，共102页。插入操作是指寄存器中某些位的内容，用新的数值取代。如要求在A寄存器高4位插入新的数值，首先应将A寄存器的高4位清0，然后再将A寄存器的高4位与要求插入的数值作逻辑或运算：与运算

A

01010111B

AND00001111A

00000111第七十七页，共102页。

然后在A寄存器的前4位插入新值0011：或运算

A

00000111B

OR00110000A

00110111第七十八页，共102页。拼组操作是指将两个或多个二进制编码信息进行组合的操作。如将十进制数串89表示成BCD码(8421码)存放在一个字节中。

001110008AND

00001111A

00001000001110019AND00001111B

00001001第七十九页，共102页。将A寄存器中的值逻辑左移四位得10000000与B寄存器进行或运算：

10000000OR

0000100110001001——89第八十页，共102页。三、异或操作异或操作是指对应位实现异或操作。主要用于数据处理中“比较”及选位置反。选位置反是指寄存器中某些位要求置反的操作。如要求A寄存器的A5

、A1，A0内容置反，则在B寄存器与之对应的位置放1，其余位放0，通过异或操作即可：

A

10100110

BXOR00100011

10000101第八十一页，共102页。比较操作是指两个寄存器内容逐位加以比较，如两个寄存器内容相同，则结果为0，否则结果为0。四、同或操作同或操作与异或操作类似。第八十二页，共102页。modulemul_signed_v2(a,b,z);00b7a6b7a5b7a4b7a3b7a2b7a1b7a02'b00,2'b11:temp=pp[bit_width*2+1:bit_width+1];若结果溢出，overflow←‘1’，否则overflow←‘0’。reg[bit_width:0]temp;`timescale1ns/1nsadd_subcodeif(start==1)state=1;000000001moduleadd_sub_tb;A10100110然后在A寄存器的前4位插入新值0011：done=0;temp=0<<bit_width;pp={temp,x};ry=y;//2'b00,2'b11:temp=pp[bit_width*2+1:bit_width+1];[-Y]补regdone,overflow;逻辑运算是在二进制位串对应位之间进行的，与相邻的高位和低位的值均无关。用于完成算术和逻辑运算的部件被称为算术与逻辑运算部件ALU(多功能函数发生器,如74LS181)。第八十三页，共102页。3.7算术逻辑运算单元(ALU)举例ALU是一个组合逻辑电路，其输出仅取决于当前的输入。外观符号和功能列表如下。注意该部件在某一特定时间段只能执行一种运算。处理器执行某种运算时，需要向其提供数据和命令，然后从其输出端取走运算结果。第八十四页，共102页。输入输出定义X(7…0)、y(7…0)和result(7…0)是字长8位的、补码形式的二进制数，其最高位为符号位。为了判断溢出，采用双符号位。若结果溢出，overflow←‘1’，否则overflow←‘0’。执行逻辑运算时，X(7…0)和y(7…0)是按位操作。逻辑右移时最高位补‘0’，逻辑左移时低位补‘0’。逻辑运算时overflow保持不变。输入信号F(2…0)是功能选择命令，决定ALU执行哪种操作。简化ALU的VerilogHDL代码如下。第八十五页，共102页。Alucodemodulealu(x,y,instruction,overflow,result); parameterbit_width=4; input[bit_width-1:0]x,y; input[2:0]instruction; outputoverflow; output[bit_width-1:0]result; reg[bit_width:0]temp; reg[bit_width:0]result; regoverflow; initial overflow=0; 第八十六页，共102页。always@(xoryorinstruction) begincase(instruction) 3'b001:begintemp={x[bit_width-1],x}+{y[bit_width-1],y}; result<=temp[bit_width-1:0]; overflow<=temp[bit_width]^temp[bit_width-1]; end 3'b010:begintemp={x[bit_width-1],x}+~{y[bit_width-1],y}+1; result<=temp[bit_width-1:0]; overflow<=temp[bit_width]^temp[bit_width-1]; end 3'b011:beginresult<=x&y;end 3'b100:beginresult<=x|y;end 3'b101:beginresult<=x^y;end 3'b110:beginresult<={1'b0,x[bit_width-1:1]};end 3'b111:beginresult<={x[bit_width-2:0],1'b0};end default:beginresult<=0;overflow<=0;end endcaseendendmodule第八十七页，共102页。Alutestbenchcode`timescale1ns/1nsmodulealu_tb;parameterbit_width=4;wire[bit_width-1:0]p;wireover;reg[bit_width-1:0]a,b;reg[2:0]instruct;regclk;initialbegina=1;b=1;instruct=3'b111;clk=0;endalways#100clk=~clk;always@(