2013年12月30日 星期一

8 bit PARALLEL DIVIDER





8 bit PARALLEL DIVIDER

module divider8(q,out,a,b);// main module for parallel 8-bit divider
  input [7:0]a;//dividend
  input [3:0]b;//divisor
  output [3:0]out;//reminder
  output [4:0]q;//quotient
  wire [3:0]r1,r2,r3,r4;
  stage s1(q[4],r1[3:0],{1'b1},a[7:4],b[3:0]);
  stage s2(q[3],r2[3:0],q[4],{r1[2:0],a[3]},b[3:0]);
  stage s3(q[2],r3[3:0],q[3],{r2[2:0],a[2]},b[3:0]);
  stage s4(q[1],r4[3:0],q[2],{r3[2:0],a[1]},b[3:0]);
  stage s5(q[0],out[3:0],q[1],{r4[2:0],a[0]},b[3:0]);
endmodule     

module stage(q,out,t,a,b); // submodule      
  input [3:0]a;
  input [3:0]b;
  input t;
  output [3:0]out;
  output q;
  wire [3:0]c;
  cas ca1(out[0],c[0],t,b[0],a[0],t);
  cas ca2(out[1],c[1],t,b[1],a[1],c[0]);
  cas ca3(out[2],c[2],t,b[2],a[2],c[1]);
  cas ca4(out[3],c[3],t,b[3],a[3],c[2]);
  not n1(q,out[3]);
endmodule
           
module cas(out,cout,t,divisor,rin,cin); //controlled add-subtract
  input t,divisor,rin,cin;
  output cout,out;
  wire x;
  xor x1(x,t,divisor);
  fadd f1(out,cout,x,rin,cin);
endmodule

module fadd(s,cout,a,b,c); //full adder submodule
  input a,b,c;
  output s,cout;
  wire w1,w2,w3;
  and a1(w1,a,b);
  and a2(w2,b,c);
  and a3(w3,c,a);
  xor x1(s,a,b,c);
  or o1(cout,w1,w2,w3);
endmodule

Division Algorithm






Division

  1. Division
    • from http://www.asic-world.com/digital/arithmetic4.htmlDivision is another example of combining simple logic function to make a more complex  circuit.  Note that the method shown below ignores the divide-by-0 condition.  (see also Multipliers and dividers)
    • Algorithm 1: attempt subtraction
      • In calculating A / B, the divisor B is repeatedly subtracted from the digits of the dividend (A), after being multiplied either with ’1′ or with ’0′.  This multiplication bit (’1′ or ’0′) is selected for each subtraction step in such a manner that the subtraction result is not negative.  The division result is composed from all the successive multiplication bits while the remainder is the result of the last subtraction step.
      • own workThis algorithm can be implemented by a series of subtractors.  Each subtractor calculates the difference between two input numbers, but if the result is negative the operation is canceled and replaced with a subtraction of zero.
      • Each divider module:
        • contains a 1-bit subtractor with the usual inputs A, B and Li and outputs D and Lo.
        • the output select (OS) signal selects between bit X and A-B.  The signal is connected to the loan output (Lo) of the most significant 1-bit subtractor.
          • 0, means subtraction result was positive → D’ = D.
          • 1, means subtraction result was negative → D’ = X.
        • Inside each divider cell the OS signal selects between bitA and A-B.
        • The outputs can be expressed as a function of the inputs as in:
          own work
      • The complete division can therefore be implemented by a matrix of divider cells connected on rows and columns as shown in figure on the right.
      • Each row performs one multiplication-and-subtraction cycle where the multiplication bit is supplied by the NOT logic gate at the end of each row.  (also see “Combinational arithmetic“)
        own work
      • The number of gates increases with the square width of the numbers being divided.  This limits its use to designs where bit-width is relatively small, typically around 16 bits or below.

Multiplication

  1. Multiplication
    • adapted from http://ecen3233.okstate.edu/PDF/Labs/Combinational%20Multiplier.pdfMultiplication shows how simple logic functions can be combined to make a much more complex function.
    • Method 1: partial products
      • The result of multiplying two n-bit numbers occupies up to 2×n bits.Multiplying the 4-bit numbers A and B can be written as A3A2A1A0 × B3B2B1B0.  The product can then be found by adding the partial products.
      • own workA basic building block can be made using:
        • Forming the partial product of two binary digits is simply an AND operation.
        • Adding the partial sums can be accomplished with 1-bit full adders.
          own work
      • These building blocks can then be used to build a 4-bit multiplier as shown in the figure below.  (see also “Combinational multiplier“)
        own work
    • Method 2: quarter squares
      • ¼·(A + B)2 - ¼·(A – B)2 = ¼·(A2 + 2·A·B + B2) – ¼·(A2 – 2·A·B + B2) =A·B
        • hard wire a look-up table of squares
        • calculate A + B, and look up C = (A + B)2
        • calculate A – B, and look up D = (A – B)2
        • calculate C – D, and divide by 4.  The result is A × B.
      • So three additions, two table look ups and divide by 4 (right shift by 2 bits).
      • The size of the look up tables scales nicely linear with the length of the operands.
        :

2013年12月27日 星期五

8bit x 8bits 乘法器轉BCD顯示於七段顯示器--適用於DE2-70

module _8x8bit_mul_BCD_7seg(SW,LEDR,HEX0 ,HEX1 ,HEX2,HEX3,,HEX4,HEX5,HEX6,HEX7);
input [15:0]SW;
output [15:0]LEDR;
output [6:0] HEX0,HEX1,HEX2,HEX3,HEX4,HEX5,HEX6,HEX7; //7-segment display

 wire [7:0] a0,b0;

 wire [3:0] S4,S3,S2,S1,S0;
 wire [7:0] segout0;   //HEX 0
 wire [7:0] segout1;   //HEX 1
 wire [7:0] segout2;   //HEX 2
 wire [7:0] segout3;   //HEX 3
 wire [7:0] segout4;   //HEX 4

 wire [15:0] Product;

 assign a0=SW[7:0];
 assign b0=SW[15:8];

 assign LEDR[15:0]=Product;

 mult8S U0(Product,a0,b0);
 BIN2BCD(Product,S4,S3,S2,S1,S0);

 //Display BCD Sum to 7-segment Display

    _7seg UUT0(.hex(S0),.seg(segout0));
    _7seg UUT1(.hex(S1),.seg(segout1));
    _7seg UUT2(.hex(S2),.seg(segout2));
    _7seg UUT3(.hex(S3),.seg(segout3));
    _7seg UUT4(.hex(S4),.seg(segout4));
           
 assign HEX0=segout0[6:0];
 assign HEX1=segout1[6:0];
 assign HEX2=segout2[6:0];
 assign HEX3=segout3[6:0];
 assign HEX4=segout4[6:0];


 assign HEX5=7'h7f; //Blank 7-segment 
 assign HEX6=7'h7f;
 assign HEX7=7'h7f;   //set 1 => off LED



endmodule


// ------------------------------------------------------------------------
//8-bit multiplier
//Filename : mult16S.v : P = A * B 
//-------------------------------------------------------------------------
module mult8S(P,A,B);
output [15:0]P; // 32-bit product

input [7:0]A; //Multiplicand
input [7:0]B; //Multiplier

reg [15:0] p;
reg [15:0] temp;
reg [7:0] a;
reg [7:0] b;
integer  i;

always @(A or B)
   begin
a = A;
b = B;
if (a==0 || b==0) // q=0 when a or b equal 0
p = 15'b0;        
else if (a==1) // q=b when a equal 1
p = {8'b0000_0000,b};
else if (b==1) // q=a when b equal 1
p = {8'b0000_0000,a};
else 
begin
p = 15'b0;
for (i=0; i<8; i=i+1)
if  (b[i] == 1)
begin
                     temp = a << i; // shift left N bits
                     p = p + temp; 
end
end
    end
assign P = p;


endmodule



module BIN2BCD(Binary,ten_thous,thousands,hundreds,tens,ones);

input [15:0]Binary;

output ten_thous;
output thousands;
output hundreds;
output tens;
output ones;

reg [3:0]ten_thous;
reg [3:0]thousands;
reg [3:0]hundreds;
reg [3:0]tens;
reg [3:0]ones;


integer i;


always@(Binary)
begin 
 ten_thous=4'd0;
 thousands=4'd0;
 hundreds=4'd0;
 tens=4'd0;
 ones=4'd0;


 for (i=15; i>=0; i=i-1)
 begin
 //add 3 to column >=5 ;
 if (ten_thous>=5)
    ten_thous=ten_thous+3;
    
 if (thousands>=5)
    thousands=thousands+3;
    
 if (hundreds>=5)
    hundreds=hundreds+3;
    
 if (tens>=5)
    tens = tens + 3;
   
 if (ones>=5)
    ones = ones +3;   
   
 //shift left one bit
 ten_thous=ten_thous<<1;
 ten_thous[0]=thousands[3];

 thousands=thousands<<1;
 thousands[0]=hundreds[3];

 hundreds=hundreds<<1;
 hundreds[0]=tens[3];
  
 tens=tens<<1;
 tens[0]=ones[3];

 ones=ones<<1;
 ones[0]=Binary[i];

 end


 end

endmodule


//-----------------------------------------
//Common-cathod seven segment display
//using case.....endcase statement
//Filename : sevenseg_case.v
//----------------------------------------- 
module _7seg(hex , seg);
    input  [3:0] hex;
    output [7:0] seg;
    reg    [7:0] seg;
 // segment encoding
 //      0
 //     ---  
 //  5 |   | 1
 //     ---   <- 6
 //  4 |   | 2
 //     ---
 //      3
 always @(hex)
 begin
  case (hex)
       // Dot point is always disable
       4'b0001 : seg = 8'b11111001;   //1 = F9H
       4'b0010 : seg = 8'b10100100;   //2 = A4H
       4'b0011 : seg = 8'b10110000;   //3 = B0H
       4'b0100 : seg = 8'b10011001;   //4 = 99H
       4'b0101 : seg = 8'b10010010;   //5 = 92H
       4'b0110 : seg = 8'b10000010;   //6 = 82H
       4'b0111 : seg = 8'b11111000;   //7 = F8H
       4'b1000 : seg = 8'b10000000;   //8 = 80H
       4'b1001 : seg = 8'b10010000;   //9 = 90H
       4'b1010 : seg = 8'b10001000;   //A = 88H
       4'b1011 : seg = 8'b10000011;   //b = 83H
       4'b1100 : seg = 8'b11000110;   //C = C6H
       4'b1101 : seg = 8'b10100001;   //d = A1H
       4'b1110 : seg = 8'b10000110;   //E = 86H
       4'b1111 : seg = 8'b10001110;   //F = 8EH
       default : seg = 8'b11000000;   //0 = C0H
     endcase
   end
   
endmodule 

8bit x 8bit 乘法器 適用於DE2-70

8bit x 8bit 乘法器

module _8x8bit_mul(SW,LEDR);
input [15:0]SW;
output [15:0]LEDR;

wire [7:0]a0,b0;

assign a0=SW[7:0];
assign b0=SW[15:8];
 mult8S U0(LEDR[15:0],a0,b0);

endmodule


// ------------------------------------------------------------------------
//8-bit multiplier
//Filename : mult16S.v : P = A * B 
//-------------------------------------------------------------------------
module mult8S(P,A,B);
output [15:0]P; // 32-bit product

input [7:0]A; //Multiplicand
input [7:0]B; //Multiplier

reg [15:0] p;
reg [15:0] temp;
reg [7:0] a;
reg [7:0] b;
integer  i;

always @(A or B)
   begin
a = A;
b = B;
if (a==0 || b==0) // q=0 when a or b equal 0
p = 15'b0;        
else if (a==1) // q=b when a equal 1
p = {8'b0000_0000,b};
else if (b==1) // q=a when b equal 1
p = {8'b0000_0000,a};
else 
begin
p = 15'b0;
for (i=0; i<8; i=i+1)
if  (b[i] == 1)
begin
                     temp = a << i; // shift left N bits
                     p = p + temp; 
end
end
    end
assign P = p;


endmodule

乘法器實驗方塊圖 適用於DE2-70




二進位轉BCD碼的硬體實現


BCD碼這種編碼形式利用了四個位元來儲存一個十進位的數碼,使二進位和十進位之間的轉換得以快捷的進行。

要介紹的是二進位轉BCD碼的硬體實現,採用左移加3的演算法,具體描述如下:
(此處以8-bit 二進位碼為例)
1、左移要轉換的二進位碼1位元
2、左移之後,BCD碼分別置於百位、十位、個位
3、如果移位後所在的BCD碼列大於或等於5,則對該值加3
4、繼續左移的過程直至全部移位元完成


舉例:將十六進位碼0xFF轉換成BCD

Shift and Add-3 Algorithm
1. Shift the binary number left one bit.
2. If 8 shifts have taken place, the BCD number is in the Hundreds, Tens, and Units column.
3. If the binary value in any of the BCD columns is 5 or greater, add 3 to that value in that BCD column.
4. Go to 1.



 Here is a Verilog module for this truth table.
module add3(in,out);
input [3:0] in;
output [3:0] out;
reg [3:0] out;

always @ (in)
 case (in)
 4'b0000: out <= 4'b0000;
 4'b0001: out <= 4'b0001;
 4'b0010: out <= 4'b0010;
 4'b0011: out <= 4'b0011;
 4'b0100: out <= 4'b0100;
 4'b0101: out <= 4'b1000;
 4'b0110: out <= 4'b1001;
 4'b0111: out <= 4'b1010;
 4'b1000: out <= 4'b1011;
 4'b1001: out <= 4'b1100;
 default: out <= 4'b0000;
 endcase
endmodule


Here is a structural Verilog module corresponding to the logic diagram.
module binary_to_BCD(A,ONES,TENS,HUNDREDS);
input [7:0] A;
output [3:0] ONES, TENS;
output [1:0] HUNDREDS;
wire [3:0] c1,c2,c3,c4,c5,c6,c7;
wire [3:0] d1,d2,d3,d4,d5,d6,d7;

assign d1 = {1'b0,A[7:5]};
assign d2 = {c1[2:0],A[4]};
assign d3 = {c2[2:0],A[3]};
assign d4 = {c3[2:0],A[2]};
assign d5 = {c4[2:0],A[1]};
assign d6 = {1'b0,c1[3],c2[3],c3[3]};
assign d7 = {c6[2:0],c4[3]};
add3 m1(d1,c1);
add3 m2(d2,c2);
add3 m3(d3,c3);
add3 m4(d4,c4);
add3 m5(d5,c5);
add3 m6(d6,c6);
add3 m7(d7,c7);
assign ONES = {c5[2:0],A[0]};
assign TENS = {c7[2:0],c5[3]};
assign HUNDREDS = {c6[3],c7[3]};

endmodule

Binary to BCD Conversion Algorithm

Binary to BCD Conversion Algorithm

162 converts to 1-6-2



Purpose:

Conversion of a binary number into separate binary numbers representing digits of the decimal number.
(this example is for 8-bits, other sizes follow the same pattern)

Algorithm:



  1. If any column (100's, 10's, 1's, etc.) is 5 or greater, add 3 to that column.
  2. Shift all #'s to the left 1 position.
  3. If 8 shifts have been performed, it's done! Evaluate each column for the BCD values.
  4. Go to step 1.


Psuedo-Code:

PsuedoCode

Algorithm In Action:

Algorithm Table


BCD Conversion in Hardware:

Verilog:
Verilog Code



Binary to BCD conversion verilog code (9-bit)
module bin_2_bcd(B,P);
input [8:0] B;
output [10:0] P;
reg [10:0] P;
reg [19:0] z;
integer i;

always @(B)
  begin
    for(i = 0; i <= 19; i = i+1)
     z[i] = 0;
    z[11:3] = B;
    for(i = 0; i <= 5; i = i+1)
    begin
      if(z[12:9] > 4)    
         z[12:9] = z[12:9] + 3;
      
      if(z[16:13] > 4)    
         z[16:13] = z[16:13] + 3;
            
      z[19:1] = z[18:0];
        end
    P = z[19:9];        
  end             
endmodule

2 digit BCD Adder at Behavioral level Modeling 適用於DE2-70

2 digit BCD Adder 00+00+0=00 ~99+99+1=199

module _2digit_BCDAdder(SW, LEDR, LEDG , CLOCK_27 ,KEY ,HEX0 ,HEX1 ,HEX2,HEX3,,HEX4,HEX5,HEX6,HEX7 );
 input  [17:0] SW;   // toggle switches
 input  [7:0] KEY;       // Push bottom
 input  CLOCK_27;   //Clock 27MHz , 50Mhz

 output [17:0] LEDR;   // red  LEDS   
 output [8:0] LEDG;   // green LEDs
   
 output [6:0] HEX0,HEX1,HEX2,HEX3,HEX4,HEX5,HEX6,HEX7; //7-segment display

 reg [3:0] a1,a0;
 reg [3:0] b1,b0;
 reg cin;
 wire [3:0] S1,S0;
 wire C4,C8;

 wire [7:0] segout0;   //HEX 0
 wire [7:0] segout1;   //HEX 1
 wire [7:0] segout2;   //HEX 2

 assign LEDR[17:0]=SW[17:0];

 always@(SW)
 begin
  a0=SW[3:0];
  a1=SW[7:4];
  b0=SW[11:8];
  b1=SW[15:12];
  cin=SW[17];
 end 

 BCD_adder U0(a0,b0,cin,S0,C4);

 BCD_adder U1(a1,b1,C4,S1,C8); 



  //Display BCD Sum to 7-segment Display

    _7seg UUT0(.hex(S0),.seg(segout0));
    _7seg UUT1(.hex(S1),.seg(segout1));
    _7seg UUT2(.hex({3'b000,C8}),.seg(segout2));
    
           
 assign HEX0=segout0[6:0];
 assign HEX1=segout1[6:0];
 assign HEX2=segout2[6:0];

 assign HEX3=7'h7f; //Blank 7-segment 
 assign HEX4=7'h7f;
 assign HEX5=7'h7f; //Blank 7-segment 
 assign HEX6=7'h7f;
 assign HEX7=7'h7f;   //set 1 => off LED

endmodule 


module BCD_adder(a,b,cin,s,cout);
 input [3:0]a,b;
 input cin;
 output [3:0]s;
 output cout;

 reg [3:0]s,a_tmp,b_tmp;
 reg cout;
 reg [4:0]z;   //5bit Sum 

 always @ ( a or b )
  begin
   if (a>9)
    a_tmp= 4'b1001;   //若是>9 則為9
   else
    a_tmp=a;

   if (b>9)
    b_tmp = 4'b1001;   //若是>9 則為9
   else
    b_tmp=b; 
  end



 always@(a_tmp or b_tmp or cin)
  begin
   z=a_tmp+b_tmp+cin;
   if (z>9)
     {cout,s}=z+6;
   else
     {cout,s}=z;  

 end
endmodule




//-----------------------------------------
//Common-cathod seven segment display
//using case.....endcase statement
//Filename : sevenseg_case.v
//----------------------------------------- 
module _7seg(hex , seg);
    input  [3:0] hex;
    output [7:0] seg;
    reg    [7:0] seg;
 // segment encoding
 //      0
 //     ---  
 //  5 |   | 1
 //     ---   <- 6
 //  4 |   | 2
 //     ---
 //      3
 always @(hex)
 begin
  case (hex)
       // Dot point is always disable
       4'b0001 : seg = 8'b11111001;   //1 = F9H
       4'b0010 : seg = 8'b10100100;   //2 = A4H
       4'b0011 : seg = 8'b10110000;   //3 = B0H
       4'b0100 : seg = 8'b10011001;   //4 = 99H
       4'b0101 : seg = 8'b10010010;   //5 = 92H
       4'b0110 : seg = 8'b10000010;   //6 = 82H
       4'b0111 : seg = 8'b11111000;   //7 = F8H
       4'b1000 : seg = 8'b10000000;   //8 = 80H
       4'b1001 : seg = 8'b10010000;   //9 = 90H
       4'b1010 : seg = 8'b10001000;   //A = 88H
       4'b1011 : seg = 8'b10000011;   //b = 83H
       4'b1100 : seg = 8'b11000110;   //C = C6H
       4'b1101 : seg = 8'b10100001;   //d = A1H
       4'b1110 : seg = 8'b10000110;   //E = 86H
       4'b1111 : seg = 8'b10001110;   //F = 8EH
       default : seg = 8'b11000000;   //0 = C0H
     endcase
   end
   
endmodule 


BCD Adder at Behavioral level Modeling

BCD Adder  at Behavioral level Modeling



l1)把 BCD 碼的資料單純地用 2 進制相加, 並做適當的補正讓結果不至於跟 BCD 碼互相矛盾

l2)2進位的相加結果如果介於0~9之間, 就直接作為 BCD 相加結果。

l3)2進位的相加結果如果大於「10, 就把結果 +6 後作為 BCD 相加結果。
C=K+Z8Z4+Z8Z2


module bcdadder(out,in1,in2,cin);
 input [3:0]in1,in2;
 input cin;
 output [3:0]out;
 
 reg [3:0]out;
 integer cout,carry;
 always @ (in1 or in2)
 begin
   {cout,out}=in1+in2+cin;
   carry=(cout|(out[3] & out[2])|(out[3] & out[1]));
   if(carry==1'b1)
      out=out+4'b0110;
   else
     out=out+4'b0000;
 end
endmodule





2013年12月26日 星期四

16bit Booth 布斯乘法器

Booth演算法一次看乘數的兩個位元
  • 依照目前與先前位元的不同,執行下面工作:
    • 00: 字串0的中間部份,不需要算術運算
    • 01: 字串1的結尾,所以將被乘數加到乘積的左半部
    • 10: 字串1的開端,所以從乘積的左半部減去被乘數
    • 11: 字串1的中間部份,所以不需要算術運算
  • 如同前面的演算法,將乘積暫存器右移1位元

//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
//16-bit Booth's algorithm for multiplier
//Filename : booth.v                                                                ;;
//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

module booth(A, B, P);
parameter width=16; //設定為16位元
input [width-1:0] A; //被乘數
input [width-1:0] B; //乘數
output [width+width-1:0] P; //乘積結果

reg [width+width-1:0] P;
integer Count; //右移次數
reg [width+width:0] PA,right; //暫存乘數

always @ (A or B)
begin
PA[width+width:0]={16'b0,A,1'b0}; //{P, A, 1'b0}
for(Count=0;Count<width;Count=Count+1)
begin
case(PA[1:0]) //用PA最後2bit用CASE選擇函數;(PA[1:0])
2'b10: //若PA[1:0]為10時
begin
//PA=PA-B ;當PA=10時,乘積=乘積-被乘積
PA[width+width:width+1]=PA[width+width:width+1] - B[width-1:0];
rightsh1(PA,right); //執行算數右移task副程式
end
2'b01: //若PA[1:0]為01時
begin
    //PA=PA+B
PA[width+width:width+1]=PA[width+width:width+1] + B[width-1:0];
rightsh1(PA,right); //執行算數右移task副程式
end
default: //若PA[1:0]為00或11時
rightsh1(PA,right); //直接執行算數右移task副程式
endcase
PA=right;
end
  P[width+width-1:0]=PA[width+width:1]; //將乘積指定給輸出端
end

//右移task副程式
task rightsh1;
input [width+width:0] PA; //輸入為PA
output [width+width:0] right; //輸出為right
case (PA[width+width])
               //最高位元為0時之算數右移
1'b0:right[width+width:0]={1'b0,PA[width+width:1]};
//最高位元為1時之算數右移
1'b1:right[width+width:0]={1'b1,PA[width+width:1]};
endcase
endtask

endmodule

FPGA系統設計實務 (4/6)


FPGA系統設計實務 (4/6)


2013年12月18日 星期三

8-bit Booth’s Multiplier Booth演算法

Booth演算法
到目前為止,我們已經處理完正數的乘法,將這種演算法改成處理有號數字的最簡單方法是:首先將乘數與被乘數轉換成正數然後記住原來的正負號。而一種較簡潔的有號數字相乘的解決方法是Booth's algorithm。其構想來自下面觀察:只要具有加法與減法的能力,計算乘積應該有很多方法。假設我們想要計算(2)10X(6)10或(0010)2X(0110)2
          (0010)2
  X       (0110)2
______________________
+          0000     移位(乘數是0)
+         0010      相加(乘數是1)
+        0010       相加(乘數是1)
+       0000        移位(乘數是0)
______________________
       00001100
Booth觀察到:能夠執行加法或減法的ALU,可以用一種以上的方法得到相同的結果。如
(6)10=(-2)10+(8)10或(0110)2=(-0010)2+(1000)2
當第一次遇到1時,可以用減法取代一串的1,當遇到最後一個1後面的0時,再加上被乘數,例如:
          (0010)2
  X       (0110)2
______________________
+          0000     移位(乘數是0)
+         0010      相減(乘數的第一個1)
+        0000       移位(字串1的中間)
+       0010        相加(上一步驟是最後一個1)
______________________
       00001100
Booth為了求快而發明了這種解決方法,他將一群的位元分成以1作為開始,中間,結尾:
如果我們局限在只看兩個位元,根據兩個位元的值,我們得到符合前面圖中的狀況:
現行位元現行位元之右邊位元解釋範例
10一群1的開始000011110002
11一群1的中間000011110002
01一群1的結束000011110002
00一群0的中間000011110002
Booth演算法一次看乘數的兩個位元
  • 依照目前與先前位元的不同,執行下面工作:
    • 00: 字串0的中間部份,不需要算術運算
    • 01: 字串1的結尾,所以將被乘數加到乘積的左半部
    • 10: 字串1的開端,所以從乘積的左半部減去被乘數
    • 11: 字串1的中間部份,所以不需要算術運算
  • 如同前面的演算法,將乘積暫存器右移1位元
在準備好開始之前,將虛構位元0放在最右邊位元的右邊。將乘積右移時,因為我們是處理有號數字,必須保留中間過程結果的正負符號,所以當乘積向右移時,擴展其符號。因此第一次重覆迴圈的乘積暫存器右移1位元時,將(111001110)2轉換成(111100111)2,不是(011100111)2,這種移位稱為算術右移(arithemetic right shift),有別於邏輯右移。
例如:以Booth演算法執行負數乘法 (0010)2X(1101)2=(11111010)2或2X(-3)=-6
重覆次數步驟被乘數暫存器乘積暫存器
0起始值00100000 1101 0
110=>乘積暫存器=乘積暫存器-被乘數暫存器00101110 1101 0
乘積暫存器右移00101111 0110 1
201=>乘積暫存器=乘積暫存器+被乘數暫存器00100001 0110 1
乘積暫存器右移00101111 1011 0
310=>乘積暫存器=乘積暫存器-被乘數暫存器00101110 1011 0
乘積暫存器右移00101111 0101 1
411=>不做任何事00101111 0101 1
乘積暫存器右移00101111 1010 1
為了得到較快的乘法,可以將Booth演算法一般化,一次檢查多個位元。

TASK 1 : 8-bit Verilog Code for Booth’s Multiplier

module multiplier(prod, busy, mc, mp, clk, start);
output [15:0] prod;
output busy;
input [7:0] mc, mp;
input clk, start;
reg [7:0] A, Q, M;
reg Q_1;
reg [3:0] count;

wire [7:0] sum, difference;

always @(posedge clk)
begin
 if (start) begin
 A <= 8'b0;
 M <= mc;
 Q <= mp;
 Q_1 <= 1'b0;
 count <= 4'b0;
 end
 else begin
 case ({Q[0], Q_1})
 2'b0_1 : {A, Q, Q_1} <= {sum[7], sum, Q};
 2'b1_0 : {A, Q, Q_1} <= {difference[7], difference, Q};
 default: {A, Q, Q_1} <= {A[7], A, Q};
 endcase
 count <= count + 1'b1;
 end
end

alu adder (sum, A, M, 1'b0);
alu subtracter (difference, A, ~M, 1'b1);

assign prod = {A, Q};
assign busy = (count < 8);

endmodule

//The following is an alu.
//It is an adder, but capable of subtraction:
//Recall that subtraction means adding the two's complement--
//a - b = a + (-b) = a + (inverted b + 1)
//The 1 will be coming in as cin (carry-in)
module alu(out, a, b, cin);
output [7:0] out;
input [7:0] a;
input [7:0] b;
input cin;

assign out = a + b + cin;

endmodule
 Testbench for Booth’s Multiplier


module testbench;

reg clk, start;
reg [7:0] a, b;

wire [15:0] ab;
wire busy;

multiplier multiplier1(ab, busy, a, b, clk, start);

initial begin
clk = 0;
$display("first example: a = 3 b = 17");
a = 3; b = 17; start = 1; #50 start = 0;
#80 $display("first example done");
$display("second example: a = 7 b = 7");
a = 7; b = 7; start = 1; #50 start = 0;
#80 $display("second example done");
$finish;
end

always #5 clk = !clk;

always @(posedge clk) $strobe("ab: %d busy: %d at time=%t", ab, busy,
$stime);

endmodule

Multipliers & Pipelining

Multipliers & Pipelining



























MQTT Explorer 與 Node-Red 介面的實驗

 MQTT Explorer 與 Node-Red 介面的實驗 MQTT EXplorer 與 Node-Red介面的設定 (1) 設定  MQTT EXplorer Client    (2)        Node-Red LED ON  --> MQTT Explor...