PROBLEM STATEMENT: DESIGN OF A 8-BIT GCD SYSTEM

The below figure shows the overall system design of a GCD (Greatest Common Divisor) System
design.
ALGORITHM:

EUCLIDEAN ALGORITHM:

Fig 1: Euclidean Algorithm Fig 2: Modified Euclidean Algorithm

EXAMPLE

CASE-1 (DIVISION) - Refer algorithm in figure -1

Let A = 42, B = 16 ;

Step 1: r = A mod B = 42 mod 16 ; remainder (r) = 10

Step 2: Check r = 0 ;

Since r != 0, new value of A = B = 16;

new value of B = r = 10;

Step 3: Repeat Step-1 ; A mod B = 16 mod 10; remainder (r) = 6;

Step 4: Check r = 0 ;

Since r != 0, new value of A = B = 10;

new value of B = r = 6;

Step 5: Repeat Step-1 ; A mod B = 10 mod 6; remainder (r) = 4;

Step 6: Check r = 0 ;

Since r != 0, new value of A = B = 6;

new value of B = r = 4;

Step 7: Repeat Step-1 ; A mod B = 6 mod 4; remainder (r) = 2;

Step 8: Check r = 0 ;

Since r != 0, new value of A = B = 4;

new value of B = r = 2;

Step 9: Repeat Step-1 ; A mod B = 4 mod 2; remainder (r) = 0;

Step 10: Check r = 0 ;

Yes, r = 0; Therefore, GCD = B = 2;

EXAMPLE

CASE-2 (REPEATED SUBTRACTION) - Refer algorithm in figure -2

Let A = 42, B = 16 ;

Step-1: Load A, B and compare A, B. (where A = 42, B = 16)

Step-2: A ! = B ; A > B; (42 > 16)

Step-3: New value of A = A-B = 42 - 16 = 26;

B = 16;

Step -4: Load new values of A, B and compare A, B. (where A = 26, B = 16)

Step-5: A ! = B ; A > B; (26 > 16)

Step-6: New value of A = A-B = 26 - 16 = 10;

B = 16;

Step -7: Load new values of A, B and compare A, B. (where A = 10, B = 16)

Step-8: A ! = B ; A < B; (10 < 16)

Step-9: New value of B = B - A = 16 - 10 = 6;

A = 10;

Step -10: Load new values of A, B and compare A, B. (where A = 10, B = 6)

Step-11: A ! = B ; A > B; (10 > 6)

Step-12: New value of A = A - B = 10 - 6 = 4;

B = 6;

Step -13: Load new values of A, B and compare A, B. (where A = 4, B = 6)

Step-14: A ! = B ; A < B; (4 < 6)

Step-15: New value of B = B - A = 6 - 4 = 2;

A = 4;

Step -16: Load new values of A, B and compare A, B. (where A = 4, B = 2)

Step-17: A ! = B ; A > B; (4 > 2)

Step-18: New value of A = A - B = 4 - 2 = 2;

B = 2;

Step -19: Load new values of A, B and compare A, B. (where A = 2, B = 2)

Step-20: A = B ; GCD = B = 2
HARDWARE REQUIREMENTS:

1. Register to load values of inputs A, B

2. Subtractor to perform either of A-B (or) B - A

3. Comparator, for comparison of values of A, B

4. Multiplexer
 DESIGN OF HARDWARE FOR DATA FLOW :

INPUT A INPUT B

A B B A
SUB SUB

B_SEL
A_SEL
SEL 1 0 0 1 SEL
2:1 MULTIPLEXER "A" 2:1 MULTIPLEXER "B"

A_LOAD B_LOAD
REGISTER REGISTER
A B

OUT_EN
REGISTER X Y
OUTPUT COMPARATOR

GT LT EQ

OUTPUT
WORKING OF DATAPATH AND GENERATION OF CONTROL SIGNALS:

EXAMPLE-1:

Let us assume input A = 42 , input B = 16

COMP IN A IN B A-B B-A A_ B_ A_ B_ REG A REG B

OUTPUT SEL SEL LD LD
GT EQ LT

- - - 42 16 0 0 1 1 1 1 42 16

1 0 0 42 16 26 -26 0 0 1 0 26 16

1 0 0 42 16 10 -10 0 0 1 0 10 16

0 0 1 42 16 -6 6 0 0 0 1 10 6

1 0 0 42 16 4 -4 0 0 1 0 4 6

0 0 1 42 16 -2 2 0 0 0 1 4 2

1 0 0 42 16 2 -2 0 0 1 0 2 2

0 1 0 42 16 OUTPUT_EN = 1; OUT = 2
EXAMPLE-2:

Let us assume input A = 60 , input B = 14

COMP IN A IN B A-B B-A A_ B_ A_ B_ REG A REG B

OUTPUT SEL SEL LD LD
GT EQ LT

- - - 60 14 0 0 1 1 1 1 60 14

1 0 0 60 14 46 -46 0 0 1 0 46 14

1 0 0 60 14 32 -32 0 0 1 0 32 14

1 0 0 60 14 18 -18 0 0 1 0 18 14

1 0 0 60 14 4 -4 0 0 1 0 4 14

0 0 1 60 14 -10 10 0 0 0 1 4 10

0 0 1 60 14 -6 6 0 0 0 1 4 6

0 0 1 60 14 -2 2 0 0 0 1 4 2

1 0 0 60 14 2 -2 0 0 1 0 2 2

0 1 0 60 14 OUTPUT_EN = 1 ; OUT = 2
CONTROL PATH DESIGN:

PURPOSE: TO GENERATE CONTROL SIGNALS

HOW TO DESIGN: USING FINITE STATE MACHINE

TYPE OF FSM : MOORE FSM

GCD SYSTEM BLOCK DIAGRAM WITH CONTROL SIGNALS

DESIGN OF CONTROL PATH SUB-SYSTEM USING FINITE STATE MACHINES

FSM-1

S0 : INITIAL STATE/RESET STATE

S1 : LOAD EXTERNAL INPUTS
S2 : WAIT STATE
S3 : COMPARISON STATE
S4 : GENERATE CONTROL SIGNALS FOR A > B CASE
S5 : GENERATE CONTROL SIGNALS FOR A < B CASE
S6 : WAIT STATE
S7 : GENERATE CONTROL SIGNALS FOR A = B CASE

DESCRIPTION OF OUTPUTS IN EACH STATE:

STATE A_SEL B_SEL A_LOAD B_LOAD OUT_EN DONE
S0 0 0 0 0 0 0
S1 1 1 1 1 0 0
S2 0 0 0 0 0 0
S3 0 0 0 0 0 0
S4 0 0 1 0 0 0
S5 0 0 0 1 0 0
S6 0 0 0 0 0 0
S7 0 0 0 0 1 1
FSM-2

FSM-3
MODELING OF GCD SYSTEM IN VERILOG HDL:

DATAPATH DESIGN + CONTROL PATH DESIGN (FSM-1)

// System inputs = [7:0] in1, in2; clock signal = clk ; reset signal = rst;
// System outputs = [7:0] out ; done signal.

module gcd (clk, rst, go, in1, in2, out, done);

input clk, rst, go ;
input [7:0] in1, in2 ;
output [7:0] out ;
output done;

// comparator outputs = intermediate input-output values = a_gt_b, a_eq_b, a_lt_b

// multiplexer selection signals = a_sel, b_sel
// register load signals = a_ld, b_ld
// output register enable signal = output_en

wire a_gt_b, a_eq_b, q_lt_b ;

wire a_ld, b_ld ;
wire a_sel, b_sel ;
wire output_en ;

// module instantiation for controller

controller c1(clk, rst, go, a_gt_b, a_eq_b, a_lt_b, a_ld, b_ld, a_sel, b_sel,
output_en, done) ;

// module instantiation for datapath

datapath d1(clk, rst, go, in1, in2, a_gt_b, a_eq_b, a_lt_b, a_ld, b_ld, a_sel, b_sel,
output_en, out) ;

endmodule
module datapath (clk, rst, in1, in2, a_gt_b, a_eq_b, a_lt_b, a_ld, b_ld, a_sel, b_sel,
output_en, out);
input clk,rst;
input a_ld, a_sel, b_ld, b_sel;
input output_en;
input [7:0] in1,in2;
output [7:0]out;
output a_gt_b, a_eq_b, a_lt_b ;

// register inputs = tain, tbin ; register outputs = taout, tbout;

// multiplexer outputs = tain, tbin ;
wire [7:0] tain,tbin,taout,tbout,t1,t2;

//module instantiation of subtractor

subtractor s1(taout,tbout,t1);
subtractor s2(tbout,taout,t2);

// module instantiation of multiplexer

// multiplexer-1 inputs = t1, in1 ; outputs = tain ; selection line = a_sel;
// multiplexer-2 inputs = t2, in2 ; outputs = tbin ; selection line = b_sel;
mux m1(tain,a_sel,t1,in1);
mux m2(tbin,b_sel,t2,in2);

//module instantiation of register

// register-a ; inputs = tain; output = taout ; load signal = a_ld;
// register-b ; inputs = tbin; output = tbout ; load signal = b_ld;
// register-out ; inputs = taout; output = out ; load signal = output_en;
register r1(clk,rst,tain,a_ld,taout);
register r2(clk,rst,tbin,b_ld,tbout);
register rout(clk,rst,taout,output_en,out);

//module instantiation of comparator

//comparator inputs = taout, tbout; outputs = a_gt_b,a_eq_b,a_lt_b
comparator c1(taout,tbout,a_gt_b,a_eq_b,a_lt_b);

endmodule
// 8-bit 2:1 Multiplexer module

module mux(out,sel,in0,in1);
output reg [7:0] out;
input [7:0] in0,in1;
input sel;
always@(sel or in1 or in0)
begin
if (sel = = 0)
out = in0;
else
out = in1;
end
endmodule

// 8-bit register module

module register (clk, rst, in, ld_en, out);

input clk,rst;
input [7:0] in;
input ld_en;
output reg [7:0] out;
always @(posedge clk)
begin
if (rst = = 1)
out <=0;
else if (ld_en==1)
out <= in;
end
endmodule
//8-bit Subtractor module

module subtractor (in1,in2,out);

input [7:0] in1,in2;
output reg [7:0] out;
always @(in1 or in2)
begin
out = in1 - in2;
end
endmodule

//8-bit comparator module

module comparator (a,b,a_gt_b,a_eq_b,a_lt_b);

input [7:0] a,b ;
output reg a_gt_b, a_eq_b, a_lt_b;
always @(a or b)
begin
if (a>b)
{a_gt_b, a_eq_b, a_lt_b} = 3'b100 ;
else if (a==b)
{a_gt_b, a_eq_b, a_lt_b} = 3'b010 ;
else
{a_gt_b, a_eq_b, a_lt_b} = 3'b001 ;
end
endmodule
// CONTROLLER (CONTROLPATH) MODULE

module controller(clk,rst,go,a_gt_b,a_eq_b,a_lt_b,a_ld,b_ld,a_sel,b_sel,
output_en, done);
input clk,rst,go;
input a_gt_b, a_eq_b, a_lt_b;
output reg a_sel, b_sel, a_ld, b_ld,done,output_en;
reg [2:0] cstate,nstate;

//STATE ASSIGNMENT
parameter s0 = 3'b000;
parameter s1 = 3'b001;
parameter s2 = 3'b010;
parameter s3 = 3'b011;
parameter s4 = 3'b100;
parameter s5 = 3'b101;
parameter s6 = 3'b110;
parameter s7 = 3'b111;

//D-FLIP FLOP DEFINITION

always @(posedge clk)
begin
if (rst = = 1)
cstate <= s0;
else
cstate <= nstate;
end
// PRESENT STATE - NEXST STATE DEFINITION - INPUT FORMING
LOGIC
always @ (go or a_gt_b or a_lt_b or a_eq_b or cstate)
begin
case ({cstate})
s0: if (go = = 0)
nstate = s0;
else
nstate = s1;
s1: nstate = s2;
s2: nstate = s3;
s3: if (a_gt_b == 1)
nstate =s4;
else if (a_eq_b ==1)
nstate =s7;
else
nstate =s5;
s4: nstate = s6;
s5: nstate = s6;
s6: nstate = s3;
s7: nstate = s0;
default : nstate = s0;
endcase
end

//OUTPUT FORMING LOGIC

always @(cstate)
begin
case ({cstate})
s0:
begin
a_sel = 0;
b_sel = 0;
a_ld = 0;
 b_ld = 0;
done = 0;
output_en =0;
end
s1:
begin
a_sel = 1;
b_sel = 1;
a_ld = 1;
b_ld = 1;
done = 0;
output_en =0;
end
s2:
begin
a_sel = 0;
b_sel = 0;
a_ld = 0;
b_ld = 0;
done = 0;
output_en =0;
end
s3:
begin
a_sel = 0;
b_sel = 0;
a_ld = 0;
b_ld = 0;
done = 0;
output_en =0;
end
s4:
begin
a_sel = 0;
 b_sel = 0;
a_ld = 1;
b_ld = 0;
done = 0;
output_en =0;
end
s5:
begin
a_sel = 0;
b_sel = 0;
a_ld = 0;
b_ld = 1;
done = 0;
output_en =0;
end
s6:
begin
a_sel = 0;
b_sel = 0;
a_ld = 0;
b_ld = 0;
done =0;
output_en =0;
end
s7:
begin
a_sel = 0;
b_sel = 0;
a_ld = 0;
b_ld = 0;
done = 1;
output_en =1;
end
default:
 begin
a_sel = 0;
b_sel = 0;
a_ld = 0;
b_ld = 0;
done = 0;
output_en =0;
end
endcase
end
endmodule

RESULTS
ASSIGNMENT:

1. REPEAT FOR 8-BIT GCD SYSTEM USING FSM-2 AND FSM-3

2. REPEAT FOR 32-BIT GCD SYSTEM, 64-BIT GCD SYSTEM

3. REPLACE TWO SUBTRACTORS WITH SINGLE SUBTRACTOR / USE

ABSOLUTE DIFFERENCE BLOCK

4. REPLACE SUBTRACTOR WITH COMPLEMENT ADDER BLOCK