Count the number of 1's in a Binary number - Verilog Implementation with Testbench

Suppose you have a binary number, how do you count the number of one's in it? There are more than one way to do it. We will see two ways to do it and compare their performances.

Let's take a 16 bit binary number. The output of our design will have a width of 5 bits, to include the maximum value of output, which is 16("10000").

For example,

Input = "1010_0010_1011_0010" =>  Output = "00111" ( 7 in decimal)

Input = "1110_1010_1001_1010" =>  Output = "01001" ( 9 in decimal)

Input = "0011_0110_1000_1011" =>  Output = "01000" ( 8 in decimal)

Design 1 - A simple Verilog code can be written to achieve this:

module num_ones_for(
    input [15:0] A,
    output reg [4:0] ones
    );

integer i;

always@(A)
begin
    ones = 0;  //initialize count variable.
    for(i=0;i<16;i=i+1)   //check for all the bits.
        if(A[i] == 1'b1)    //check if the bit is '1'
            ones = ones + 1;    //if its one, increment the count.
end

endmodule

The code isn't that big and the logic is easy to understand. But it's less efficient and uses much more resources than the customized design I will present next.

Another way to achieve our purpose, would be to add all the bits in our input. Think of it as a sequence of 16 one bit-adders. The zeros in the input vector will not change the sum, and effectively we get the sum as the number of ones in the vector.

***Design 2 -See the Verilog code below to get what I meant:

module num_ones_for(
    input [15:0] A,
    output reg [4:0] ones
    );

integer i;

always@(A)
begin
    ones = 0;  //initialize count variable.
    for(i=0;i<16;i=i+1)   //for all the bits.
        ones = ones + A[i]; //Add the bit to the count.
end

endmodule

Testbench(same for both the designs):

module tb;

    // Inputs
    reg [15:0] A;

    // Outputs
    wire [4:0] ones;

    // Instantiate the Unit Under Test (UUT)
    num_ones_for uut (
        .A(A), 
        .ones(ones)
    );

    initial begin
        A = 16'hFFFF;   #100;
        A = 16'hF56F;   #100;
        A = 16'h3FFF;   #100;
        A = 16'h0001;   #100;
        A = 16'hF10F;   #100;
        A = 16'h7822;   #100;
        A = 16'h7ABC;   #100;   
    end
      
endmodule

Well, design 2 looks much more simpler than design 1 and the synthesis results showed that its much more faster and uses less number of LUT's. See the table below to see how the performance have improved.

Comparison:-

Name of Design	Combination delay	Number of Slice LUT’s used
Design 1	5.632 ns	47
Design 2	2.597 ns	20

As you can see Design 2 is much better than Design 1.

Verilog code for Carry Save Adder with Testbench

Carry save adder is very useful when you have to add more than two numbers at a time. Normally if you have three numbers, the method would be to add the first two numbers together and then add the result to the third one. This causes so much delay.

In this post I have implemented a 4 bit carry save adder which adds three numbers at a time. You might want to see page 1 and 2 of this paper to get a better understanding of how this exactly works.

fulladder.v

module fulladder
        (   input a,b,cin,
            output sum,carry
            );

assign sum = a ^ b ^ cin;
assign carry = (a & b) | (cin & b) | (a & cin);

endmodule

CSA.v

module CSA
        (   input [3:0] x,y,z,
            output [4:0] s,
            output cout
            );
            
wire [3:0] c1,s1,c2;

fulladder fa_inst10(x[0],y[0],z[0],s1[0],c1[0]);
fulladder fa_inst11(x[1],y[1],z[1],s1[1],c1[1]);
fulladder fa_inst12(x[2],y[2],z[2],s1[2],c1[2]);
fulladder fa_inst13(x[3],y[3],z[3],s1[3],c1[3]); 

fulladder fa_inst20(s1[1],c1[0],1'b0,s[1],c2[1]);
fulladder fa_inst21(s1[2],c1[1],c2[1],s[2],c2[2]);
fulladder fa_inst22(s1[3],c1[2],c2[2],s[3],c2[3]);
fulladder fa_inst23(1'b0,c1[3],c2[3],s[4],cout); 

assign s[0] = s1[0];

endmodule
tb_adder.v

module tb_adder;

    reg [3:0] x,y,z;
    wire [4:0] s;
    wire cout;  
    integer i,j,k,error;

    // Instantiate the Unit Under Test (UUT)
    CSA uut (x,y,z,s,cout);

//Stimulus block - all the input combinations are tested here.
//the number of errors are recorded in the signal named "error".
    initial begin
        // Initialize Inputs
        x = 0;
        y = 0;
        z = 0;
        error = 0;
        //three for loops to test all input combinations.
      for(i=0;i<16;i=i+1) begin
            for(j=0;j<16;j=j+1) begin
                for(k=0;k<16;k=k+1) begin
                     x = i;
                     y = j;
                     z = k;
                     #10;
                     if({cout,s} != (i+j+k)) 
                          error <= error + 1;
                end       
            end  
      end
    end 
    
endmodule

Simulation waveform:

The simulated waveform in Xilinx ISIM would look like this: