Sorting algorithms form a cornerstone of computer science, and bubble sort, though not the most efficient, provides a clear lens into the mechanics of sorting. A recent lab assignment from the University of Engineering and Technology, Lahore, tasked students with translating bubble sort into hardware using a datapath and controller paradigm. The challenge lay in sorting four 4-bit numbers in ascending order with a single comparator in the datapath. This blog post explores a theoretical approach to the design, presents Verilog code implementations, and reflects on the process. Let’s dive into the details.
Background Theory
Bubble sort operates by repeatedly traversing a list, comparing adjacent elements, and swapping them if they are out of order. For four numbers, this involves multiple passes, with the largest number “bubbling up” to the end each time. In software, such as the C code provided in the lab, nested loops manage this process seamlessly. Hardware, however, demands a different approach: a datapath for data manipulation paired with a controller to sequence the operations. Bubble sort algorithm in C language works as follows:
The above C program can be seen in action here. The block diagram of a 4-bit bubble sort logic circuit is shown below:
Theoretical Design
The theoretical design can be outlined as follows:
- Inputs and Storage: Four 4-bit numbers enter through a 4-bit
data_inbus, with a 2-bitselinput determining which register (A, B, C, or D) stores each number. These registers later output the values asOut_A,Out_B,Out_C, andOut_D. Initially, these outputs display the unsorted numbers as entered by the user. - Datapath: A single 4-bit comparator evaluates adjacent pairs (e.g., A vs. B, B vs. C, C vs. D). Multiplexers route register outputs to the comparator, and a swap mechanism updates the registers when necessary. The block diagram of the datapath is given as:
- Controller: A finite state machine (FSM) governs the sorting process, orchestrating the sequence of comparisons and swaps to mimic bubble sort’s behavior. When the user activates the
SORTsignal (e.g., by pressing a button), the FSM transitions through states corresponding to each pair-wise comparison. For four numbers, at least three comparisons are needed to cover all adjacent pairs: A-B, B-C, and C-D. The controller directs the multiplexers to select the correct registers, enables swapping when required, and progresses through these steps across multiple clock cycles. Upon completing the sorting, it asserts a 1-bitDONEsignal, at which point the outputsOut_AthroughOut_Ddisplay the numbers in ascending order (lowest atOut_A, highest atOut_D). - Optimization: Limited to one comparator, the design relies on time-multiplexing, performing one comparison per clock cycle and updating registers sequentially.
Verilog Code for Datapath
module datapath_sort(clk,reset,data_in,sel_mux,en_R,reg_A,reg_B,reg_C,reg_D,sel_comp,g_t,en_count,count); input[3:0] data_in,en_R; input[1:0] sel_comp,sel_mux; input clk,reset,en_count; output reg[3:0] reg_A,reg_B,reg_C,reg_D; output reg count; output g_t; wire[3:0] w1,w2,w3,w4,mux_1,mux_2; // Input data control multiplexers for Registers assign w1 = (sel_mux==0)? data_in : (sel_mux == 1)? reg_B:4'bx; assign w2 = (sel_mux==0)? data_in : (sel_mux == 1)? reg_A :reg_C; assign w3 = (sel_mux==0)? data_in : (sel_mux == 2)? reg_B :reg_D; assign w4 = (sel_mux==0)? data_in : (sel_mux == 3)? reg_C :4'bx; // Input data control multiplexers for Comparator assign mux_1 = (sel_comp==0)? reg_A : (sel_comp==1)? reg_B:(sel_comp==2)?reg_C:4'bx; assign mux_2 = (sel_comp==0)? reg_B : (sel_comp==1)? reg_C:(sel_comp==2)?reg_D:4'bx; // 4-bit Comparator assign g_t = (mux_1 > mux_2)? 1 :0; // Four 4-bit Registers always @ (posedge clk) begin if(reset) begin reg_A <= 0; reg_B <= 0; reg_C <= 0; reg_D <= 0; count <= 0; end else begin if(en_R[3]) reg_A <= w1; if(en_R[2]) reg_B <= w2; if(en_R[1]) reg_C <= w3; if(en_R[0]) reg_D <= w4; if(en_count) count <= count + 1; end end endmodule
Verilog Code for Controller FSM
module controller_sort(clk,reset,sel_comp,sel_mux,en_count,sort,count,select,g_t,out_ready,en_R); input clk,reset,g_t,sort; output reg[1:0] sel_comp,sel_mux; input count; input[1:0] select; output reg[3:0] en_R; output reg out_ready,en_count; parameter s_wait = 2'b00, s1= 2'b01, s2 = 2'b10, s3= 2'b11; reg[1:0] state,next_state; always @ (posedge clk) begin if(reset) state <= s_wait; else state <= next_state; end always @ (*) begin sel_comp = 0; sel_mux = 0; en_R = 4'b0000; out_ready = 0; en_count = 0; case(state) s_wait :if(count)begin next_state = s_wait; out_ready = 1; end else if(sort)begin next_state = s1; end else begin en_R[3-select] =1; next_state = s_wait; end s1 :if(g_t)begin en_R = 4'b1100; sel_mux = 1; next_state = s2; end else begin sel_mux = 2'bx; next_state = s2; end s2 :if(g_t)begin en_R = 4'b0110; sel_mux = 2;sel_comp = 1; next_state = s3; end else begin sel_mux=2'bx;sel_comp = 1; next_state = s3; end s3 :if(count && g_t)begin next_state = s_wait; sel_mux = 1; en_R=4'b1100; end else if(count && !g_t)begin next_state = s_wait; sel_mux=2'bx; end else if(g_t)begin en_R = 4'b0011; sel_mux = 3;sel_comp = 2; en_count = 1; next_state = s1; end else begin sel_mux=2'bx;sel_comp = 2;en_count = 1; next_state = s1; end endcase end endmodule
Verilog Code for Bubble Sort (Top Level Module)
module bubble_sort(clk,reset,select,data_in,sort,out_ready,reg_A,reg_B,reg_C,reg_D); input clk,reset,sort; input[1:0] select; input[3:0] data_in; output[3:0] reg_A,reg_B,reg_C,reg_D; output out_ready; wire[1:0] sel_comp,sel_mux; wire count; wire[3:0] en_R; reg[3:0] mux_out; // Instantiation of Controller controller_sort cc1(clk,reset,sel_comp,sel_mux,en_count,sort,count,select,g_t,out_ready,en_R); // Instantiation of Datapath datapath_sort dp1(clk,reset,data_in,sel_mux,en_R,reg_A,reg_B,reg_C,reg_D,sel_comp,g_t,en_count,count); endmodule
Verilog Code for Testbench
module tb_bubble_sort();
reg sort,clk,reset;
reg[1:0] select;
reg[3:0] data_in;
wire out_ready;
wire[3:0] reg_A,reg_B,reg_C,reg_D;
reg error;
reg[3:0] a,b,c,d,s_a,s_b,s_c,s_d;
reg[3:0] array[0:3],swap;
integer error_count, total_tests,i,j,func_call;
// Instantiate bubble sort module, which is our device-under-test (DUT)
bubble_sort b_s(clk,reset,select,data_in,sort,out_ready,reg_A,reg_B,reg_C,reg_D);
// Clock generator
initial
begin
clk = 0;
forever #10 clk=~clk;
end
// Stimulus
initial
begin
reset = 0;sort = 0; data_in = 0; select = 0; error_count = 0; total_tests = 5;error = 0;
// First apply the reset sequence to the DUT.
reset_dut;
repeat(total_tests)
begin
reset_dut;
// Random number generation.
a = $random%9;
b = $random%9;
c = $random%9;
d = $random%9;
// Writing the four numbers to internal memory of the circuit.
write_mem(a, b, c, d);
// function call to the behavioral model of bubble sort.
func_call = out_array(a, b, c, d);
// assign sorted numbers.
s_a = array[0];
s_b = array[1];
s_c = array[2];
s_d = array[3];
// sort asserstion for sorting algorithm to start.
repeat(5) @(posedge clk);
sort = 1;
repeat(2) @(posedge clk);
sort = 0;
repeat(10) @ (posedge clk);
// Error check and display condtitions.
if({reg_A,reg_B,reg_C,reg_D} == {s_a,s_b,s_c,s_d})
$display("%0dns: Test completed successfully",$time);
else
begin
$display("%0dns: Error in Second test",$time);
error = 1;
end
if(error)
begin
error_count = error_count + 1;
end
end
$display("Total number of errors = %d", error_count);
#100 $stop;
end
// bubble sort algorithm behavioral model
function [3:0] out_array(input[3:0] a,b,c,d);
begin
array[0] = a;
array[1] = b;
array[2] = c;
array[3] = d;
for(i=0;i < 3;i=i+1)
begin
for(j=0;j < 3-i;j=j+1)
begin
if (array[j] > array[j+1]) /* For decreasing order use < */
begin
swap = array[j];
array[j] = array[j+1];
array[j+1] = swap;
end
end
end
out_array = array[0];
end
endfunction
// RESET
// Executes the reset sequence for the DUT
task reset_dut;
begin
reset = 0;
@(posedge clk); reset = 1;
repeat(5) @(posedge clk); reset = 0;
end
endtask
// WRITE_MEM writes four 3-bit words a, b, c and d
// to the DUT's internal memory.
task write_mem (input [3:0] a, b, c, d);
begin
reset = 0;
repeat(2) @(posedge clk); data_in = a; select = 0;
repeat(2) @(posedge clk); data_in = b; select = 1;
repeat(2) @(posedge clk); data_in = c; select = 2;
repeat(2) @(posedge clk); data_in = d; select = 3;
end
endtask
endmodule
Simulation Result
Conclusion
The exploration of designing a bubble sort circuit using a datapath and controller reveals the intricacies of adapting a classic software algorithm to hardware constraints. By employing a single comparator, four registers, and a finite state machine, the system successfully sorts four 4-bit numbers in ascending order, meeting the lab’s requirements with a balance of simplicity and functionality. The theoretical approach highlights the importance of time-multiplexing and precise control to overcome the limitation of minimal hardware resources, ensuring that unsorted numbers transition to a sorted sequence over a series of clock cycles. While the design sacrifices the full iterative nature of bubble sort for practicality, it serves as an effective educational tool, demonstrating how datapaths and controllers collaborate to solve real-world problems in digital systems. This exercise underscores the value of creative problem-solving in hardware design, bridging the gap between algorithmic theory and tangible implementation.