Dominando Mapas de Karnaugh de 5 e 6 Variáveis para Projeto Lógico Eficiente

À medida que a lógica combinacional cresce, o tamanho do mapa de Karnaugh se expande. Saber quando um mapa de 5 ou 6 variáveis é apropriado – e como interpretar e agrupar suas células – pode reduzir drasticamente o uso de lógica em projetos FPGA e ASIC.

A Altera (agora parte da Intel) examinou milhares de projetos de clientes para entender tamanhos típicos de fan-in. A distribuição resultante foi quase plana de duas a seis entradas, com um pico claro em cinco. Na prática, a maioria dos circuitos usa no máximo seis entradas, e o projeto médio cabe confortavelmente dentro de cinco.

Os próprios dados da Altera, extraídos de sua biblioteca de projetos de clientes, apoiam o valor da heterogeneidade. Ao examinar cones lógicos, mapeá-los em nós baseados em LUT e ordená-los pelo número de entradas que seriam melhores em cada nó, a Altera descobriu que a distribuição de fan-ins era quase plana entre duas e seis entradas, com um belo pico em cinco.

Abaixo está um clássico mapa de Karnaugh de cinco variáveis.

Mapa K de Cinco Variáveis (Mapa de Reflexão)

O estilo de reflexão mais antigo rotula o topo (e, para um mapa de 6 variáveis, o lado) do mapa com código Gray completo. O código Gray é espelhado ao redor do centro do mapa – uma convenção encontrada em muitos textos clássicos. Um layout mais novo e preferido é mostrado a seguir.

Versão Overlay do K-map

O mapa overlay consiste em dois sub-mapas idênticos de 4 células, distinguidos apenas pelo bit mais significativo do endereço de 3 bits no topo. A numeração difere do mapa de reflexão: se o dígito mais significativo for ignorado, a sequência 00, 01, 11, 10 aparece em ambos os sub-mapas. A sequência de oito bits não é código Gray, mas o sufixo de dois bits 01, 10 é.

Vamos aplicar o mapa de cinco variáveis a um problema real: projetar um circuito que aceita uma entrada binária de 5 bits (A = MSB, B, C, D, E) e sai HIGH lógico sempre que o número binário for primo.

Os números primos dentro do intervalo de 5 bits são (1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Marque um 1 em cada célula correspondente, então agrupe os uns. Termine escrevendo a expressão simplificada.

No mapa de reflexão, o grupo de 4 células A'B'E abrange dois pares espelhados, enquanto o grupo de 2 células AB'DE aparece como um par refletido. Ao usar o mapa overlay, procure imagens espelhadas através das duas metades.

Out = A'B'E + B'C'E + A'CDE + A'CD'E + ABCE + AB'DE + A'B'C'D

Abaixo está a versão overlay da mesma expressão.

Comparando os dois mapas, algumas células mudam porque o esquema de endereçamento difere. Sobrepor uma metade sobre a outra revela grupos sobrepostos que guiam a simplificação. Por exemplo, o grupo de 4 células A'B'E cobre o padrão ABCDE = 00xx1, significando A, B e E fixos em 0,0,1 respectivamente enquanto C e D variam.

Um exemplo de mapa de Karnaugh de seis variáveis segue. Empilhando mentalmente os quatro sub-mapas, podemos identificar um grupo de 4 células que implementa Out = C'F'.

Para ilustrar o mapa de 6 variáveis, considere um comparador de magnitude de 3 bits que produz três saídas: igual, maior-que, e menor-que. O comparador recebe duas entradas de 3 bits A₂A₁A₀ e B₂B₁B₀. Para simplificar, resolveremos apenas a saída A > B.

Mapa K de 6 Variáveis

O mapa overlay abaixo auxilia na simplificação da lógica para a saída A > B de um comparador de 3 bits. O código de endereço binário no topo e ao longo do lado esquerdo não é um código Gray completo de 3 bits, mas os códigos de 2 bits de cada um dos quatro sub-mapas são Gray.

Onde ABC excede XYZ, um 1 é plotado. O mapa é preenchido accordingly.

Agrupamento segue estas diretrizes:

• Um grupo de 16 células
• Dois grupos de 8 células
• Quatro grupos de 4 células

O grupo de 16 células AX' ocupa o sub-mapa inferior direito. Dois grupos de 8 células são formados sobrepondo padrões idênticos de 4 células dos sub-mapas superior e inferior. Quatro grupos de 4 células aparecem no mapa; cada um produz um termo de produto. A redução final Soma-de-Produtos contém sete termos.

Contando os 1s, há 28 uns. Antes da redução, a SOP conteria 28 termos de produto de seis entradas cada. O K-map colapsa isso para sete termos de produto de quatro ou menos entradas – uma simplificação dramática.

O diagrama de fiação é omitido, mas aqui está a lista de peças para um comparador de magnitude de 3 bits (A > B) usando componentes da família lógica 4-TTL:

• 1 × 7410 tripla porta NAND de 3 entradas (AX', ABY', BX'Y')
• 2 × 7420 dual porta NAND de 4 entradas (ABCZ', ACY'Z', BCX'Z', CX'Y'Z')
• 1 × 7430 porta NAND de 8 entradas (para a saída final de 7 termos)

Revisão

• Álgebra booleana, mapas de Karnaugh e CAD são ferramentas essenciais para simplificação lógica.
• Uma solução de custo mínimo usa o menor número de portas com o menor número de entradas.
• Diagramas de Venn ajudam a visualizar expressões booleanas antes de traduzi-las para K-maps.
• Células de K-map são organizadas em código Gray, revelando redundâncias que permitem simplificação.
• Expressões Soma-de-Produtos (SOP) são tipicamente implementadas como portas AND alimentando uma única porta OR.
• SOP pode ser realizada com lógica NAND-NAND substituindo ANDs e ORs por NANDs.
• Produto-de-Somas (POS) é menos comum mas pode ser implementado com portas OR alimentando uma única porta AND, baseada nos 0s do mapa (maxtermos).