Simplificación deFunciones Booleanas

Circuitos Digitales,2º de Ingeniero de Telecomunicación

ETSIT — ULPGC

Temario

1.Representación con mapas2.Método de simplificación con mapas3.Condiciones de indiferencia4.Método de tabulación5.Traslación a la tecnología de arrays de puertas6.Traslación a la tecnología de bibliotecas específicas7.Diseño libre de riesgos

Cubos booleanos deorden 1, 2, 3 y 4

Funciones booleanas ycubos booleanos

Un cubo de orden n representa las combinaciones de las n variables de una función Un cubo de orden n con vértices marcados

representa una función

Cada vértice representa un minterm Cada vértice marcado representa un

minterm 1 de la función

Funciones booleanas ycubos booleanos

Cada subcubo de orden m representa 2m minterms con n −m literales idénticos

Implicante primo, implicante primo esencial

En una función booleana, un implicante primo es un subcubo no contenido dentro de ningún otro implicante primo

Un implicante primo esencial es aquél que contiene minterms 1 no contenidos dentro de ningún otro implicante primo

Representación de funcionessuma y acarreo con cubos booleanos

ci+1

si+1

Tabla de verdad

Representación de mapas

Los mapas (de Karnaugh) definen funciones booleanasLa representación de mapas es equivalente a cualquiera de las otrasLos mapas ayudan a identificar de forma visual los implicantes primos y los implicantes primos esencialesLos mapas se emplean para optimización manual de funciones booleanas

Subcubos booleanos de orden 1, 2, 3 y 4 y mapas de Karnaugh correspondientes

Subcubos booleanos de orden 1, 2, 3 y 4 y mapas de Karnaugh correspondientes

Subcubos booleanos de orden 1, 2, 3 y 4 y mapas de Karnaugh correspondientes

Mapa de 2 variables

Organización del mapaEjemplos de

subcubos de orden 1

Mapa de 2 variables

Mapa de 3 variables

Organización del mapaEjemplos de

subcubos de orden 1

Mapa de 3 variables

Ejemplos desubcubos de orden 2

Representación con mapas de las funciones de suma y acarreo

Tabla de verdad

si

ci+1

Mapa de 4 variables

Organización del mapaEjemplos de

subcubos de orden 2

Mapa de 4 variables

Ejemplos desubcubos de orden 3

Las funciones mayor que y menor que

Las funciones mayor que y menor que

Mapas de 5 variables

Organización del mapa

Mapas de 5 variables

Ejemplos de subcubos de orden 3 y 4

Mapas de 6 variables

Organización del mapa

Mapas de 6 variables

Ejemplos de subcubos de orden 4

Método de simplificación con mapaGenerar mapa A partir de la forma canónica, de la tabla

de verdad o de una expresión algebraica

Identificar implicantes primos Son los subcubos más grandes que

pueden hacerse

Seleccionar implicantes primos esenciales Son aquellos que contienen al menos un

minterm 1 no incluido dentro de otro subcubo

Método de simplificación con mapa

Encontrar la cobertura mínima Elegir el menor número de subcubos que

contemplen todos los minterms 1 Deben estar los implicantes primos

esenciales Pueden haber varias combinaciones

Escribir la forma normalizada Pueden haber varias expresiones

normalizadas para la misma función

Método de simplificación con mapaSimplificar lafunción...

Método de simplificación con mapa

Selección de implicantes primos

Selección de implicantes primos

Indiferencias

Las funciones completamente especificadas tienen un valor definido para cada mintermLas funciones no completamente especificadas no tienen un valor para ciertos minterms Indiferencias o minterms d

Las indiferencias pueden tomar cualquier valor durante el proceso de simplificación

IndiferenciasObtenga las expresiones de

las funciones para los bits del complemento a 9 de un dígito BCD

Indiferencias

Indiferencias

Método tabular

El método del mapa es un procedimiento de prueba y errorEl método tabular realiza una búsqueda exhaustivaComienza con los minterms 1 y busca qué cubos se pueden formar, y se identifican los de mayor tamañoSe buscan las listas mínimas de cobertura

Método tabular

Generación de implicantes primos: Se comienza agrupando los minterms 1 por

el número de “unos” Se comparan los minterms agrupando

aquellos que se diferencien en una variable Se construyen así subcubos de orden

superior Se repiten estos pasos hasta que no se

puedan formar más subcubos

Método tabular

Generación de coberturas mínimas Se identifican los implicantes primos

esenciales mediante una tabla Se completan las listas de cobertura

observando los minterms 1 no cubiertos por los esenciales

Método tabular

Método tabular

Método tabular

Método tabular

Método tabular

IPs: P1, P2, P3 y P4

IPEs: P1 y P4

Método tabular

Listas de Cobertura (mínima): (1) P1, P2 y P4

(2) P1, P3 y P4

Expresiones normalizadas de F:(1) F = w 'z ' + wz + w 'y(2) F = w 'z ' + wz + yz

Método tabular

Método tabular

Método tabular

Método tabular

IPs: P1, P2, P3, P4, P5 y P6

IPEs: P1 y P2

Método tabular

Listas de Cobertura (mínima): (1) P1, P2 y... ¿?

P3 o P5, P4 o P6, y P5 o P6...

Método tabular

(P3 + P5)(P4 + P6)(P5 + P6) =

= (P3P4 + P3P6 + P4 P5+P5P6)(P5 + P6) =

= P3P4P5+ P3P6P5+ P4P5P5+P5P6P5 +

+ P3P4P6+ P3P6P6+ P4P5P6+ P5P6P6 =

= P3P4P5+ P3P6P5+ P4P5+P5P6 +

+ P3P4P6+ P3P6+ P4P5P6+ P5P6 =

= P3P6+ P4P5+P5P6

Método tabular

Listas de Cobertura (mínima): (1) P1, P2, P3, P6

(2) P1, P2, P4, P5

(3) P1, P2, P5, P6

Expresiones normalizadas de F:(1) F = w 'y z ' + x 'y 'z + w 'x y + w y z(2) F = w 'y z ' + x 'y 'z + w x 'z + x y z(3) F = w 'y z ' + x 'y 'z + x y z + w y z

Forma normalizada de producto de sumas

El proceso de simplificación se deriva de la ley de D'Morgan generalizadaSe cogen los maxterms 0Donde se ponían las variables afirmadas se ponen negadas, donde se ponían negadas se ponen afirmadasDonde se multiplicaban los literales se suman, donde se sumaban se multiplican

Forma normalizada de producto de sumas

Implicados Primos: w '+ z, w +y +z 'Implicados Primos Esenciales: w '+ z, w +y +z 'Listas de Cobertura: (1) w '+ z, w +y +z 'Expresiones normalizadas: (1) F = (w '+ z )(w +y +z ')

Traslación a la tecnología de arrays de puertas

Matrices de puertas Dispositivos programables Contienen puertas de tipo NAND o NOR de

un número máximo de entradas (m)

La traslación tecnológica (o mapeo tecnológico) es la construcción de una función empleando únicamente puertas de este tipo

Traslación a la tecnología de arrays de puertas

Se realiza con tres tareas o pasos: Mediante decomposición se sustituyen

puertas de n entradas con otras de m Se sustituye cada puerta del circuito original

con combinaciones de puertas de tipo NAND o NOR que realizan la misma función

Mediante la optimización se eliminan grupos de inversores innecesarios

Traslación a la tecnología de arrays de puertas

Reglas deconversión

Regla deoptimización

Traslación de términos estándares a esquemas con NAND y NOR

Conversión a puertas NANDRealización con puertas NAND de la función ci+1

Definición con mapa dela función c

i+1

Expresiones normalizadas dela función c

i+1

Conversión a puertas NAND

Conversión a puertas NAND

Conversión a puertas NANDRealización con puertas NAND de la función si

Definición con mapa dela función s

i

Expresiones normalizadas dela función s

i

Conversión a puertas NAND

Implementación conpuertas AND y OR

Conversión a puertas NAND

Decomposición dela puerta OR

Conversión a puertas NAND

Conversión ared con NANDs

Conversión a puertas NAND

Red con NANDsoptimizada

Retemporización del diseño

Retemporización del diseño

Retemporización del diseño

Mapeo tecnológico parabibliotecas predefinidas

Las bibliotecas contienen puertas con funcionalidad diversa y retardos diferentesEl mapeo tecnológico persigue lograr la misma funcionalidad con puertas de la bibliotecaPara optimizar el diseño Se minimiza el retardo en la ruta crítica Se reduce el coste en las rutas no críticas

Mapeo tecnológico parabibliotecas predefinidas

Implementación con ANDs y ORs.td = 7,2 ns, Coste = 28 transistores.

Mapeo tecnológico para bibliotecas predefinidas

Implementación con NANDs y NORs.td = 5,2 ns, Coste = 22 transistores.

Mapeo tecnológico para bibliotecas predefinidas

Alternativa A.td = 5,2 ns, Coste = 20 transistores.

Mapeo tecnológico para bibliotecas predefinidas

Alternativa Btd = 3,8 ns, Coste = 20 transistores.

Mapeo tecnológico para bibliotecas predefinidas

Optimización de la alternativa B.td = 3,8 ns, Coste = 18 transistores.

Diseño libre de riesgos

Los circuitos con riesgos pueden presentar malfuncionamientosLos malfuncionamientos podrían mostrarse con cambios en los valores de las salidas llamados glitchesLos glitches se deben a rutas convergentes con una fuente común y retardos distintos

Diseño libre de riesgos

Diseño librede riesgos

Diseño libre de riesgos

Diseño librede riesgos

Diseño libre de riesgos

Riesgo estático al 1 Cuando hay dos minterms 1 que difieren en

una variable y no se cubren con un término común en una implementación de suma de productos

Riesgo estático al 0 Cuando hay dos maxterms 0 que difieren en

una variable y no se cubren con un término común en una implementación de producto de sumas

Diseño libre de riesgos

El riesgo dinámico se debe a un error estático producido durante una transición en la salida

Diseño librede riesgos