Circuitos Digitais - Método K-Map

Nos capítulos anteriores, simplificamos as funções booleanas usando postulados e teoremas booleanos. É um processo demorado e temos que reescrever as expressões simplificadas após cada etapa.

Para superar essa dificuldade, Karnaughintroduziu um método para simplificação de funções booleanas de forma fácil. Este método é conhecido como método do mapa de Karnaugh ou método do K-map. É um método gráfico, que consiste em 2 n células para 'n' variáveis. As células adjacentes diferem apenas na posição de um único bit.

K-Maps para 2 a 5 variáveis

O método K-Map é mais adequado para minimizar funções booleanas de 2 variáveis ​​para 5 variáveis. Agora, vamos discutir sobre os K-Maps para 2 a 5 variáveis, uma por uma.

2 Variável K-Map

O número de células em 2 variáveis ​​K-map é quatro, já que o número de variáveis ​​é dois. A figura a seguir mostra2 variable K-Map.

  • Existe apenas uma possibilidade de agrupar 4 termos mínimos adjacentes.

  • As combinações possíveis de agrupamento de 2 termos min adjacentes são {(m 0 , m 1 ), (m 2 , m 3 ), (m 0 , m 2 ) e (m 1 , m 3 )}.

3 Variáveis ​​K-Map

O número de células em 3 variáveis ​​K-map é oito, já que o número de variáveis ​​é três. A figura a seguir mostra3 variable K-Map.

  • Existe apenas uma possibilidade de agrupar 8 termos mínimos adjacentes.

  • As combinações possíveis de agrupamento de 4 termos min adjacentes são {(m 0 , m 1 , m 3 , m 2 ), (m 4 , m 5 , m 7 , m 6 ), (m 0 , m 1 , m 4 , m 5 ), (m 1 , m 3 , m 5 , m 7 ), (m 3 , m 2 , m 7 , m 6 ) e (m 2 , m 0 , m 6 , m 4 )}.

  • As combinações possíveis de agrupamento de 2 termos min adjacentes são {(m 0 , m 1 ), (m 1 , m 3 ), (m 3 , m 2 ), (m 2 , m 0 ), (m 4 , m 5 ) , (m 5 , m 7 ), (m 7 , m 6 ), (m 6 , m 4 ), (m 0 , m 4 ), (m 1 , m 5 ), (m 3 , m 7 ) e ( m 2 , m 6 )}.

  • Se x = 0, então o K-map de 3 variáveis ​​torna-se o K-map de 2 variáveis.

4 Variável K-Map

O número de células em 4 variáveis ​​K-map é dezesseis, já que o número de variáveis ​​é quatro. A figura a seguir mostra4 variable K-Map.

  • Existe apenas uma possibilidade de agrupar 16 termos mínimos adjacentes.

  • Sejam R 1 , R 2 , R 3 e R 4 representem os termos mínimos da primeira linha, segunda linha, terceira linha e quarta linha, respectivamente. Da mesma forma, C 1 , C 2 , C 3 e C 4 representam os termos mínimos da primeira coluna, segunda coluna, terceira coluna e quarta coluna, respectivamente. As combinações possíveis de agrupamento de 8 termos min adjacentes são {(R 1 , R 2 ), (R 2 , R 3 ), (R 3 , R 4 ), (R 4 , R 1 ), (C 1 , C 2 ) , (C 2 , C 3 ), (C 3 , C 4 ), (C 4 , C 1 )}.

  • Se w = 0, então o mapa K de 4 variáveis ​​se torna o mapa K de 3 variáveis.

5 Variável K-Map

O número de células em 5 variáveis ​​K-map é trinta e dois, uma vez que o número de variáveis ​​é 5. A figura a seguir mostra 5 variable K-Map.

  • Existe apenas uma possibilidade de agrupar 32 termos mínimos adjacentes.

  • Existem duas possibilidades de agrupar 16 termos mínimos adjacentes. ou seja, agrupamento de termos mínimos de m 0 a m 15 e m 16 a m 31 .

  • Se v = 0, então o K-map de 5 variáveis ​​se torna o K-map de 4 variáveis.

Acima em todos os K-maps, usamos exclusivamente a notação de termos mínimos. Da mesma forma, você pode usar exclusivamente a notação de termos máximos.

Minimização de funções booleanas usando K-Maps

Se considerarmos a combinação de entradas para as quais a função booleana é '1', então obteremos a função booleana, que está em standard sum of products formulário após simplificar o K-map.

Da mesma forma, se considerarmos a combinação de entradas para as quais a função booleana é '0', então obteremos a função booleana, que está em standard product of sums formulário após simplificar o K-map.

Siga estes rules for simplifying K-maps a fim de obter a soma padrão do formulário de produtos.

  • Selecione o respectivo K-map com base no número de variáveis ​​presentes na função booleana.

  • Se a função booleana for dada como a soma da forma de termos mínimos, coloque-os nas respectivas células de termos mínimos no K-map. Se a função booleana for dada como a forma da soma dos produtos, coloque aqueles em todas as células possíveis do K-map para as quais os termos do produto dados são válidos.

  • Verifique a possibilidade de agrupar o número máximo de adjacentes. Deve ser potências de dois. Comece com a maior potência de dois e pelo menos a potência de dois. A maior potência é igual ao número de variáveis ​​consideradas no K-map e a menor potência é zero.

  • Cada agrupamento fornecerá um termo literal ou um termo de produto. É conhecido comoprime implicant. O implicante principal é dito seressential prime implicant, se pelo menos o único '1' não for coberto por nenhum outro agrupamento, mas apenas esse agrupamento abrange.

  • Anote todos os implicantes primos e implicantes primos essenciais. A função booleana simplificada contém todos os implicantes primos essenciais e apenas os implicantes primos necessários.

Note 1 - Se as saídas não forem definidas para alguma combinação de entradas, esses valores de saída serão representados com don’t care symbol ‘x’. Isso significa que podemos considerá-los como '0' ou '1'.

Note 2- Se os termos não importados também estiverem presentes, coloque 'x' não importados nas respectivas células do K-map. Considere apenas os irrelevantes 'x' que são úteis para agrupar o número máximo de unidades adjacentes. Nesses casos, trate o valor irrelevante como '1'.

Exemplo

Deixe-nos simplify a seguinte função booleana, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ usando o K-map.

A função booleana fornecida está na forma de soma dos produtos. Tem 4 variáveis ​​W, X, Y e Z. Portanto, exigimos4 variable K-map. o4 variable K-map com aqueles correspondentes aos termos do produto fornecidos é mostrado na figura a seguir.

Aqui, 1s são colocados nas seguintes células do K-map.

  • As células, que são comuns à interseção da linha 4 e colunas 1 e 2, correspondem ao termo do produto, WX’Y’.

  • As células, que são comuns à interseção das Linhas 3 e 4 e colunas 3 e 4, correspondem ao termo do produto, WY.

  • As células, que são comuns à interseção das Linhas 1 e 2 e coluna 4, correspondem ao termo do produto, W’YZ’.

Não há possibilidade de agrupar 16 adjacentes ou 8 adjacentes. Existem três possibilidades de agrupar 4 adjacentes. Após esses três agrupamentos, não há mais nenhum agrupado. Portanto, não precisamos verificar o agrupamento de 2 adjacentes. o4 variable K-map com esses três groupings é mostrado na figura a seguir.

Aqui, temos três implicantes primos WX ', WY e YZ'. Todos esses implicantes primários sãoessential pelos seguintes motivos.

  • Dois uns (m8 & m9)do agrupamento da quarta linha não são cobertos por nenhum outro agrupamento. Apenas o quarto agrupamento de linhas cobre esses dois.

  • Um único (m15)de agrupamento de formato quadrado não é coberto por nenhum outro agrupamento. Apenas o agrupamento de forma quadrada cobre aquele.

  • Dois uns (m2 & m6)do quarto agrupamento de colunas não são cobertos por nenhum outro agrupamento. Apenas o quarto agrupamento de colunas cobre esses dois.

Portanto, o simplified Boolean function é

f = WX’ + WY + YZ’

Siga estes rules for simplifying K-maps a fim de obter o produto padrão do formulário de somas.

  • Selecione o respectivo K-map com base no número de variáveis ​​presentes na função booleana.

  • Se a função booleana for fornecida como produto da forma de termos Max, coloque os zeros nas respectivas células de termo Max no K-map. Se a função booleana é fornecida como produto da forma de somas, coloque os zeros em todas as células possíveis do K-map para as quais os termos de soma fornecidos são válidos.

  • Verifique as possibilidades de agrupar o número máximo de zeros adjacentes. Deve ser potências de dois. Comece com a maior potência de dois e pelo menos a potência de dois. A maior potência é igual ao número de variáveis ​​consideradas no K-map e a menor potência é zero.

  • Cada agrupamento fornecerá um termo literal ou um termo de soma. É conhecido comoprime implicant. O implicante principal é dito seressential prime implicant, se pelo menos o único '0' não for coberto por nenhum outro agrupamento, mas apenas aquele agrupamento abrange.

  • Anote todos os implicantes primos e implicantes primos essenciais. A função booleana simplificada contém todos os implicantes primos essenciais e apenas os implicantes primos necessários.

Note- Se os termos não importados também estiverem presentes, coloque 'x' não importados nas respectivas células do K-map. Considere apenas os 'x' irrelevantes que são úteis para agrupar o número máximo de zeros adjacentes. Nesses casos, trate o valor irrelevante como '0'.

Exemplo

Deixe-nos simplify a seguinte função booleana, $ f \ left (X, Y, Z \ right) = \ prod M \ left (0,1,2,4 \ right) $ usando K-map.

A função booleana fornecida é um produto da forma de termos máximos. Tem 3 variáveis ​​X, Y e Z. Portanto, precisamos de 3 variáveis ​​K-map. Os termos máximos fornecidos são M 0 , M 1 , M 2 e M 4 . Os 3variable K-map com zeros correspondendo aos termos máximos fornecidos é mostrado na figura a seguir.

Não há possibilidades de agrupar 8 zeros adjacentes ou 4 zeros adjacentes. Existem três possibilidades de agrupar 2 zeros adjacentes. Após esses três agrupamentos, não há um único zero deixado como desagrupado. o3 variable K-map com esses três groupings é mostrado na figura a seguir.

Aqui, temos três implicantes primos X + Y, Y + Z & Z + X. Todos esses implicantes primos são essential porque um zero em cada agrupamento não é coberto por nenhum outro agrupamento, exceto com seus agrupamentos individuais.

Portanto, o simplified Boolean function é

f = (X + Y).(Y + Z).(Z + X)

Desta forma, podemos simplificar facilmente as funções booleanas em até 5 variáveis ​​usando o método K-map. Para mais de 5 variáveis, é difícil simplificar as funções usando o K-Maps. Porque, o número decells no K-map obtém doubled incluindo uma nova variável.

Devido a esta verificação e agrupamento de uns adjacentes (termos mínimos) ou zeros adjacentes (termos máximos) será complicado. Vamos discutirTabular method no próximo capítulo para superar as dificuldades do método K-map.