Cómo averiguar si un número binario es cero

16

Estaba implementando la ALU a partir de las especificaciones dadas en mi libro de los sistemas de Elementos de Computación. Estoy atrapado en un solo problema. ¿Cómo puedo encontrar si un número dado es cero o no? Una cosa que puedo hacer es o cada bit en el autobús, y luego aplicar una puerta no en eso. Pero tiene que haber alguna otra solución elegante.

Rick_2047
fuente
66
no parece que estés atascado realmente, más como si no estuvieras satisfecho :)
vicatcu
77
una entrada X NOR es la solución elegante. Para determinar si el registro contiene cero, se debe examinar cada bit para ver si contiene un 0 lógico. Especificó que necesita una salida de un solo bit. Por lo tanto, necesita alguna función con X entradas y una salida, como un NOR.
W5VO

Respuestas:

14

Simplemente no hay forma de evitar ORing todos los bits, por más insatisfactorio que parezca. Sin embargo, tampoco está restringido a dos puertas de entrada en silicio. Puede construir una puerta NOR de 4 entradas en la lógica CMOS colocando 4 transistores tipo p de la serie en la red pullup y 4 transistores paralelos de tipo n en la red pulldown. Eso reduce la profundidad de la topología de su árbol y, por lo tanto, su retraso de propagación. Sin embargo, solo puede llevar esa teoría hasta el momento antes de que la caída de voltaje acumulada a través de los transistores en serie haga que el pull-up no sea lo suficientemente pull-up como para ser un "1" ... cuatro es una buena regla general si no recuerdo mal.

vicatcu
fuente
Para un mayor número de bits, ¿tendría sentido usar puertas NOR y NAND alternadas? Por ejemplo, con un fan-in de 4 puertas, una prueba de cero de 64 bits podría usar 16 puertas NOR alimentando un resultado de 1 si los 4 bits son cero a 4 puertas NAND que alimentan un resultado de 0 si los 4 bits son 1 (todos 16 bits originales fueron 0), estos cuatro resultados se enviarían a una puerta NOR final. (No soy un EE, pero eso parece ser mejor que usar inversores intermedios para que el resultado de cero vuelva a 0 y usar solo puertas NOR)
Paul A. Clayton
También puede haber formas de plegar parcialmente la latencia de detección cero en la latencia de adición.
Paul A. Clayton
¿Qué pasa con el uso de NMOS: una resistencia pull-up y transistores X para reducir el nivel a 0 si alguna entrada es 1?
Oskar Skog
13

La función lógica es la puerta NOR. Esa es la función lógica más simple que existe.

Rex Logan
fuente
8

La solución típica con máquinas de 8 bits era que la ALU produciría una cantidad de bits de 'bandera' que representarían el resultado de la operación más reciente. Si bien sería posible tener cualquier número de bits de bandera (es decir, podría tener una bandera 'Z' para cada registro en su CPU), generalmente es lo que acaba de calcular en el que es más interesante, por lo que tiene cierto sentido hacerlo de esa manera.

Algunas de esas CPU antiguas establecerían automáticamente bits de marca para casi cada movimiento de datos, mientras que otras requerirían que pegue una instrucción específica de 'comparación' en su código si de repente necesita saber si un registro determinado era cero. Y ya sea que proporcione una verificación de cero para cada registro o solo para lo que se acaba de calcular, realmente no hay una forma más simple de verificar "es esta palabra cero" que simplemente O todos los bits juntos.

JustJeff
fuente
1
Esto también es típico de los chips ARM de 32 bits, y puede ser típico de la mayoría de las arquitecturas. Para el ARM, el APSR (Registro de estado del programa de aplicación) contiene bits N, Z, C, V y Q (Negativo, Cero, Llevar, oVerflow, saturateQ) para proporcionar otras funciones además del bit cero que está buscando . Estos pueden o no ser útiles para su máquina.
Kevin Vermeer el
Obtuve la solución o bien, pero me molesta tener que usar tanta lógica para obtener solo un bit. Tiene que haber alguna solución elegante.
Rick_2047
@ Rick_2047: no mencionaste con qué estás implementando esto, pero ¿adivino un FPGA? También me molestaría tener que atar cualquier número de bloques lógicos solo para hacer una gran puerta de entrada. Esa es una buena razón para poner solo uno de ellos.
JustJeff
no exactamente un FPGA sino un simulador de hardware y HDL.
Rick_2047
3

Algunas CPU, MIPS, por ejemplo, tienen un registro que siempre contiene cero, lo que hace que probar otro registro para cero sea muy rápido.

Leon Heller
fuente
¿Cómo verifico el número si tengo un registro que contiene cero? También quiero generar solo un bit que sea verdadero o falso dependiendo de si el bus de 16 bits es cero o no
Rick_2047
1
un comparador ... que degenera en una
gloriosa
Podría ganar algo de esta manera si los registros son baratos (están en un bloque SRAM en un FPGA) y de todos modos necesita una instrucción de comparación de registros por otras razones.
jpc
@vicatu: en realidad, si desea comparar dos números de N bits, necesitaría puertas XOR de 2 entradas N. Lo de OR / NOR solo es bueno para pruebas cero.
JustJeff
pero en última instancia, necesitaría usar tantas puertas como bits de entrada o al menos tantos transistores.
Rick_2047
0

Soy un gran admirador or_reduce: la mayoría de las herramientas de síntesis lo optimizarán para la mejor implementación, ya que saben exactamente lo que está haciendo.

Aaron D. Marasco
fuente