Mapa de Karnaugh - Karnaugh map
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 .
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).
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
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
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.
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
- Forma normal algébrica (ANF)
- Diagrama de decisão binária (BDD), uma estrutura de dados que é uma representação compactada de uma função booleana
- Minimizador lógico heurístico Espresso
- Lista de tópicos de álgebra booleana
- Otimização lógica
- Quadrado de Punnett (1905), um diagrama semelhante em biologia
- Algoritmo Quine-McCluskey
- Expansão Reed-Muller
- Diagrama de Venn (1880)
- Polinômio de Zhegalkin
Notas
Referências
Leitura adicional
- Katz, Randy Howard (1998) [1994]. Design Lógico Contemporâneo . Benjamin / Cummings Publishing Company . pp. 70–85 . doi : 10.1016 / 0026-2692 (95) 90052-7 . ISBN 0-8053-2703-7.
- Vingron, Shimon Peter (2004) [2003-11-05]. "Mapas de Karnaugh". Teoria de comutação: percepção por meio da lógica de predicados . Berlin, Heidelberg, New York: Springer-Verlag . pp. 57–76. ISBN 3-540-40343-4.
-
Wickes, William E. (1968). "3.5. Diagramas de Veitch". Projeto lógico com circuitos integrados . Nova York, EUA: John Wiley & Sons . pp. 36–49 . LCCN 68-21185 . p. 36:
[...] um refinamento do diagrama de Venn em que os círculos são substituídos por quadrados e organizados em uma forma de matriz. O diagrama de Veitch rotula os quadrados com os mintermos . Karnaugh atribuiu 1s e 0s aos quadrados e seus rótulos e deduziu o esquema de numeração de uso comum.
- Maxfield, Clive "Max" (2006-11-29). "Lógica Reed-Muller" . Logic 101 . EE Times . Parte 3. Arquivado do original em 19-04-2017 . Recuperado em 19-04-2017 .
- Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). "Seção 2.3". Análise e Projeto de Sistemas Digitais Sequenciais . Macmillan Press . ISBN 0-33319266-4. (146 páginas)
- Holder, Michel Elizabeth (março de 2005) [2005-02-14]. "Uma técnica de mapa de Karnaugh modificada" . IEEE Transactions on Education . IEEE . 48 (1): 206–207. doi : 10.1109 / TE.2004.832879 . eISSN 1557-9638 . ISSN 0018-9359 . S2CID 25576523 . [2]
- Cavanagh, Joseph (2008). Computer Arithmetic and Verilog HDL Fundamentals (1 ed.). CRC Press .
- Kohavi, Zvi; Jha, Niraj K. (2009). Switching and Finite Automata Theory (3 ed.). Cambridge University Press . ISBN 978-0-521-85748-2.
links externos
- Detectar Retângulos Sobrepostos , de Herbert Glarner.
- Usando mapas de Karnaugh em aplicações práticas , projeto de design de circuito para controle de semáforos.
- Tutorial K-Map para variáveis 2,3,4 e 5
- Exemplo de mapa de Karnaugh
- POCKET – PC BOOLEAN FUNCTION SIMPLIFICATION, Ledion Bitincka - George E. Antoniou
- Solução de problemas do K-Map