Aula 07 Eletrônica_Básica_Mapa_de_Karnaugh

Prévia do material em texto

Eletrônica Básica:
Mapa de Karnaugh
Profa. Ranoyca Nayana Alencar Leão e Silva Aquino
Instituto de Engenharia e Desenvolvimento Sustentável
Engenharia de Energias
Tópicos
◼ Resumo dos Métodos para Descrição
◼ Projetando Circuitos Lógicos Combinacionais
◼ Forma de Soma-de-Produtos
◼ Simplificação de Circuitos Lógicos
 Método da Simplificação Algébrica
 Método do Mapa de Karnaugh
Tabela-Verdade
Circuito
Expressão Lógica
Tabela-Verdade
Circuito
Expressão Lógica
Circuito
Expressão Lógica
Circuito
Expressão Lógica
Tabela-Verdade Tabela-Verdade
Mudanças de DescriçãoK
Projetando Circuitos 
Lógicos Combinacionais
Circuitos Lógicos Combinacionais
Os circuitos descritos e analisados até o momento podem ser classificados
como CIRCUITOS LÓGICOS COMBINACIONAIS porque, em qualquer
instante de tempo, o nível lógico da saída do circuito depende APENAS da
combinação dos níveis lógicos presente nas entradas.
Um circuito combinacional não possui a característica de memória, portanto
sua saída depende apenas dos valores atuais das entradas.
Para projetar circuitos combinacionais, justifica-se um estudo mais detalhado
da simplificação dos circuitos lógicos. Dois métodos serão usados: o
primeiro usará os teoremas da álgebra Booleana, e o segundo usará uma
técnica de mapeamento
Forma de Soma-de-Produtos
Os métodos de simplificação e projetos de circuitos lógicos a serem estudados
requerem que a expressão esteja na forma de soma-de-produtos. Alguns
exemplos de expressões desse tipo são:
CBAABC +1. K.
2. J.
3. j
DDCCBAAB +++
LHGKEFDCBA ++++
Cada uma dessas expressões consiste em dois ou mais termos AND (produtos
lógicos) conectados por operações OR. Cada termo AND consiste em uma ou
mais variáveis que aparecem individualmente na sua forma complementada ou
não-complementada.
Produto-de-Somas: Outra forma geral, utilizada algumas vezes, para
expressões lógicas é chamada de produto-de-somas, e consiste em dois ou
mais termos OR (somas lógicas) conectados por operações AND.
( )( )CACBA +++1. K.
2. J.( )( )FEDCBA +++
Simplificação de Circuitos Lógicos
Uma vez obtida a expressão de um circuito lógico, podemos reduzi-la a uma
forma mais simples - que contenha um menor número de (i) termos ou (ii)
variáveis em um ou mais termos da expressão. Essa nova expressão pode
então ser usada na implementação de um circuito equivalente ao circuito
original, mas que contém menos portas lógicas e conexões.
Exemplo:
( )



 = BCAABx
( ) CBAAB +=
( )CABAAB +=
CAABBAAB +=
Dois métodos para simplificação de circuitos lógicos serão estudados:
(i) Simplificação Algébrica e (ii) Mapa de Karnaugh.
Simplificação AlgébricaK
Podemos usar os teoremas da Álgebra Booleana para nos auxiliar a
simplificar expressões de circuitos lógicos. Entretanto, nem sempre é óbvio
qual teorema deve ser aplicado para se obter o resultado mais
simplificado. Assim, as simplificações algébricas são, muitas vezes, um
processo de tentativa-e-erro. Entretanto, com a experiência, pode-se obter
resultados razoavelmente bons.
Uma metodologia para a aplicação dos teoremas Booleanos na busca pela
simplificação de expressões lógicas é seguir os dois seguintes passos:
1. A expressão original é colocada na forma de soma-de-produtos
aplicando-se repetidamente os teoremas de DeMorgan e a multiplicação
de termos.
2. Uma vez que a expressão original esteja na forma de soma-de-produtos,
verifica-se se os termos produto têm fatores comuns, realizando a
fatoração sempre que possível. Esta fatoração pode levar à eliminação
de termos.
Simplificação AlgébricaK
Exemplo: Simplifique o circuito lógico abaixo.
Solução:
O primeiro passo é colocar a expressão na forma soma-de-produtos.
( )CABAABCz +=





 ++= CABAABC
( )CABAABC ++=
CBAABAABC ++=
CBABAABC ++=
DeMorgan
cancela inversões
multiplica
A . A = A
primeiro passo
Solução:
Obtida a forma soma-de-produtos (primeiro passo da simplificação):
CBABAABCz ++=
parte-se para o passo 2 (buscar fatores comuns para realizar fatoração):
CBABAABCz ++=
BABBAC ++= )(
BAAC +=
( )CBA +=
Simplificação AlgébricaK
Exemplo: Simplifique o circuito lógico abaixo.
Simplificação AlgébricaKSimplificação AlgébricaK
Exemplo: Simplifique o circuito lógico abaixo.
Projetando Circuitos Lógicos Combinacionais
Quando o nível de saída desejado de um circuito lógico é dado para todas as
condições de entrada possíveis, os resultados podem ser convenientemente
apresentados em uma tabela-verdade. A expressão Booleana para o
circuito requerido pode então ser obtida a partir desta tabela-verdade.
Por exemplo, considere a Tabela-Verdade abaixo que tem duas entradas, A e
B, e a saída x que será nível 1 apenas para o caso em que A = 0 e B = 1.
O circuito mostrado acima implementa a tabela-verdade apresentada.
Caso se tenha interesse em conhecer circuitos que tenham saída 1 para 
uma única combinação na entrada ?
Projetando Circuitos Lógicos Combinacionais
Para o caso de duas variáveis lógicas, temos abaixo quatro circuitos que têm
saída nível 1 apenas para uma das 4 possíveis combinações na entrada.
Esses circuitos poderiam ser combinados para implementar outras tabelas 
verdade ?
Projetando Circuitos Lógicos Combinacionais
Quando o nível de saída desejado de um circuito lógico é dado para todas as
condições de entrada possíveis, os resultados podem ser convenientemente
apresentados em uma tabela-verdade. A expressão Booleana para o circuito
requerido pode então ser obtida a partir desta tabela-verdade.
Vamos considerar o caso no qual temos uma tabela-verdade em que a saída
será 1 apenas para dois casos distintos: A = 0, B = 1 e A = 1, B = 0. Como isso
pode ser implementado ?
BA
BA
Projetando Circuitos Lógicos Combinacionais
Expressão Lógica Circuito
Tabela-Verdade Tabela-Verdade
Qual seria o procedimento geral ?
Projetando Circuitos Lógicos Combinacionais
Ao associar cada saída 1 a um termo que seja um produto das entradas
(invertidas ou não), a expressão do circuito é a soma lógica destes termos.
Se estaria escrevendo a expressão do circuito no formato de 
soma-de-produtos !
Entretanto, há outros métodos de simplificação. Um deles é o
Método do Mapa de Karnaugh - um método gráfico que automatiza
a busca pela simplificação da expressão do circuito caso esta
estiver no formato de soma de produtos.
A partir da expressão lógica no formato de soma-de-produtos,
pode-se aplicar o Método da Simplificação Algébrica para
simplificar a expressão e obter um circuito com um número menor
de portas lógicas e conexões.
Método do Mapa de Karnaugh
O mapa de Karnaugh é um método gráfico usado para simplificar uma
equação lógica ou para converter uma tabela-verdade no seu circuito lógico
correspondente, de uma forma simples e metódica. Embora um mapa de
Karnaugh, ou simplesmente mapa K, possa ser usado em problemas que
envolvem qualquer número de variáveis de entrada, sua utilidade prática está
limitada a cinco ou seis variáveis – trabalharemos com até 4 variáveis.
O mapa K, assim como uma tabela-verdade, é um meio de mostrar a relação
entre as entradas lógicas e a saída desejada. Segue abaixo um exemplo da
tabela-verdade de uma expressão lógica e seu mapa K correspondente.
ExpressãoTabela-Verdade Mapa de Karnaugh
Como montar o mapa para mais de duas variáveis ?
Método do Mapa de Karnaugh
Pontos mais importantes do Mapa de Karnaugh:
1. A tabela-verdade fornece o valor da saída X para cada combinação de
valores de entrada. O mapa K fornece a mesma informação em um formato
diferente. Cada linha na tabela-verdade corresponde a um quadrado no
mapa K. A condição A=0, B=0, por exemplo, corresponde ao quadrado A’B’
do mapa K. Visto que X=1 para essa condição, é colocado 1 no quadrado
correspondente (A’B’).
Método do Mapa de Karnaugh
Exemplos com mais variáveis:
ExpressãoTabela-Verdade Mapa de Karnaugh
Método do Mapa de Karnaugh
Exemplos com mais variáveis:
ExpressãoTabela-Verdade Mapade Karnaugh
Método do Mapa de Karnaugh
Pontos mais importantes do Mapa de Karnaugh:
1. A tabela-verdade fornece o valor da saída X para cada combinação de
valores de entrada. O mapa K fornece a mesma informação em um formato
diferente. Cada linha na tabela-verdade corresponde a um quadrado no
mapa K. A condição A=0, B=0, por exemplo, corresponde ao quadrado A’B’
do mapa K. Visto que X=1 para essa condição, é colocado 1 no quadrado
correspondente (A’B’).
2. Os quadrados no mapa K são nomeados de forma que quadrados
adjacentes horizontalmente, ou verticalmente, diferem em apenas uma
variável. O quadrado A’B’CD é adjacente ao AB’CD.
3. Para que os quadrados adjacentes difiram em apenas uma variável, as
denominações, de cima pra baixo, devem ser A’B’, A’B, AB, AB’. Da
mesma forma, da direita pra esquerda, C’D’, C’D, CD, CD’.
4. Uma vez que um mapa K tenha sido preenchido com 0s e 1s, a expressão
na forma de soma-de-produtos para a saída X pode ser obtida fazendo-
se a operação OR dos quadrados que contêm 1.
Método do Mapa de Karnaugh
A expressão para a saída X pode ser simplificada combinando adequadamente
os quadrados do mapa K que contêm 1. O processo de combinação desses 1s
é denominado agrupamento.
Agrupamento de dois quadros no mapa K
Agrupando um par de 1s adjacentes em um mapa K, elimina-se a variável
que aparece nas formas complementada e não-complementada.
Exemplo:
CABCBAX +=
( )AACB +=
CB=
Exemplos:
Método do Mapa de Karnaugh
Agrupamento de quatro quadros no mapa K (quartetos)
Agrupando um quarteto de 1s adjacentes em um mapa K, elimina-se duas
variáveis que aparecem nas formas complementada e não-
complementada.
Exemplo:
CBAABCBCACBAX +++=
( ) ( )BBACBBCA +++=
ACCA +=
( )AAC +=
C=
CX =
Exemplos:
Método do Mapa de Karnaugh
Agrupamento de oito quadros no mapa K (octetos)
Agrupando um octeto de 1s adjacentes em um mapa K, elimina-se três
variáveis que aparecem nas formas complementada e não-
complementada.
Exemplos:
Exemplos:
Método do Mapa de Karnaugh
Processo Completo de Simplificação
Quando uma variável aparece nas formas complementada e não-
complementada em um agrupamento, tal variável é eliminada da
expressão. As variáveis que não se alteram para todos os quadros do
agrupamento têm de permanecer na expressão final
Deve ficar claro que um grupo maior de 1s elimina mais variáveis. Para ser
exato, um grupo de dois 1s elimina uma variável, um grupo de quatro 1s
elimina duas variáveis, e um grupo de oito 1s elimina três variáveis. Esse
princípio será usado para se obter a expressão lógica simplificada a partir do
mapa K que contém qualquer combinação de 1s e 0s.
Método do Mapa de Karnaugh
Procedimento para uso do mapa K na simplificação de expressões Booleanas:
1. Construa o mapa K e coloque os 1s nos quadros que correspondem aos 1s
na tabela-verdade. Coloque 0s nos demais quadros.
2. Analise o mapa quanto aos 1s adjacentes e agrupe os 1s que não sejam
adjacentes e quaisquer outros 1s. Esses são denominados 1s isolados.
3. Em seguida, procure os 1s que são adjacentes a somente um outro 1.
Agrupe todo par que contém tal 1.
4. Agrupe qualquer octeto, mesmo que ele contenha alguns 1s que já
tenham sido agrupados.
5. Agrupe qualquer quarteto que contenha um ou mais 1s que ainda não
tenham sido agrupados, certifique-se de usar o menor número de
agrupamentos.
6. Agrupe quaisquer pares necessários para incluir quaisquer 1s que ainda
não tenham sido agrupados, certifique-se de usar o menor número de
agrupamentos.
7. Forme a soma OR de todos os termos gerados por cada agrupamento.
Método do Mapa de Karnaugh
Pontos mais importantes do Mapa de Karnaugh:
1. A tabela-verdade fornece o valor da saída X para cada combinação de
valores de entrada. O mapa K fornece a mesma informação em um formato
diferente. Cada linha na tabela-verdade corresponde a um quadrado no
mapa K.
2. Os quadrados no mapa K são nomeados de forma que quadrados
adjacentes horizontalmente, ou verticalmente, diferem em apenas uma
variável.
3. Uma vez que um mapa K tenha sido preenchido com 0s e 1s, a expressão
na forma de soma-de-produtos para a saída X pode ser obtida fazendo-
se a operação OR dos quadrados que contêm 1.
Exemplo I: A partir do mapa k abaixo, obtenha a expressão
simplificada.
0 0 0 1
0 1 1 0
0 1 1 0
0 0 1 0
Método do Mapa de Karnaugh
1
5
9
13
2
6
10
14
3
7
11
15
4
8
12
16
Método do Mapa de Karnaugh
Exemplo II: A partir do mapa k abaixo, obtenha a expressão
simplificada.
0 0 1 0
1 1 1 1
1 1 0 0
0 0 0 0
1
5
9
13
2
6
10
14
3
7
11
15
4
8
12
16
Exemplo III: A partir do mapa k abaixo, obtenha a expressão
simplificada.
0 1 0 0
0 1 1 1
1 1 1 0
0 0 1 0
Método do Mapa de Karnaugh
1
5
9
13
2
6
10
14
3
7
11
15
4
8
12
16
Se for dada uma expressão lógica, pode-se usar o método de Karnaugh ?
Bibliografia Básica
◼ Tocci, R. J., Widmer, N. S., Moss, G. L.;
Sistemas Digitais - Princípios e Aplicações -
10ª Ed, Editora Pearson, 2007.
◼ Floyd, Thomas L.; Sistemas Digitais 
Fundamentos e Aplicações - 9ª Ed, Editora 
Bookman, 2007.
◼ Pedroni, V. A.; Eletronica Digital Moderna e
VHDL, Editora Elsevier, 2010.