¿Existe algún algoritmo para determinar el número mínimo de compuertas NAND o NOR con
- número dado de entradas
- Disponibilidad / indisponibilidad de entrada complementada
requerido para realizar una expresión booleana? Podemos obtener una forma AND-OR como implicantes principales a través de los mapas de Karnaugh que es mínima (que yo sepa, el algoritmo Quine-McCluskey los obtiene de manera determinista). ¿Existe una técnica similar para implementaciones NAND o NOR también? Al menos, dicha técnica debería determinar el número mínimo requerido de compuertas NAND / NOR incluso sin encontrar el diagrama real.
Aplicar la ley de De Morgan sobre los principales implicados no parece determinista,
A ⊕ B = A'B + AB' = ((A'B)'(AB')')' [5 NAND gates]
A ⊕ B = (AB + A'B')' = ((ABAB+ABB') + (A'AB+A'B'))' = (AB(AB+B') + A'(AB+B'))' = ((AB+A')(AB+B'))' = (((AB)'A)'((AB)'B)')' [4 NAND gates by reusing (AB)']
logic-gates
boolean-algebra
Samik
fuente
fuente
Respuestas:
Solo puede encontrar el número mínimo de compuertas en una red de varios niveles resolviendo un problema de programación de enteros [o equivalentes, consulte a continuación]. Este problema es NP-completo, por lo que solo es práctico para resolver hasta una docena de puertas más o menos.
Existen métodos de aproximación que no le darán el número mínimo, pero son más manejables en términos de tiempo requerido ... Este es un gran tema en sí mismo, básicamente todo el campo de la optimización de niveles múltiples. Puede leer una descripción general [gratuita] aquí .
Para redes pequeñas de NAND (hasta 4 variables), el problema se ha resuelto completamente mediante una enumeración exhaustiva [o métodos equivalentes]. Hay una tesis doctoral bastante reciente [2009] de Elizabeth Ann Ernst que resume los resultados antiguos y los extiende. Ernst usa ramificación y encuadernación, lo que mejora el método exhaustivo en la práctica, pero no asintóticamente. También señala que otros métodos de enumeración implícita, como la programación de enteros o CSP (satisfacción de restricciones, resuelta mediante SAT), funcionan peor en la práctica.
Obviamente, escribió un software para su método (llamado BESS), pero no estoy seguro de si está disponible públicamente en algún lugar. El texto completo de su tesis está disponible gratuitamente en umich . Y, de hecho, ha encontrado la expresión mínima para xor de 2 entradas (obviamente la segunda), la que se resalta a continuación:
También comparó los resultados exactos (para NAND) con los producidos por el optimizador heurístico de ABC .
Hay (obviamente) algunas redes [más grandes] para las que BESS no terminó, pero permitió encontrar un límite superior (en el punto donde se abandonó la búsqueda). Para aquellos, a ABC le fue bastante bien [bien con respecto a los límites encontrados], como puede ver en el segundo gráfico a continuación.
fuente
resyn2guión. Así que no es mejor que Logic Friday (que usa misII).Probablemente hay mejores técnicas, pero allá en la edad oscura, encontré que Karnaugh Maps funcionaba bien.
fuente
NAND seguido de NAND es equivalente a AND seguido de OR.
NOR seguido de NOR es equivalente a OR seguido de AND.
NAND seguido de NOR sería equivalente a AND seguido de AND, lo que no tiene mucho sentido. NOR seguido de NAND sería igualmente equivalente a OR seguido de OR.
No creo que, en el caso general, haya una forma factible de encontrar una solución mínima para un problema con un gran número de entradas (obviamente, para recuentos de entradas pequeñas, puede aplicar fuerza bruta). Quine-McClusky solo analiza las soluciones de dos niveles (la solución mínima de dos niveles a menudo no es la solución mínima general) y puede volverse computacionalmente inviable con tablas de verdad complejas y gran cantidad de entradas.
fuente
El mejor algoritmo es el algoritmo Espresso . Hasta cierto punto, esto se implementa en la síntesis de FPGA
El viernes lógico es un software que puedes usar. NOTA: esto reduce un XOR a 5 puertas NAND.
fuente