2013年12月30日星期一

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

Division
- Division 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.
  - This 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 L_i and outputs D and L_o.
    - 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:
  - 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“)
  - 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

Multiplication
- Multiplication 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 A₃A₂A₁A0 × B₃B₂B₁B₀. The product can then be found by adding the partial products.
  - A 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.
  - These building blocks can then be used to build a 4-bit multiplier as shown in the figure below. (see also “Combinational multiplier“)
- Method 2: quarter squares
  - ¼·(A + B)² - ¼·(A – B)² = ¼·(A² + 2·A·B + B²) – ¼·(A² – 2·A·B + B²) =A·B
    - hard wire a look-up table of squares
    - calculate A + B, and look up C = (A + B)²
    - calculate A – B, and look up D = (A – B)²
    - 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月29日星期日

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

http://www.4shared.com/web/preview/doc/R_3O3-BU?

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

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碼的硬體實現

http://people.ee.duke.edu/~dwyer/courses/ece52/Binary_to_BCD_Converter.pdf

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

http://www.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html

Binary to BCD Conversion Algorithm

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:

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

Psuedo-Code:

Algorithm In Action:

BCD Conversion in Hardware:

Verilog:

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

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)

http://www.4shared.com/web/preview/doc/GNZbzD6w?

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作為開始，中間，結尾：

如果我們局限在只看兩個位元，根據兩個位元的值，我們得到符合前面圖中的狀況：

現行位元	現行位元之右邊位元	解釋	範例
1	0	一群1的開始	000011110002
1	1	一群1的中間	000011110002
0	1	一群1的結束	000011110002
0	0	一群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	起始值	0010	0000 1101 0
1	10=>乘積暫存器=乘積暫存器-被乘數暫存器	0010	1110 1101 0
1	乘積暫存器右移	0010	1111 0110 1
2	01=>乘積暫存器=乘積暫存器+被乘數暫存器	0010	0001 0110 1
2	乘積暫存器右移	0010	1111 1011 0
3	10=>乘積暫存器=乘積暫存器-被乘數暫存器	0010	1110 1011 0
3	乘積暫存器右移	0010	1111 0101 1
4	11=>不做任何事	0010	1111 0101 1
4	乘積暫存器右移	0010	1111 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