Mapa de Karnaugh - Karnaugh map

Um exemplo de mapa de Karnaugh. Esta imagem na verdade mostra dois mapas de Karnaugh: para a função ƒ , usando mintermos (retângulos coloridos) e para seu complemento, usando maxtermos (retângulos cinza). Na imagem, E () significa uma soma de mintermos, denotados no artigo como .

O mapa de Karnaugh ( KM ou K-map ) é um método de simplificar as expressões da álgebra booleana . Maurice Karnaugh o apresentou em 1953 como um refinamento do gráfico Veitch de Edward W. Veitch , de 1952 , que foi uma redescoberta do diagrama lógico de Allan Marquand de 1881, também conhecido como diagrama de Marquand, mas agora com foco em sua utilidade para comutação de circuitos. Os gráficos de Veitch são, portanto, também conhecidos como diagramas Marquand-Veitch e os mapas de Karnaugh como mapas de Karnaugh-Veitch ( mapas KV ).

O mapa de Karnaugh reduz a necessidade de cálculos extensos, aproveitando a capacidade de reconhecimento de padrões dos humanos. Também permite a rápida identificação e eliminação de potenciais condições de corrida .

Os resultados booleanos necessários são transferidos de uma tabela verdade para uma grade bidimensional onde, nos mapas de Karnaugh, as células são ordenadas em código Gray e cada posição de célula representa uma combinação de condições de entrada. As células também são conhecidas como mintermos, enquanto cada valor de célula representa o valor de saída correspondente da função booleana. Grupos ótimos de 1s ou 0s são identificados, os quais representam os termos de uma forma canônica da lógica na tabela verdade original. Esses termos podem ser usados ​​para escrever uma expressão booleana mínima que representa a lógica necessária.

Os mapas de Karnaugh são usados ​​para simplificar os requisitos lógicos do mundo real para que possam ser implementados usando um número mínimo de portas lógicas. Uma expressão de soma de produtos (SOP) sempre pode ser implementada usando portas AND alimentando uma porta OR , e uma expressão de produto de somas (POS) leva a portas OR alimentando uma porta AND. A expressão POS fornece um complemento da função (se F for a função, então seu complemento será F '). Os mapas de Karnaugh também podem ser usados ​​para simplificar expressões lógicas no projeto de software. As condições booleanas, como usadas por exemplo em instruções condicionais , podem se tornar muito complicadas, o que torna o código difícil de ler e manter. Uma vez minimizadas, as expressões canônicas de soma de produtos e produto de somas podem ser implementadas diretamente usando operadores lógicos AND e OR.

Exemplo

Os mapas de Karnaugh são usados ​​para facilitar a simplificação das funções da álgebra booleana . Por exemplo, considere a função booleana descrita pela seguinte tabela verdade .

Tabela verdade de uma função
  UMA B C D
0 0 0 0 0 0
1 0 0 0 1 0
2 0 0 1 0 0
3 0 0 1 1 0
4 0 1 0 0 0
5 0 1 0 1 0
6 0 1 1 0 1
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 1
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 1
13 1 1 0 1 1
14 1 1 1 0 1
15 1 1 1 1 0

A seguir estão duas notações diferentes que descrevem a mesma função na álgebra booleana não simplificada, usando as variáveis ​​booleanas A , B , C , D e seus inversos.

  • onde estão os mintermos a serem mapeados (ou seja, linhas que têm saída 1 na tabela verdade).
  • onde estão os maxtermos a serem mapeados (ou seja, linhas que têm saída 0 na tabela verdade).
K-map desenhado em um toro e em um avião. As células marcadas com pontos são adjacentes.
Construção do K-map. Em vez dos valores de saída (os valores mais à direita na tabela verdade), este diagrama mostra uma representação decimal da entrada ABCD (os valores mais à esquerda na tabela verdade), portanto, não é um mapa de Karnaugh.
Em três dimensões, pode-se dobrar um retângulo em um toro.

Construção

No exemplo acima, as quatro variáveis ​​de entrada podem ser combinadas de 16 maneiras diferentes, então a tabela verdade tem 16 linhas e o mapa de Karnaugh tem 16 posições. O mapa de Karnaugh é, portanto, organizado em uma grade 4 × 4.

Os índices de linha e coluna (mostrados na parte superior e inferior do lado esquerdo do mapa de Karnaugh) são ordenados em código Gray em vez de ordem numérica binária. O código cinza garante que apenas uma variável mude entre cada par de células adjacentes. Cada célula do mapa de Karnaugh completo contém um dígito binário que representa a saída da função para aquela combinação de entradas.

Agrupamento

Depois que o mapa de Karnaugh foi construído, ele é usado para encontrar uma das formas mais simples possíveis - uma forma canônica - para as informações na tabela verdade. Os 1s adjacentes no mapa de Karnaugh representam oportunidades para simplificar a expressão. Os mintermos ('termos mínimos') para a expressão final são encontrados circundando grupos de 1s no mapa. Os grupos Minterm devem ser retangulares e devem ter uma área com uma potência de dois (ou seja, 1, 2, 4, 8 ...). Os retângulos Minterm devem ser os maiores possíveis sem conter 0s. Os grupos podem se sobrepor para torná-los maiores. Os agrupamentos ideais no exemplo abaixo são marcados pelas linhas verde, vermelha e azul, e os grupos vermelho e verde se sobrepõem. O grupo vermelho é um quadrado 2 × 2, o grupo verde é um retângulo 4 × 1 e a área de sobreposição é indicada em marrom.

As células são freqüentemente indicadas por uma abreviação que descreve o valor lógico das entradas que a célula cobre. Por exemplo, AD significaria uma célula que cobre a área 2x2 onde A e D são verdadeiros, ou seja, as células numeradas 13, 9, 15, 11 no diagrama acima. Por outro lado, A D significaria as células em que A é verdadeiro e D é falso (ou seja, D é verdadeiro).

A grade é conectada toroidalmente , o que significa que grupos retangulares podem envolver as bordas (veja a imagem). As células na extrema direita são, na verdade, "adjacentes" às da extrema esquerda, no sentido de que os valores de entrada correspondentes diferem apenas em um bit; da mesma forma, também estão os que estão no topo e os que estão embaixo. Portanto, A D pode ser um termo válido - ele inclui as células 12 e 8 na parte superior e quebra na parte inferior para incluir as células 10 e 14 - assim como o B D , que inclui os quatro cantos.

Solução

Diagrama mostrando dois mapas K. O K-map para a função f (A, B, C, D) é mostrado como retângulos coloridos que correspondem a mintermos. A região marrom é uma sobreposição do quadrado vermelho 2 × 2 e do retângulo verde 4 × 1. O K-map para o inverso de f é mostrado como retângulos cinza, que correspondem a maxtermos.

Uma vez que o mapa de Karnaugh foi construído e os 1s adjacentes ligados por caixas retangulares e quadradas, os mintermos algébricos podem ser encontrados examinando quais variáveis ​​permanecem as mesmas dentro de cada caixa.

Para o grupo vermelho:

  • A é o mesmo e é igual a 1 em toda a caixa, portanto, deve ser incluído na representação algébrica do mintermo vermelho.
  • B não mantém o mesmo estado (muda de 1 para 0) e, portanto, deve ser excluído.
  • C não muda. É sempre 0, então seu complemento, NOT-C, deve ser incluído. Portanto, C deve ser incluído.
  • D muda, por isso é excluído.

Assim, o primeiro mintermo na expressão booleana soma de produtos é um C .

Para o agrupamento verde, A e B mantêm o mesmo estado, enquanto C e D mudam. B é 0 e deve ser negado antes de ser incluído. O segundo termo, por conseguinte, é um B . Observe que é aceitável que o agrupamento verde se sobreponha ao vermelho.

Da mesma forma, o agrupamento azul dá o termo BC D .

As soluções de cada agrupamento são combinadas: a forma normal do circuito é .

Assim, o mapa de Karnaugh guiou uma simplificação de

Também teria sido possível derivar essa simplificação aplicando cuidadosamente os axiomas da álgebra booleana , mas o tempo que leva para fazer isso aumenta exponencialmente com o número de termos.

Inverso

O inverso de uma função é resolvido da mesma maneira, agrupando os 0s.

Os três termos para cobrir o inverso são todos mostrados com caixas cinza com bordas de cores diferentes:

  • marrom : A B
  • ouro : A C
  • azul : BCD

Isso produz o inverso:

Por meio do uso das leis de De Morgan , o produto das somas pode ser determinado:

Não liga

O valor de para ABCD = 1111 é substituído por um "não importa". Isso remove o termo em verde completamente e permite que o termo em vermelho seja maior. Também permite que o termo inverso azul mude e se torne maior

Os mapas de Karnaugh também permitem minimizações mais fáceis de funções cujas tabelas de verdade incluem condições " irrelevantes ". Uma condição "não importa" é uma combinação de entradas para as quais o designer não se importa com a saída. Portanto, as condições "irrelevantes" podem ser incluídas ou excluídas de qualquer grupo retangular, o que for maior. Geralmente são indicados no mapa com um travessão ou X.

O exemplo à direita é igual ao exemplo acima, mas com o valor de f (1,1,1,1) substituído por um "não me importo". Isso permite que o termo em vermelho se expanda totalmente e, assim, remove completamente o termo em verde.

Isso produz a nova equação mínima:

Note-se que o primeiro termo é apenas uma , não um C . Nesse caso, não importa o termo (o retângulo verde); outro simplificado (o vermelho); e removeu o perigo da corrida (removendo o termo amarelo conforme mostrado na seção a seguir sobre os perigos da corrida).

O caso inverso é simplificado da seguinte forma:

Por meio do uso das leis de De Morgan , o produto das somas pode ser determinado:

Riscos de corrida

Eliminação

Os mapas de Karnaugh são úteis para detectar e eliminar condições de corrida . Os perigos da corrida são muito fáceis de detectar usando um mapa de Karnaugh, porque uma condição de corrida pode existir ao mover-se entre qualquer par de regiões adjacentes, mas disjuntas, circunscritas no mapa. No entanto, por causa da natureza da codificação Gray, adjacente tem uma definição especial explicada acima - na verdade, estamos nos movendo em um toro, em vez de um retângulo, envolvendo a parte superior, inferior e os lados.

  • No exemplo acima , existe uma condição de corrida potencial quando C é 1 e D é 0, A é 1 e B muda de 1 para 0 (passando do estado azul para o estado verde). Para este caso, a saída é definida para permanecer inalterada em 1, mas como essa transição não é coberta por um termo específico na equação, existe um potencial para uma falha (uma transição momentânea da saída para 0).
  • Há uma segunda falha potencial no mesmo exemplo que é mais difícil de detectar: ​​quando D é 0 e A e B são ambos 1, com C mudando de 1 para 0 (passando do estado azul para o estado vermelho). Nesse caso, a falha ocorre da parte superior do mapa para a parte inferior.
Os perigos da corrida estão presentes neste diagrama.
Diagrama acima com termos de consenso adicionados para evitar riscos de corrida.

Se as falhas realmente ocorrerão depende da natureza física da implementação, e se precisamos nos preocupar com isso depende do aplicativo. Na lógica com clock, é suficiente que a lógica se estabeleça no valor desejado a tempo de cumprir o deadline de temporização. Em nosso exemplo, não estamos considerando a lógica com clock.

Em nosso caso, um termo adicional de eliminaria o risco potencial de corrida, criando uma ponte entre os estados de saída verde e azul ou estados de saída azul e vermelho: isso é mostrado como a região amarela (que envolve de baixo para cima à direita metade) no diagrama adjacente.

O termo é redundante em termos da lógica estática do sistema, mas tais termos redundantes, ou consensuais , são freqüentemente necessários para garantir um desempenho dinâmico livre de corrida.

Da mesma forma, um termo adicional de deve ser adicionado ao inverso para eliminar outro risco potencial de corrida. A aplicação das leis de De Morgan cria outro produto da expressão de somas para f , mas com um novo fator de .

Exemplos de mapa de 2 variáveis

A seguir estão todos os mapas de Karnaugh 2 × 2 possíveis de 2 variáveis. Listados com cada um estão os mintermos em função da equação mínima sem risco de corrida ( consulte a seção anterior ). Um mintermo é definido como uma expressão que fornece a forma mais mínima de expressão das variáveis ​​mapeadas. Todos os blocos interconectados horizontais e verticais possíveis podem ser formados. Esses blocos devem ser do tamanho das potências de 2 (1, 2, 4, 8, 16, 32, ...). Essas expressões criam um mapeamento lógico mínimo das expressões de variáveis ​​lógicas mínimas para as expressões binárias a serem mapeadas. Aqui estão todos os blocos com um campo.

Um bloco pode ser continuado na parte inferior, superior, esquerda ou direita do gráfico. Isso pode até ultrapassar a borda do gráfico para minimizar a variável. Isso ocorre porque cada variável lógica corresponde a cada coluna vertical e linha horizontal. Uma visualização do k-map pode ser considerada cilíndrica. Os campos nas bordas à esquerda e à direita são adjacentes e as partes superior e inferior são adjacentes. Os K-Maps para quatro variáveis ​​devem ser representados em formato de rosca ou toro. Os quatro cantos do quadrado desenhado pelo k-map são adjacentes. Mapas ainda mais complexos são necessários para 5 variáveis ​​e mais.

Métodos gráficos relacionados

Os métodos de minimização gráfica relacionados incluem:

  • Diagrama de Marquand (1881) por Allan Marquand (1853–1924)
  • Veitch chart (1952) por Edward W. Veitch (1924–2013)
  • Mapa Mahoney ( M-map , números de designação , 1963) por Matthew V. Mahoney (uma extensão simétrica de reflexão de mapas de Karnaugh para um número maior de entradas)
  • Reduzida Karnaugh mapa (RKM) técnicas (de 1969) como variáveis infrequentes , variáveis introduzidos pelo mapa (MEV), mapa entrou-variável (VEM) ou mapa Karnaugh entrou-variável (VEKM) por GW Schultz, Thomas E. Osborne , Christopher R . Clare, J. Robert Burgoon, Larry L. Dornhoff, William I. Fletcher, Ali M. Rushdi e outros (várias extensões de mapa de Karnaugh sucessivas com base em entradas variáveis ​​para um número maior de entradas)
  • Mapa Minterm-ring (MRM, 1990) por Thomas R. McCalla (uma extensão tridimensional dos mapas de Karnaugh para um grande número de entradas)

Veja também

Notas

Referências

Leitura adicional

links externos