¿Por qué las implementaciones de sumas de productos son más populares que las implementaciones de productos de sumas?

6

En mi libro sobre diseño de circuitos ( Fundamentals of Digital Logic con VHDL de Stephen Brown y Zvonko Vranesic ), los escritores siempre prefieren una suma de producto para representar e implementar circuitos simples.

En Álgebra Booleana, esta preferencia también se usa, pero creo que principalmente porque escribir sumas de productos es más fácil y más corto. Y tal vez más fácil de entender para los lectores.

Pero cuando se implementa el uso de puertas lógicas, supongo que también se hacen otras consideraciones. Al igual que los costos y retrasos de las puertas.

Entonces, ¿hay alguna razón específica por la que se realicen implementaciones de suma de productos? F.e. ¿Son las puertas AND más baratas que las puertas OR? Leí sobre la realización de transistores de estas puertas, pero no puedo recordar tal declaración.

    
pregunta Steven Roose

5 respuestas

5

De lo que aprendí en mis cursos de lógica digital, todo tiende a hacerse con NAND, ya que son más baratos y cualquier función booleana puede realizarse con NAND (o NOR, en realidad). Me imagino que las implementaciones de suma de productos (puertas AND y OR) no son particularmente omnipresentes debido a esto.

    
respondido por el Shamtam
4

Aunque el producto de sumas y la suma de productos tienen una complejidad esencialmente equivalente (uno puede transformarse en el otro invirtiendo todas las entradas y salidas), creo que a la mayoría de las personas les resulta más fácil trabajar con la suma de productos. Por ejemplo, supongamos que se debe seleccionar un chip ROM en las direcciones de memoria [durante las cuales MREQ estará activo] en 0xC000-0xFFFF, y también se debe seleccionar en la dirección 0x0000-0x3FFF si BANKSEL no está configurado. Su ecuación de selección se podría escribir en forma de suma de productos como:

UseROM = (MREQ & A15 & A14) # (MREQ & !A15 & !A14 & !BANKSEL)

La correspondiente forma de producto de sumas, asumiendo la misma polaridad de salida, sería

UseROM = MREQ & (A15 # !A14) & (!A15 # A14) & (A14 # !BANKSEL)

El formulario de suma de productos identifica efectivamente las circunstancias en que la salida debería estar activa, mientras que el producto de sumas identifica efectivamente las circunstancias donde la salida debería estar inactiva. En el primero, hay dos términos de productos, cada uno de los cuales está claramente asociado con el acceso en uno de los dos rangos. En este último, hay cuatro factores, solo uno de los cuales tiene una relación obvia con el comportamiento deseado. Uno podría invertir el sentido de las entradas y salidas y obtener algo más parecido al anterior:

DontUseROM = (!MREQ # !A15 # !A14) & (!MREQ # A15 # A14 # BANKSEL)

Eso reducirá la complejidad para que coincida con el primer ejemplo, pero es mucho menos intuitivo. De hecho, la única forma de darle sentido es averiguar qué debe suceder para que DontUseROM disminuya, es decir, O EL primero o el segundo factor deben disminuir. Y cada factor solo se reducirá cuando las entradas cumplan TODAS las condiciones necesarias para que eso suceda. En otras palabras, volver a la suma de productos.

    
respondido por el supercat
3

La lógica invertida puede ser antinatural. Vayamos a la lógica cuantificada:

$$ \ forall x: ({duck} (x) \ land {quacks} (x)) \ lor ({dog} (x) \ land {barks} (x)) \ lor (\ lnot {duck } (x) \ land \ lnot {dog} (x)) $$

"Todo es un pato (y charlatanes), un perro (y ladridos) o no es un pato ni un perro".

Si escribimos el dual, y luego usamos DeMorgan para cambiar la lógica, obtenemos algo antinatural:

Dual (hasta ahora bien):

$$ \ lnot \ existe x: \ lnot ((({{pato} (x) \ land {quacks} (x)) \ lor ({dog} (x) \ land {barks} (x)) \ lor (\ lnot {duck} (x) \ land \ lnot {dog} (x))) $$

DeMorgan's, paso 1:

$$ \ lnot \ existe x: \ lnot (({duck} (x) \ land {quacks} (x)) \ land \ lnot ({dog} (x) \ land {barks} (x) \ land \ lnot (\ lnot {duck} (x) \ land \ lnot {dog} (x)) $$

paso 2:

$$ \ lnot \ existencia x: (({\ lnot duck} (x) \ lor {\ lnot quacks} (x)) \ land ({\ lnot dog} (x) \ lor {\ lnot barks} (x) \ land ({duck} (x) \ lor {dog} (x)) $$

"No existe una cosa que, simultáneamente:

  • es un no quacker o un no pato; y
  • no es un ladrón ni un perro; y
  • es un pato excavado o un perro ".

¿Decir qué? :)

La suma de productos va de la mano con dividir y conquistar. Una representación de la suma de productos de una proposición la divide en todos los casos en los que de forma independiente la hacen verdadera. La Proposición P es verdadera si tal y tal; o alguna situación; o si ese otro caso. La división en casos independientes ayuda a la claridad en el razonamiento.

Además, en la lógica de predicados y el razonamiento relacionado, usualmente tratamos con aspectos positivos, como "pato", y menos con aspectos negativos como "no pato". "no pato" no es una clase de objeto. Las cosas se clasifican utilizando los atributos positivos que tienen, no lo que no tienen. El espacio de las cosas que son "no pato" es ilimitado. Razonar con tales negativos es confuso.

En lógica proposicional , como en zeroth order logic sin cuantificadores, como con lo que tratamos en los circuitos lógicos, podemos escribir la tabla de verdad completa. Puede resultar que el espacio negativo de una función sea, de hecho, más fácil de caracterizar.

Por ejemplo, una fórmula booleana sobre cuatro variables tiene solo una tabla de 16 filas. Supongamos que hay tres filas para las que es verdadero, y es falso en cualquier otra parte. Luego se produce una fórmula simple al dar esas tres combinaciones de cuatro variables, y combinarlas con o .

Pero supongamos que la fórmula solo es falsa en tres filas. Entonces puede ser más conveniente y natural caracterizar estas excepciones, y expresarlo de esa manera: la fórmula es verdadera cuando las variables no están en esta combinación, y no están en esta otra combinación, y no en esta tercera combinación. Los operadores no pueden luego distribuir en las combinaciones, dando como resultado un producto sobre sumas.

Ejemplo positivo:

A B C D  P
0 0 0 0  0 
0 0 0 1  0
0 0 1 0  0
0 0 1 1  0
0 1 0 0  1 *
0 1 0 1  0
0 1 1 0  0
0 1 1 1  1 *    Sum of products:
1 0 0 0  0      P = A'BC'D' + A'BCD + ABC'D
1 0 0 1  0
1 0 1 0  0
1 0 1 1  0
1 1 0 0  0
1 1 0 1  1 *
1 1 1 0  0
1 1 1 1  0

Ejemplo negativo:

A B C D  P
0 0 0 0  1 
0 0 0 1  1
0 0 1 0  1
0 0 1 1  1
0 1 0 0  0 *
0 1 0 1  1
0 1 1 0  1
0 1 1 1  0 *    Product of sums:
1 0 0 0  1      P = (A'BC'D' + A'BCD + ABC'D)'
1 0 0 1  1      P = (A'BC'D')'(A'BCD)'(ABC'D)'
1 0 1 0  1      P = (A + B' + C + D)(A + B' + C' + D')(A' + B' + C + D')
1 0 1 1  1
1 1 0 0  1      Sum of products:
1 1 0 1  0 *    A'B'C'D' + A'B'C'D + A'B'CD' ... (10 more terms)
1 1 1 0  1
1 1 1 1  1

Aun así, a pesar de su simplicidad, es un poco difícil entender la tercera fórmula (producto de sumas) en comparación con la segunda (producto de productos negados). Sin embargo, la suma no simplificada alternativa de 13 productos también es difícil de entender, debido a la gran cantidad de términos.

    
respondido por el Kaz
1

Primero que todo: como han dicho otros, es posible implementar todas las funciones lógicas utilizando las puertas NAND o NOR de forma única.

Ahora, debido a su implementación CMOS estática, la puerta NAND tiende a ser más rápida que la NOR. Esto se debe a que la compuerta NAND tiene la ruta crítica como una serie de transistores N nMOS, donde N es el fan-in:

ElNOR,encambio,tienelarutacríticaconunaseriedetransistoresNpMOS.

En las mismas condiciones, debido a la menor movilidad de los orificios que los electrones, los pMOS son menos conductores que los nMOS y, por lo tanto, es preferible utilizar puertas NAND.

    
respondido por el clabacchio
0

el retardo de propagación a la puerta AND es menor que la puerta OR, por lo que la implementación de la lógica en SOP es mejor que POS. El segundo punto es el costo de la puerta, y la puerta es más barata que la puerta O.

    
respondido por el ram

Lea otras preguntas en las etiquetas