Me gustaría tener una solución optimizada y sintetizable para el operador de módulo en Verilog (%) para la no potencia de dos enteros.
cnt_mod <= cnt % 3;
Para la potencia de dos enteros (n_arg), podría verse como un proceso de desplazamiento a la izquierda seguido de un truncamiento a n_arg bits.
¿Cómo se puede implementar para la no potencia de dos enteros?
Gracias
De hecho, es posible implementar el módulo mediante una constante con solo una suma y una pequeña tabla de consulta.
Suponga que tiene un número binario de 8 bits. Fíjate en todas las potencias de dos representables en 8 bits, que son las siguientes:
00000001 = 1
00000010 = 2
00000100 = 4
00001000 = 8
00010000 = 16
00100000 = 32
01000000 = 64
10000000 = 128
Ahora aplique el operador de módulo (% 3 en nuestro caso) a estas potencias de dos:
00000001 -> 1
00000010 -> 2
00000100 -> 1
00001000 -> 2
00010000 -> 1
00100000 -> 2
01000000 -> 1
10000000 -> 2
Esto nos da el valor de cada bit en el número mod 3. Usando el hecho de que (a + b)%x = (a%x + b%x)%x, podemos derivar un número más pequeño que tiene el mismo valor mod 3 como el número original:
n2 = cnt[0] + 2*cnt[1] + cnt[2] + 2*cnt[3] + cnt[4] + 2*cnt[5] + cnt[6] + 2*cnt[7];
Esta expresión es máxima cuando se establecen todos los bits en cnt. Por simple suma, obtenemos que n2 es como máximo 12. Por lo tanto, n2 es un número de 4 bits.
Ahora hemos "comprimido" nuestro número original de 8 bits en un número de 4 bits que tiene el mismo valor mod 3. Es decir, cnt%3 = n2%3.
Para obtener el módulo real, solo tenemos que tomar ese pequeño número de 4 bits mod 3 ahora, que la síntesis asignará a una tabla de búsqueda:
always @(*) begin
if (n2 < 3) cnt_mod3 = n2;
else if (n2 < 6) cnt_mod3 = n2 - 3;
else if (n2 < 9) cnt_mod3 = n2 - 6;
else if (n2 < 12) cnt_mod3 = n2 - 9;
else cnt_mod3 = n2 - 12;
end
Entonces, al final, todo lo que necesitábamos para calcular la expresión mod3 era un sumador y una tabla de búsqueda de 4 entradas.
Este método es aplicable a números arbitrariamente amplios y módulos arbitrarios siempre que el módulo sea constante. Lo único que cambiará es la lista de constantes con las que se debe multiplicar cada bit. Si "n2" sigue siendo demasiado ancho (es decir, 6 bits o más) después de aplicar la primera ronda de "compresión bit a bit", simplemente aplique otra ronda hasta que sea lo suficientemente pequeño.
Supongo que cnt es un contador.
Si es así, y si comienza desde 0 (o un número fijo N), entonces por qué no mantener una segunda variable cnt_mod_3, que se incrementa en el mismo momento que cnt y se restablece a 0 al llegar a 3.
De esa manera, no tiene que hacer ningún cálculo de módulo/división, y no tiene demora adicional.
En caso de que cnt no sea un contador (o se inicialice en tiempo de ejecución con números para los que no tiene el modolus 3), puede buscar el siguiente truco: N=0b a(n) a(n-1) . .. un(1) un(0). a(0) % 3 = +a(0) % 3 a(1) 0 % 3 = -a(1) % 3 a(2) 0 0 % 3 = +a(2) % 3 ... a( 2 i) 0...0 = +a(2 i) % 3 a(2 i+1) 0...0 = -(a i+1) % 3 ...
Entonces N%3 = suma(a(i)*(-1)^i) %3
Entonces puede reducir N a sum (a (i) * (-1) ^ i) para verificar el modolus 3 (que es un número mucho más grande). Reduzca en 1 o varios de estos pasos, ya sea hasta que pueda garantizar que el resultado está entre 0 y 2, o hasta que sea lo suficientemente pequeño como para usar una tabla de búsqueda para terminar.
NB: si prefiere usar números sin firmar, puede usar 2 a (2 i + 1) en lugar de -a (2 * i + 1)