Determinando o número mínimo de portas NAND / NOR necessárias para realizar uma expressão booleana

9

Existe algum algoritmo para determinar o número mínimo de portas NAND ou NOR com

  1. determinado número de entradas
  2. disponibilidade / indisponibilidade de insumos complementados

necessário para realizar uma expressão booleana? Podemos obter um formulário AND-OR como implicantes primários via mapas de Karnaugh que é mínimo (tanto quanto eu sei, o algoritmo Quine-McCluskey os obtém deterministicamente). Existe uma técnica semelhante também para implementações NAND ou NOR? Pelo menos, essa técnica deve determinar o número mínimo necessário de portas NAND / NOR, mesmo sem encontrar o diagrama real?

A aplicação da lei de De Morgan aos principais implicantes não parece determinística,

A ⊕ B = A'B + AB' = ((A'B)'(AB')')' [5 NAND gates]
A ⊕ B = (AB + A'B')' = ((ABAB+ABB') + (A'AB+A'B'))' = (AB(AB+B') + A'(AB+B'))' = ((AB+A')(AB+B'))' = (((AB)'A)'((AB)'B)')' [4 NAND gates by reusing (AB)']
Samik
fonte
Isso é para uma implementação de dois estágios ou vários estágios?
Fizz
@RespawnedFluff O objetivo da implementação em vários níveis é minimizar o número de portas, portanto a implementação mínima da NAND / NOR também deve ser em vários níveis.
Samik
O K-map não oferece resultados mínimos para otimização em vários níveis.
Fizz

Respostas:

10

Você pode encontrar apenas o número mínimo de portas em uma rede de vários níveis, resolvendo um problema de programação inteira [ou equivalente, veja abaixo]. Esse problema é NP-completo, portanto, apenas prático para resolver até uma dúzia de portas.

Existem métodos de aproximação que não fornecem o número mínimo, mas são mais tratáveis ​​em termos de tempo necessário ... Esses são um tópico vasto em si, basicamente todo o campo da otimização em vários níveis. Você pode ler uma visão geral [gratuita] aqui .

Para pequenas redes de NAND (até 4 variáveis), o problema foi completamente resolvido por enumeração exaustiva [ou métodos equivalentes]. Há uma tese de doutorado de Elizabeth Ann Ernst [2009] bastante recente que resume os resultados antigos e os estende. Ernst usa ramificação e vinculação, o que melhora o método exaustivo na prática, mas não assintoticamente. Ela também observa que outros métodos de enumeração implícita, como programação inteira ou CSP (satisfação de restrição, resolvida via SAT), apresentam desempenho pior na prática.

Ela obviamente escreveu algum software para seu método (chamado BESS), mas não tenho certeza se ele está disponível publicamente em algum lugar. O texto completo de sua tese está disponível gratuitamente em umich . E, de fato, você encontrou a expressão mínima para xor de 2 entradas (sua segunda obviamente), a destacada abaixo:

insira a descrição da imagem aqui

Ela também comparou os resultados exatos (para NANDs) com os produzidos pelo otimizador heurístico da ABC .

A ABC conseguiu produzir uma rede ideal para 340 das 4.043 funções em que a rede ideal é conhecida. Para aquelas funções em que o ABC não produziu uma rede ótima, era em média 36% maior que a rede ótima [.]

Existem (obviamente) algumas redes [maiores] para as quais o BESS não terminou, mas permitiu que um limite superior fosse encontrado (no ponto em que a pesquisa foi abandonada). Para aqueles que a ABC se saiu muito bem [bem com relação aos limites encontrados], como você pode ver no segundo gráfico abaixo.

insira a descrição da imagem aqui

Efervescer
fonte
Se você está curioso, eu tentei o ABC no problema xor ... e dá 5 portas, pelo menos com o resyn2script. Portanto, não é melhor que o Logic Friday (que usa misII).
Fizz
Existem scripts e bancos de dados para o ABC que basicamente pesquisam uma grande quantidade de funções para implementações ideais pré-calculadas, por exemplo: arxiv.org/pdf/1108.3675.pdf Eu não tentei esse, mas mesmo que funcione, o trabalho duro foi feito em outro lugar.
Fizz
Estou revisando os materiais que você forneceu e eles parecem muito interessantes, mas estou lutando para entendê-los. Depois de entendê-los adequadamente, provavelmente atribuirei a recompensa. Enquanto isso, faça um voto positivo.
Samik 7/12/15
1

Provavelmente existem técnicas melhores por aí, mas quando, na idade das trevas, eu achei o Karnaugh Maps funcionando muito bem

R Drast
fonte
Você se importaria de lançar alguma luz sobre a "idade das trevas" sobre como proceder para a implementação mínima NAND / NOR da implementação AND-OR obtida nos mapas de Karnaugh?
Samik
1

NAND seguido por NAND é equivalente a AND seguido por OR.

NOR seguido por NOR é equivalente a OR seguido por AND.

NAND seguido por NOR seria equivalente a AND seguido por AND, o que realmente não faz muito sentido. NOR seguido por NAND seria similarmente igual a OR seguido por OR.

Eu não acredito que, no caso geral, exista uma maneira viável de encontrar uma solução mínima para um problema com um grande número de entradas (obviamente, para pequenas contagens de entrada, você pode usar força bruta). Quine-McClusky analisa apenas soluções de dois níveis (a solução mínima de dois níveis geralmente não é a solução mínima geral) e pode se tornar inviável computacionalmente com tabelas verdadeiras complexas e grande número de entradas.

Peter Green
fonte
Portanto, não há maneira melhor do que a troca de bolhas?
Samik
1

O melhor algoritmo é o algoritmo Espresso . Até certo ponto, isso é implementado na síntese do FPGA

Sexta-feira lógica é um software que você pode usar. NOTA: isso reduz um XOR para 5 portas NAND.

JonRB
fonte
Mas o Espresso também fornece a implementação AND-OR, não é?
Samik
11
O café expresso é "melhor" apenas no sentido em que é viável para entradas grandes (fórmulas) [ao contrário dos k-maps], mas não fornece a melhor / mínima fórmula em todos os casos.
Fizz