¿Hay formas a nivel de puerta de producir el mínimo o el máximo de dos valores binarios?

Algunos conceptos básicos de la lógica digital son el medio sumador y el sumador completo . Sabemos cómo producir la suma de dos valores binarios al nivel de las puertas AND/OR/NOT, de una manera sencilla que se presenta en muchos libros de texto. (No importa los trucos avanzados que se usan en los chips de alto rendimiento del mundo real). Unos pocos ajustes, y podemos restar .

Lo que no recuerdo haber visto nunca son formas a nivel de puerta para producir el mínimo o el máximo de dos valores binarios. ¿Existe tal cosa? Si es así, ¿algún microprocesador lo usa?

Las comparaciones relativas requieren una conexión en cascada a través de los bits y no se pueden realizar con menos de capas de registro n. Otras dos capas para AND y OR con los valores de entrada y listo.
@IgnacioVazquez-Abrams, ¿qué quiere decir con "no se puede realizar con menos de capas de registro n"? Una ROM lo suficientemente grande podría hacerlo en 1 paso.
@ThePhoton: Revisé mi Gran lista de puertas, pero no pude encontrar una llamada "ROM".
@IgnacioVazquez-Abrams Piense en ello como una suma de productos muy amplia.
@IgnacioVazquez-Abrams No hay una sola puerta que pueda resolver este problema, incluso lo que usted propuso. ROM LUT ciertamente se puede construir a partir de puertas al igual que su sistema en cascada ...
@ThePhoton: la velocidad de conmutación de una sola puerta grande de entrada N será proporcional a N cuando cambie en la dirección "cualquiera" y a N ^ 2 en la dirección "todas" [por ejemplo, para una NAND, la dirección "cualquiera" es "cualquier entrada baja: salida alta", y la dirección "todas" es "todas las entradas altas: salida baja"]. Una función NAND de 32 entradas generalmente no se implementará usando una sola puerta de 32 entradas, sino como ocho puertas NAND de 4 entradas que controlan dos puertas NOR de 4 entradas que a su vez controlan una NAND de dos entradas. Tal implementación requeriría más circuitos, pero sería mucho más rápida que usar una puerta.
@supercat, "impracticablemente lento" no es lo mismo que "no se puede hacer".
@ThePhoton: Supongo que depende de cuál sea su objetivo para tratar de tener menos capas. Si un circuito de "dos capas" tomara más área que uno con más capas, tuviera un tiempo de propagación más largo y usara más energía cada vez que cambia, consideraría el hecho de que el circuito "podría" implementarse en dos capas para ser sólo de vago interés teórico.
@supercat, no lo haría de esa manera, pero no diría que "no se puede hacer". La pregunta nos pide específicamente que "no se preocupen por los trucos avanzados que se utilizan en los chips de alto rendimiento del mundo real". Entonces, es una pregunta sobre lo que es teóricamente posible, no la mejor manera de implementar las cosas en el mundo real.
@ThePhoton: Supongo que una buena pregunta podría ser si una puerta con 32 transistores en serie debe considerarse una "capa" o 32. Si las entradas están disponibles tanto en forma invertida como no invertida, se podría implementar cualquier función combinatoria para proporcionar tanto las salidas normales como las complementadas sin que la puerta de ningún transistor esté conectada a nada más que a las entradas. La mayoría de las ROM usan dos pasos además de la inversión de entrada, pero las funciones combinatorias nunca "necesitan" más de uno. Por otro lado, ¿dónde preguntó el OP sobre 'capas'? Creo que IVA estaba hablando desde un punto de vista práctico.

Respuestas (2)

Antes de considerar el mínimo/máximo, ¿qué tal comparar dos números? Digamos que tienes dos números binarios: A y B, y quieres saber si A>B. Lo que haces es una simple resta, C=BA. Si C es negativo, entonces A era mayor que B. Con un número binario complementario a dos, el bit más significativo (MSB) será 1 si el número es negativo y 0 si es positivo. Entonces, después de la resta, un solo bit te dirá si A o B es más grande.

Ahora, esa fue una manera súper simple de explicarlo. Hay algunos detalles a los que hay que prestar atención.

Esto funciona con números con signo (el complemento de dos). Si A y B no están firmados, primero deberá convertirlos a firmados. Todo lo que esto realmente significa es que agrega un bit cero a la izquierda y el número resultante es un poco más grande. Por ejemplo, si A = 1111 (sin firmar), entonces debe hacer A = 01111 (firmado).

El otro problema es que debe prestar atención al rango de números que va a utilizar y asegurarse de que no tiene condiciones de desbordamiento/desbordamiento. La forma habitual en que trato esto es darle a A y B un poco más. Entonces, un número con signo de 8 bits se convertirá en un número con signo de 9 bits. Esto se hace duplicando el bit superior (signo). Por ejemplo, si A = 1000 (firmado), A se convertirá en 11000 (firmado).

Una vez que haya hecho los cálculos correctamente, puede usar el MSB de C para determinar qué número es mayor. Luego puede usar un MUX simple para seleccionar A o B dependiendo del valor del MSB de C.

Restar seguido de seleccionar uno u otro. Bueno, esa es la forma obvia, y actualmente lo que se hace. Esperaba que hubiera una forma inteligente más directa.

Se llama comparador de magnitud y usa menos puertas que la solución vainilla. Consulte https://stackoverflow.com/questions/10767316/finding-the-maximum-of-two-integers-in-binary-using-bit-logic-only .

La solución "vainilla" de calcular la diferencia y mirar el MSB tiene la ventaja de reutilizar "partes" conocidas y puede ahorrarle algo de tiempo de diseño, según su caso de uso. Al menos puede guardar todas las puertas menos una para la salida, ya que solo verá el MSB.

¿Hay formas a nivel de puerta de producir el mínimo o el máximo de dos valores binarios?
RespuestasAquíPolítica de privacidad1y, 0v