Forma normal canónica

Hay 2 ⁿ minterms de n variables, ya que una variable en la expresión del minterm puede estar en su forma directa o en su forma complementada; dos opciones por variable. Los minterms a menudo se numeran mediante una codificación binaria del patrón de complementación de las variables, donde las variables se escriben en un orden estándar, generalmente alfabético. Esta convención asigna el valor 1 a la forma directa (${\displaystyle x_{i}}$) y 0 a la forma complementada (${\displaystyle x'_{i}}$); el miniterm es entonces${\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {valor} (x_{i})}$. Por ejemplo, minterm${\displaystyle abc'}$está numerado 110 ₂  =  6 ₁₀ y se denota${\displaystyle m_{6}}$.

Dada la tabla de verdad de una función lógica, es posible escribir la función como una "suma de productos" o "suma de minitérminos". Esta es una forma especial de la forma normal disyuntiva . Por ejemplo, si se da la tabla de verdad para el bit de suma aritmética u de la lógica de una posición de bit de un circuito sumador, como una función de x e y de los sumandos y el acarreo de entrada, ci :

Observando que las filas que tienen una salida de 1 son la 2.ª, la 3.ª, la 5.ª y la 8.ª, podemos escribir u como una suma de minitérminos.${\displaystyle m_{1},m_{2},m_{4},}$y${\displaystyle m_{7}}$Si queremos verificar esto:${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)}$Evaluado para las 8 combinaciones de las tres variables coincidirá con la tabla.

Hay nuevamente 2 ⁿ maxterms de n variables, ya que una variable en la expresión del maxterm puede estar tanto en su forma directa como en su forma complementada; dos opciones por variable. La numeración se elige de manera que el complemento de un minterm sea el maxterm correspondiente. Es decir, a cada maxterm se le asigna un índice basado en la codificación binaria convencional opuesta utilizada para los minterms. La convención del maxterm asigna el valor 0 a la forma directa.${\displaystyle (x_{i})}$y 1 a la forma complementada${\displaystyle (x'_{i})}$Por ejemplo, asignamos el índice 6 al maxterm.${\displaystyle a'+b'+c}$(110) y denotemos ese maxterm como M ₆ . El complemento${\displaystyle (a'+b'+c)'}$es el miniterm${\displaystyle abc'=m_{6}}$, utilizando la ley de De Morgan .

Si se nos da una tabla de verdad de una función lógica, es posible escribir la función como un "producto de sumas" o "producto de maxitérminos". Esta es una forma especial de la forma normal conjuntiva . Por ejemplo, si se nos da la tabla de verdad para el bit de acarreo de salida co de la lógica de una posición de bit de un circuito sumador, como una función de x e y de los sumandos y el acarreo de entrada, ci :

Observando que las filas que tienen una salida de 0 son la 1.ª, 2.ª, 3.ª y 5.ª, podemos escribir co como un producto de maxtérminos.${\displaystyle M_{0},M_{1},M_{2}}$y${\displaystyle M_{4}}$Si queremos verificar esto:

${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+y)(ci'+x+y)}$

Evaluado para las 8 combinaciones de las tres variables coincidirá con la tabla.

Un conjunto de 8 compuertas NOR, si sus entradas son todas combinaciones de las formas directa y complementaria de las 3 variables de entrada ci, x e y , siempre producen minterms, nunca maxterms; es decir, de las 8 compuertas necesarias para procesar todas las combinaciones de 3 variables de entrada, solo una tiene el valor de salida 1. Esto se debe a que una compuerta NOR, a pesar de su nombre, podría considerarse mejor (utilizando la ley de De Morgan) como la operación AND de los complementos de sus señales de entrada.

La razón por la que esto no es un problema es la dualidad de los minitérminos y los maxitérminos, es decir, cada maxitérmino es el complemento del minitérmino con el mismo índice, y viceversa.

En el ejemplo del miniterm anterior, escribimos${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}}$pero para realizar esto con una puerta NOR de 4 entradas necesitamos reformularlo como un producto de sumas (PoS), donde las sumas son los max-términos opuestos. Es decir,

${\displaystyle u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0},m_{3},m_{5},m_{6}).}$

En el ejemplo de maxterm anterior, escribimos${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$pero para realizar esto con una puerta NOR de 4 entradas necesitamos notar la igualdad con la NOR de los mismos minitérminos. Es decir,

${\displaystyle co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).}$

Podría pensarse que el diseño de la etapa sumadora ya está completo, pero aún no hemos abordado el hecho de que las tres variables de entrada deben aparecer tanto en su forma directa como en su complemento. No hay dificultad alguna con los sumandos x e y en este sentido, ya que son estáticos durante la suma y, por lo tanto, normalmente se almacenan en circuitos de retención que suelen tener salidas tanto directas como complementarias. (El circuito de retención más simple, compuesto por puertas NOR, consiste en un par de puertas acopladas en cruz para formar un flip-flop: la salida de cada una se conecta como una de las entradas de la otra). Tampoco es necesario crear la forma complementaria de la suma u . Sin embargo, el acarreo de salida de una posición de bit debe pasarse como acarreo a la siguiente posición de bit, tanto en su forma directa como complementaria. La forma más sencilla de hacerlo es pasar co a través de una puerta NOR de una entrada y etiquetar la salida como co ' , pero esto añadiría un retardo de puerta en el peor lugar posible, ralentizando la propagación de acarreos de derecha a izquierda. Una puerta NOR adicional de 4 entradas que construye la forma canónica de co ′ (a partir de los minitérminos opuestos a co ) resuelve este problema.

${\displaystyle co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).}$

La compensación para mantener la velocidad máxima de esta manera incluye un costo inesperado (además de tener que usar una puerta más grande). Si solo hubiéramos usado esa puerta de 1 entrada para complementar co , no habría habido uso para el miniterm${\displaystyle m_{7}}$y la puerta que lo generó podría haberse eliminado. Sin embargo, sigue siendo un buen negocio.

Podríamos haber implementado esas funciones exactamente según sus formas canónicas SoP y PoS, transformando las compuertas NOR en las funciones especificadas. Una compuerta NOR se convierte en una compuerta OR al conectar su salida a una compuerta NOR de una entrada; y se convierte en una compuerta AND al conectar cada una de sus entradas a una compuerta NOR de una entrada. Sin embargo, este enfoque no solo aumenta el número de compuertas utilizadas, sino que también duplica el número de retardos de compuerta en el procesamiento de las señales, reduciendo la velocidad de procesamiento a la mitad. Por consiguiente, cuando el rendimiento es crucial, vale la pena ir más allá de las formas canónicas y realizar el álgebra booleana para que las compuertas NOR sin modificar cumplan la función.

Ahora hemos visto cómo las herramientas de minterm/maxterm pueden usarse para diseñar una etapa sumadora en forma canónica con la adición de álgebra booleana, con un costo de solo 2 retardos de puerta para cada una de las salidas. Esa es la forma "de arriba hacia abajo" de diseñar el circuito digital para esta función, pero ¿es la mejor? La discusión se ha centrado en identificar "más rápido" como "mejor", y la forma canónica aumentada cumple ese criterio a la perfección, pero a veces otros factores predominan. El diseñador puede tener como objetivo principal minimizar el número de puertas y/o minimizar la ramificación de señales a otras puertas, ya que una gran ramificación reduce la resistencia a una fuente de alimentación degradada u otros factores ambientales. En tal caso, un diseñador puede desarrollar el diseño en forma canónica como base, luego intentar un desarrollo de abajo hacia arriba y finalmente comparar los resultados.

El desarrollo ascendente implica observar que u = ci XOR ( x XOR y ), donde XOR significa OR exclusivo [verdadero cuando cualquiera de las entradas es verdadera pero no cuando ambas lo son], y que co = ci x + xy + y ci . Un desarrollo de este tipo requiere doce puertas NOR en total: seis puertas de 2 entradas y dos puertas de 1 entrada para producir u en 5 retardos de puerta, más tres puertas de 2 entradas y una puerta de 3 entradas para producir co ′ en 2 retardos de puerta. La línea base canónica requirió ocho puertas NOR de 3 entradas más tres puertas NOR de 4 entradas para producir u, co y co ′ en 2 retardos de puerta. Si el inventario de circuitos incluye realmente puertas NOR de 4 entradas, el diseño canónico descendente parece ser el ganador tanto en número de puertas como en velocidad. Pero si (contrariamente a nuestra suposición conveniente) los circuitos son en realidad puertas NOR de 3 entradas, de las cuales se requieren dos para cada función NOR de 4 entradas, entonces el diseño canónico requiere 14 puertas en comparación con las 12 del enfoque ascendente, pero aún así produce el dígito suma u considerablemente más rápido. La comparación de ramificación se presenta en la siguiente tabla:

La descripción del desarrollo ascendente menciona co ′ como una salida, pero no co . ¿Acaso ese diseño simplemente nunca necesita la forma directa de la salida de acarreo? Bueno, sí y no. En cada etapa, el cálculo de co ′ depende solo de ci ′ , x ′ e y ′ , lo que significa que la propagación del acarreo se propaga a lo largo de las posiciones de bits con la misma rapidez que en el diseño canónico sin desarrollar nunca co . El cálculo de u , que sí requiere que ci se construya a partir de ci ′ mediante una NOR de 1 entrada, es más lento, pero para cualquier longitud de palabra, el diseño solo paga esa penalización una vez (cuando se desarrolla el dígito de suma más a la izquierda). Esto se debe a que esos cálculos se superponen, cada uno en lo que equivale a su propia pequeña tubería sin afectar cuándo se puede calcular el bit de suma de la siguiente posición de bit. Y, por supuesto, la salida de co ′ de la posición de bit más a la izquierda probablemente tendrá que complementarse como parte de la lógica que determina si la suma se desbordó. Pero utilizando puertas NOR de 3 entradas, el diseño ascendente es casi igual de rápido para realizar sumas paralelas en una longitud de palabra no trivial, reduce la cantidad de puertas y utiliza menores ramificaciones... ¡así que gana si la cantidad de puertas y/o la ramificación son primordiales!

Dejaremos el circuito exacto del diseño ascendente del cual todas estas afirmaciones son verdaderas como un ejercicio para el lector interesado, asistido por una fórmula algebraica más: u = ci ( x XOR y ) + ci ′ ( x XOR y ) ′ ] ′ . Desacoplar la propagación del acarreo de la formación de la suma de esta manera es lo que eleva el rendimiento de un sumador de anticipación de acarreo sobre el de un sumador de acarreo en cascada .