Baixe o app para aproveitar ainda mais
Prévia do material em texto
Sistemas Digitais I Introduc¸a˜o Myle`ne Christine Queiroz de Farias Departamento de Engenharia Ele´trica Universidade de Bras´ılia (UnB) Bras´ılia, DF 70910-900 mylene@unb.br March 22, 2018 Aula 04: Mapas de Karnaugh Suma´rio Mapas de Karnaugh; 2 / 65 Mapas de Karnaugh Mapas de Karnaugh Forma de Tabela verdade ou uma extensa˜o do diagrama de Venn; Cada ‘quadrado’ representa um mintermo da expressa˜o booleana; Permite encontrar as redundancias das varia´veis de entrada da expressa˜o, ajudando a reduzir a expressa˜o de sa´ıda Cada mapa mostra os termos-produto (mintermos) que podem ser formados por n varia´veis, cada um em um quadrado distinto. 3 varia´veis: 8 mintermos 4 varia´veis: 16 mintermos 3 / 65 Mapas de Karnaugh 4 / 65 Mapas de Karnaugh 5 / 65 Mapas de Karnaugh Um mapa de n varia´veis tera´ 2n quadrados, cada um representado um mintermo; O mintermo em cada quadrado ou elemento do mapa e´ o produto das varia´veis listadas na linha e na coluna do elemento; O mapa e´ preenchido colocando-se 1’s nos quadrados cujos mintermos correspondentes levam a resposta a zero. 6 / 65 Mapas de Karnaugh O uso do mapa de Karnaugh e´ regido pela disposic¸a˜o de seus elementos (quadrados); Cada elemento difere do elemento adjacente por ter exatamente uma varia´vel complementar em seu mintermo; Cada expressa˜o deve ser escrita em sua forma canonica e cada termo da expresso deve conter cada uma das varia´veis de entrada. 7 / 65 Mapas de Karnaugh Exemplo: Z = A · B · C + A · B · C + A · B · C + A · B · C 8 / 65 Mapas de Karnaugh Exemplo: Z = A · B · C + A · B · C + A · B · C + A · B · C A linha BC e´ numerada de modo que somente ocorra mudana de 1 bit quando se passar de um quadrado para outro adjacente (Na˜o e´ numerada na sequencia usual, mas em relac¸a˜o a`s varia´veis. Se elementos adjacentes tiverem o valor 1: O produto dos termos correspondentes diferem em apenas uma varia´vel Os termos podem ser simplificados de modo a eliminar essa varia´vel. 9 / 65 Mapas de Karnaugh Exemplo: Z = A · B · C + A · B · C + A · B · C + A · B · C Expressa˜o Mı´nima: Z = A · B + B · C ... Pode-se incluir o terceiro c´ıculo: Z = A · B + B · C + A · C Mas, na˜o seria a expressa˜o m´ınima. Os dois c´ırculos cobrem a expressa˜o m´ınima. 10 / 65 Mapas de Karnaugh Exemplo: Z = A · B · C + A · B · C + A · B · C + A · B · C Expressa˜o Mı´nima: Z = A · B + B · C ... Pode-se incluir o terceiro c´ıculo: Z = A · B + B · C + A · C Mas, na˜o seria a expressa˜o m´ınima. Os dois c´ırculos cobrem a expressa˜o m´ınima. 10 / 65 Mapas de Karnaugh Exemplo1: F = B(A + A) 11 / 65 Mapas de Karnaugh Exemplo2: f (A,B,C ) = A · B + A · C + B · C 12 / 65 Mapas de Karnaugh Exemplo3: f (A,B,C ) = A · C + B · C + A · B = A · C + B · C 13 / 65 Mapas de Karnaugh Exemplo4: f (A,B,C ) = A · B · C + A · B · C + A · B · C + A · B · C = A · C + A · C = A 14 / 65 Mapas de Karnaugh Exemplo4: f (A,B,C ) = A · B · C + A · B · C + A · B · C + A · B · C = B · C + A · C 15 / 65 Mapas de Karnaugh 16 / 65 Mapas de Karnaugh Pode-se combinar apenas 1’s que sejam adjacentes Pode-se combinar 1’s apenas em grupos de poteˆncia de 2 (1,2,4,8 etc.) Deve-se tentar formar os maiores grupos poss´ıveis Na˜o gerar grupos ale´m do necessa´rio para cobrir todos os 1’s 17 / 65 Mapas de Karnaugh Regra para agrupamento de termos (exemplos): 18 / 65 Mapas de Karnaugh Regra para agrupamento de termos (exemplos): 19 / 65 Mapas de Karnaugh Mapas de 4 varia´veis: 20 / 65 Mapas de Karnaugh Mapas de 4 varia´veis: Exemplos 21 / 65 Mapas de Karnaugh Mapas de 4 varia´veis: Exemplos 22 / 65 Mapas de Karnaugh Mapas de 4 varia´veis: Exemplos 23 / 65 Mapas de Karnaugh Mapas de 5 varia´veis: 24 / 65 Implicantes Para um dado termo, cada aparic¸a˜o de uma varia´vel (em sua forma natural ou complementar) e´ chamada de literal: xyz – 3 literais abcd – 4 literais Qualquer ‘1’ ou grupo de ‘1’s que podem ser combinados em um mapa de Karnaugh representa um termo implicante de uma func¸a˜o. Um implicante e´ denominado implicante-primo se na˜o puder ser combinado com outro implicante para que uma varia´vel seja eliminada. 25 / 65 Implicantes Terminologia: 26 / 65 Implicantes Implicante primo: Essencial: necessa´rio para formar uma soluc¸a˜o m´ınima Na˜o-essencial: na˜o necessa´rio para formar uma soluc¸a˜o m´ınima 27 / 65 Implicantes Exemplo: 28 / 65 Implicantes Ce´lula 1 Distinta Uma ce´lula 1 distinta uma combinac¸a˜o de entrada que e´ coberta por apenas um implicante primo. Implicante Primo Essencial Um implicante primo essencial e´ um implicante primo que cobre uma (ou mais) ce´lula(s) 1 distinta(s). Como um implicante primo essencial e´ o u´nico implicante primo que cobre alguma ce´lula 1 distinta, ele deve estar inclu´ıdo na soma m´ınima (sena˜o, a soma estaria necessariamente incompleta). 29 / 65 Implicantes Ce´lula 1 Distinta Uma ce´lula 1 distinta uma combinac¸a˜o de entrada que e´ coberta por apenas um implicante primo. Implicante Primo Essencial Um implicante primo essencial e´ um implicante primo que cobre uma (ou mais) ce´lula(s) 1 distinta(s). Como um implicante primo essencial e´ o u´nico implicante primo que cobre alguma ce´lula 1 distinta, ele deve estar inclu´ıdo na soma m´ınima (sena˜o, a soma estaria necessariamente incompleta). 29 / 65 Implicantes Ce´lula 1 Distinta Uma ce´lula 1 distinta uma combinac¸a˜o de entrada que e´ coberta por apenas um implicante primo. Implicante Primo Essencial Um implicante primo essencial e´ um implicante primo que cobre uma (ou mais) ce´lula(s) 1 distinta(s). Como um implicante primo essencial e´ o u´nico implicante primo que cobre alguma ce´lula 1 distinta, ele deve estar inclu´ıdo na soma m´ınima (sena˜o, a soma estaria necessariamente incompleta). 29 / 65 Passos para Obter a Func¸a˜o M´ınima Logo, o primeiro passo na selec¸a˜o de implicantes primos e´ identificarmos as ce´lulas 1 distintas e os implicantes primos essenciais correspondentes e incluirmos esses termos na soma. Em seguida, precisamos determinar como cobrir as ce´lulas 1 que na˜o foram cobertas pelos implicantes primos essenciais (se houver). 30 / 65 Passos para Obter a Func¸a˜o M´ınima Exemplos F WX YZ 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 00 01 11 10 00 01 11 10 F = W · Y + W · X + X · Z + Y · Z Como todas as ce´lulas 1 distintas sa˜o cobertas pelos implicantes primos essenciais, essa e´ a soma m´ınima. 31 / 65 Exemplos F WX YZ 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 00 01 11 10 00 01 11 10 Uma func¸a˜o lo´gica onde nem todas as ce´lulas 1 distintas sa˜o cobertas por implicantes primos essenciais e´ mostrada ao lado. 32 / 65 Exemplos Removendo os implicantes primos essenciais: F WX YZ 1 00 01 11 10 00 01 11 10 Chegamos a apenas uma ce´lula 1 e os implicantes primos que cobrem esta ce´lula (W · Z e X · Y · Z). Neste caso, a escolha e´ simples: usamos o termo W · Z pois ele tem menos literais. 33 / 65 Exemplos Exemplos F WX YZ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 11 1 00 01 11 10 00 01 11 10 Os implicantes primos que englobam os mintermos 2 (W · Y · Z) e 9 (W · Y · Z) so implicantes primos essenciais e, portanto, devem ser inclu´ıdos na soma m´ınima. Como decidir entre os demais implicantesprimos? 34 / 65 Exemplos Exemplos F WX YZ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 00 01 11 10 00 01 11 10 Os demais implicantes primos sa˜o: W · X · Y , X · Y · Z e W · X · Z. Podemos observar que X · Y · Z eclipsa os demais implicantes primos W · X · Y e W · X · Z (i.e., ele cobre pelo todas as ce´lulas 1s cobertas por estes implicantes primos). Como X · Y · Z no custa mais do que os demais, podemos retirar os outros de considerac¸a˜o. Logo, X · Y · Z deve ser inclu´ıdo na soma m´ınima. F = W ·Y · Z + W ·Y · Z + X ·Y · Z Dizemos que X · Y · Z e´ um implicante primo essencial secunda´rio. 35 / 65 Exemplos F WX YZ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 11 00 01 11 10 00 01 11 10 Esta func¸a˜o na˜o tem nenhum implicante primo essencial! Como proceder nesses casos? 36 / 65 Exemplo Branching Method 1 Comec¸ando com uma ce´lula 1 qualquer, selecionamos um implicante primo que cobre essa ce´lula como se ele fosse essencial, e removemos ele do mapa. 2 Aplicamos o me´todo visto anteriormente (identificar as ce´lulas 1 distintas, identificar os implicantes primos essenciais, etc...). 3 Quando terminamos, repetimos o processo utilizando o outro implicante primo (isto e´, aquele que deixamos de fora inicialmente), gerando uma segunda tentativa de soma m´ınima. 4 Finalmente, comparamos o custo de todas as alternativas e escolhemos a menor. Pode ocorrer de ficarmos empacados (isto e´, na˜o encontrarmos nenhum implicante primo essencial). Neste caso, podemos aplicar esse procedimento recursivamente. 37 / 65 Exemplos F WX YZ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 11 00 01 11 10 00 01 11 10 F = W ·X · Z + W ·Y · Z + X ·Y · Z F WX YZ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 11 00 01 11 10 00 01 11 10 F = X ·Y · Z + W ·X · Z + W ·Y · Z 38 / 65 Produto de Somas Minimizac¸a˜o usando mapas de Karnaugh tambe´m pode ser feita usando a forma produto de somas (POS) O procedimento e´ o mesmo, entretanto, faz-se agrupamentos de 0s Deve-se atribuir 0 no mapa para todos os maxtermos que fazem parte da func¸a˜o 39 / 65 Produto de Somas Exemplo: 40 / 65 Produto de Somas Exemplo: 41 / 65 Mapas de Karnaugh Exemplo: 42 / 65 Minimizac¸a˜o com indiferenc¸as Frequentemente, em sistemas digitais, algumas condio˜es de entrada, ou seja, algumas combinac¸o˜es doa valores de entrada na˜o acontecem Uma combinac¸a˜o de entradas que pode nunca acontecer e´ denominada dont care ou indiferenc¸a Quando um circuito e´ projetado, um dont care pode ser ignorado (a sa´ıda pode ser tratada como ‘1’ ou ‘0’ na tabela-verdade) Um func¸a˜o que tem dont care e´ denominada func¸a˜o de especificac¸a˜o incompleta 43 / 65 Minimizac¸a˜o com indiferenc¸as Exemplo: 44 / 65 Minimizac¸a˜o com indiferenc¸as Exemplo: 45 / 65 Minimizac¸a˜o com indiferenc¸as Exemplo: 46 / 65 Minimizac¸a˜o com va´rias sa´ıdas Ate´ agora somente exemplos com uma u´nica sad´a foram considerados Geralmente, na pra´tica, os sistemas possuem mais de uma sa´ıda Circuitos podem ser combinados de forma a implementar o sistema com o menor custo poss´ıvel (menor nmero de portas) 47 / 65 Minimizac¸a˜o com va´rias sa´ıdas Exemplo: 48 / 65 Minimizac¸a˜o com va´rias sa´ıdas Minimizac¸a˜o com com va´rias sa´ıdas: 49 / 65 Minimizac¸a˜o com va´rias sa´ıdas Exemplo: Supor que as func¸o˜es F1 e F2 abaixo sa˜o sa´ıdas do mesmo circuito: F1 = A · D + B · D + A · B · C F2 = B · D + A · D + A · B · C · D F1 possui 4 portas AND, 2 portas OR, 2 inversoras e 5 entradas. F2 possui 5 portas AND, 2 portas OR, 3 inversoras e 7 entradas. 50 / 65 Minimizac¸a˜o com com va´rias sa´ıdas: F1 = A ·D +A ·B ·D +A ·B ·C ·D || F2 = B ·D +A ·B ·D +A ·B ·C ·D F1 possui 6 portas AND, 2 portas OR e 3 inversoras. F2 possui 6 portas AND, 2 portas OR e 3 inversoras. Observe que F1 e F2 possui possuem 2 termos em comum. Logo, o sistema geral pode ser implementado com F = A · D + B · D + A · B · D + A · B · C · D que utiliza 7 portas AND, 3 portas OR e 3 inversoras 51 / 65 Va´riaveis Introduzidas Podemos reduzir a dimensa˜o do mapa de Karnaugh introduzindo varia´veis no mapa. A ideia ba´sica e´ expressar F em termos de uma varia´vel V. Para func¸o˜es de especificac¸a˜o completa (isto e´, sem don’t cares), temos quatro possibilidades: V F F (V) 0 0 0 1 0 V F F (V) 0 0 V 1 1 V F F (V) 0 1 1 1 1 V F F (V) 0 1 V 1 0 52 / 65 Va´riaveis Introduzidas Considere a func¸a˜o de 4 varia´veis: Linha W X Y Z F 0 0 0 0 0 1 1 0 0 0 1 1 2 0 0 1 0 0 3 0 0 1 1 1 4 0 1 0 0 1 5 0 1 0 1 1 6 0 1 1 0 0 7 0 1 1 1 0 8 1 0 0 0 1 9 1 0 0 1 0 10 1 0 1 0 0 11 1 0 1 1 0 12 1 1 0 0 1 13 1 1 0 1 1 14 1 1 1 0 0 15 1 1 1 1 0 F WX YZ 1 1 1 1 1 11 1 00 01 11 10 00 01 11 10 F = Y · Z + X · Y + W · X · Z 53 / 65 Va´riaveis Introduzidas Podemos montar uma tabela de F (Z): Linha W X Y Z F 0 0 0 0 0 1 1 0 0 0 1 1 2 0 0 1 0 0 3 0 0 1 1 1 4 0 1 0 0 1 5 0 1 0 1 1 6 0 1 1 0 0 7 0 1 1 1 0 8 1 0 0 0 1 9 1 0 0 1 0 10 1 0 1 0 0 11 1 0 1 1 0 12 1 1 0 0 1 13 1 1 0 1 1 14 1 1 1 0 0 15 1 1 1 1 0 Linha W X Y F (Z) 0 0 0 0 1 1 0 0 1 Z 2 0 1 0 1 3 0 1 1 0 4 1 0 0 Z 5 1 0 1 0 6 1 1 0 1 7 1 1 1 0 54 / 65 Va´riaveis Introduzidas Podemos montar uma tabela de F (Z): Linha W X Y F (Z) 0 0 0 0 1 1 0 0 1 Z 2 0 1 0 1 3 0 1 1 0 4 1 0 0 Z 5 1 0 1 0 6 1 1 0 1 7 1 1 1 0 E tambe´m o mapa de F (Z): FZ WX Y 0 1 2 3 4 5 6 7 1 Z 1 0 Z 0 1 0 0 1 00 01 11 10 55 / 65 Va´riaveis Introduzidas Como proceder para minimizar o mapa de Karnaugh de F (Z)? FZ WX Y 0 1 2 3 4 5 6 7 1 Z 1 0 Z 0 1 0 0 1 00 01 11 10 Esta minimizac¸a˜o e´ realizada em duas etapas. Na primeira etapa, devem ser cobertos os termos contendo Z e Z, sendo que na˜o e´ necessa´rio cobrir os termos 1s (na˜o nessa etapa). Os termos Z podem ser associados, em ordem de prioridade, com os termos Z e 1 (pois 1 = Z + Z), e os termos Z podem ser associados, em ordem de prioridade, com os termos Z e 1 (pelo mesmo motivo anterior). 56 / 65 Va´riaveis Introduzidas Logo, podemos fazer os agrupamentos: FZ WX Y 1 Z 1 0 Z 0 1 0 0 1 00 01 11 10 Note que devemos multiplicar o valor do termo gerado pelo agrupamento pelo valor da varia´vel dentro do mapa. Logo, geramos os termos: Y · Z e W · X · Z. 57 / 65 Va´riaveis Introduzidas Na segunda etapa do processo, ja´ com os termos Z e Z cobertos, redesenhamos o mapa fazendo as seguintes substituic¸o˜es: Termo original Substitu´ıdo por Z, Z ou 0 0 1, se foi associado com Z e Z d 1, se na˜o foi associado com Z e Z 1 E o mapa se torna: FZ WX Y d 1 10 1 00 01 11 10 O que gera o termo X · Y. 58 / 65 Va´riaveis Introduzidas Finalmente: Linha W X Y F (Z) 0 0 0 0 1 1 0 0 1 Z 2 0 1 0 1 3 0 1 1 0 4 1 0 0 Z 5 1 0 1 0 6 1 1 0 1 7 1 1 1 0 FZ WX Y 1 Z 1 0 Z 0 1 0 0 1 00 01 11 10 F = Y · Z + X · Y + W · X · Z 59 / 65
Compartilhar