16位布斯算法乘法器和ALU

1、Booth算法16位乘法器西安电子科技大学 大三 集成电路设计与集成系统专业 尹俊镖一 乘法器原理分析 16位有符号乘法器可以分为三个部分：根据输入的被乘数和乘数产生部分积、部分积压缩产生和和进位、将产生的和和进位相加。这三个部分分别对应着编码方式、拓扑结构以及加法器。1 编码方式：本设计采用booth2编码。部分积是负数时S=1，部分积是正数时S=0；当部分积是+0时，E=1，部分积是-0时，E=0，其余情况E=S取反。2 拓扑结构：本设计采用二进制树的拓扑结构。二进制树拓扑结构排列的较为规整，且部分积压缩的速度也非常快。部分积压缩的目的是为了减小进位传播的延时，采用进位保留加法器，根据当前

2、位信息产生下一位的进位，仅仅产生而没有进位行波传播，这样就可以把当前的多位压缩到较少的位数。经过几次压后，把部分积压缩成和以及进位。部分积主要是通过counter和compressor进行压缩，通常使用（3:2）counter和（4:2）compressor。（3:2）counter其实质就是一个全加器，进位输入为ci，进位输出为c；（4:2）compressor可以由两个全加器组成，ci为进位输入，Coin为内部进位，输入到下一位的进位输入Ci，Coex为输出进位。上图为二进制树的拓扑结构图，每4个部分积输入到一个（4:2）compressor中，产生两个输出，则8个部分积使用3次（4:2）

3、compressor就可以得到和和进位。部分积的压缩方式可以见下图。如图中所示，加上最后一个部分积的进位，共有9个部分积，本设计把最后的进位位移到第一个部分积上，使用5个全加器，把进位融合到第一个部分积，这样就转变成8个部分积了，再使用两级二进制树压缩，所以总共使用了三级压缩，最终得到部分积的和和进位。为了免去不必要的硬件开销，对于部分积边上的位采用counter压缩。上文提到的符号位扩展的改进方法，其目的也就是减少硬件开销，所以在不影响性能的情况下，单独出来部分积的边缘位是十分有必要的。3 加法器本设计采用超前进位加法器。为了使得乘法器的延时最小，最后一级的加法器采用传播延时最小的超前进位加

4、法器。超前进位加法器的原理及构成，在此不做详述。二 仿真验证 对于16位乘法器的仿真验证，若采用穷举法，则有232种情况，验证次数太多，所以只能采用随机数的验证方法。产生两个随机数，加入到乘法器的两个输入端，如此循环10000次，若没有错误，则可以认为乘法器功能正确。X，Y是产生的两个随机数，product是两数的乘积，product_check是用于验证结果是否正确。Count用于计数，循环10000次，error记录计算一万次错误的次数，若发生错误，则退出仿真。 三 源程序代码1 Booth2 模块 module mul_16 (x,y,product); /generate partia

5、l product input 15:0 x; input 15:0 y; output 31:0 product; wire 19:0 pp1; /partial product wire 20:0 pp2; wire 20:0 pp3; wire 20:0 pp4; wire 20:0 pp5; wire 20:0 pp6; wire 20:0 pp7; wire 19:0 pp8; reg symb8; /ninth partial product reg 16:0 tpp1; reg 16:0 tpp2; reg 16:0 tpp3; reg 16:0 tpp4; reg 16:0 t

6、pp5; reg 16:0 tpp6; reg 16:0 tpp7; reg 16:0 tpp8; reg symb1; reg symb2; reg symb3; reg symb4; reg symb5; reg symb6; reg symb7; / the first partial product always (y or x) begin symb1=1'b0; case(y1:0) 2'b00: tpp1=17'b0; 2'b01: tpp1=x15,x; 2'b10: begin tpp1=x,1'b0; symb1=1'

7、b1; end 2'b11: begin tpp1=x15,x; symb1=1'b1; end endcase end / the sencod partial product always (y or x) begin symb2=1'b0; case(y3:1) 3'b000: tpp2=17'b0; 3'b001, 3'b010: tpp2=x15,x; 3'b011: tpp2=x,1'b0; 3'b100: begin tpp2=x,1'b0; symb2=1'b1; end 3'

8、;b101, 3'b110: begin tpp2=x15,x; symb2=1'b1; end 3'b111: tpp2=1'b0,16'b0; endcase end / the third partial product always (y or x) begin symb3=1'b0; case(y5:3) 3'b000: tpp3=17'b0; 3'b001, 3'b010: tpp3=x15,x; 3'b011: tpp3=x,1'b0; 3'b100: begin tpp3=x

9、,1'b0; symb3=1'b1; end 3'b101, 3'b110: begin tpp3=x15,x; symb3=1'b1; end 3'b111: tpp3=1'b0,16'b0; endcase end / the fourth partial product always (y or x) begin symb4=1'b0; case(y7:5) 3'b000: tpp4=17'b0; 3'b001, 3'b010: tpp4=x15,x; 3'b011: tpp4

10、=x,1'b0; 3'b100: begin tpp4=x,1'b0; symb4=1'b1; end 3'b101, 3'b110: begin tpp4=x15,x; symb4=1'b1; end 3'b111: tpp4=1'b0,16'b0; endcase end / the fifth partial product always (y or x) begin symb5=1'b0; case(y9:7) 3'b000: tpp5=17'b0; 3'b001, 3

11、9;b010: tpp5=x15,x; 3'b011: tpp5=x,1'b0; 3'b100: begin tpp5=x,1'b0; symb5=1'b1; end 3'b101, 3'b110: begin tpp5=x15,x; symb5=1'b1; end 3'b111: tpp5=1'b0,16'b0; endcase end / the sixth partial product always (y or x) begin symb6=1'b0; case(y11:9) 3'b

12、000: tpp6=17'b0; 3'b001, 3'b010: tpp6=x15,x; 3'b011: tpp6=x,1'b0; 3'b100: begin tpp6=x,1'b0; symb6=1'b1; end 3'b101, 3'b110: begin tpp6=x15,x; symb6=1'b1; end 3'b111: tpp6=1'b0,16'b0; endcase end / the seventh partial product always (y or x) be

13、gin symb7=1'b0; case(y13:11) 3'b000: tpp7=17'b0; 3'b001, 3'b010: tpp7=x15,x; 3'b011: tpp7=x,1'b0; 3'b100: begin tpp7=x,1'b0; symb7=1'b1; end 3'b101, 3'b110: begin tpp7=x15,x; symb7=1'b1; end 3'b111: tpp7=1'b0,16'b0; endcase end / the ei

14、ghth partial product always (y or x) begin symb8=1'b0; case(y15:13) 3'b000: tpp8=17'b0; 3'b001, 3'b010: tpp8=x15,x; 3'b011: tpp8=x,1'b0; 3'b100: begin tpp8=x,1'b0; symb8=1'b1; end 3'b101, 3'b110: begin tpp8=x15,x; symb8=1'b1; end 3'b111: tpp8=1

15、'b0,16'b0; endcase end assign pp119:0=!tpp116,tpp116,tpp116,tpp1; assign pp220:0=1'b1,!tpp216,tpp2,1'b0,symb1; assign pp320:0=1'b1,!tpp316,tpp3,1'b0,symb2; assign pp420:0=1'b1,!tpp416,tpp4,1'b0,symb3; assign pp520:0=1'b1,!tpp516,tpp5,1'b0,symb4; assign pp620:0

16、=1'b1,!tpp616,tpp6,1'b0,symb5; assign pp720:0=1'b1,!tpp716,tpp7,1'b0,symb6; assign pp819:0=!tpp816,tpp8,1'b0,symb7; compressor comprs(.pp1(pp1), .pp2(pp2), .pp3(pp3), .pp4(pp4), .pp5(pp5), .pp6(pp6), .pp7(pp7), .pp8(pp8), .symb8(symb8), .product(product); endmodule 2 加法器module ad

17、der_32(input 31:0 add_in1,add_in2, / input c0, output 31:0 add_out); wire 31:0 p,g,psum; /form the psum?propagate and generate signals from the input xor(psum0,add_in10,add_in20); xor(psum1,add_in11,add_in21); xor(psum2,add_in12,add_in22); xor(psum3,add_in13,add_in23); xor(psum4,add_in14,add_in24);

18、xor(psum5,add_in15,add_in25); xor(psum6,add_in16,add_in26); xor(psum7,add_in17,add_in27); xor(psum8,add_in18,add_in28); xor(psum9,add_in19,add_in29); xor(psum10,add_in110,add_in210); xor(psum11,add_in111,add_in211); xor(psum12,add_in112,add_in212); xor(psum13,add_in113,add_in213); xor(psum14,add_in1

19、14,add_in214); xor(psum15,add_in115,add_in215); xor(psum16,add_in116,add_in216); xor(psum17,add_in117,add_in217); xor(psum18,add_in118,add_in218); xor(psum19,add_in119,add_in219); xor(psum20,add_in120,add_in220); xor(psum21,add_in121,add_in221); xor(psum22,add_in122,add_in222); xor(psum23,add_in123,

20、add_in223); xor(psum24,add_in124,add_in224); xor(psum25,add_in125,add_in225); xor(psum26,add_in126,add_in226); xor(psum27,add_in127,add_in227); xor(psum28,add_in128,add_in228); xor(psum29,add_in129,add_in229); xor(psum30,add_in130,add_in230); xor(psum31,add_in131,add_in231); or(p0,add_in10,add_in20)

21、; or(p1,add_in11,add_in21); or(p2,add_in12,add_in22); or(p3,add_in13,add_in23); or(p4,add_in14,add_in24); or(p5,add_in15,add_in25); or(p6,add_in16,add_in26); or(p7,add_in17,add_in27); or(p8,add_in18,add_in28); or(p9,add_in19,add_in29); or(p10,add_in110,add_in210); or(p11,add_in111,add_in211); or(p12

22、,add_in112,add_in212); or(p13,add_in113,add_in213); or(p14,add_in114,add_in214); or(p15,add_in115,add_in215); or(p16,add_in116,add_in216); or(p17,add_in117,add_in217); or(p18,add_in118,add_in218); or(p19,add_in119,add_in219); or(p20,add_in120,add_in220); or(p21,add_in121,add_in221); or(p22,add_in122

23、,add_in222); or(p23,add_in123,add_in223); or(p24,add_in124,add_in224); or(p25,add_in125,add_in225); or(p26,add_in126,add_in226); or(p27,add_in127,add_in227); or(p28,add_in128,add_in228); or(p29,add_in129,add_in229); or(p30,add_in130,add_in230); or(p31,add_in131,add_in231); and(g0,add_in10,add_in20);

24、 and(g1,add_in11,add_in21); and(g2,add_in12,add_in22); and(g3,add_in13,add_in23); and(g4,add_in14,add_in24); and(g5,add_in15,add_in25); and(g6,add_in16,add_in26); and(g7,add_in17,add_in27); and(g8,add_in18,add_in28); and(g9,add_in19,add_in29); and(g10,add_in110,add_in210); and(g11,add_in111,add_in21

25、1); and(g12,add_in112,add_in212); and(g13,add_in113,add_in213); and(g14,add_in114,add_in214); and(g15,add_in115,add_in215); and(g16,add_in116,add_in216); and(g17,add_in117,add_in217); and(g18,add_in118,add_in218); and(g19,add_in119,add_in219); and(g20,add_in120,add_in220); and(g21,add_in121,add_in22

26、1); and(g22,add_in122,add_in222); and(g23,add_in123,add_in223); and(g24,add_in124,add_in224); and(g25,add_in125,add_in225); and(g26,add_in126,add_in226); and(g27,add_in127,add_in227); and(g28,add_in128,add_in228); and(g29,add_in129,add_in229); and(g30,add_in130,add_in230); and(g31,add_in131,add_in23

27、1); /first level of operator wire 31:1 p1,g1; wire 31:2 p2,g2; wire 31:4 p3,g3; wire 31:8 p4,g4; wire 31:16 p5,g5; op op11(.p1(p0),.p2(p1),.g1(g0),.g2(g1), .p3(p11),.g3(g11); op op12(.p1(p1),.p2(p2),.g1(g1),.g2(g2), .p3(p12),.g3(g12); op op13(.p1(p2),.p2(p3),.g1(g2),.g2(g3), .p3(p13),.g3(g13); op op

28、14(.p1(p3),.p2(p4),.g1(g3),.g2(g4), .p3(p14),.g3(g14); op op15(.p1(p4),.p2(p5),.g1(g4),.g2(g5), .p3(p15),.g3(g15); op op16(.p1(p5),.p2(p6),.g1(g5),.g2(g6), .p3(p16),.g3(g16); op op17(.p1(p6),.p2(p7),.g1(g6),.g2(g7), .p3(p17),.g3(g17); op op18(.p1(p7),.p2(p8),.g1(g7),.g2(g8), .p3(p18),.g3(g18); op op

29、19(.p1(p8),.p2(p9),.g1(g8),.g2(g9), .p3(p19),.g3(g19); op op110(.p1(p9),.p2(p10),.g1(g9),.g2(g10), .p3(p110),.g3(g110); op op111(.p1(p10),.p2(p11),.g1(g10),.g2(g11), .p3(p111),.g3(g111); op op112(.p1(p11),.p2(p12),.g1(g11),.g2(g12), .p3(p112),.g3(g112); op op113(.p1(p12),.p2(p13),.g1(g12),.g2(g13),

30、.p3(p113),.g3(g113); op op114(.p1(p13),.p2(p14),.g1(g13),.g2(g14), .p3(p114),.g3(g114); op op115(.p1(p14),.p2(p15),.g1(g14),.g2(g15), .p3(p115),.g3(g115); op op116(.p1(p15),.p2(p16),.g1(g15),.g2(g16), .p3(p116),.g3(g116); op op117(.p1(p16),.p2(p17),.g1(g16),.g2(g17), .p3(p117),.g3(g117); op op118(.p

31、1(p17),.p2(p18),.g1(g17),.g2(g18), .p3(p118),.g3(g118); op op119(.p1(p18),.p2(p19),.g1(g18),.g2(g19), .p3(p119),.g3(g119); op op120(.p1(p19),.p2(p20),.g1(g19),.g2(g20), .p3(p120),.g3(g120); op op121(.p1(p20),.p2(p21),.g1(g20),.g2(g21), .p3(p121),.g3(g121); op op122(.p1(p21),.p2(p22),.g1(g21),.g2(g22

32、), .p3(p122),.g3(g122); op op123(.p1(p22),.p2(p23),.g1(g22),.g2(g23), .p3(p123),.g3(g123); op op124(.p1(p23),.p2(p24),.g1(g23),.g2(g24), .p3(p124),.g3(g124); op op125(.p1(p24),.p2(p25),.g1(g24),.g2(g25), .p3(p125),.g3(g125); op op126(.p1(p25),.p2(p26),.g1(g25),.g2(g26), .p3(p126),.g3(g126); op op127

33、(.p1(p26),.p2(p27),.g1(g26),.g2(g27), .p3(p127),.g3(g127); op op128(.p1(p27),.p2(p28),.g1(g27),.g2(g28), .p3(p128),.g3(g128); op op129(.p1(p28),.p2(p29),.g1(g28),.g2(g29), .p3(p129),.g3(g129); op op130(.p1(p29),.p2(p30),.g1(g29),.g2(g30), .p3(p130),.g3(g130); op op131(.p1(p30),.p2(p31),.g1(g30),.g2(

34、g31), .p3(p131),.g3(g131); /second level op op22(.p1(p0),.p2(p12),.g1(g0),.g2(g12), .p3(p22),.g3(g22); op op23(.p1(p11),.p2(p13),.g1(g11),.g2(g13), .p3(p23),.g3(g23); op op24(.p1(p12),.p2(p14),.g1(g12),.g2(g14), .p3(p24),.g3(g24); op op25(.p1(p13),.p2(p15),.g1(g13),.g2(g15), .p3(p25),.g3(g25); op op

35、26(.p1(p14),.p2(p16),.g1(g14),.g2(g16), .p3(p26),.g3(g26); op op27(.p1(p15),.p2(p17),.g1(g15),.g2(g17), .p3(p27),.g3(g27); op op28(.p1(p16),.p2(p18),.g1(g16),.g2(g18), .p3(p28),.g3(g28); op op29(.p1(p17),.p2(p19),.g1(g17),.g2(g19), .p3(p29),.g3(g29); op op210(.p1(p18),.p2(p110),.g1(g18),.g2(g110), .

36、p3(p210),.g3(g210); op op211(.p1(p19),.p2(p111),.g1(g19),.g2(g111), .p3(p211),.g3(g211); op op212(.p1(p110),.p2(p112),.g1(g110),.g2(g112), .p3(p212),.g3(g212); op op213(.p1(p111),.p2(p113),.g1(g111),.g2(g113), .p3(p213),.g3(g213); op op214(.p1(p112),.p2(p114),.g1(g112),.g2(g114), .p3(p214),.g3(g214); op op215(.p1(p113),.p2(p115),.