Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 1 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 1 Módulo 06a – Análise e Síntese de Circuitos Combinatórios Marco Túlio Carvalho de Andrade Professor Responsável Versão: 2.0 (Setembro de 2.013) PCS 2215 Sistemas Digitais I © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 2 Conteúdo Análise e Síntese de Circuitos Combinatórios 0. Notas e Definições Preliminares. 1. Formas Canônicas. 1.1 Identidades Básicas. 2. Análise de Circuitos Combinatórios 2.1 Circuitos a Portas. 3. Síntese de Circuitos Combinatórios. 3.1 Síntese por Método Algébrico. 3.2 Síntese por Mapa de Karnaugh. 2 2 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 3 Conteúdo Análise e Síntese de Circuitos Combinatórios 4. Minimização de Circuitos. 4.1 Implicantes primários. 4.1.1 Tabela de Cobertura 4.2 Minimização pelo Método Tabular 4.3 Mapas de Karnaugh Considerando-se os “Zeros” das Funções. 4.4 Funções Incompletamente Definidas 5. Exemplos de Aplicação. Bibliografia © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 4 0. Notas e Definições Preliminares Nota 1. - Uma Álgebra de Chaveamento ({F.C.}, , , ~, 0t, 1t) pode ser vista como um caso particular de uma estrutura algébrica genérica denominada Álgebra de Boole, onde o conjunto “S” gerador da estrutura é o conjunto de funções de chaveamento “{F.C.}”. 3 3 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 5 0. Notas Preliminares Nota 2. - Álgebra Booleana (ver Complementos de Álgebra Boolena) - É uma sêxtupla: (S, , , ~, fronteira inferior Máxima, Fronteira Superior mínima) Nota 3. - Outra particularização de interesse é a Álgebra Booleana constituída pelas Classes de Equivalência geradas por funções de chaveamen- to de n variáveis (x1, x2, ..., xn), onde existe uma correspondência biunívoca entre elementos de {F.C.} e de {C.E.}: ({C.E.}, , , ~, Ft, Vt) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 6 0. Notas Preliminares Nota 4. - Todo teorema de uma Álgebra Booleana vale para uma Álgebra de Chaveamento. Definição 1. - Literal - Representa uma variável ou uma variável complementada, tendo um sentido mais amplo que o de variável. 4 4 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 7 0. Notas Preliminares Definição 2. - Expressões Booleanas geradas sobre x1, x2, ..., xn são definidas recursivamente: 1-) 0, 1, x1, x2, ..., xn são expressões Booleanas. 2-) Se X1 e X2 são expressões Booleanas então, também também são expressões Booleanas: (a) (X1) (b) ~X1 (c) X1 ∨ X2 (d) X1 ∧ X2 3-) Se X é uma expressão Booleana gerada sobre os símbolos x1, x2, ..., xn então podemos escrever X = X(x1, x2, ..., xn) onde cada símbolo xi (ou ~xi) é chamado de um Literal. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 8 1. Formas Canônicas Sejam, a Álgeb. de Chaveamento ({F.C.},,,~,0t,1t) e a Álgebra de Boole ({C.E.},,,~,Ft,Vt) das formas e Classes Booleanas geradas pelas variáveis x1, x2, ..., xn. Seja li uma metavariável que pode valer xi ou ~xi. Definição 1.1 - Produto Canônico (ou minter- mo) é toda Expressão de Chaveamento (ou Booleana) composta pelo Produto de todas as variáveis, complementadas ou não: n j jni llllPC 1 21 )(,.,.,. 5 5 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 9 1. Formas Canônicas Definição 1.2 - Primeira Forma Canônica é toda Expressão de Chaveamento (ou Ex- pressão Booleana) composta pela Soma de produtos canônicos, ou de mintermos, dife- rentes entre si. Teorema 1.1 - Toda Classe de Equivalência Cn pode representar-se mediante sua Primeira Forma Canônica que é única para esta Classe. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 10 Observações (I): – Como em um produto canônico intervém todas as variáveis, sua interpretação será sempre “0” a menos de uma determinada: aquela que associe “1” a todas variáveis sem “~” e “0” a todas com “~”. – Portanto cada um dos 2n produtos canôni- cos serve para representar um, e apenas um, dos 2n átomos (ou elementos atômi- cos). 1. Formas Canônicas 6 6 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 11 1. Formas Canônicas Observações (II): – Segundo Teorema da Álgebra de Chaveamento todo elemento desta Álgebra distinto de 0 pode expressar-se, de maneira única, como uma soma de átomos. Logo qualquer classe de equivalência distinta de C0 pode expressar-se de maneira única como uma soma de átomos. – Portanto pode-se representar de maneira única como uma Soma de Produtos Canônicos, isto é, representar na Primeira Forma Canônica (ou Soma Canônica). © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 12 1. Formas Canônicas Observações (III) - Existe uma notação abreviada para descrever as formas canônicas: 1-) Baseia-se em associar um número decimal a cada produto canônico; 2-) Este número é aquele que resulta ao interpretar-se como um número binário a combinação de “Zeros” e “Uns” das variáveis para a qual a interpretação do produto em questão é “1”. 3-) Por exemplo: A interpretação de ~x3.x2.x1 é “1” para x3=0, x2=1 e x1=1 e “011” em binário é “3” em decimal (“m3”). 7 7 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 13 1. Formas Canônicas Mintermos para três variáveis: x3 x2 x1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 = ~x3 ~x2 ~x1 m1 = ~x3 ~x2 x1 m2 = ~x3 x2 ~x1 m3 = ~x3 x2 x1 m4 = x3 ~x2 ~x1 m5 = x3 ~x2 x1 m6 = x3 x2 ~x1 m7 = x3 x2 x1 Mintermos © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 14 1. Formas Canônicas C0 = ~(C1 + C2 + C4 + C8) C1 = C1 C2 = C2 C3 = C1 + C2 C4 = C4 C5 = C1 + C4 C6 = C2 + C4 C7 = C1 + C2 + C4 C8 = C8 C9 = C1 + C8 C10 = C2 + C8 C11 = C1 + C2 + C8 C12 = C4 + C8 C13 = C1 + C4 + C8 C14 = C2 + C4 + C8 C15 = C1 + C2 + C4 + C8 x2 0 0 1 1 x1 0 1 0 1 C2 0 0 1 0 C0 0 0 0 0 C1 0 0 0 1 C3 0 0 1 1 C4 0 1 0 0 C5 0 1 0 1 C6 0 1 1 0 C7 0 1 1 1 C1 0 1 0 1 0 C8 1 0 0 0 C9 1 0 0 1 C11 1 0 1 1 C1 2 1 1 0 0 C1 3 1 1 0 1 C1 4 1 1 1 0 C15 1 1 1 1 m0 m1 m2 m3 8 8 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 15 1. Formas Canônicas Definição 1.3 - Soma Canônica (ou Maxtermo) é to- da Expressão de Chaveamento (ou Booleana) composta pela soma de todas as variáveis, comple- mentadas ou não: n j jni llllSC 1 21 )(... Definição1.4- Segunda Forma Canônica é toda Expressão de Chaveamento (ou Booleana) composta pelo produto de somas canônicas, ou de Maxtermos, diferentes entre si. Teorema 1.2 - Toda Classe de Equivalência Cn pode repre- sentar-se mediante sua Segunda Forma Canônica que é única para esta Classe. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 16 1. Formas Canônicas Observações: Como em uma soma canônica intervém todas as variáveis, sua interpretação será sempre “1”, a menos de uma determinada: aquela que associe “0” a todas variáveis sem “~” e “1” a todas com “~”. Em resumo: Qualquer classe de equivalência pode também ser expressa de maneira única como um Produto de Somas Canônicas, isto é, pode ser representada na Segunda Forma Canônica. (ou “Produto Canônico”). 9 9 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 17 1. Formas Canônicas Observações (II) - Existe uma notação abreviada para descrever a segunda Forma Canônica: 1-) Baseia-se em associar um número decimal a cada soma canônica. 2-) Este número é aquele que resulta ao interpretar-se como um número binário a combinação de “Zeros” e “Uns” das variáveis para a qual a interpretação da soma em questão é “0”. 3-) Por exemplo: A interpretação de x3+~x2+~x1 é “0” para x3=0, x2=1 e x1=1 e “011” em binário é “3” em decimal (“M3”). © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 18 1. Formas Canônicas Maxtermos para três variáveis: x3 x2 x1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M0 = x3 + x2 + x1 M1 = x3 + x2 + ~x1 M2 = x3 + ~x2 + x1 M3 = x3 + ~x2 + ~x1 M4 = ~x3 + x2 + x1 M5 = ~x3 + x2 + ~x1 M6 = ~x3 + ~x2 + x1 M7 = ~x3 + ~x2 + ~x1 Maxtermos 10 10 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 19 1. Formas Canônicas C0 = C7 . C11 . C13 . C14 C1 = C7 . C11 . C13 C2 = C7 . C11 . C14 C3 = C7 . C11 C4 = C7 . C13 . C14 C5 = C7 . C13 C6 = C7 . C14 C7 = C7 C8 = C11 . C13 . C14 C9 = C11 . C13 C10 = C11 . C14 C11 = C11 C12 = C13 . C14 C13 = C13 C14 = C14 C15 = ~(C7 . C11 . C13 . C14) x2 0 0 1 1 x1 0 1 0 1 C2 0 0 1 0 C0 0 0 0 0 C1 0 0 0 1 C3 0 0 1 1 C4 0 1 0 0 C5 0 1 0 1 C6 0 1 1 0 C7 0 1 1 1 C1 0 1 0 1 0 C8 1 0 0 0 C9 1 0 0 1 C11 1 0 1 1 C1 2 1 1 0 0 C1 3 1 1 0 1 C1 4 1 1 1 0 C15 1 1 1 1 M0 M1 M2 M3 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 20 1. Formas Canônicas Mintermos e Maxtermos para três variáveis: x3 x2 x1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 = ~x3 ~x2 ~x1 = ~M0 m1 = ~x3 ~x2 x1 = ~M1 m2 = ~x3 x2 ~x1 = ~M2 m3 = ~x3 x2 x1 = ~M3 m4 = x3 ~x2 ~x1 = ~M4 m5 = x3 ~x2 x1 = ~M5 m6 = x3 x2 ~x1 = ~M6 m7 = x3 x2 x1 = ~M7 M0 = x3 + x2 + x1 = ~m0 M1 = x3 + x2 + ~x1 = ~m1 M2 = x3 + ~x2 + x1 = ~m2 M3 = x3 + ~x2 + ~x1 = ~m3 M4 = ~x3 + x2 + x1 = ~m4 M5 = ~x3 + x2 + ~x1 = ~m5 M6 = ~x3 + ~x2 + x1 = ~m6 M7 = ~x3 + ~x2 + ~x1 = ~m7 Mintermos Maxtermos 11 11 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 21 1. Formas Canônicas Observações adicionais: A Álgebra de Chavea- mento ({F.C.}, , , ~, 0t, 1t) tem o mesmo número de Funções de Chaveamento que o de classes de equivalência da Álgebra Booleana ({C.E.}, , , ~, Ft, Vt), que é: – {F.C.} tem um número de “n-tuplas” diferentes em {0,1}n igual a k = 2n e gera 2k combinações distintas para aplicar cada uma destas k “n-tuplas” em {0,1}. 2 2 n =k © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 22 1. Formas Canônicas Observações adicionais: – {C.E.} tem um número de k = 2n produtos canônicos com os quais pode-se escrever as 2k primeiras formas canônicas diferentes. – Pela definição 4.3 do material adicional de Álgebra Booleana, elas são isomorfas. – Sendo isomorfas existe uma correspondên- cia biunívoca entre cada Função de Chavea- mento de ordem “n” e cada classe de equi- valência de Expressões Booleanas de “n” variáveis. 12 12 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 23 1. Formas Canônicas Observações (continuação): A correspondência é tal que se fi e fk estão em correspondência com Ci e Ck então (fi+fk) e (fi.fk) estarão em correspondência com (Ci+Ck) e (Ci.Ck). Importância na aplicação ao projeto de circuitos lógicos: – A saída de um circuito expressa como uma Função de Chaveamento tem infinitas formas associadas a uma classe de equivalência. – Como Engenheiros nos interessa encontrar a forma mínima! © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 24 1.1. Identidades Básicas A seguir são apresentadas identidades básicas para duas ou três variáveis: I1 - x+0=x x.1=x [Elemento neutro ou identidade] I2 - x+1=1 x.0=0 [Elementos máximo/mínimo ou elemento nulo] I3 - x+~x=1 x.~x=0 [Complemento] I4 - ~(~x) = x [Involução] 13 13 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 25 1.1. Identidades Básicas Mais identidades: I5 - x + x = x x . x = x [Idempotência] I6 - x+y=y+x x.y=y.x [Comutativa] I7 - x+(y+z)=(x+y)+z x.(y.z)=(x.y).z [Associativa] I8 - x.(y+z)=x.y+x.z x+(y.z)=(x+y).(x+z) [Distributiva] I9 - x+x.y=x [I9a] x.(x+y)=x [I9b] [Absorção ou cobertura] © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 26 1.1. Identidades Básicas Mais identidades: I10 - ~(x+y)=~x.~y ~(x.y)=~x+~y [De Morgan] I11a-(x+y).(~x+z).(y+z)=(x+y).(~x+z)=x.z+~x.y I11b - x.y+~x.z+y.z=x.y+~x.z [Consenso] I12 - x . y + x . ~y = x (x + y) . (x + ~y) = x [Combinação] I13 - (x+y).(~x+z)= x.z+~x.y I14 - (x+~x.y)=(x+y) x.(~x+y)=x.y 14 14 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 27 1.1. Identidades Básicas Exemplo 1.1: Simplificar (x+y+z).(x.~y+y.z+x.~z) = = x.x.~y+x.y.z+x.x.~z+x.y.~y+y.y.z+x.y.~z+x.~y.z+y.z.z+x.z.~z= = x.~y + x.y.z + x.~z + x.0 + y.z + x.y.~z + x.~y.z + y.z + x.0 = = x.(~y + y.z) + x.~z + x.y.~z + y.z + x.~y.z + y.z = = x.(~y + z) + x.~z(1 + y) + z.(y + x.~y) + y.z = = x.~y + x.z + x.~z + z.(y + x) + y.z = = x.~y + x.z + x.~z + y.z + x.z + y.z = = x.~y + x.z + x.z + x.~z + y.z + y.z = = x.~y + x.(z + ~z) + y.z = = x.~y + x.1 + y.z = = x.~y + x + y.z = = x + y.z © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 28 1.1. Identidades Básicas Exemplo 1.2: Calcular (desenvolver) f = ~(x.y+~y.z+x.~z) Exemplo 1.3: Verificar que a expressão (~y + w.x.z + ~x.z + ~w.x) . (y + w.x + x.z) é idêntica à expressão x . (w + y) . (~w + ~y) + z . (x + y) Exemplo 1.4: Comprovar a validade da identidade I14, [(x + ~x.y) = (x+y)],por Diagrama de Venn. 15 15 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 29 1.1. Identidades Básicas Exemplo 1.4: Comprovar a validade da identidade I14, [(x + ~x.y) = (x+y)], por Diagrama de Venn. ~x y ~x . y x x + ~x . y x + y © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 30 1.1. Identidades Básicas Maxtermos/mintermos permitem a decomposição sistemática de Expressões de Chaveamento em subexpressões com subconjuntos das variáveis. Teorema da Expansão de Shannon: Qualquer Expressão de Chaveamento do tipo fn(x1, x2, x3, ..., xn) pode ser decomposta na Expressão [I15a] x1 . fn(1, x2, x3, ..., xn) + ~ x1 . fn(0, x2, x3, ..., xn) ou decomposta em sua Expressão dual [I15b] [x1+fn(0, x2, x3, ..., xn)] . [ ~ x1+fn(1, x2, x3, ..., xn)] 16 16 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 31 1.1. Identidades Básicas Exemplo da aplicação de [I15a]: f3(x1, x2, x3) = x1.f3(1, x2, x3) + ~ x1.f3(0, x2, x3) f3(x1, x2, x3) = x1.x2.f3(1,1, x3) + x1.~x2.f3(1,0, x3) + ~x1.x2.f3(0,1, x3) + ~ x1.~x2.f3(0,0, x3) f3(x1, x2, x3)= x1.x2.x3.f3(1,1,1) + x1.x2.~x3.f3(1,1,0) + x1.~x2.x3.f3(1,0,1) + x1.~x2.~x3.f3(1,0,0) + ~x1.x2.x3.f3(0,1,1) + ~x1.x2.~x3.f3(0,1,0) + ~x1.~x2.x3.f3(0,0,1) + ~x1.~x2.~x3.f3(0,0,0) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 32 1.1. Identidades Básicas Exemplo da aplicação de [I15b]: f3(x1, x2, x3)=[x1 + f3(0, x2, x3)].[~ x1 + f3(1, x2, x3)] f3(x1, x2, x3)=[x1+x2+f3(0,0, x3)].[x1+~x2+f3(0,1, x3)] .[~x1+x2+f3(1,0, x3)].[~ x1+~x2+f3(1,1, x3)] f3(x1,x2, x3)=[x1+x2+x3+f3(0,0,0)].[x1+x2+~x3+f3(0,0,1)] . [x1+~x2+x3+f3(0,1,0)] . [x1+~x2+~x3+f3(0,1,1)] . [~x1+x2+x3+f3(1,0,0)] . [~x1+x2+~x3+f3(1,0,1)] . [~x1+~x2+x3+f3(1,1,0)] . [~x1+~x2+~x3+f3(1,1,1)] 17 17 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 33 1.1. Identidades Básicas Mais Identidades: (fn DUAL)DUAL = fn [I16] [fn = gn] [fn DUAL = gn DUAL] [I17] fDUAL(x1, x2, ..., xn) = ~f(~x1, ~x2, ..., ~xn) [I18a] fDUAL(x, y, ..., z) = ~f(~x, ~y, ..., ~z) [I18b] Exemplo: Dado fn = x.y + ~y.z fn DUAL = (x+y) . (~y+z) ~fn=~(x.y+~y.z)=~(x.y).~(~y.z)= (~x+~y) . (y+~z) Portanto: fn DUAL(x,y,z) = ~fn(~x,~y,~z) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 34 2. Análise de Circuitos Combinatórios Um Circuito Combinatório (ou circuito sem me- mória) pode ser visto como um dispositivo lógi- co cuja saída (isto é, o efeito da operação lógica que ele realiza) depende apenas das entradas no instante presente (isto é, das causas lógicas). Em vista disto pode-se representar a saída de um circuito combinatório por uma função do tipo fn(x1, x2, ..., xn), sendo (x1, x2, ..., xn) as entradas lógicas. Ou ainda, por uma função do tipo fn(x, y, ..., z), sendo (x, y, ..., z) as entradas lógicas. 18 18 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 35 2. Análise de Circuitos Combinatórios A forma de análise de um Circuito Combinatório depende do modelo utilizado para especificá-lo: Diagrama Lógico Expressão de Chaveamento Estrutura exposta; comportamento escondido (este pode ser extraído) Comportamento exposto; Estrutura escondida (representa infinitas estruturas) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 36 2. Análise de Circuitos Combinatórios Tipicamente extrai-se a Expressão de Chaveamen- to do Diagrama Lógico, quando então constrói- se a Tabela da Verdade. Diagrama Lógico Identificação exata das opera- ções algébricas envolvidas: - Modelo funcional - Interpretação de Engenharia Expressão de Chaveamento Tabela da Verdade 19 19 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 37 2. Análise de Circuitos Combinatórios Ao analisar um circuito combinatório pode-se utilizar um de três procedimentos básicos: 1-) Enumeração de todos os caminhos de propaga- ção dos sinais de entrada - Levantam-se os cami- nhos possíveis das entradas para as saídas. 2-) Aplicação da Identidade de Shanonn (I15) - Fi- xam-se os valores lógicos de uma dada variável xi gerando-se dois subcircuitos de n-1 variáveis. 3-) Decomposição - Divide-se o circuito em blocos e faz-se a análise no nível de blocos elementares. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 38 2. Análise de Circuitos Combinatórios Exemplo 2.1.1 - 1) Enumeração dos caminhos dos sinais de entrada: x1 x2 ~x1 ~x2 ~x1.~x2 x1.x2 x1.x2 + ~x1.~x2 20 20 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 39 Exemplo 2.1.2-2) Aplicação da identidade de Shanonn (I15): f2(x1, x2) = x1 . f2(1, x2) + ~x1 . f2(0, x2) 2. Análise de Circuitos Combinatórios [a] x1 = 0 ~x1 = 1 I15a [b] x1 . f(1, x2) + ~x1 . f(0, x2) [c] f(1, x2) = x2 e [d] f(0, x2) = ~x2 x1 x2 0 x2 1 ~x2 0 ~x2 ~x2 x1 x2 1 x2 0 ~x2 x2 0 x2 Expressão final [e]: x1 . x2 + ~x1 . ~x2 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 40 2. Análise de Circuitos Combinatórios Exemplo 2.1.3 - 3) Decomposição em blocos elementares: x1 x2 ~x1 ~x2 x1 x2 x1.x2 + ~x1.~x2 ~x1.~x2 x1.x2 ~x1.~x2 x1.x2 ~x1 ~x2 21 21 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 41 2.1. Circuitos a Portas Definição 2.1.1 - Portas Lógicas: – Uma porta lógica é uma função de em . – A porta AND (E) é a função de em . – A porta OR (OU) é a função de em . – A porta NOT (NÃO) é a função ~ de em . Definição 2.1.2 - O conjunto {p1, p2, ..., pn} de por- tas é denominado funcionalmente completo se, dado qualquer inteiro positivo n e uma função f de em , é possível construir um circuito combinatório que compute a função f utilizando apenas {p1, p2, ..., pn}. nZ2 2Z nZ2 2 Z nZ2 2 Z 2Z 2Z nZ2 2Z © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 42 2.1. Circuitos a Portas Exemplo 2.1.4 - Os teoremas que atestam que toda classe de equivalência pode ser gerada a partir da primeira e da segunda formas canônicas (1.1 e 1.2) permitem mostrar que o conjunto de portas {AND, OR, NOT} é funcionalmente completo. Definição 2.1.3 - Portas lógicas NAND e NOR. Teorema 2.1.1 - Os conjuntos de portas {AND, NOT}={NAND} e {OR, NOT}={NOR} são funcionalmente completos. NAND NOR 22 22 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 43 2.1. Circuitos a Portas - Análise Quando o circuito aparece determinado por meio de um diagrama de portas lógicas a maneira mais eficiente de análise é a decomposição em funções intermediárias, da saída para a entrada, ou a composição de funções, da entrada para a saída. x1 x2 x3 f3 f1 f2 x4 x5 f © Andrade,Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 44 2.1. Circuitos a Portas - Análise As entradas do circuito anterior são (x1, x2, x3, x4, x5) e sua saída é o valor lógico f(x1, x2, x3, x4, x5). Da saída para a entrada tem-se: f(x1, x2, x3, x4, x5) = f1(x1, x2) + f2(x3, x4, x5) = f(x1, x2, x3, x4, x5) = x1. x2 + x3 . f3(x4, x5) = f(x1, x2, x3, x4, x5) = x1. x2 + x3 . (x4 + x5) = f(x1, x2, x3, x4, x5) = x1. x2 + x3 . x4 + x3 . x5 x1 x2 x3 f3 f1 f2 x4 x5 f Exemplo 2.1.5 23 23 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 45 2.1. Circuitos a Portas - Análise Exemplo 2.1.6 - Análise de circuitos E-OU (OU-E) a dois níveis: x1 x2 x3 f1 f2 f3 f x4 x5 x6 x1 x2 x3 f1 f2 f3 f x4 x5 x6 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 46 2.1. Circuitos a Portas - Análise Exemplo 2.1.7 - Análise de circuitos XOR: x1 x2 f1 x3 fx4 x5 f2 f3 Verifica-se a associatividade da operação, de modo que f poderia ser representada por: f x1 x3 x2 x5 x4 24 24 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 47 2.1. Circuitos a Portas - Análise Exemplo 2.1.8 - Análise de circuitos NAND: x1 x2 f1 x3 fx4 x5 f2 f3 x1 x2 f1 x3 fx4 x5 f2 f3 Exemplo 2.1.9 - Análise de circuitos NOR: © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 48 3. Síntese de Circuitos Combinatórios Síntese Diagrama Lógico Expressão Algébrica Tabela da Verdade Inter- pretação Análise 25 25 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 49 3. Síntese de Circuitos Combinatórios Terminologia: Engenheiro de Computação - No exercício da profissão: »Envolvimento na realização de Projeto de Sistemas Digitais. Projeto de Sistemas Digitais - Fases: »Especificação: requisitos, escopo. »Modelo: técnicas, métodos de implementação. »Implementação: simulação, laboratório. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 50 3. Síntese de Circuitos Combinatórios Projeto de Sistemas Digitais - Necessidade de representação: – Linguagem. – Diagramas. Álgebra Booleana e Álgebra de Chaveamento - Aparecem como ferramenta aderente ao encaminhamento da solução desta classe de problemas. Projeto de Sistemas Digitais - Envolve a atividade do Projeto Lógico Digital. 26 26 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 51 3. Síntese de Circuitos Combinatórios Projeto Lógico Digital: – Atividade na qual o projetista de um sistema eletrônico digital cria circuitos analisando um problema e elaborando sua solução no nível conceitual dos Circuitos Lógicos. Circuitos Lógicos - – Circuitos que existem apenas como Abstrações Matemáticas: » Independentes do mundo físico da eletrônica digital; » Constituídos de associações de Módulos Lógicos Funcionais. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 52 3. Síntese de Circuitos Combinatórios Módulos Lógicos Funcionais: – Associações de Portas Lógicas Fundamentais que realizam as Operações Lógicas Primitivas definidas na Álgebra de Chaveamento adotada. Realização de um Projeto Lógico Digital: – É o projeto de uma Máquina Abstrata, ou Equipamento Matemático, onde as primitivas (tijolos da construção) são operações matemáti- cas. – O Circuito Lógico pode ser visto como uma associação (ou rede) de operadores matemáticos. 27 27 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 53 3. Síntese de Circuitos Combinatórios Engenharia do Projeto Lógico Digital [Fregni-95]: – Muda o enfoque do projeto - Parte do princípio de que a Finalidade de todo Circuito Lógico é ser Materializado em um Circuito Físico. – Define: Módulos Matemáticos a serem utilizados. – Estabelece Técnicas e Métodos de implementação. – Define as Características Físicas do circuito final. – Projetista usa a Intuição - A ação do Projetista deixa de ser exclusivamente mecanizada ou formal e este usa sua experiência como ferramenta. – Projetar passa a ser uma Arte, com método científico! © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 54 3. Síntese de Circuitos Combinatórios Objetivo: Obter a solução mais econômica! Solução mais econômica - Difícil de ser definida com precisão. Critérios possíveis: – Minimização do número de literais da função de chaveamento. – Minimização do número de interconexões entre as portas. – Minimização do número de pinos do circuito integrado a ser eventualmente construído. 28 28 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 55 3.1. Síntese por Método Algébrico O Teorema da Expansão de Shannon [I15] mostrou que pode-se decompor uma Expressão de Chavea- mento fn(x1, x2, x3, ..., xn) em duas formas canôni- cas: Soma de Produtos [“SP” - I15a] e Produto de Somas [“PS” - I15b]. Ex. 3.1. f = x1.x2 + ~x2.x3 pode ser representada por: f = x1.x2 .~x3 + x1.x2.x3 + x1.~x2.x3 + ~x1.~x2.x3 (SP) ou por f=(x1+x2 +x3).(x1+~x2+x3).(x1+~x2+~x3).(~x1+x2+x3) (PS) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 56 3.1. Síntese por Método Algébrico Usando a definição de mintermos e maxtermos: f = x1.x2 .~x3 + x1.x2.x3 + x1.~x2.x3 + ~x1.~x2.x3 (SP) f = m3 + m7 + m5 + m4 (SP) f = . ou f=(x1+x2 +x3).(x1+~x2+x3).(x1+~x2+~x3).(~x1+x2+x3) (PS) f= M0 . M2 . M6 . M1 (PS) f = . )7,5,4,3(m )6,2,1,0(M 29 29 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 57 3.1. Síntese por Método Algébrico Teorema 3.1.1 - Uma Expressão de Chaveamento do tipo fn(x1, x2, x3, ..., xn) pode ser expressa de maneira única como uma soma de mintermos ou um produto de maxtermos. Teorema 3.1.2 - Se a Expressão de Chaveamento fn(x1, x2, x3, ..., xn) é expressa como uma soma de p mintermos então ela também é expressa co- mo um produto de (2n - p) maxtermos. , onde: i j. )2( pn j p in Mmf © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 58 3.1. Síntese por Método Algébrico Síntese por Método Algébrico – Seja um sistema e uma especificação deste: – O processo de síntese consiste na obtenção de uma Expressão de Chaveamento do tipo fn(x1, x2, x3, ..., xn), que represente o comportamento do sistema em questão. A especificação pode vir: – Por meio de linguagem natural (uma descrição de seu comportamento lógico, por exemplo). – Tabela da verdade. 30 30 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 59 3.1. Síntese por Método Algébrico Exemplo3.1.1 - Sintetizar um circuito de chaveamento para detectar os códigos BCD correspondentes aos números ímpares. x1 x3 x2 x4 Detector y © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 60 3.1. Síntese por Método Algébrico x4 x3 x2 x1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 ~x4 . ~x3 . ~x2 . x1 y 0 0 0 0 0 1 1 1 1 1 ~x4 . ~x3 . x2 . x1 ~x4 . x3 . ~x2 . x1 ~x4 . x3 . x2 . x1 x4 . ~x3 . ~x2 . x1 Soma Produtos Produto Somas x4 + x3 + x2 + x1 x4 + x3 + ~x2 + x1 x4 + ~x3 + x2 + x1 x4 + ~x3 + ~x2 + x1 ~x4 + x3 + x2 + x1 Exemplo 3.1.1 31 31 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 61 3.1. Síntese por Método Algébrico Exemplo 3.1.1 - Soma de Produtos: y = ~x4.~x3.~x2.x1 + ~x4.~x3.x2.x1+~x4.x3.~x2.x1+~x4.x3.x2.x1+x4.~x3.~x2.x1 y x1 x2x3x4 x1 x2x3x4 x1 x2x3x4 x1 x2x3x4 x1 x2x3x4 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 62 3.1. Síntese por Método Algébrico Ex3.1.1-Produto de Somas: y=(x4+x3+x2+x1).(x4+x3+~x2+x1) .(x4+~x3+x2+x1).(x4+~x3+~x2+x1).(~x4+x3+x2+x1) y x1 x2x3x4 x1 x2x3x4 x1 x2x3x4 x1 x2x3x4 x1 x2x3x4 32 32 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 63 3.2. Síntese por Mapa de Karnaugh Um Mapa de Karnaugh pode ser considerado como uma representação modificada de uma Tabela da Verdade, em n dimensões. Consegue-se visualizar propriedades explícitas por meio de padrões e/ou estruturas que permitem simplificações nas fun- ções de chaveamento, com complexidade de repre- sentação proporcional ao número de variáveis. Célula - É um mintermo ou um Maxtermo. Células Adjacentes - Duas células são adjacentes quan- do diferem apenas no valor de uma variável. Adjacências - Grupamentos (retangulares ou quadrados) de 2n células adjacentes. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 64 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh - Obtenção e interpretação para duas variáveis: ~x2 ~x1 (0) (2) (1) (3) x2 x1 ~x2 ~x1 x2 x1 ~x2 x2Conjunto Universal f=~x2.~x1 x2 0 1x1 0 1 1 f=x2.~x1 x2 0 1x1 0 1 1 f=~x2.x1 x2 0 1x1 0 1 1 f=x2.x1 x2 0 1x1 0 1 1 Mintermos 33 33 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 65 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh - Interpretação das Leis de De Morgan para duas variáveis: f=x2.x1 x2 0 1x1 0 1 x2 0 1x1 0 1 1 x2 0 1x1 0 1 11 1 f = ~(x2 . x1) = ~x2 + ~x1 = ~x2 + ~x1 1 1 1 x2 0 1x1 0 1 1 1 x2 0 1x1 0 1 11 f=x2+x1 x2 0 1x1 0 1 x2 0 1x1 0 1 x2 0 1x1 0 11 f= ~(x2 + x1) = ~x2 . ~x1 = ~x2 . ~x1 1 1 x2 0 1x1 0 1 1 1 x2 0 1x1 0 1 111 1 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 66 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh - Representação de alguns Conectivos Lógicos para duas variáveis: x2 x2 0 1x1 0 1 1 1 1 1 Conjunto Universal f=x2ORx1 0 1x1 0 1 1 f=x2XORx1 0 1 1 f=x2ANDx1 0 1 111 1 0 1 1 1 1 1 Conjunto Universal f=x2NORx1 0 1 f=x2NXORx1 0 1 1 f=x2NANDx1 0 1 11 1 1 1 x2 x1 0 1 x2 x1 0 1 x2 x1 0 1 x2 x1 0 1 x2 x1 0 1 x2 x1 0 1 34 34 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 67 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh - Representação: x1 0 1 (0) (1) Uma variável x2 0 1x1 0 1 (0) (2) (1) (3) Duas variáveis x3x2 00 01 11 10x1 0 1 (0) (2) (6) (4) (1) (3) (7) (5) Três variáveis © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 68 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh - Representação: Três variáveis: x3,x2,x1 x3x2 00 01 11 10x1 0 1 (0) (2) (6) (4) (1) (3) (7) (5) ~x1 x1 x3~x2x3x2~x3x2~x3~x2 x3~x2x3x2 ~x3x2 ~x3~x2~x1 x1 35 35 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 69 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh - Representação: x4x3 00 01 11 10x2x1 00 01 11 10 (0) (4) (12) (8) (1) (5) (9)(13) (3) (7) (15) (2) (6) (14) (11) (10) Quatro variáveis x4x3 00 01 11 10x2x1 00 01 11 10 x4x3 00 01 11 10 x2x1 00 01 11 10 (0) (4) (12) (8) (1) (5) (9)(13) (3) (7) (15) (2) (6) (14) (11) (10) (16) (20) (28) (24) (17) (21) (25)(29) (19) (23) (31) (18) (22) (30) (27) (26) x5 = 0 x5 = 1 Cinco variáveis © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 70 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh - Representação: Quatro variáveis x4x3 00 01 11 10x2x1 00 01 11 10 (0) (4) (12) (8) (1) (5) (9)(13) (3) (7) (15) (2) (6) (14) (11) (10) 00 01 11 10 00 01 11 10 (0) (4) (12) (8) (1) (5) (9)(13) (3) (7) (15) (2) (6) (14) (11) (10) x3 x4 x1 x2 36 36 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 71 3.2. Síntese por Mapa de Karnaugh Mapa de Karnaugh para Seis Variáveis: x4x3 00 01 11 10x2x1 00 01 11 10 x4x3 00 01 11 10 x2x1 00 01 11 10 (0) (4) (12) (8) (1) (5) (9)(13) (3) (7) (15) (2) (6) (14) (11) (10) (16) (20) (28) (24) (17) (21) (25)(29) (19) (23) (31) (18) (22) (30) (27) (26) x5 = 0 x5 = 1 x4x3 00 01 11 10 00 01 11 10 x2x1 x4x3 00 01 11 10 00 01 11 10 x2x1 (32) (36) (44) (40) (33) (37) (41)(45) (35) (39)(47) (34) (38) (46) (43) (42) x6 = 0 x6 = 1 x6 = 0 x6 = 1 x5 = 0 x5 = 1 (48) (52) (60) (56) (49) (57) (51) (55) (63) (50) (54) (62) (59) (58) (53) (61) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 72 Exercício 3.2.1 - Determinar o menor conjunto de adja- cências que cubra (ou contenha) todos os mintermos das funções de três variáveis dadas: 3.2. Síntese por Mapa de Karnaugh x3x2 00 01 11 10x1 0 1 1 1 1 1 0 0 0 0 x3x2 00 01 11 10x1 0 1 1 10 1 1 1 00 x3x2 00 01 11 10x1 0 1 1 10 0 1 10 0 37 37 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 73 3.2. Síntese por Mapa de Karnaugh Exercício 3.2.2 - Determinar o menor conjunto de adja- cências que cubra (ou contenha) todos os mintermos das funções de quatro variáveis dadas: x4x3 00 01 11 10x2x1 00 01 11 10 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x4x3 00 01 11 10x2x1 00 01 11 10 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 © Andrade, Corrêa, Gomie Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 74 3.2. Síntese por Mapa de Karnaugh Cubo-r (“cubo de ordem r” ou “cubo erre”) - É o elemento básico em um Mapa de Karnaugh. Sua definição pode ser gerada de maneira indutiva: Cubo-0: Em um Mapa de Karnaugh de n variáveis, uma entrada qualquer com “1” (isto é, uma célula ou um mintermo) é um Cubo-0. Cubo-1: Em um Mapa de Karnaugh de n variáveis sejam dois Cubos-0 que diferem apenas no valor de uma variável (Cubos-0 adjacentes). As n-1 va- riáveis em que dois Cubos-0 adjacentes são con- cordantes definem um Cubo-1. 38 38 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 75 3.2. Síntese por Mapa de Karnaugh Cubo-r - Analogia com representações geométricas de variáveis contínuas: x10 1 x = 2,37 0 1 2 3x1 (2,37 ; 1,2) 0 1 2 3x1 x2 1 2 x1 (0,0) (0,1) (1,0) (1,1) x2 (x2,x1)Duas variáveis Uma variável © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 76 3.2. Síntese por Mapa de Karnaugh Cubo-r (r 1): Em um Mapa de Karnaugh de n variáveis sejam dois Cubos-(r-1) diferindo exa- tamente no valor de uma variável (denominados Cubos-(r-1) adjacentes). As n-r variáveis em que dois Cubos adjacentes são concordantes definem um Cubo-r. Cubo-r - Analogia com representações geométri- cas de variáveis contínuas. Exemplo com a função: )7,6,3,2,0(),,( 321 p in mxxxf 39 39 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 77 3.2. Síntese por Mapa de Karnaugh x1(0,0,0) x2 (0,0,1) (1,1,0) (1,1,1) x3 (0,1,0) (0,1,1) (1,0,0) (1,0,1) m0 m1 m2 m3 m7m6 m5 m4 (x3,x2,x1) Cubos-0 possíveis para uma função de três variáveis Três variáveis (2,37;1,2;2) 0 1 2 3x1 x2 11 2 2 x3 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 78 3.2. Síntese por Mapa de Karnaugh Exemplo: Cubos-0 da função de três variáveis. Exemplo: Cubos-1 da função de três variáveis. (1,1,1)m7 (0,0,0) (0,1,1)(0,1,0) m0 m2 m3 (x3,x2,x1) (1,1,0)m6 0,0,0 0,1,1 1,1,1 0,1,0 0,X,0 0, 1,X X, 1,1 (x3,x2,x1) 1,1,0 X,1,0 1,1,X 40 40 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 79 3.2. Síntese por Mapa de Karnaugh Exemplo: Cubo-2 da função de três variáveis. Cubo-2 213321 ~~),,( xxxxxxfn 0,X,0 0, 1,X X, 1,1 (x3,x2,x1) X,1,0 1,1,X Cubo-1 )7,6,3,2,0(),,( 321 p in mxxxf © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 80 4. Minimização de Circuitos No momento de simplificar-se um circuito é conve- niente determinar uma topologia (ou formato) de circuito antes de definir-se o critério para o signi- ficado de mais simples possível. Vejamos as im- plementações de três formas distintas da seguinte função: )14,13,10,9,6,5( p in mf 123123124124 ~~~~ xxxxxxxxxxxxfn )~~)(( 121234 xxxxxxfn 41 41 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 81 4. Minimização de Circuitos Qual é a forma mais simples (I)? fn x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 m5 m6 m9 m10 m13 m14 (I) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 82 4. Minimização de Circuitos Qual é a forma mais simples (II e III)? fn (II) (III) fn x4 x3 x2 x1 x2 x1 x1x2x4 x1x2x4 x1x2x3 x1x2x3 42 42 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 83 4.1. Implicantes Primários Implicante Primário: Um Cubo é um IP – implicante primário – se ele não estiver incluído em nenhum outro Cubo de ordem superior. Uma função de chaveamento pode ser representada por uma soma de todos os seus implicantes primá- rios. Esta representação especial em Soma de Pro- dutos é denominada Soma Completa. Tal representação não é necessariamente a função de chaveamento minimizada, porém é um passo importante para a minimização. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 84 4.1. Implicantes Primários Implicante Primário Essencial: Seja Ipj um implicante primário e seja fn uma função expressa na forma da soma de todos os seus Ipi. Ipj é um Implicante Primário Essencial (IPE) se Ipj contiver um cubo qualquer não contido na somatória dos Ipi. Os IPEs deverão estar presentes em uma realização mínima para fn. Se estes IPEs cubrirem fn total- mente então o problema de minimização está con- cluído. 43 43 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 85 4.1.1. Tabela de Cobertura Tabela de Cobertura: Se ocorrer o caso de que os IPE’s não cubram fn totalmen- te, então deve-se usar algum procedi- mento que permita descobrir os IP’s (dentre os não essenciais), que façam parte da expressão mínima: Expressão Mínima = = IPE1 + IPE2 + … + IPEn + [(Demais Implicantes)] Um destes procedimentos denomina-se Tabela de Cobertura. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 86 4.1.1. Tabela de Cobertura Considere-se o exemplo de uma função definida por seu Mapa de Karnaugh, onde o custo (k) é igual ao número de Literais do IP. Para descobrir os demais implicantes realiza-se um processo de redução da Tabela de Cobertura: 1-) Por meio da eliminação das células já cobertas por IPE’s; 2-) Encontrando-se implicantes de menor custo (k) possível e que cobrem o maior número de células. Diz-se que estes implicantes dominam os demais. 44 44 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 87 4.1.1. Tabela de Cobertura Exemplo – Função dada por seu Mapa de Karnaugh: IPE’s: IPE1 = ~x4.x1 IPE2 = x4.~x3.~x1 x 4 x 3 00 01 11 10x2 x 1 00 01 11 10 1 0 1 1 0 1 0 1 0 0 1 1 0 0 11 IPE1 IPE2 *: Células não cobertas por nenhum outro cubo que seja o maior possível. x 4 x 3 00 01 11 10x2 x 1 00 01 11 10 1 0 1* 1 0 1* 0 1 0 0 1 1* 0 0 11 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 88 4.1.1. Tabela de Cobertura Todos os IP’s: IPE’s: IP1 = IPE1 = ~x4.x1 IP2 = IPE2 = x4.~x3.~x1 Demais IP’s: IP3 = ~x4.~x3.~x2 IP4 = ~x3.~x2.~x1 IP5 = x3.~x2.x1 IP6 = x4.x3.~x2 IP7 = x4.~x2.~x1 IP1=IPE1 IP2=IPE2 x 4 x 3 00 01 11 10x2 x 1 00 01 11 10 1 0 1* 1 0 1* 0 1 0 0 1 1* 0 0 11 IP7 IP3 IP6 IP4 IP5 45 45 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 89 4.1.1. Tabela de Cobertura Tabela de Cobertura- Para aplicação do processo de redução: Obs: Lembrar que o custo (k) é igual ao número de Literais do Implicante. IP1=IPE1 IP2=IPE2 IP7 IP3 IP6 IP4 IP5 0Implicantes X 1 3 5 7 8 Custo(k)1012 13 X X X 2 3 3 3 3 3 3 X X X X X X X X X X XX © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 90 4.1.1. Tabela de Cobertura Tabela de Cobertura - Após processo de redução: fmín = IP1 + IP2 + IP3 + IP6 OU IP1 + IP2 + IP4 + IP6 (k=2+3+3+3=11) (k=2+3+3+3=11) IP7 IP3 IP6 IP4 IP5 0Implicantes Custo(k)12 13 3 3 3 3 3 X X X X X X IP6 domina IP5 e IP7 IP3 e IP4 são indiferentes (k e m0 iguais) 46 46 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 91 4.2 Minimização pelo Método Tabular Exemplo: Procedimento de extração dos Implican- tes Primários pelo método tabular. Dada a Função: )15,12,10,8,7,5,4,2,0( p in mf x4x3 00 01 11 10x2x1 00 01 11 10 1 1 1 1 1 1 1 1 1 x4x3 00 01 11 10x2x1 00 01 11 10 (0) (4) (12) (8) (1) (5) (9)(13) (3) (7) (15) (2) (6) (14) (11) (10) © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 92 4.2 Minimização pelo Método Tabular Passo 1 -Listam-se os mintermos de fn com a nota- ção Cubo-0 correspondente (Ex:m7=~x4x3x2x1). Agrupam-se os Cubos-0 de modo que: – No primeiro grupo todos possuam zero 1’s. – No segundo grupo todos possuam um 1, etc. Identificam-se pares de Cubos-0 compatíveis, isto é, que exista um Cubo-1 que os contenha. Define-se uma operação entre Cubos-0 compatíveis para gerar o Cubo-1 que os contém. Os Cubos-0 são marcados com “” e os Cubos-1 gerados colocados em outra tabela para o passo 2. 47 47 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 93 4.2 Minimização pelo Método Tabular Exemplo – Método Tabular de extração dos Implicantes Primários : Passo 1 0 0 0 0 x4 x3 x2 x1 (0) (4) (12) (8) (5) (7) (15) (2) (10) 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 94 4.2 Minimização pelo Método Tabular Passo 2 - Os Cubos-1 gerados pelo Passo 1 são agrupados, de maneira que os elementos do pri- meiro grupo possuem zero 1’s, os do segundo grupo um 1, etc. É utilizado o mesmo procedi- mento de operação entre Cubos-1 para gerar Cubos-2 para o passo 3. Passo 3 - O procedimento é análogo aos anterio- res. Como não são gerados Cubos-3 para este exemplo termina-se o algoritmo de geração de Implicantes Primários. 48 48 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 95 4.2 Minimização pelo Método Tabular Exemplo - Método Tabular de extração dos Implicantes Primários: Passo 2 0 0 - 0 x4 x3 x2 x1 (0,2) (2,10) 0 - 0 0 - 0 0 0 - 0 1 0 0 1 0 - - 1 0 0 1 0 - 0 1 - 0 0 0 1 - 1 (7,15) - 1 1 1 (0,4) (0,8) (5,7) (8,12) (4,5) (4,12) (8,10) Passo 3 - 0 - 0 x4 x3 x2 x1 (0,2,8,10) - - 0 0(0,4,8,12) f = ~x4x3~x2 + ~x4x3x1 + x3x2x1 + + ~x3~x1 + ~x2~x1 IPE1IPE2 IPE3IP4IP5 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 96 4.2 Minimização pelo Método Tabular Verificar se há necessidade dos termos (4,5) ou (5,7) dado que: – 4 (0,4,8,12) e 5 (5,7). Ou outra maneira de ver é que: – 5 (4,5) e 7 (7,15). f = ~x4x3~x2 + ~x4x3x1 + x3x2x1 + ~x3~x1 + ~x2~x1 (4,5) (5,7) (7,15) (0,2,8,10) (0,4,8,12) IPE1IPE2IPE3IP4IP5 49 49 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 97 4.2 Minimização pelo Método Tabular fmín = ~x4x3x1 + x3x2x1 + ~x3~x1 + ~x2~x1 x 4 x 3 00 01 11 10x 2 x 1 00 01 11 10 0 7 5 8 10* 4 12* 15* IPE2 (0,2*,8,10*) 2* IPE1 (0,4,8,12*) IPE3 (7,15*) IP4 (5,7) IP5 (4,5) IPE1IPE2IPE3IP4 fmín = ~x4x3~x2 + x3x2x1 + ~x3~x1 + ~x2~x1 OU IPE1IPE2IPE3IP5 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 98 4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções Até o momento identificamos Adjacências – isto é, grupamentos (retangulares ou quadra- dos) de 2n células (mintermos) adjacentes, para as quais o valor da Função é 1. Pode-se identificar outro tipo de Adjacências – isto é, grupamentos (retangulares ou qua- drados) de 2n células (Maxtermos) adjacen- tes, para as quais o valor da Função é 0. 50 50 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 99 4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções Exemplos: x4x3 00 01 11 10x2x1 00 01 11 10 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 x2 x4 f = x2 + x4 Realmente, considerando-se os uns chega-se ao mesmo valor. x4x3 00 01 11 10x2x1 00 01 11 10 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 ~x1 f = ~x1 + ~x3 ~x3 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 100 4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções Dicas: 1-) Constrói-se o Mapa de Karnaugh de ~f; 2-) Escreve-se a expressão de ~f, considerando-se os uns (mintermos); 3-) Complementa-se ~f, obtendo-se f. Na prática nem se chega a construir o Mapa de ~f, define-se o Mapa de f considerando-se os Zeros (Maxtermos); Lembrar que os Maxtermos, identificados por seus índices, estão nas mesmas posições que os mintermos. x4x3 00 01 11 10x2x1 00 01 11 10 (0) (4) (12) (8) (1) (5) (9)(13) (3) (7) (15) (2) (6) (14) (11) (10) Maxtermos M0=x4 + x3 + x2 + x1 51 51 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 101 4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções Exercício – Considerando-se os Zeros das Funções, determinar a expressão de chaveamento das seguintes funções: x4x3 00 01 11 10x2x1 00 01 11 10 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 x4x3 00 01 11 10x2x1 00 01 11 10 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 102 4.4 Funções Incompletamente Definidas Funções Incompletamente Definidas – São aquelas que, por razões diversas, tem o do- mínio de interesse de respostas menor que o conjunto de combinações de todas suas en- tradas. São funções para as quais não impor- ta (Don’t Care - X) que, para algumas com- binações de entradas, a saída possa valer 0 ou 1 (X). Pode-se tirar proveito deste grau de liberdade escolhendo-se o valor mais adequado de X para se obter a expressão mínima possível. 52 52 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 103 4.4 Funções Incompletamente Definidas Funções Incompletamente Definidas – Exemplo: Quer-se sintetizaro Circuito2 de maneira que: x1 f1 fn f2 Circuito2 x2 x3 x3 x2 )7,6,4,3,1(mf p in Observa-se que a função f1=x3.x2 já foi fornecida, e que fn=f1+f2. Por meio dos Mapas de Karnaugh faz-se a análise de quais mintermos podem ser don’t care (X). © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 104 4.4 Funções Incompletamente Definidas Pode-se ver que a função f2 deverá fornecer 1’s nas posições m1, m3 e m4, e não importa seu valor lógico (1 ou 0) nas posições m6 e m7 (onde foi anotado um X). Procura-se a melhor distribuição de 0’s e 1’s para os X’s, de maneira que se obtenha a menor expressão de chaveamento. + x1 0 1x3x2 00 01 11 10 (0) (1) (2) (3) (6) (7) (4) (5) x1 0 1x3x2 00 01 11 10 1 1 1 1 1 = x1 0 1x3x2 00 01 11 10 1 1 x1 0 1x3x2 00 01 11 10 1 1 X X 1 )]}7,6(X)4,3,1(m[f{)}7,6(mf{)7,6,4,3,1(mf p i p i2 p i1 p in fn f1 f2 53 53 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 105 4.4 Funções Incompletamente Definidas Para sintetizar a soma mínima é preciso: 1. Marcar os Implicantes Primários (IP’s) considerando- se as células X’s como se tivessem valor 1; 2. Eliminar os IP’s que cubram apenas células X’s e apagar os X’s do Mapa de Karnaugh; 3. Eliminar IP’s contidos em outros deixando apenas os IP’s Essenciais (IPE’s). 1 2 3x1 0 1x3x2 00 01 11 10 1 1 X X 1 x1 0 1x3x2 00 01 11 10 1 1 1 x1 0 1x3x2 00 01 11 10 1 1 1 1 x1.~x3 ~x1.x3 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 106 4.4 Funções Incompletamente Definidas Funções Incompletamente Definidas – Exemplo: Por meio da análise de quais mintermos podem ser Don’t Care (X) nos Mapas de Karnaugh e a aplicação de técnicas de minimização conhecidas (identificação do Implicantes primários Essenciais – IPE’s) pode-se sintetizar o Circuito2: x1 f1 fn f2 Circuito2 x2 x3 x3 x2 54 54 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 107 5. Exemplos de Aplicação: 5.1. Somador 1-) Análise – Fornece-se o circuito lógico e pede-se para extrair a Expressão Algébrica e a Tabela da Verdade, interpretando-se suas Funções de Engenharia. 2-) Síntese: a.) Pela Função de Engenharia – A partir da espe- cificação funcional vão sendo desenvolvidos os módulos constituintes dos sistema. b.) Por Mapa de Karnaugh – O funcionamento do circuito é especificado por uma Tabela da Verdade, da qual, por Mapa de Karnaugh, são extraídas as expressões algébricas . © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 108 5. Exemplos de Aplicação: 5.2. Half Adder Full Adder x y c s 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 s c x y “Half Adder” - Equivale a um circuito “meio-somador” de dois dígitos binários. 55 55 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 109 5. Exemplos de Aplicação: 5.2. Meio Somador - Somador Completo xi yi ci ci+1 s Meio Somador sint cint x y Meio Somador sint cint x y Somador Completo © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 110 5. Exemplos de Aplicação: 5.3. Soma de Dois Números M = x3x2x1 N = y3y2y1 Meio Somador Somador Completo x1 x2 y1 y2 x3 y3 Somador Completo s c s c s c z1 z2 z3 z4 56 56 © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 111 Bibliografia Dias, Francisco José de Oliveira; “Introdução aos circuitos de Chaveamento”; Apostila, PEL/EPUSP, 1.989. Ercegovac, Milos D.; Lang, Tomás; “Digital Systems and Hardware/Firmware Algorithms”; John Wiley, 1.985. Fernández, Gregório; Saez Vacas, Fernando; “Fundamentos de Informática”, Alianza Editorial, Colección Alianza Informática, 1.987. Fregni, Edson; Saraiva, Antônio Mauro; “Engenharia do Projeto Lógico Digital”, Editora Edgard Blucher, 1.995. Gersting, Judith L.; “Fundamentos Matemáticos Para a Ciência da Computação”, LTC - Livros Técnicos e Científicos Editora S. A., 1.995. © Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 112 Bibliografia Guerra Vieira, Antônio Hélio; Dias, Francisco José de Oliveira “Notas de Aula de PEL 213 - Circuitos de Chaveamento”, Apostila, EPUSP, 1.979. Hill, Frederic and Peterson, Gerald; “Introduction To Switching Theory and Logical Design”, John Wiley Sons, 1.974. Mendelson, Elliott; “Álgebra Booleana e Circuitos de Chaveamento”, Coleção Schaum, Editora McGraw-Hill, 1.977. Ranzini, Edith; Fregni, Edson; “Notas de Aula de PCS 214 - Teoria da Comutação: Introdução aos Circuitos Digitais”, Apostila, EPUSP, 1.996. Tremblay, J. P. and Monohar, R.; “Discrete Mathematical Structures With Applications to Computer Science”, McGraw-Hill, 1.975.
Compartilhar