Post on 13-Mar-2020
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