Określanie minimalnej liczby bramek NAND / NOR wymaganych do realizacji wyrażenia logicznego

Czy istnieje algorytm określający minimalną liczbę bramek NAND lub NOR

1. podana liczba wejść
2. dostępność / niedostępność uzupełnionego wejścia

wymagane do realizacji wyrażenia logicznego? Możemy uzyskać formę AND-OR jako główne implanty za pomocą map Karnaugh, która jest minimalna (o ile mi wiadomo, algorytm Quine-McCluskey uzyskuje je deterministycznie). Czy podobna technika istnieje również w przypadku implementacji NAND lub NOR? Przynajmniej taka technika powinna określić wymaganą minimalną liczbę bramek NAND / NOR, nawet bez znalezienia faktycznego schematu?

Stosowanie prawa De Morgana do głównych implantów nie wydaje się deterministyczne,

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)']

Minimalną liczbę bramek można znaleźć tylko w sieci wielopoziomowej, rozwiązując problem z programowaniem liczb całkowitych [lub odpowiedniki, patrz poniżej]. Ten problem jest NP-zupełny, więc praktyczne jest rozwiązanie tylko kilkunastu bramek.

Istnieją metody aproksymacyjne, które nie dają minimalnej liczby, ale są łatwiejsze do opanowania pod względem wymaganego czasu ... Są to same w sobie obszerne tematy, w zasadzie całe pole optymalizacji wielopoziomowej. Można przeczytać [Free] przegląd tutaj .

W przypadku małych sieci NAND (do 4 zmiennych) problem został całkowicie rozwiązany przez wyczerpujące wyliczenie [lub równoważne metody]. Istnieje dość niedawna rozprawa doktorska [2009] Elizabeth Ann Ernst, która podsumowuje starożytne wyniki i je rozszerza. Ernst używa rozgałęzień, co poprawia wyczerpującą metodę w praktyce, ale nie asymptotycznie. Zauważa również, że inne metody wyliczania domyślnego, takie jak programowanie liczb całkowitych lub CSP (spełnienie ograniczeń, rozwiązane przez SAT) działają gorzej w praktyce.

Oczywiście napisała oprogramowanie dla swojej metody (zwane BESS), ale nie jestem pewien, czy jest to gdzieś publicznie dostępne. Pełny tekst jej pracy dyplomowej jest dostępny bezpłatnie na stronie umich . I rzeczywiście znalazłeś minimalne wyrażenie dla xor 2-wejściowych (oczywiście twój drugi), ten wyróżniony poniżej:

Porównała również dokładne wyniki (dla NAND) z wynikami heurystycznego optymalizatora z ABC .

ABC udało się stworzyć optymalną sieć dla 340 z 4043 funkcji, w których znana jest optymalna sieć. Dla tych funkcji, w których ABC nie stworzył optymalnej sieci, była ona średnio o 36% większa niż optymalna sieć [.]

Istnieją (oczywiście) niektóre [większe] sieci, dla których BESS nie zakończył, ale umożliwił znalezienie górnej granicy (w punkcie, w którym wyszukiwanie zostało porzucone). Dla tych ABC wypadło całkiem dobrze [dobrze w odniesieniu do znalezionych granic], jak widać na drugim wykresie poniżej.

Prawdopodobnie istnieją lepsze techniki, ale w czasach, gdy w średniowieczu odkryłem, że Karnaugh Maps działa dobrze

NAND, po której następuje NAND, jest równoważne AND, po której następuje OR.

NOR, po której następuje NOR, jest równoważne OR, po której następuje AND.

NAND, po którym następuje NOR, będzie równoznaczne z AND, a po nim AND, co tak naprawdę nie ma większego sensu. NOR, po której następuje NAND, będzie podobnie równoważne OR, a następnie OR.

Nie wierzę, że w ogólnym przypadku istnieje jakikolwiek możliwy sposób na znalezienie minimalnego rozwiązania problemu z dużą liczbą danych wejściowych (oczywiście w przypadku niewielkiej liczby danych wejściowych można użyć siły). Quine-McClusky patrzy tylko na rozwiązania dwupoziomowe (minimalne rozwiązanie dwupoziomowe często nie jest ogólnym rozwiązaniem minimalnym) i może stać się niewykonalne obliczeniowo ze złożonymi tabelami prawdy i dużą liczbą danych wejściowych.

Najlepszym algorytmem jest algorytm Espresso . W pewnym stopniu jest to zaimplementowane w syntezie FPGA

Logic Friday to oprogramowanie, którego możesz użyć. UWAGA: zmniejsza to XOR do 5 bramek NAND.