Minimização de Nível de Gate – DE Parte 7

No tutorial anterior, todos os possíveis funções booleanas entre duas variáveis ​​foram discutidas. No tutorial – Álgebra Booleana, foram declarados vários teoremas e postulados que são úteis para simplificar uma expressão ou função booleana. No entanto, a simplificação de uma expressão booleana utilizando teoremas e postulados é bastante complicada e sujeita a erros. Portanto, para simplificação de expressões booleanas, alguns métodos de mapas foram desenvolvidos. O método de mapa mais comumente usado é Karnaugh Map ou K-Map.

Esses métodos são baseados no fato de que cada função booleana possui uma tabela verdade única. Uma função booleana pode ser representada por diversas expressões booleanas, mas sua tabela verdade permanecerá sempre a mesma. Isto se deve ao fato de que um circuito digital sempre terá saídas fixas ou resposta correspondente às entradas. Vamos primeiro discutir o K-map.

Mapa de Karnaugh –

O mapa de Karnaugh é a técnica de simplificação mais comum para expressões booleanas. Baseia-se nos seguintes fatos –

1) Qualquer função booleana, entretanto, pode ser representada em várias formas ou expressões booleanas sempre têm uma tabela verdade única. Se duas expressões booleanas tiverem a mesma tabela verdade, elas terão a mesma função.

2) Qualquer função booleana pode ser representada por soma de produtos (Mintermos) ou produto de somas (Maxtermos).

3) A soma dos Mintermos ou produto dos Maxtermos é redutível pela aplicação de vários teoremas booleanos.

O K-map é basicamente uma representação tabular da tabela verdade. Por exemplo, uma função de duas variáveis ​​pode ter a seguinte tabela verdade –

Seu K-map tabulará as saídas da função correspondentes aos valores das variáveis ​​​​de entrada como segue –

Um mapa K de duas variáveis

Figura 1: Um mapa K de duas variáveis

K-Map é útil para minimizar expressões booleanas contendo até 5 variáveis ​​ou menos. Uma vez construído o mapa, a expressão minimizada pode ser deduzida pelo seguinte processo –

1) Insira 1s nas células correspondentes às combinações para as quais o valor da função é 1 na tabela verdade. Em seguida, preencha 0s nas células restantes do K-map. Cada célula do mapa representa um Minterm. A função booleana representada pelo mapa (o mapa é apenas uma representação gráfica da tabela verdade) é a soma dos mintermos que podem conter uma ou mais variáveis ​​booleanas como literais.

2) Examine o mapa em busca de células de valor 1 que não podem ser combinadas com nenhuma outra célula de valor 1 ou forme grupos com outras células de valor 1. Isso significa identificar células com valor 1 que não possuem células adjacentes com valor 1. Esses grupos representam mintermos contendo todas as variáveis ​​booleanas como literais no termo como parte da função booleana.

3) Examine o mapa para células com valor 1 que são adjacentes apenas umas às outras células com valor 1 e formem grupos contendo apenas duas células com valor 1, mas não fazem parte de nenhum grupo contendo quatro ou oito células com valor 1. Esses grupos representam mintermos contendo variáveis ​​booleanas como literais um a menos que o número máximo de variáveis ​​booleanas no termo como parte da função. Esses grupos são chamados de pares.

4) Examine o mapa em busca de células com valor 1 que sejam adjacentes a apenas três outras células com valor 1 e formem grupos contendo apenas quatro células com valor 1, mas não façam parte de nenhum grupo contendo oito células com valor 1. Esses grupos representam mintermos contendo variáveis ​​booleanas como literais dois a menos que o número máximo de variáveis ​​booleanas no termo como parte da função. Esses grupos são chamados de quads. Em uma função de 2 variáveis, a formação de quad significa que a saída da função é 1.

5) Examine o mapa em busca de células com valor 1 que sejam adjacentes a sete outras células com valor 1 e formem grupos contendo oito células com valor 1, mas que não façam parte de nenhum grupo contendo dezesseis células com valor 1 ou superior. Esses grupos representam mintermos contendo variáveis ​​booleanas como literais três a menos que o número máximo de variáveis ​​booleanas no termo como parte da função. Esses grupos são chamados de octetos. Em uma função de 3 variáveis, a formação do octeto significa que a saída da função é 1.

6) Forme todos os grupos de simples, pares, quádruplos e octetos de forma que haja um número mínimo de grupos. Os pares, quádruplos e octetos também podem ser formados com a combinação de células de valor 1 em bordas opostas do mapa. Como no mapa K a seguir para função booleana de 3 variáveis, m0 e m8 nos cantos estão formando um par.

Um mapa K de três variáveis

Figura 2: Um mapa K de três variáveis

7) Remova quaisquer grupos redundantes.

8) Uma célula com valor 1 sem nenhuma célula adjacente com valor 1 fornece um Minterm contendo 2, 3, 4, 5 termos variáveis ​​para função booleana de 2 variáveis, 3 variáveis, 4 variáveis ​​e 5 variáveis ​​ou mapa K respectivamente . Um par de células com valor 1 fornece um Minterm contendo 1, 2, 3, 4 termos variáveis ​​para função booleana de 2 variáveis, 3 variáveis, 4 variáveis ​​e 5 variáveis ​​ou mapa K, respectivamente. Um quádruplo de células com valor 1 fornece um Minterm contendo 1, 2, 3 termos variáveis ​​para função booleana de 3 variáveis, 4 variáveis ​​e 5 variáveis ​​ou mapa K, respectivamente. A formação de quad para uma função de 2 variáveis ​​significa que é igual a 1. Um octeto de células com valor 1 fornece um Minterm contendo 2 ou 3 termos variáveis ​​para função booleana de 4 e 5 variáveis ​​ou mapa K, respectivamente. A formação do octeto para uma função de 3 variáveis ​​significa que é igual a 1.

9) Se uma única célula com valor 1 for identificada, ela representa um Minterm tendo a variável booleana como literal no termo for correspondente ao valor 1 para a respectiva variável booleana e/ou tendo complemento da variável booleana como literal no termo for foi correspondido ao valor 0 para a respectiva variável booleana. Essa célula com valor 1 induzirá um Minterm na função contendo todas as variáveis ​​​​booleanas na forma complementar ou normal. Se um par for identificado, uma variável booleana será eliminada e um Minterm contendo um número a menos de variáveis ​​booleanas máximas será induzido na função booleana. Da mesma forma, um quad leva à eliminação de duas variáveis ​​booleanas no Minterm e assim por diante. A variável booleana que tem uma mudança de bit dentro do par, quádruplo ou octeto é eliminada no termo.

10) A função booleana é a soma lógica dos Mintermos gerados por todos os grupos. A função booleana como produto da soma pode ser gerada de forma semelhante por grupos de 0s.

Mapa K de duas variáveis

Um mapa K de duas variáveis ​​possui quatro células, pois o número máximo de mintermos possíveis com duas variáveis ​​booleanas é 4 (2 ^ 2). Pode haver no máximo 16 funções (2^2*2) geradas por duas variáveis ​​booleanas.

K-Map e Mintermos de Duas Variáveis

Figura 3: K-Map e Mintermos de Duas Variáveis

Uma função gerada por um mapa K de duas variáveis ​​é redutível por células ou pares únicos de valor 1. A formação de um quad no mapa K de duas variáveis ​​significa que a função é igual a 1.

Mapa K de três variáveis

Um mapa K de três variáveis ​​possui oito células, pois o número máximo de mintermos possíveis com três variáveis ​​booleanas é 8 (2 ^ 3). Pode haver no máximo 64 funções (2^2*3) geradas por três variáveis ​​booleanas.

K-Map e Mintermos de três variáveis

Figura 4: K-Map e Mintermos de três variáveis

Uma função gerada por um mapa K de três variáveis ​​é redutível por células únicas de valor 1, pares ou quádruplos. A formação de um octeto no mapa K de três variáveis ​​significa que a função é igual a 1.

Mapa K de quatro variáveis

Um mapa K de quatro variáveis ​​tem dezesseis células, pois o número máximo de mintermos possíveis com quatro variáveis ​​booleanas é 16 (2 ^ 4). Pode haver no máximo 256 funções (2^2*4) geradas por quatro variáveis ​​booleanas.

K-Map de quatro variáveis ​​e mintermos

Figura 5: Mapa K de quatro variáveis ​​e mintermos

Uma função gerada por um mapa K de quatro variáveis ​​é redutível por células únicas de valor 1, pares, quádruplos ou octetos. A formação de 16 células de valor único no mapa K de quatro variáveis ​​significa que a função é igual a 1.

Mapa K de cinco variáveis

Um mapa K de cinco variáveis ​​tem trinta e duas células, pois o número máximo de mintermos possíveis com cinco variáveis ​​booleanas é 32 (2 ^ 5). Pode haver no máximo 1.024 funções (2^2*5) geradas por cinco variáveis ​​booleanas.

K-Map de cinco variáveis ​​e mintermos

Figura 6: Mapa K de cinco variáveis ​​e mintermos

Uma função gerada por um mapa K de cinco variáveis ​​​​é redutível por células únicas de valor 1, pares, quádruplos, octetos ou grupo de 16 células de valor 1. A formação de 32 células de valor único em um mapa K de cinco variáveis ​​significa que a função é igual a 1.

Não me importo com combinações

Não é necessário que todas as saídas de uma função booleana sejam sempre conhecidas. Em circuitos digitais, pode haver a possibilidade de, para certas combinações, a saída ser 1 ou 0. Nesse caso, d, x ou Ø é inserido no mapa K para as combinações de entrada correspondentes. Para derivar a expressão booleana, 1 ou 0 pode ser assumido em combinações indiferentes para deduzir uma soma mínima de produtos ou produto da expressão de soma.

Método Quine-McCluskey

O K-map é útil na dedução de expressões booleanas envolvendo quatro variáveis ​​booleanas ou menos. Além disso, fica complexo. Portanto, outro método denominado método Quine-McCluskey é usado para deduzir expressões booleanas envolvendo quatro ou mais variáveis ​​​​booleanas. O método Quine-McCluskey é um método tabular para derivar a expressão booleana mínima. Na tabela verdade de uma função booleana, podem ser listadas as combinações para as quais a saída da função é 1. Essas combinações podem ser indexadas em ordem crescente como números binários. Por exemplo, suponha que exista uma função booleana envolvendo quatro variáveis ​​booleanas (A, B, C, D) com a seguinte tabela verdade –

As combinações resultantes em 1 ao serem indexadas em ordem crescente como números binários fornecem a tabela a seguir para o caso acima

Esta função booleana pode ser escrita da seguinte forma –As combinações resultantes em 1 ao serem indexadas em ordem crescente como números binários fornecem a seguinte tabela para o caso acima –

F (A, B, C, D) = ∑ (0, 5, 8, 9, 10, 11, 14, 15)

No primeiro passo de Quine-McCluskey método, os mintermos são organizados em grupos pelo número de 1s neles como segue –

Quaisquer dois mintermos em grupos adjacentes como grupo 0 e 1, grupo 1 e 2 ou grupo 2 e 3 e assim por diante são agora comparados e examinados quanto à mudança no valor de apenas uma variável booleana. Tais mintermos são selecionados como corresponder e tabulados como pares na próxima etapa com um travessão lugar onde solteiro a variável booleana mudou para a correspondência como a seguir –


Na próxima etapa, as partidas nos grupos adjacentes de mesa na etapa 2 são comparados e examinados para traço para a mesma variável e alteração no valor de apenas uma variável booleana. Essas correspondências são selecionadas como quadras e tabuladas na tabela seguinte com um travessão lugar onde solteiro variável booleana foi alterada para a partida. Os pares na segunda tabela e os mintermos na primeiro tabelas que não foram correspondidas nas respectivas tabelas também são tabuladas na próxima tabela (terceira tabela) como segue –

Os quádruplos, pares ou simples derivados na terceira tabela (removendo os redundantes) são chamados de implementos principais. Na próxima etapa, os implementos principais são tabulados em relação aos mintermos e os mintermos incluídos no respectivo implemento principal (quádruplo, par ou único) são marcados por X em relação ao respectivo implemento principal como segue –

Na tabela final, as colunas que possuem um único X são examinadas e as linhas que contêm esse X são identificadas. Os implementos principais respectivos a essas linhas são anotados e os termos respectivos a esses implementos principais são incluídos como soma de produtos na expressão booleana por comparação de implementos principais e variáveis ​​booleanas da terceira tabela. Na terceira tabela, a variável booleana contra o implemento principal selecionado com valor traço não é incluída, a variável booleana contra o implemento principal selecionado com valor 1 é incluída na forma normal no respectivo termo e a variável booleana contra o implemento principal selecionado com valor 0 é incluído em elogio formulário no respectivo termo. Os implementos principais selecionados de quarto tabela são chamados de implementos essenciais. Para a função booleana acima, na quarta tabela, todas as linhas são tendo um X que é único em pelo menos uma coluna. Portanto, todas as linhas são selecionadas e todos os implementos principais são implementos essenciais para a função booleana. De terceiro tabela, a expressão booleana para a função pode ser derivada da seguinte forma –

F (A, B, C, D) =AB' + AC + B'C'D' + A'BC'D

Agora, com o conhecimento do K-map e do método Quine-McCluskey, qualquer função booleana com uma determinada tabela verdade pode ser facilmente minimizada. No próximo tutorial, aprenda sobre lógica implementação de portão de uma expressão booleana minimizada.

Conteúdo Relacionado

Qual o papel dos sensores automotivos nos veículos modernos?
Uma rede de sensores é incorporada em todos os...
Como escolher um controlador de e-bike
O controlador do motor é um dos componentes mais...
Como solucionar problemas comuns do ESP32-CAM
ESP32-CAM é um módulo de câmera compacto que combina...
Um guia para padrões USB de 1.0 a USB4
A evolução dos padrões USB foi fundamental para moldar...
Schurter aprimora série de seletores de tensão com revestimento prateado
A SCHURTER anuncia um aprimoramento para sua conhecida série...
A interface serial PCI fornece conectividade confiável em ambientes extremos
A Sealevel Systems anuncia o lançamento da Interface Serial...
STMicroelectronics expande portfólio de conversão de energia com diodos Trench Schottky de 100 V
A STMicroelectronics introduziu Diodos retificadores Schottky de trincheira de...
O que são Sistemas Globais de Navegação por Satélite (GNSS) e como são usados?
Determinar uma localização precisa é necessário em várias indústrias...
O conversor GaN de 50 W da STMicroelectronics permite projetos de energia de alta eficiência
O novo VIPerGaN50 da STMicroelectronics simplifica a construção de...
Samsung e Red Hat farão parceria em software de memória de próxima geração
A Samsung Electronics, fornecedora de tecnologia de memória avançada,...
Primeiro MPU single-core com interface de câmera MIPI CSI-2 e áudio
O mercado embarcado tem uma necessidade de soluções de...
Decodificação de fluência no motor de indução para melhor desempenho
Você provavelmente já se deparou com o termo 'arrastar'...
Compreendendo os isoladores de suporte em sistemas elétricos
Você provavelmente tem um Isolador de suporte Se você...
Explore Stay Insulator – segurança, instalação e manutenção
Você provavelmente já viu permanecer um isolante sente-se em...
Mais segurança e eficiência com o isolador de manilha
Você provavelmente já viu Isoladores de manilha entronizados em...
Descubra o poder dos relés de travamento para eficiência energética e muito mais
Você provavelmente já passou por situações em que o...
Voltar para o blog

Deixe um comentário

Os comentários precisam ser aprovados antes da publicação.