Verilog Code | Datapath and Controller Design | Design 2 | GCD of two numbers
Problem Statement :
In the previous blog, we discussed on how data path and control paths can be together designed
in complex digital systems. We take up one more design example in this blog to get better understanding of the design procedure . We shall be taking another example, namely that of computing the GCD of two numbers (greatest common divisor , also known as HCF) .
Note that the GCD of two numbers is defined as the largest integer that divides both of them. For example if you have one number as 26 one number as 39 and if you compute the GCD of them. GCD will be 13, because 13 is the largest number which divides 26 as well as 39.
Algorithm Designed :
The method we follow is the method of repeated subtraction so the algorithm is depicted in this flowchart .
The algorithm i s very simple. If you are given two numbers A and B , for which you are trying to
compute the GCD. Then you compare A and B. If A is less than B, then subtract A from B , compute B - A and store the result in B . And if A is greater than B, then you subtract B from A and store it in A . If we find that A=B, then GCD is nothing but the value of either A or B.
Data path Design :
Our preliminary step is identifying the functional blocks that will be required in the data path and identify the control signals and design the FSM to execute this in sequence. okay
From the flowchart in Fig 1 ,we identify what are the elements in the data path that are required. First we will have to read the two numbers A and B, for them you will be needing two registers. Then you need subtraction so you need a subtractor. But one thing you see, is that sometimes we are doing A-B and sometimes we are doing B-A. SO the inputs must come through a multiplexer module which selects either to pass A-B or B-A . Finally to carry out the comparison you need some kind of comparator circuit.
Fig 2: Datapath Module
Control Path Design :
As we see in Fig 2, we need control signals to be generated at the appropriate instant, so as to function the datapath module in correct manner. We do so, by designing the following control module with 6 states {S0,S1--->S5}.
Fig 3: Control Path Module
The state transitions take place according to the FSM described below.
Fig 4: FSM depicting the state transitions
Signal Interface b/w the modules :
Verilog Code | Data Path Top Level Module :
`timescale 1ns / 1ps
module GCD_datapath(
input ldA,
input ldB,
input sel1,
input sel2,
input sel_in,
input clk,
input [15:0] data_in,
output gt,
output lt,
output eq
);
wire [15:0] Aout,Bout,X,Y,Bus,SubOut;
PIPO A (Aout,Bus,ldA,clk);
PIPO B (Bout,Bus,ldB,clk);
MUX MUX_in1 (X,Aout,Bout,sel1);
MUX MUX_in2 (Y,Aout,Bout,sel2);
MUX MUX_load (Bus,SubOut,data_in,sel_in);
SUB SB (SubOut,X,Y);
COMPARE COMP (lt,gt,eq,Aout,Bout);
endmodule
Verilog Code | Block Level Description of Data Path Module :
`timescale 1ns / 1ps
// Note that all modules here are implemented in behavioral manner //
// For complete control over circuit design, you may design the same in a structural fashion //
/***************** Registers to load A,B ************************/
module PIPO(data_out,data_in,load,clk);
input [15:0] data_in;
input load,clk;
output reg [15:0] data_out;
always@(posedge clk)
if(load)
data_out<=data_in;
endmodule
/******************* Multiplexer Module ********************/
module MUX (out,in0,in1,sel);
input [15:0] in0,in1;
input sel;
output [15:0] out;
assign out = sel ? in1 :in0 ;
endmodule
/******************* Comparator Module ********************/
module COMPARE (lt,gt,eq,data1,data2);
input [15:0] data1,data2;
output lt,gt,eq;
assign lt = data1 < data2 ;
assign gt = data1 > data2 ;
assign eq = data1 == data2 ;
endmodule
/******************* Subtractor Module ********************/
module SUB (out,in1,in2);
input [15:0] in1,in2;
output reg [15:0] out;
always@(*)
out = in1-in2;
endmodule
/**********************************************************/
Verilog Code | Control Path | Controller Design :
`timescale 1ns / 1ps
module controller(
input clk,
input lt,
input gt,
input eq,
input start,
output reg ldA,
output reg ldB,
output reg sel1,
output reg sel2,
output reg sel_in,
output reg done
);
reg [2:0] state;
parameter S0 = 3'b000 , S1 = 3'b001 , S2 = 3'b010 , S3 = 3'b011 , S4 = 3'b100 , S5 = 3'b101;
/************** State Transitions *******************/
always @(posedge clk)
begin
case(state)
S0: if(start) state <= S1;
S1: state<= S2;
S2: #2 if(eq) state<= S5;
else if(lt) state<= S3;
else if(gt) state<= S4;
S3: #2 if(eq) state<= S5;
else if(lt) state<= S3;
else if(gt) state<= S4;
S4: #2 if(eq) state<= S5;
else if(lt) state<= S3;
else if(gt) state<= S4;
S5: state<= S5;
default: state<= S0;
endcase
end
/********** Generation of Load Signals ****************/
always@(state)
begin
case(state)
S0: begin sel_in = 1; ldA = 1; ldB = 0; done = 0; end
S1: begin sel_in = 1; ldA = 0; ldB = 1; end
S2: if(eq) done = 1;
else if(lt) begin
sel1 = 1; sel2 = 0; sel_in = 0;
#1 ldA = 0; ldB = 1;
end
else if(gt) begin
sel1 = 0; sel2 = 1; sel_in = 0;
#1 ldA = 1; ldB = 0;
end
S3: if(eq) done = 1;
else if(lt) begin
sel1 = 1; sel2 = 0; sel_in = 0;
#1 ldA = 0; ldB = 1;
end
else if(gt) begin
sel1 = 0; sel2 = 1; sel_in = 0;
#1 ldA = 1; ldB = 0;
end
S4: if(eq) done = 1;
else if(lt) begin
sel1 = 1; sel2 = 0; sel_in = 0;
#1 ldA = 0; ldB = 1;
end
else if(gt) begin
sel1 = 0; sel2 = 1; sel_in = 0;
#1 ldA = 1; ldB = 0;
end
S5: begin
done = 1 ; sel1 = 0; sel2 = 0 ; sel_in = 0 ; ldA = 0 ; ldB = 0;
end
default : begin ldA = 0; ldB = 0 ; end
endcase
end
endmodule
Verilog Code | Testbench :
`timescale 1ns / 1ps
module GCD_testbench;
reg [15:0] data_in;
reg clk, start;
wire done;
GCD_datapath DP (ldA,ldB,sel1,sel2,sel_in,clk,data_in,gt,lt,eq);
controller CON (clk,lt,gt,eq,start,ldA,ldB,sel1,sel2,sel_in,done);
initial
begin
clk = 1'b0;
#3 start = 1'b1;
#1000 $finish;
end
always #5 clk = ~clk; // Clock period = 10 //
initial
begin
#12 data_in = 143;
#10 data_in = 78;
end
initial
begin
$monitor($time, "%d %b",DP.Aout,done);
$dumpfile ("gcd.vcd");$dumpvars(0,GCD_testbench);
end
endmodule
We come to an end of this post. I hope by the end of
this post, reader realizes that design of complex digital designs can
often by simplified by following a systematic breakdown approach into
data path and control path units.
Do share !
For more queries you can contact me at abhishekch0808@gmail.com
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete