Grátis
62 pág.

Denunciar
5 de 5 estrelas









3 avaliações
Enviado por
marçal mesquita
5 de 5 estrelas









3 avaliações
Enviado por
marçal mesquita
Pré-visualização | Página 1 de 2
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 implicantes