第3章 计算机算法及其Verilog HDL实现

1、逻辑运算逻辑运算(增加增加)算术逻辑运算单元算术逻辑运算单元(ALU)举例举例(增加增加)Steps of Software Developmentswap(int v, int k)int temp;temp = vk;vk = vk+1;vk+1 = temp;swap:000000001010000100000000000110000000000010001110000110000010000110001100011000100000000000000000100011001111001000000000000001001010110011110010000000000000000010

2、10110001100010000000000000010000000011111000000000000000001000muliaddlwlwswswjr$5, 4$4, $20($2)4($2)0($2)4($2)$2,$2,$15,$16,$16,$15,$31高级语言程序汇编语言程序汇编器机器码程序链接可执行的机器码程序机器码程序库编译器Program CPU Can Execute机器码程序机器码程序Instruction and Data机器码程序的内容机器码程序的内容指令和数据指令和数据在计算机内部，指令和数据均用在计算机内部，指令和数据均用 表示表示指令和数据的表示方法指令和

3、数据的表示方法二进制数二进制数数制转换数制转换. . . . . . . . . . . . . . . . (10012 = 910). . . . . . . . . . . . . . . (10012 = 110). . . . . . . . . . . . . . (10012 = 710)10012an1an2.a1a0 = an1 2n1 + an2 2n2 + . + a1 21 + a0 20= 010= 110= 210= 4,294,967,29310= 4,294,967,29410= 4,294,967,29510N位无符号数的最小值是0，最大值是2n 1c32位无

4、符号数：0000 0000 0000 0000 0000 0000 0000 00000000 0000 0000 0000 0000 0000 0000 00010000 0000 0000 0000 0000 0000 0000 00101111 1111 1111 1111 1111 1111 1111 11011111 1111 1111 1111 1111 1111 1111 11101111 1111 1111 1111 1111 1111 1111 11113.1.1 无符号二进制整数无符号二进制整数无符号数无符号数（ Unsigned ）：所有的二进制数据位）：所有的二进制数据

5、位数均用来表示数值本身，没有正负之分。数均用来表示数值本身，没有正负之分。符号数值部分 0.00优点：优点：比较大小移码非常方便。比较大小移码非常方便。性质：性质：l 1 1、移码符号与原码、补码符号相反、移码符号与原码、补码符号相反l 2 2、一个数的移码等于该数补码反符号。、一个数的移码等于该数补码反符号。0 2n 2n+1-1x移码移码-2n 0 2n-1真值真值 1.00真值原码补码移码+1111111011111110111111111111111+1111110011111100111111011111110 +0000000000000000000000010000000-000

6、0000100000000000000010000000-0000001100000011111111101111111 -1111111111111111000000100000001-10000000不能表示1000000000000000补码表示0123456789ABCDEF0000+100010010001101000101011001111100010011010101111001101111111100+1+2+3+4+5+6+7876543210000+100010010001101000101011001111100010011010101111001101111111100

7、 (4位无符号数位无符号数 ) 158 (4位补码表示的带符号二进制整数位补码表示的带符号二进制整数) +7补码表示的补码表示的带符号数带符号数c无符号数无符号数补码表示0123456789ABCDEF0000+100010010001101000101011001111100010011010101111001101111111100+1+2+3+4+5+6+7876543210000+10001001000110100010101100111110001001101010111100110111111110由图看出，无符号数的加减和带符号数的加减相同，最高位为1时，两种表示方法有不同的意义

8、。c无符号数无符号数补码表示的补码表示的带符号数带符号数例1X=0.1011，Y=-0.1110，求X+Y补.解 X补=0.1011，Y补=1.0010 X补00.1011+Y补11.0010 X补+Y补11.1101所以X+Y补=1.1101注：这里的小数点可以理解为符号与数值的分隔符 注：这里的逗号可以理解为符号与数值的分隔符注：这里的小数点可以理解为符号与数值的分隔符开始开始被加（减）数，补码被加（减）数，补码X X加加( (减减) )数，补码数，补码Y Y加法吗？加法吗？（X X）+ +（Y Y） X X（mod 2mod 2或或mod 2mod 2n+1n+1) )溢出吗？溢出吗？结

9、束结束置溢出标志置溢出标志T TF F减数求补减数求补T TF F准备准备相加相加判溢出判溢出补码加减运算控制流程补码加减运算控制流程执行减法执行减法执行执行加法加法X+Y补补X补补 Y补补： XF, YF, FXX-Y补补X补补 -Y补补： XF, YF, 1 F , FX补充1nnCCOVR结果符号位溢出情况00无溢出01正溢出10负溢出11无溢出所谓正溢出，即超出机器所能表示的最大正数。 所谓负溢出，即超出机器所能表示的最小负数。Sf1 Sf2=01，正溢出正溢出Sf1 Sf2=11，无溢出无溢出Sf1 Sf2=00，无溢出无溢出Sf1 Sf2=10，负，负溢出溢出+CiSiAiBiCi

10、-1ABCiSCO0000001010100101100100110011011010111111S = A + B + CiCo = ACi+BCi+AB = (A + B)Ci+ABFA全加器符号：全加器符号：Sum延迟为延迟为6；进位；进位Carryout延迟延迟为为2(假定一个与门假定一个与门/或门延迟为或门延迟为1，异异或门的延迟则为或门的延迟则为3)FAFAFAn位串行位串行(行波行波)加法器：加法器：串行加法器的缺点：串行加法器的缺点：进位按串行方式传递，速度慢！进位按串行方式传递，速度慢！问题：问题：n位串行加法器从位串行加法器从C0到到Cn的延迟时间为多少？的延迟时间为多少？

11、最后一位和数的延迟时间为最后一位和数的延迟时间为多少？多少？ 2n+1级门延迟！级门延迟！2n级门延迟！级门延迟！)()()()(333334222223111112000001BACBACBACBACBACBACBACBAC下面给出8位加法器的Verilog HDL描述。补充 修改描述加法器长度,可以仿真不同长度的加法器。补充下面给出8位减法器的Verilog HDL描述。 修改描述减法器长度,可以仿真不同长度的减法器。Add_Subcontrol sumoverflow a bcontroloperation0a+b（x+y）1a+/b+1(x+/y+1)说明：(1)a,b均为补码(2)运

12、算结果sum也是补码(3)Overflow溢出标志timescale 1ns/1ns include add_sub.vmodule add_sub_tb; parameter bit_width=4; wire bit_width-1:0 sum; wire cout,overflow; reg bit_width-1:0 a,b; reg control;/carry,control=0 integer i,k; initial begin #0 $display(timetatbtcontroltcouttoverflowtsum); #0 k=bit_width*2;control=0

13、; for(i=0;i=k*k;i=i+1) begin #i a=i;b=i*k; end /adder for(i=0;i=k*k;i=i+1) begin #i a=i*k;b=i; control=1; end /subtractor endadd_sub m(.a(a),.b(b),.control(control),.cout(cout),.overflow(overflow),.sum(sum); initial begin $dumpfile(test.vcd); $dumpvars; /这两行主要是给gtkwave这个工具使用的. $monitor(%1dt%bt%bt%bt

14、%bt%bt%b,$time,a,b,control,cout,overflow,sum);/屏幕显示 #2500 $finish; end endmoduleX=1101Y=1011 1101 (13)10 1011 (11)10 1101位积M1 1101 位积M2 0000位积M3 1101 位积M4 10001111 (143)10n 相邻位积相邻位积 做加法做加法观察：将观察：将M1右移一右移一位对齐位对齐M2再加，再加，l用用n+1位加法器位加法器l需要右移运算需要右移运算Iterative Version in Cmain()int x,y;fprintf(stderr,inpu

15、t 1st 16-bit unsigned integer in hex format: );fscanf(stdin,%x,&x);fprintf(stderr,input 2nd 16-bit unsigned integer in hex format: );fscanf(stdin,%x,&y);x &= 0 xffff;y &= 0 xffff;fprintf(stderr,%04x * %04x = %08xn, x, y, mul(x, y);编译并执行：yaminlocalhost verilog$ gcc mul.c -o mulyaminlo

16、calhost verilog$ ./mulinput 1st 16-bit unsigned integer in hex format: c9aeinput 2nd 16-bit unsigned integer in hex format: f6e5c9ae * f6e5 = c2819ca6cA.D.Booth算法，已知算法，已知X补补=x0 x1 xn , Y补补= y0y1 yniniiyy210iniiiyy2)(01niiiiyyXYX012)(*补补 =(y1-y0)X补补+ 2-1( y2-y1) )X补补+ 2-1( y3-y2) )X补补+ +2-1(yn-i+1-yn

17、-i) )X补补+ +2-1(yn-yn-1) )X补补+2-1(yn+1-yn) )X补补 补充 P1补补=2-1(yn+1-yn)*X补补 (i= 0) P2补补=2-1(P1补补+ (yn-yn-1)*X补补 (i= 1) Pn补补=2-1(Pn-1 补补+ (y2-y1)*X补补 (i= n-1) Pn+1补补=Pn 补补+ (y1-y0)*X补补 令令P0补补=0 则则 X*Y补补=Pn+1补补= Pn 补补 + (y1-y0)*X补补 = Pn 补补+ (y1-y0)* X补补 判断位YnYn+1操作说明 0 0 1 1Pi补=1/2Pi-1补上次部分积加上次部分积加0后右移一位后

18、右移一位 0 1Pi补=1/2（Pi-1补+X补）上次部分积加上次部分积加X补补后，右移一位后，右移一位 1 0Pi补=1/2（Pi-1补-X补）上次部分积减上次部分积减X补补后，右移一位后，右移一位已知已知 X补补=0.1101, Y补补= 1.0110，-X补补=1.0011。 求求X*Y补补 P Y yn+1 说明说明 00 0000 1 0110 0 开始，设开始，设y5=0，P0补补=0 y4 y5 =00，P、Y同时右移一位同时右移一位 00 0000 01 011 0 得得P1补补+11 0011 y3 y4 =10，+-X补补 11 0011 P、Y同时右移一位同时右移一位 1

19、1 1001 101 01 1 得得P2补补 y2 y3 =11，P、Y同时右移一位同时右移一位 11 1100 1101 0 1 得得P3补补+00 1101 y1y2 =01，+X补补 00 1001 P、Y同时右移一位同时右移一位 00 0100 11101 0 得得P4补补+11 0011 y0 y1 =10，+-X补补 11 0111 1110 1 最后一次不右移最后一次不右移 X X * * Y Y补补=1.01111110=1.01111110 0 0 . 0 0 0 00. 1 0 1 1 0Y n+1=0 1 1 . 0 0 1 1YnY n+1=10， 加加-X补补+ 1

20、1 . 0 0 1 1 1 1 . 1 0 0 11. 0 1 0 1 1右移一位+ 0 0 . 0 0 0 0YnY n+1=11， 加加0 1 1 . 1 0 0 1 1 1 . 1 1 0 0 1 1 0 1 0 1 右移一位+ 0 0 . 1 1 0 1YnY n+1=01， 加加X补补 0 0 . 1 0 0 1 0 0 . 0 1 0 01 1 1 0 1 0 右移一位+ 1 1 . 0 0 1 1 1 1 . 0 1 1 1YnY n+1=10， 加加-X补补 1 1 . 1 0 1 11 1 1 1 0 1右移一位 0 0 . 1 1 0 1+YnY n+1=01， 加加X补补

21、 0 0 . 1 0 0 01 1 1 1 0 1最后一次不移位X*Y补=0.10001111R0R1 ynyn+1计数器计数器i&TiQSQR+1LDR0LDR1+1+ -R2原原 反反被乘数被乘数x&ynyn+110&ynyn+101f部分积部分积zi多路开关多路开关T1,T2,Cx启动启动乘数乘数y 保存部分积，它也是具有右移功能的移位寄存器，其符号位与加法器符号位始终一致。当计数器时，封锁和控制信号，使最后一步不移位。 被乘数的符号和乘数的符号都参加运算。 乘数寄存器有附加位，其初始状态为“”。当乘数和部分积每次右移时，部分积最低为移至的首位位置，故必须是具有右

22、移功能的寄存器。 被乘数寄存器的每一位用原码或反码经多路开关传送到加法器对应位的一个输入端，而开关的控制信号由的输出译码器产生。当0时，送补；当时，送补，即送的反码且在加法器最末位加上“”。pp1.0?开始pp2n+1:00, i0, ryn+1:1, X, tempn:0temp=pp2n+1:n+1pp tempn+1 ,temp ,ppn:1 i i+1in?结束Y00 OR 11N01启动乘法器， i1 ， ryy ， ryn+1=ryn ， ppn:1=X ，pp0=0temp=pp2n+1:n+1+ry10temp=pp2n+1:n+1+ry+1Booth乘法算法流程图p temp

23、n:1 , ppn:2 二进制定点小数的补码乘法器的代码如下。 complement multiplier y x clk startresetdone poverflow 部分积部分积 乘乘 数数 Bn+1 P0补补 00000 0 1 0 1 0 +-A补补 00011 00011 P1补补 1 00001 1 0 1 0 1 +A补补 11101 11110 P2补补 1 11111 0 1 0 1 0 +-A补补 00011 00010 P3补补 1 00001 0 0 1 0 1 +A补补 11101 11110 P4补补 1 0 0 0 1 0 A B补补=1.110001 部分积

24、部分积 乘乘 数数 Bn+1 P0补补 00000 1 0 0 0 0 P1补补 1 00000 0 1 0 0 0 P2补补 1 00000 0 0 1 0 0 P3补补 1 00000 0 0 0 1 0 P4补补 +-A补补 01000 01000 1 0 0 0 0 1 AB补补=C补补 =01.000000； 此结果为此结果为+1溢出，无意义。溢出，无意义。(-1) (-1)是补码乘法（定点小数）唯一溢出的情况。是补码乘法（定点小数）唯一溢出的情况。where A7 and B7 are two 7-bit unsigned numbersSigned Number Multipli

25、cationBecause (a + b) (x + y) = ax + ay + bx + byZ16 =A8 B8(a7 27 + A7) (b7 27 + B7)=+a7 b7 214(a7 B7) 27(b7 A7) 27A7 B7 Same as unsigned Negative Negative Same as unsignedNote: X = X + 1c其中a7*b7和A7*B7与无符号数乘法相同，其他2项为负。15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 a7b0 a6b0 a5b0 a4b0 a3b0 a2b0 a1b0 a0b0 a7b1

26、 a6b1 a5b1 a4b1 a3b1 a2b1 a1b1 a0b1 a7b2 a6b2 a5b2 a4b2 a3b2 a2b2 a1b2 a0b2 a7b3 a6b3 a5b3 a4b3 a3b3 a2b3 a1b3 a0b3 a7b4 a6b4 a5b4 a4b4 a3b4 a2b4 a1b4 a0b4 a7b5 a6b5 a5b5 a4b5 a3b5 a2b5 a1b5 a0b5 a7b6 a6b6 a5b6 a4b6 a3b6 a2b6 a1b6 a0b6 0 a7b7 a6b7 a5b7 a4b7 a3b7 a2b7 a1b7 a0b7z15 z14 z13 z12 z11 z10

27、 z9 z8 z7 z6 z5 z4 z3 z2 z1 z0(-a7)*B7*27(-a7)*(-b7) *214A7* (- b7)*2715 14 13 12 11 10 9 8 7 1 1 a7b6 a7b5 a7b4 a7b3 a7b2 a7b1 a7b01 1 a6b7 a5b7 a4b7 a3b7 a2b7 a1b7 a0b70 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 1Signed Number Multiplication151101411013a7b6a6b7012a7b5a5b7011a7b4a4b7010a7b3a3b709a7b2a2b708a7b

28、1a1b707a7b0a0b71+000000001化简:1500140013a7b6a6b712a7b5a5b711a7b4a4b710a7b3a3b79a7b2a2b78a7b1a1b77a7b0a0b7+100000010c将1放到适当位置并把所有乘积项相加后即得到乘积。a7b0 a6b0 a5b0 a4b0 a3b0 a2b0 a1b0 a0b0NANDNAND0123456789101112131415z15z14z13z12z11z10z09z08z07z06z05z04z03z02z01z00+ 1 a7b7 a6b7 a5b7 a4b7 a3b7 a2b7 a1b7 a0b71

29、add 1a7b1 a6b1 a5b1 a4b1 a3b1 a2b1 a1b1 a0b1a7b2 a6b2 a5b2 a4b2 a3b2 a2b2 a1b2 a0b2a7b3 a6b3 a5b3 a4b3 a3b3 a2b3 a1b3 a0b3a7b4 a6b4 a5b4 a4b4 a3b4 a2b4 a1b4 a0b4ANDa7b5 a6b5 a5b5 a4b5 a3b5 a2b5 a1b5 a0b5a7b6 a6b6 a5b6 a4b6 a3b6 a2b6 a1b6 a0b6cSigned Number MultiplicationSimulationDrawback of the implementation: Additionstake long timeSolution: Use Wallace-Treectimescale 1ns/1ns/定义时延单位定义时延单位1ns和时延精度为和时延精度为1nsinclude mul_signed.v/被测试模块被测试模块module mul_signed_tb; parameter bit_width=8;