16位布斯算法乘法器和ALU

1、Booth算法16位乘法器西安電子科技大學(xué) 大三 集成電路設(shè)計(jì)與集成系統(tǒng)專業(yè) 尹俊鏢一 乘法器原理分析 16位有符號(hào)乘法器可以分為三個(gè)部分：根據(jù)輸入的被乘數(shù)和乘數(shù)產(chǎn)生部分積、部分積壓縮產(chǎn)生和和進(jìn)位、將產(chǎn)生的和和進(jìn)位相加。這三個(gè)部分分別對(duì)應(yīng)著編碼方式、拓?fù)浣Y(jié)構(gòu)以及加法器。1 編碼方式：本設(shè)計(jì)采用booth2編碼。部分積是負(fù)數(shù)時(shí)S=1，部分積是正數(shù)時(shí)S=0；當(dāng)部分積是+0時(shí)，E=1，部分積是-0時(shí)，E=0，其余情況E=S取反。2 拓?fù)浣Y(jié)構(gòu)：本設(shè)計(jì)采用二進(jìn)制樹的拓?fù)浣Y(jié)構(gòu)。二進(jìn)制樹拓?fù)浣Y(jié)構(gòu)排列的較為規(guī)整，且部分積壓縮的速度也非?？?。部分積壓縮的目的是為了減小進(jìn)位傳播的延時(shí)，采用進(jìn)位保留加法器，根據(jù)當(dāng)前

2、位信息產(chǎn)生下一位的進(jìn)位，僅僅產(chǎn)生而沒有進(jìn)位行波傳播，這樣就可以把當(dāng)前的多位壓縮到較少的位數(shù)。經(jīng)過幾次壓后，把部分積壓縮成和以及進(jìn)位。部分積主要是通過counter和compressor進(jìn)行壓縮，通常使用（3:2）counter和（4:2）compressor。（3:2）counter其實(shí)質(zhì)就是一個(gè)全加器，進(jìn)位輸入為ci，進(jìn)位輸出為c；（4:2）compressor可以由兩個(gè)全加器組成，ci為進(jìn)位輸入，Coin為內(nèi)部進(jìn)位，輸入到下一位的進(jìn)位輸入Ci，Coex為輸出進(jìn)位。上圖為二進(jìn)制樹的拓?fù)浣Y(jié)構(gòu)圖，每4個(gè)部分積輸入到一個(gè)（4:2）compressor中，產(chǎn)生兩個(gè)輸出，則8個(gè)部分積使用3次（4:2）

3、compressor就可以得到和和進(jìn)位。部分積的壓縮方式可以見下圖。如圖中所示，加上最后一個(gè)部分積的進(jìn)位，共有9個(gè)部分積，本設(shè)計(jì)把最后的進(jìn)位位移到第一個(gè)部分積上，使用5個(gè)全加器，把進(jìn)位融合到第一個(gè)部分積，這樣就轉(zhuǎn)變成8個(gè)部分積了，再使用兩級(jí)二進(jìn)制樹壓縮，所以總共使用了三級(jí)壓縮，最終得到部分積的和和進(jìn)位。為了免去不必要的硬件開銷，對(duì)于部分積邊上的位采用counter壓縮。上文提到的符號(hào)位擴(kuò)展的改進(jìn)方法，其目的也就是減少硬件開銷，所以在不影響性能的情況下，單獨(dú)出來部分積的邊緣位是十分有必要的。3 加法器本設(shè)計(jì)采用超前進(jìn)位加法器。為了使得乘法器的延時(shí)最小，最后一級(jí)的加法器采用傳播延時(shí)最小的超前進(jìn)位加

4、法器。超前進(jìn)位加法器的原理及構(gòu)成，在此不做詳述。二 仿真驗(yàn)證 對(duì)于16位乘法器的仿真驗(yàn)證，若采用窮舉法，則有232種情況，驗(yàn)證次數(shù)太多，所以只能采用隨機(jī)數(shù)的驗(yàn)證方法。產(chǎn)生兩個(gè)隨機(jī)數(shù)，加入到乘法器的兩個(gè)輸入端，如此循環(huán)10000次，若沒有錯(cuò)誤，則可以認(rèn)為乘法器功能正確。X，Y是產(chǎn)生的兩個(gè)隨機(jī)數(shù)，product是兩數(shù)的乘積，product_check是用于驗(yàn)證結(jié)果是否正確。Count用于計(jì)數(shù)，循環(huán)10000次，error記錄計(jì)算一萬次錯(cuò)誤的次數(shù)，若發(fā)生錯(cuò)誤，則退出仿真。 三 源程序代碼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),.