8주차 (2023. 02.15~2023.02.17) Booth Algorithm, Wallace Tree

[2023. 02.15~02.17]

Booth algorithm, Wallace Tree 구현에 계속 시간을 썻다.

1. Modified Booth algorithm  계수 모듈(x_sel, x_2sel, neg)

1.1. Coding circuit (x_sel, x_2sel, neg 생성)

3bit pair operation

위를 회로로 만들고 code로 만든것은 다음과 같다.

coding circuit

//----------------------------Part circuit coding -----------------------------------------------------------------------------------------
//Coding_circuit ..............................x_sel,x_2sel 신호 만들기
module coding_circuit(pre_y,y,next_y,x_sel,x_2sel,neg);
input pre_y,y,next_y;
output x_sel,x_2sel,neg;

//coding circuit 
//x_sel,x_2sel genearate
xor(x_sel,pre_y,y);
wire L,H,H_temp;
and(L,pre_y,y); or(H_temp,pre_y,y); not(H,H_temp);
mux2_to_1 mux(L,H,x_2sel,next_y);

buf(neg,next_y);
endmodule
//-----------------------mux2_to_1-------------------------------------
module mux2_to_1(i0,i1,out,s);
input i0,i1,s;
output out;
wire s_not;
not(s_not,s);
wire w1,w2;

and(w1,i0,s_not);
and(w2,i1,s);
or(out,w1,w2);
endmoduleBASH

1.2. Partial product 생성

3bit pair operation 그림에서 y' 는 위의 operation그림의 recode와 같으며 그 숫자에 따른 operation은 위와 같다.

 

따라서 앞으로 코딩해야할 순서는 다음과 같다.

①Operation 0,1,2에 따른 Shift 먼저 진행.

②Neg=1일 때에는 보수 후 +1을 해야함. 하지만 이미 shift되었으므로 operation이 1일때에는 00..01 (1)을, 2일때에는 shift되니 00..0010(2) 를 더해야 한다.

③2’complement에 따른 임시 reg +0 (그대로), +1 (neg=1 operation = 1), +2(neg=1, operation= 2)를 만든다. Reg 와 partial product를 더한다.

1.2.1. ①Operation 0,1,2에 따른 Shift 먼저 진행.

shift진행할 때, x_2sel=1인 경우 shift가 되면 p[0]는 비어있게 되므로 p[0] module을 따로 만들어야 한다.

 

p[0] circuit

X_sel [0]	X_2sel[0]	Neg	p
0	0	0	0
1	0	0	X [0]
0	1	0	0
1	0	1	-X [0]
0	1	1	0

p[0] circuit

 

p[1:15] circuit

X_sel [0]	X_2sel[0]	Neg	p
0	0	0	0
1	0	0	X
0	1	0	( X-1 )
1	0	1	- X
0	1	1	- ( X-1 )

p[1:15] circuit

//Partial proudct generator  ----------- p[0] 모듈----------------------
module Partial_pg0(x,x_sel,x_2sel,neg,p0);
//Difined p[0], becasue If x_2sel is 1 then p[0] is empth.
input x,x_sel,x_2sel,neg;
output p0;
wire x_sel_not,x_2sel_not,neg_not,x_not;
not(x_not,x);
not(x_2sel_not,x_2sel); 
not(neg_not,neg);
wire p0_1,p0_2,p0_3;
and(p0_1,x_sel,x_2sel_not,neg_not,x);
and(p0_2,x_sel,x_2sel_not,neg,x_not);
and(p0_3,x_sel_not,x_2sel_not,neg);
or(p0,p0_1,p0_2);
endmodule

//Partial proudct generator-------------x [ 1: 15 ] , p [1: 15] 생성----------------
module Partial_pg(x,pre_x,x_sel,x_2sel,neg,pp);
//Defined p[ 1 : 15 ] using x [ 1: 15 ] 
input x,pre_x;
input x_sel,x_2sel,neg;
output pp;

wire xj,xj_1,or_x;
and(xj,x,x_sel); and(xj_1,pre_x,x_2sel); or(or_x,xj,xj_1);
wire pp_temp1;

xor(pp_temp1,or_x,neg);
wire x_sel_not,x_2sel_not,pp_temp2,pp_temp3;
not(x_sel_not,x_sel); not(x_2sel_not,x_2sel); and(pp_temp2,x_sel_not,x_2sel_not,neg);
not(pp_temp3,pp_temp2); and(pp,pp_temp3,pp_temp1);
endmodule


// 16bit pg ---------------------pg 16bit으로 합치기----------------------------------------//////////////////////
module pg_16bit(x,x_sel,x_2sel,neg,pp);
input x_sel,x_2sel,neg;
input [15:0] x;
output [15:0] pp;
//Generate p [ 0 : 15]
Partial_pg0 pg0(x[0],x_sel,x_2sel,neg,pp[0]);
Partial_pg pg1(x[1],x[0],x_sel,x_2sel,neg,pp[1]);           Partial_pg pg2(x[2],x[1],x_sel,x_2sel,neg,pp[2]);
Partial_pg pg3(x[3],x[2],x_sel,x_2sel,neg,pp[3]);           Partial_pg pg4(x[4],x[3],x_sel,x_2sel,neg,pp[4]);
Partial_pg pg5(x[5],x[4],x_sel,x_2sel,neg,pp[5]);           Partial_pg pg6(x[6],x[5],x_sel,x_2sel,neg,pp[6]);
Partial_pg pg7(x[7],x[6],x_sel,x_2sel,neg,pp[7]);           Partial_pg pg8(x[8],x[7],x_sel,x_2sel,neg,pp[8]);
Partial_pg pg9(x[9],x[8],x_sel,x_2sel,neg,pp[9]);           Partial_pg pg10(x[10],x[9],x_sel,x_2sel,neg,pp[10]);
Partial_pg pg11(x[11],x[10],x_sel,x_2sel,neg,pp[11]);           Partial_pg pg12(x[12],x[11],x_sel,x_2sel,neg,pp[12]);
Partial_pg pg13(x[13],x[12],x_sel,x_2sel,neg,pp[13]);           Partial_pg pg14(x[14],x[13],x_sel,x_2sel,neg,pp[14]);
Partial_pg pg15(x[15],x[14],x_sel,x_2sel,neg,pp[15]); 

endmodule

//coding, parital product circuit module 합치기
module booth_coding(x,y,product1,product2,product3,product4,product5,product6,product7,product8,x_sel,x_2sel,neg);
input [15:0] x,y;
output[15:0] product1,product2,product3,product4,product5,product6,product7,product8;
output [7:0] x_sel,x_2sel,neg;

reg temp; //0을 담을 reg
initial begin temp=0; end
// 3bit pair and generate x_sel,x_2sel,neg by coding_circuit
coding_circuit c1(temp,y[0],y[1],x_sel[0],x_2sel[0],neg[0]); coding_circuit c2(y[1],y[2],y[3],x_sel[1],x_2sel[1],neg[1]);
coding_circuit c3(y[3],y[4],y[5],x_sel[2],x_2sel[2],neg[2]); coding_circuit c4(y[5],y[6],y[7],x_sel[3],x_2sel[3],neg[3]);
coding_circuit c5(y[7],y[8],y[9],x_sel[4],x_2sel[4],neg[4]); coding_circuit c6(y[9],y[10],y[11],x_sel[5],x_2sel[5],neg[5]);
coding_circuit c7(y[11],y[12],y[13],x_sel[6],x_2sel[6],neg[6]); coding_circuit c8(y[13],y[14],y[15],x_sel[7],x_2sel[7],neg[7]);

//Generate partial product generator, product
pg_16bit pg_1(x,x_sel[0],x_2sel[0],neg[0],product1); pg_16bit pg_2(x,x_sel[1],x_2sel[1],neg[1],product2);
pg_16bit pg_3(x,x_sel[2],x_2sel[2],neg[2],product3); pg_16bit pg_4(x,x_sel[3],x_2sel[3],neg[3],product4);
pg_16bit pg_5(x,x_sel[4],x_2sel[4],neg[4],product5); pg_16bit pg_6(x,x_sel[5],x_2sel[5],neg[5],product6);
pg_16bit pg_7(x,x_sel[6],x_2sel[6],neg[6],product7); pg_16bit pg_8(x,x_sel[7],x_2sel[7],neg[7],product8);
endmoduleBASH

---

1.2.2. ② Modified booth coding neg에 따른 2’complement

Neg=1인 경우 operation=1일때는 +1 , operation이 2일 때는 +2를 해야함.

그 외에는 b[0:15] = 0

X_sel	X_2sel	Neg	B[0]	B[1]	B[2:15]
0	0	0	0	0	0
1	0	0	0	0	0
0	1	0	0	0	0
1	0	1	1	0	0
0	1	1	0	1	1

reg b circuit

//module 2'complement의 +1 or +2 신호 만들기.
module pluse(x_sel,x_2sel,neg,b);
input x_sel,x_2sel,neg; output[15:0] b; 
reg temp; initial begin temp=0; end //assign 0 to temp
wire x_2sel_not,x_sel_not;       not(x_2sel_not,x_2sel);         not(x_sel_not,x_sel);

// if neg=1  x_sel=1 , b[0]=1
// if neg=1  x_2sel=1 , b[1]=1
and(b[0],x_sel,x_2sel_not,neg); and(b[1],x_sel_not,x_2sel,neg);

//the others b is 0
buf(b[2],temp);buf(b[3],temp);buf(b[4],temp);buf(b[5],temp);buf(b[6],temp);buf(b[7],temp);buf(b[8],temp);buf(b[9],temp);
buf(b[10],temp);buf(b[11],temp);buf(b[12],temp);buf(b[13],temp);buf(b[14],temp);buf(b[15],temp);

endmoduleBASH

1.2.3.  

1.2.4. ③Reg 와 partial product를 더하기

 

//---------------------------------------------------------------------보수 circuit module ---------------------------------------------------------
//---------------2'complement. +1 하기. 하지만 한칸 밀린경우 +2하기.
module two_com(pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8,x_sel,x_2sel,neg,product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8);
input [7:0] x_sel,x_2sel,neg;
input [15:0]pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8;
output [15:0]product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8;
wire [15:0] b1,b2,b3,b4,b5,b6,b7,b8;
pluse two1(x_sel[0],x_2sel[0],neg[0],b1); pluse two2(x_sel[1],x_2sel[1],neg[1],b2);
pluse two3(x_sel[2],x_2sel[2],neg[2],b3); pluse two4(x_sel[3],x_2sel[3],neg[3],b4);
pluse two5(x_sel[4],x_2sel[4],neg[4],b5); pluse two6(x_sel[5],x_2sel[5],neg[5],b6);
pluse two7(x_sel[6],x_2sel[6],neg[6],b7); pluse two8(x_sel[7],x_2sel[7],neg[7],b8);

adder_16bit adder1(pp1,b1,product_1);   adder_16bit adder2(pp2,b2,product_2);
adder_16bit adder3(pp3,b3,product_3);   adder_16bit adder4(pp4,b4,product_4);
adder_16bit adder5(pp5,b5,product_5);   adder_16bit adder6(pp6,b6,product_6);
adder_16bit adder7(pp7,b7,product_7);   adder_16bit adder8(pp8,b8,product_8);
endmodule


//16bit adder----------------보수 시 덧셈------------------------------------------
module adder_16bit (a,b,sum);
input [15:0] a,b;
reg c_in; initial begin c_in=0; end
output [15:0] sum;
wire  c_out;
wire [15:0] c;
//connect fulladder [16bit]
FullAdder adder0(a[0],b[0],c_in,sum[0],c[0]);         FullAdder adder1(a[1],b[1],c[0],sum[1],c[1]);    
FullAdder adder2(a[2],b[2],c[1],sum[2],c[2]);         FullAdder adder3(a[3],b[3],c[2],sum[3],c[3]);      
FullAdder adder4(a[4],b[4],c[3],sum[4],c[4]);         FullAdder adder5(a[5],b[5],c[4],sum[5],c[5]);       
FullAdder adder6(a[6],b[6],c[5],sum[6],c[6]);         FullAdder adder7(a[7],b[7],c[6],sum[7],c[7]);       
FullAdder adder8(a[8],b[8],c[7],sum[8],c[8]);         FullAdder adder9(a[9],b[9],c[8],sum[9],c[9]);         
FullAdder adder10(a[10],b[10],c[9],sum[10],c[10]);    FullAdder adder11(a[11],b[11],c[10],sum[11],c[11]);   
FullAdder adder12(a[12],b[12],c[11],sum[12],c[12]);   FullAdder adder13(a[13],b[13],c[12],sum[13],c[13]);  
FullAdder adder14(a[14],b[14],c[13],sum[14],c[14]);   FullAdder adder15(a[15],b[15],c[14],sum[15],c_out);   
endmodule

//1bit fulladder--------------------------------------------------------------------------
module FullAdder(x,y,c_in,sum,c_out);
input x,y,c_in;
output sum,c_out;
wire s1,c1,c2;

xor(s1,x,y);
and(c1,x,y);
xor(sum,s1,c_in);
and(c2,s1,c_in);
xor(c_out,c2,c1);
endmoduleBASH

1.3. 32bit 으로 만들기

//----------------------product 32bit 만들기 ----------------------
module booth_algorithm(p1,p2,p3,p4,p5,p6,p7,p8,x_sel,x_2sel,neg,product1,product2,product3,product4,product5,product6,product7,product8);
input [15:0] p1,p2,p3,p4,p5,p6,p7,p8;
input [7:0] x_sel,x_2sel,neg;
output [31:0] product1,product2,product3,product4,product5,product6,product7,product8;
reg [15:0] temp;
initial begin temp=0; end
//2bit shift (booth algorithm's point)
//Fill right empty space with 0
//Fill left empty pace with p[15] (signed)
assign product1 [31:0] = {{16 {p1[15] }},p1[15:0]};
assign product2 [31:0] = {{14 { p2[15] }},p2[15:0],temp[1:0]}; 
assign product3 [31:0] = {{12 { p3[15]  }},p3[15:0],temp[3:0]};
assign product4 [31:0] = {{10 { p4[15]  }},p4[15:0],temp[5:0]};
assign product5 [31:0] = {{8 { p5[15] }},p5[15:0],temp[7:0]};
assign product6 [31:0] = {{6 { p6[15] }},p6[15:0],temp[9:0]};
assign product7 [31:0] = {{4 { p7[15]  }},p7[15:0],temp[11:0]};
assign product8 [31:0] = {{2 { p8[15] }},p8[15:0],temp[13:0]};
endmodule

module Modified_booth_algorithm (x,y,pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8);
input [15:0] x,y;
output [31:0] pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8;

wire [15:0] product1,product2,product3,product4,product5,product6,product7,product8;
wire [7:0] x_sel,x_2sel,neg;
wire [15:0] product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8;
booth_coding booth1(x,y,product1,product2,product3,product4,product5,product6,product7,product8,x_sel,x_2sel,neg);
two_com twocom(product1,product2,product3,product4,product5,product6,product7,product8,x_sel,x_2sel,neg,product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8);
booth_algorithm booth(product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8,x_sel,x_2sel,neg, pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8);
endmoduleBASH

 

2. 최종 Modified_booth_algorithm 연결

module Modified_booth_algorithm (x,y,pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8);
input [15:0] x,y;
output [31:0] pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8;

wire [15:0] product1,product2,product3,product4,product5,product6,product7,product8;
wire [7:0] x_sel,x_2sel,neg;
wire [15:0] product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8;
booth_coding booth1(x,y,product1,product2,product3,product4,product5,product6,product7,product8,x_sel,x_2sel,neg);
two_com twocom(product1,product2,product3,product4,product5,product6,product7,product8,x_sel,x_2sel,neg,product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8);
booth_algorithm booth(product_1,product_2,product_3,product_4,product_5,product_6,product_7,product_8,x_sel,x_2sel,neg, pp1,pp2,pp3,pp4,pp5,pp6,pp7,pp8);
endmoduleBASH

---

3. 32bit Wallace Tree

---

3.1. 1bit 3input adder

//1bit CSA-------------------------------------------------------------------------------------------------
module CSA_1bit(a,b,c,sum,cout);
input a,b,c;
output sum,cout;
wire w1,w2,w3,w4,w5;
wire a_not,b_not,c_not; not(a_not,a); not(b_not,b); not(c_not,c);
wire w11,w22,w33;
wire ab,ac,bc;
xor(w1,b,c);
and(w2,w1,a_not); and(w3,a,b,c); and(w4,a,b_not,c_not); or(sum,w2,w3,w4);

and(w11,b,c);and(w22,a,b); and(w33,a,c);
or(cout,w11,w22,w33);
endmoduleBASH

---

3.2. 8bit CSA , 32bit CSA

//8bit CSA_CIN-------------------------------------------------------------------------------------------------
module CSA_8bit_cin(product1,product2,product3,sum,cout);
input [7:0] product1,product2,product3;
output [7:0] sum, cout;
reg temp;
initial begin temp=0; end
buf(cout[0],temp); //cout[0]=0
//cout이 하나씩 밀려 carry역할을 함.
CSA_1bit CSA1(product1[0],product2[0],product3[0],sum[0],cout[1]);  CSA_1bit CSA2(product1[1],product2[1],product3[1],sum[1],cout[2]);
CSA_1bit CSA3(product1[2],product2[2],product3[2],sum[2],cout[3]);  CSA_1bit CSA4(product1[3],product2[3],product3[3],sum[3],cout[4]);
CSA_1bit CSA5(product1[4],product2[4],product3[4],sum[4],cout[5]);  CSA_1bit CSA6(product1[5],product2[5],product3[5],sum[5],cout[6]);
CSA_1bit CSA7(product1[6],product2[6],product3[6],sum[6],cout[7]);  
endmodule

//8bit CSA_Cout-------------------------------------------------------------------------------------------------
module CSA_8bit_cout(product1,product2,product3,sum,cout);
input [7:0] product1,product2,product3;
output [7:0] sum, cout;
//cout하나씩 밀기
CSA_1bit CSA1(product1[0],product2[0],product3[0],sum[0],cout[1]);  CSA_1bit CSA2(product1[1],product2[1],product3[1],sum[1],cout[2]);
CSA_1bit CSA3(product1[2],product2[2],product3[2],sum[2],cout[3]);  CSA_1bit CSA4(product1[3],product2[3],product3[3],sum[3],cout[4]);
CSA_1bit CSA5(product1[4],product2[4],product3[4],sum[4],cout[5]);  CSA_1bit CSA6(product1[5],product2[5],product3[5],sum[5],cout[6]);
CSA_1bit CSA7(product1[6],product2[6],product3[6],sum[6],cout[7]); 
endmodule


//------------------------------------- 32bit CSA---------------------------------------------------------
module CSA_32bit(product1,product2,product3,sum,cout);
input [31:0] product1,product2,product3;
output [31:0] sum, cout;
CSA_8bit_cin csa1(product1[7:0],product2[7:0],product3[7:0],sum[7:0],cout[7:0]);
CSA_8bit_cout csa2(product1[14:7],product2[14:7],product3[14:7],sum[14:7],cout[14:7]);
CSA_8bit_cout csa3(product1[21:14],product2[21:14],product3[21:14],sum[21:14],cout[21:14]);
CSA_8bit_cout csa4(product1[28:21],product2[28:21],product3[28:21],sum[28:21],cout[28:21]);
CSA_1bit CSA5(product1[28],product2[28],product3[28],sum[28],cout[29]); 
CSA_1bit CSA6(product1[29],product2[29],product3[29],sum[29],cout[30]); 
CSA_1bit CSA7(product1[30],product2[30],product3[30],sum[30],cout[31]); 
wire w1,w2,w3,w4;
wire product1_not,product2_not,product3_not; not(product1_not,product1[31]); not(product2_not,product2[31]); not(product3_not,product3[31]);
xor(w1,product2[31],product3[31]);
and(w2,w1,product1_not); and(w3,product1[31],product2[31],product3[31]); and(w4,product1[31],product2_not,product3_not); 
or(sum[31],w2,w3,w4);
endmoduleBASH

3.3. Wallace Tree

//------------------------------------- Wallace_tree---------------------------------------------------------
module Wallace_tree(product1,product2,product3,product4,product5,product6,product7,product8,sum,cout);
input [31:0] product1,product2,product3,product4,product5,product6,product7,product8;
output [31:0]sum,cout;
wire [31:0] cout1,cout2,cout3,cout4,cout5;
wire [31:0 ] sum1,sum2,sum3,sum4,sum5;

CSA_32bit cas_32bit1(product1,product2,product3,sum1,cout1);
CSA_32bit cas_32bit2(product4,product5,product6,sum2,cout2);
CSA_32bit cas_32bit3(product7,product8,sum2,sum4,cout4);
CSA_32bit cas_32bit4(cout1,sum1,cout2,sum3,cout3);
CSA_32bit cas_32bit5(cout3,sum3,cout4,sum5,cout5);

CSA_32bit cas_32bit6(cout5,sum5,sum4,sum,cout);
endmoduleBASH

---

4. testbench