Location of Most Significant ‘ON’ Bit

This algorithm is little complex and is based on binary seach mechanism, mainly hardware version of the binary search. This algorithm is explained in brief here. Please post your question if you need more information. Basic operation in the algorithm is that number of bits can be divided into two sub sections and operations on these two subsections can be performed in parallel.

This algorithm performs following steps

  • Divide 32 bit number in 2 16-bit numbers
  • Determine if Significant portion [31:16] is zero or not. If [31:16] is zero, perform search on [15:0] and else perform search on [31:16].
  • If search is being performed on [31:16], Add 16 to index in the number.
  • Repeat above operation, i.e. divide 32 bit into 2 16-bit, divide 16-bit into 2 8-bit number, & so on.

 Proposed Binary Search Based Algorithm
 module only1 (
      input wire [31:0] inb,
      input wire clk,
      input wire rst_n,
      output reg [4:0] loc,
      output reg val
      );

      reg if_1;
      reg [4:0] nval;
      integer i;

      always @(*) begin
         if_1 = 0;
         nval = 0;
         if (inb[31:16] == 0) begin
            if (inb[15:8] == 0) begin
               if (inb[7:4] == 0) begin
                  if (inb[3:2] == 0) begin
                     if (inb[1:0] == 0) begin
                        if_1 = 0;
                     end else begin
                        nval[0] = inb[1];
                        if_1 = 1;
                     end
                  end else begin
                     nval = inb[3] + 'b10;
                     if_1 = 1;
                  end
               end else begin
                  if (inb[7:6] == 0) begin
                     nval = inb[5] + 'b100;
                     if_1 = 1;
                  end else begin
                     nval = inb[7] + 'b110;
                     if_1 = 1;
                  end
               end
            end else begin
               if (inb[15:12] == 0) begin
                  if (inb[11:10] == 0) begin
                     nval = inb[9] + 'b1000;
                     if_1 = 1;
                  end else begin
                     nval = inb[11] + 'b1010;
                     if_1 = 1;
                  end
               end else begin
                  if (inb[15:14] == 0) begin
                     nval = inb[13] + 'b1100;
                     if_1 = 1;
                  end else begin
                     nval = inb[15] + 'b1110;
                     if_1 = 1;
                  end
               end
            end
         end else begin
               if (inb[31:24] == 0) begin
                  if (inb[23:20] == 0) begin
                     if (inb[19:18] == 0) begin
                        nval[0] = inb[17] + 'b10000;
                        if_1 = 1;
                     end else begin
                        nval = inb[19] + 'b10010;
                        if_1 = 1;
                     end
                  end else begin
                     if (inb[23:22] == 0) begin
                        nval = inb[21] + 'b10100;
                        if_1 = 1;
                     end else begin
                        nval = inb[23] + 'b10110;
                        if_1 = 1;
                     end
                  end
               end else begin
                  if (inb[31:28] == 0) begin
                     if (inb[27:26] == 0) begin
                        nval = inb[25] + 'b11000;
                        if_1 = 1;
                     end else begin
                        nval = inb[27] + 'b11010;
                        if_1 = 1;
                     end
                  end else begin
                     if (inb[31:30] == 0) begin
                        nval = inb[29] + 'b11100;
                        if_1 = 1;
                     end else begin
                        nval = inb[31] + 'b11110;
                        if_1 = 1;
                     end
                  end
               end
            end
      end

      always @(posedge clk or negedge rst_n) begin
         if (~rst_n)
               loc <= 1'b0;
         else
               loc <= nval;
      end

      always @(posedge clk or negedge rst_n) begin
         if (~rst_n)
               val <= 1'b0;
         else
               val <= if_1;
      end

endmodule

 

 
HW performance is

    • Complexity – 6/10 on simplicity scale. (More the better – Little Subjective)
    • Basic Gate Count & Timing –  Area is 1300.6 micron2 (Less the better), Critical Path Delay 2.74ns(Less the better)
    • Optimizable – Area is 1862 micron2(Less the better), Critical Path Delay 0.85ns (Less the better)

Next: Conclusion

Leave a Reply

Your email address will not be published. Required fields are marked *