Verilog - Sintetizar el conteo inicial de cero de alta velocidad

Los encoders iniciales pueden hacerse con una estructura de árbol equilibrada y agradable.

Primero, codifica los bits 2 por 2:

• 00 = > 10: 2 primeros ceros
• 01 = > 01: 1 cero inicial
• 10 = > 00: 0 cero inicial
• 11 = > 00: 0 cero inicial

Luego, ensambla en pares.

• Si ambos lados comienzan con 1xxx, el resultado es 10 ... 0
• Si el lado izquierdo comienza con 0, el resultado es 0 [izquierda]
• Si el lado izquierdo comienza con 1, el resultado es 01 [derecho (msb-1: 0)]

Sólo necesitas multiplexores.

Por ejemplo, el valor de 8 bits: 00000111

• 2 por 2: 00 00 01 11
• codificado: 10 10 01 00
• ensamblar: 100 001
• ensamblar: 0101 = 5 ceros iniciales.

En VHDL (no tengo ningún código de Verilog a mano), obtienes eso:

FUNCTION enc(CONSTANT a : unsigned(1 DOWNTO 0)) RETURN unsigned IS
BEGIN
  CASE a IS
    WHEN "00" => RETURN "10";
    WHEN "01" => RETURN "01";
    WHEN "10" => RETURN "00";
    WHEN OTHERS => RETURN "00";
  END CASE;
END FUNCTION enc;

FUNCTION clzi(
  CONSTANT n : IN natural;
  CONSTANT i : IN unsigned) RETURN unsigned IS
  VARIABLE v : unsigned(i'length-1 DOWNTO 0):=i;  
BEGIN
  IF v(n-1+n)='0' THEN
    RETURN (v(n-1+n) AND v(n-1)) & '0' & v(2*n-2 DOWNTO n);
  ELSE
    RETURN (v(n-1+n) AND v(n-1)) & NOT v(n-1) & v(n-2 DOWNTO 0);
  END IF;
END FUNCTION clzi;

FUNCTION clz64 (CONSTANT v : unsigned(0 TO 63)) RETURN unsigned IS
  VARIABLE e : unsigned(0 TO 63);     -- 64
  VARIABLE a : unsigned(0 TO 16*3-1); -- 48
  VARIABLE b : unsigned(0 TO 8*4-1);  -- 32
  VARIABLE c : unsigned(0 TO 4*5-1);  -- 20
  VARIABLE d : unsigned(0 TO 2*6-1);  -- 12
BEGIN
  FOR i IN 0 TO 31 LOOP e(i*2 TO i*2+1):=enc(v(i*2 TO i*2+1));  END LOOP;
  FOR i IN 0 TO 15 LOOP a(i*3 TO i*3+2):=clzi(2,e(i*4 TO i*4+3)); END   LOOP;
  FOR i IN 0 TO 7  LOOP b(i*4 TO i*4+3):=clzi(3,a(i*6 TO i*6+5)); END   LOOP;
 FOR i IN 0 TO 3  LOOP c(i*5 TO i*5+4):=clzi(4,b(i*8 TO i*8+7)); END LOOP;
 FOR i IN 0 TO 1  LOOP d(i*6 TO i*6+5):=clzi(5,c(i*10 TO i*10+9)); END LOOP;
 RETURN clzi(6,d(0 TO 11));
END FUNCTION clz64;

enc() hace la codificación clzi() fusiona dos vectores. clz64() es una implementación de ejemplo para una entrada de 64 bits.

Acabo de reescribir la solución anterior (y brillante) en Verilog.

module enc
(
   input wire     [1:0]       d,
   output logic   [1:0]       q
);

   always_comb begin
      case (d[1:0])
         2'b00    :  q = 2'b10;
         2'b01    :  q = 2'b01;
         default  :  q = 2'b00;
      endcase
   end

endmodule // enc

module clzi #
(
   // external parameter
   parameter   N = 2,
   // internal parameters
   parameter   WI = 2 * N,
   parameter   WO = N + 1
)
(
   input wire     [WI-1:0]    d,
   output logic   [WO-1:0]    q
);

   always_comb begin
      if (d[N - 1 + N] == 1'b0) begin
         q[WO-1] = (d[N-1+N] & d[N-1]);
         q[WO-2] = 1'b0;
         q[WO-3:0] = d[(2*N)-2 : N];
      end else begin
         q[WO-1] = d[N-1+N] & d[N-1];
         q[WO-2] = ~d[N-1];
         q[WO-3:0] = d[N-2 : 0];
      end
   end

endmodule // clzi

Puede usar la recursión para implementar su tipo de búsqueda binaria de manera sucinta.

module count_lead_zero #(
    parameter W_IN = 64, // Must be power of 2, >=2
    parameter W_OUT = $clog2(W_IN) // Let this default
) (
    input wire  [W_IN-1:0] in,
    output wire [W_OUT-1:0] out
);

generate
if (W_IN == 2) begin: base
    assign out = !in[1];
end else begin: recurse
    wire [W_OUT-2:0] half_count;
    wire [W_IN / 2-1:0] lhs = in[W_IN / 2 +: W_IN / 2];
    wire [W_IN / 2-1:0] rhs = in[0        +: W_IN / 2];
    wire left_empty = ~|lhs;

    count_lead_zero #(
        .W_IN (W_IN / 2)
    ) inner (
        .in  (left_empty ? rhs : lhs),
        .out (half_count)
    );

    assign out = {left_empty, half_count};
end
endgenerate

endmodule

Resultados del sintetizador de Yosys para 64 bits:

=== count_lead_zero ===

   Number of cells:                121
     $_ANDNOT_                       1
     $_AOI3_                         1
     $_MUX_                         56
     $_NOR_                          1
     $_NOT_                          7
     $_ORNOT_                        1
     $_OR_                          54

Es bastante compacto, pero la ruta crítica será a través de una capa mux y una reducción NOR por etapa (ya que los árboles de reducción no comienzan a calcular la salida correcta hasta que sus entradas son válidas), lo que funciona a ~ 20 niveles lógicos para obtener el LSB. Imagino que la otra solución con el árbol equilibrado sería más rápida pero de tamaño similar.

Tenga en cuenta que esto dará una salida de 63 (todos unos) si se le da una entrada de todos los ceros; no especificó esto en su pregunta, por lo que no está seguro de si es necesario. Esto es sencillo y económico de enmendar: haga una reducción de NOR en toda la entrada, concatene este bit al LHS del resultado y enmascare el resto del resultado cuando este bit esté establecido.