Existe algum algoritmo para determinar o número mínimo de portas NAND ou NOR com
- determinado número de entradas
- 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)']
logic-gates
boolean-algebra
Samik
fonte
fonte
Respostas:
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:
Ela também comparou os resultados exatos (para NANDs) com os produzidos pelo otimizador heurístico da ABC .
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.
fonte
resyn2
script. Portanto, não é melhor que o Logic Friday (que usa misII).Provavelmente existem técnicas melhores por aí, mas quando, na idade das trevas, eu achei o Karnaugh Maps funcionando muito bem
fonte
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.
fonte
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.
fonte