Leading zeros counter

Question

I am implementing a normalization unit for floating point and I want to know how to efficiently implement a leading zeros counter?

I know I can write the following, but I was wondering if there is a better method if I am targeting low area and high energy efficiency?:

always @(mantissa) begin
  case(mantissa)
    25'b1????????????????????????: newmant = mantissa[24:1];
    25'b01???????????????????????: newmant = mantissa[23:0];
    25'b001??????????????????????: newmant = {mantissa[22:0],1'b0};
    25'b0001?????????????????????: newmant = {mantissa[21:0],2'b0};
    // ... (details ommited for brevity)
  endcase
end

Answer 1

In VHDL (which should be readily portable to Verilog):

process
   variable leading_zeros : natural;
begin
   leading_zeros := 0;
   for i in input_vector'range loop
      if input_vector(i) = '1' then
         break;
      end if;
      leading_zeros := leading_zeros + 1;
   end for;
end process;

For non-VHDL speakers, all this does is loop over all the bits in input_vector from left to right, incrementing a counter each time it sees a 0. Once it finds the first 1, it drops out of the loop, leaving the counter containing the number of leading zeros.

To find out whether that is high-efficiency enough, you'll have to try the synthesis - let us know!

Answer 2

Why do you need a leading zero counter? Even if you have counted how many zeros in the prefix, at the end you still need the comparators and MUXs to determine how many zeros you have and compute the output. It could waste more for your performance/area due to many 1'b1 adders, MUXs, and comparators.

The for/while loop will be unrolled to 25 steps (according to the width) in the synthesizer. If you use leading zero counters, your architecture becomes like

// you will have 25 mux and adders
always @(mantissa) begin
  leading_zeros = 0;
  // for-loop expanded
  if (mantissa[24] == 1)
    disable count_n_2;
  else begin : count_n_2
    leading_zeros ++;
    if (mantissa[23] == 1)
       disable count_n_3;
    else begin : count_n_3
      leading_zeros ++;
      ...
    end
  end
end // always

// you will have 25 comparator and mux
always @(leading_zeros) begin
  case(leading_zeros)
    5'd0: newmant = mantissa[24:1];
    5'd1: newmant = mantissa[23:0];
    5'd2: newmant = {mantissa[22:0],1'b0};
    5'd25: ...
  endcase
end

so... you just use your own design and use tool's synthesis/mapping commands to see what it can do to achieve your requirements of area and power.