Mapas de Karnaugh y condiciones de don’t-care

De la tabla de verdad al coste de implementación

La tabla de verdad^{iTabla de verdad Tabla que enumera todas las combinaciones posibles de entradas y la salida de cada una. La evolución temporal se comprueba por separado en las formas de onda. Más información} define la función; la minimización decide con qué expresión implementarla. Con tres entradas, numeraremos los mintérminos por el binario ABC, con A como bit más significativo.

Por ejemplo, el mintérmino 4 es ABC=100. Las filas no enumeradas, 0, 2 y 6, producen 0. En lugar de cinco productos, pueden agruparse términos que difieran en un solo bit.

Karnaugh es una tabla con otro orden

Coloque BC en el orden 00, 01, 11, 10. Es código Gray: entre columnas adyacentes cambia un solo bit. También son adyacentes la primera y la última.

Los grupos son rectángulos con $1,2,4,8,\ldots$ celdas. Incluir un 0 cambia la función; incluir el mismo 1 en varios grupos está permitido.

1. Agrupe las cuatro celdas de las dos columnas con C=1. A y B varían, pero la salida sigue en 1: queda C.
2. Agrupe BC=00 y 01 en la fila A=1. Solo cambia C: queda $A\overline B$.
3. Una OR de ambos grupos cubre todos los unos y evita todos los ceros.

Compare la definición inicial y la expresión simplificada para las ocho entradas. Verifique por separado que la expresión es más corta y que la función se conserva.

El flujo siguiente convierte los grupos en expresiones: en el grupo C se eliminan A y B, que varían; en el grupo de dos celdas se elimina C.

Don’t-care concede libertad de optimización bajo una hipótesis

Suponga que el contrato del sistema garantiza que ABC=000 nunca aparece. Marcar esa celda X permite usarla como 0 o como 1. Agrupando las cuatro celdas con B=0 se obtiene:

La nueva expresión produce 1 con ABC=000 y difiere de la tabla completa original. Para afirmar equivalencia debe añadirse la condición de que la entrada no es 000. Si 000 aparece durante inicialización o recuperación de errores, esta optimización puede incumplir los requisitos del sistema.

Minimizar la expresión no equivale a minimizar el chip

Usar menos literales no garantiza un área, un retardo y una potencia óptimos en una biblioteca concreta. Influyen carga, fan-out, puertas compuestas disponibles, cableado y pulsos espurios. Aquí establecemos función e hipótesis; el coste físico se evalúa con síntesis y temporización.

Lectura adicional: MIT OpenCourseWare — Combinational Logic

Práctica · Solapamiento y condiciones de don’t-care

1. Seleccione el grupo C. A y B varían dentro de sus cuatro celdas; solo queda C.
2. Seleccione A·¬B. Cubre m4 y m5, y m5 también pertenece a C. Se permite solapamiento, pero no incluir ceros.
3. Pulse m0 dos veces: 0 → 1 → X. Con X, la especificación es incompleta e incluye d(0). El grupo B=0 se amplía y resulta $C+\overline B$.
4. Pulse m0 otra vez para volver a 0. Al recuperar el requisito original, debe desaparecer el grupo ampliado.

Seleccionar un grupo no cambia valores. Se mantiene la expresión completa que cubre todos los unos y se resalta solo el término que está examinando. «Mínimo» prioriza productos y después literales; si existen varias soluciones, se muestra una.