Simplificao de Circuitos Mtodo do Mapa de Veitch-Karnaugh

Maurice Karnaugh

O MAPA DE KARNAUGH UM MTODO GRFICO USADO PARA SIMPLIFICAR UMA EQUAO LGICA OU PARA CONVERTER UMA TABELA-VERDADE NO SEU CIRCUITO LGICO CORRESPONDENTE, DE UMA FORMA SIMPLES E METDICA. EMBORA UM MAPA DE KARNAUGH, OU SIMPLESMENTE MAPA K, POSSA SER USADO EM PROBLEMAS QUE ENVOLVEM QUALQUER NMERO DE VARIVEIS DE ENTRADA, SUA UTILIDADE PRTICA EST LIMITADA A CINCO OU SEIS VARIVEIS TRABALHAREMOS COM AT 4 VARIVEIS.

O MAPA K, ASSIM COMO UMA TABELA-VERDADE, UM MEIO DE MOSTRAR A RELAO ENTRE AS ENTRADAS LGICAS E A SADA DESEJADA. SEGUE ABAIXO UM EXEMPLO DA TABELA-VERDADE DE UMA EXPRESSO LGICA E SEU MAPA K CORRESPONDENTE.MAPA DE KARNAUGH

TABELAVERDADE

EXPRESSO

O MAPA K, ASSIM COMO UMA TABELA-VERDADE, UM MEIO DE MOSTRAR A RELAO ENTRE AS ENTRADAS LGICAS E A SADA DESEJADA. SEGUE ABAIXO UM EXEMPLO DA TABELA-VERDADE DE UMA EXPRESSO LGICA E SEU MAPA K CORRESPONDENTE.MAPA DE KARNAUGH

TABELAVERDADE

EXPRESSO

COMO MONTAR O MAPA PARA MAIS DE DUAS VARIVEIS ?

Exemplos com mais variveis:Tabela-Verdade Expresso Mapa de Karnaugh

Mtodo do Mapa de KarnaughExemplos com mais variveis:Tabela-Verdade Expresso Mapa de Karnaugh

Pontos mais importantes do Mapa de Karnaugh: 1. A tabela-verdade fornece o valor da sada X para cada combinao de valores de entrada. O mapa K fornece a mesma informao em um formato diferente. Cada linha na tabela-verdade corresponde a um quadrado no mapa K. 2. Os quadrados no mapa K so nomeados de forma que quadrados adjacentes horizontalmente, ou verticalmente, diferem em apenas uma varivel. 3. Uma vez que um mapa K tenha sido preenchido com 0s e 1s, a expresso na forma de soma-de-produtos para a sada X pode ser obtida fazendo-se a operao OR dos quadrados que contm 1. Como utilizar o mapa K para simplificar expresses ?

A expresso para a sada X pode ser simplificada combinando adequadamente os quadrados do mapa K que contm 1. O processo de combinao desses 1s denominado agrupamento.

Agrupamento de dois quadros no mapa KAgrupando um par de 1s adjacentes em um mapa K, elimina-se a varivel que aparece nas formas complementada e no-complementada.

Exemplo:

X ABC ABC BC A A

BC

Exemplos:

Mtodo do Mapa de KarnaughAgrupamento de quatro quadros no mapa K (quartetos)Agrupando um quarteto de 1s adjacentes em um mapa K, elimina-se duas variveis que aparecem nas formas complementada e no-complementada.

Exemplo:

X ABC ABC ABC ABC

AC B B AC B B

X C

AC AC C A A

C

Exemplos:

Mtodo do Mapa de KarnaughAgrupamento de oito quadros no mapa K (octetos)Agrupando um octeto de 1s adjacentes em um mapa K, elimina-se trs variveis que aparecem nas formas complementada e no-complementada.

Exemplos:

Exemplos:

Mtodo do Mapa de KarnaughPROCESSO COMPLETO DE SIMPLIFICAOQUANDO UMA VARIVEL APARECE NAS FORMAS COMPLEMENTADA E NOCOMPLEMENTADA EM UM AGRUPAMENTO, TAL VARIVEL ELIMINADA DA EXPRESSO. AS VARIVEIS QUE NO SE ALTERAM PARA TODOS OS QUADROS DO AGRUPAMENTO TM DE PERMANECER NA EXPRESSO FINAL

DEVE FICAR CLARO QUE UM GRUPO MAIOR DE 1S ELIMINA MAIS VARIVEIS. PARA SER EXATO, UM GRUPO DE DOIS 1S ELIMINA UMA VARIVEL, UM GRUPO DE QUATRO 1S ELIMINA DUAS VARIVEIS, E UM GRUPO DE OITO 1S ELIMINA TRS VARIVEIS. ESSE PRINCPIO SER USADO PARA SE OBTER A EXPRESSO LGICA SIMPLIFICADA A PARTIR DO MAPA K QUE CONTM QUALQUER COMBINAO DE 1S E 0S.

Mtodo do Mapa de KarnaughProcedimento para uso do mapa K na simplificao de expresses 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 no sejam adjacentes e quaisquer outros 1s. Esses so denominados 1s isolados. 3. Em seguida, procure os 1s que so adjacentes a somente um outro 1. Agrupe todo par que contm 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 no tenham sido agrupados, certifique-se de usar o menor nmero de agrupamentos. 6. Agrupe quaisquer pares necessrios para incluir quaisquer 1s que ainda no tenham sido agrupados, certifique-se de usar o menor nmero de agrupamentos. 7. Forme a soma OR de todos os termos gerados por cada agrupamento.

Mtodo do Mapa de KarnaughExemplo I: A partir do mapa k abaixo, obtenha a expresso simplificada.

01

02

03

14

05

16

17

08

09

110

111

012

013

014

115

016

Mtodo do Mapa de KarnaughExemplo II: A partir do mapa k abaixo, obtenha a expresso simplificada.

01

02

13

04

15

16

17

18

19

110

011

012

013

014

015

016

Mtodo do Mapa de KarnaughExemplo III: A partir do mapa k abaixo, obtenha a expresso simplificada.

01

12

03

04

05

16

17

18

19

110

111

012

013

014

115

016

Se for dada uma expresso lgica, pode-se usar o mtodo de Karnaugh ?

Mtodo do Mapa de KarnaughPreenchendo o Mapa K a partir da expresso da sadaQuando a sada desejada apresentada como uma expresso Booleana em vez de uma tabela-verdade, o mapa K pode ser preenchido usando os seguintes passos: 1. Passe a expresso para a forma de soma-de-produtos caso ela no esteja neste formato. 2. Para cada termo produto da expresso na forma soma-de-produtos, coloque um 1 em cada quadrado do mapa K cuja denominao seja a mesma da combinao das variveis de entrada. Coloque um 0 em todos os outros quadrados.

Mtodo do Mapa de KarnaughPreenchendo o Mapa K a partir da expresso da sada ExemploUse o mapa K para simplificar a expresso:

y C AB D D ABC DSoluo:Multiple o primeiro termo para obter:

y C AB D CD ABC D

E a expresso simplificada ?????????

Mtodo do Mapa de KarnaughPreenchendo o Mapa K a partir da expresso da sada ExemploUse o mapa K para simplificar a expresso:

y C AB D D ABC DSoluo:Expresso simplificada:

y C D ABCONCLUSO: Dada uma expresso lgica, ou uma tabela-verdade, podemos montar o mapa K correspondente e us-lo p/ obter a expresso simplificada.

Mas...

Mtodo do Mapa de KarnaughCondies de dont-careAlguns circuitos lgicos podem ser projetados de forma que existam certas condies de entrada para as quais no existem nveis de sada especificada normalmente essas condies nunca ocorrero. Para estas condies de entrada, a sada z no especificada nem como 0 nem como 1, e sim por um x que indica que aquela condio no importa (dont-care).

Como simplificar a expresso lgica associada com essa tabela-verdade ?

Mtodo do Mapa de KarnaughCondies de dont-careComo no h uma sada especificada para as condies dont-care, o projetista est livre para fazer a sada ser 0 ou 1 de forma a obter a expresso mais simple.

Assim, sempre que ocorrerem condies de dont-care temos que decidir qual x ser alterado para 0 e qual ser alterado para 1 de forma a se obter o melhor agrupamento no mapa k.

Ex. 1. Simplificar o circuitoa a a+b b b b(a+b)a

a+b(a+b)

s b

a + b.(a + b)

= = a + b.a+ b.b = a + b.a + 0 = a + b.a = (a + b).(a + a) = (a + b).1 =a+b

(distributiva) (x . x = 0) (x + 0 = x) (distributiva) (x + x = 1) (x . 1 = x)

a 0 0 1 1

b 0 1 0 1

a 1 1 0 0

b 1 0 1 0

a+b 0 1 1 1

a+b 1 1 1 0

b.(a+b) 0 1 0 0

a+b.(a+b) 0 1 1 1

a0 1

b

0 0 1

1 1 1 a.b + a.b = b

a.b + a.b = a

s=a+b

Qual a expresso simplificada do diagrama abaixo?

A A

AB 0 0

AB 1 1

AB 0 1

AB 1 1