Podręcznik

Minimalizacja funkcji boolowskich jest zagadnieniem intensywnych prac badawczych od początku lat 50. XX wieku. Później, w latach 70. pojawienie się układów scalonych średniej i wielkiej skali integracji spowodowało wyraźne zmniejszenie zainteresowania tym problemem. Ale ponowny wzrost zainteresowania minimalizacją funkcji boolowskich powstał w latach 80. Bezpośrednią przyczyna tej sytuacji stała się możliwość realizacji układów logicznych w strukturach scalonych o złożoności milionów bramek logicznych.

Najbardziej znaną i powszechnie stosowaną metodą graficzną jest metoda tablic Karnaugha. Klasyczną metodą analityczną jest metoda Quine’a – McCluskey’a. Obie metody opracowane zostały w połowie lat 50. XX wieku. Niestety zarówno metoda Karnugha, jak też Quine’a – McCluskey’a  nie są przystosowane do wymagań dzisiejszych technologii.

Wadą pierwszej jest graficzny sposób obliczeń ograniczający z natury liczbę zmiennych minimalizowanych funkcji, natomiast w przypadku drugiej barierą ograniczająca jest złożoność  obliczeniowa stosowanych algorytmów.

Dlatego powstały nowe, całkowicie odmienne metody syntezy dwupoziomowej. Przede wszystkim znalazły one zastosowanie w klasycznym już algorytmie ESPRESSO opracowanym na Uniwersytecie Kalifornijskim w Berkeley w latach 80. Znajdują one minimalne lub suboptymalne rozwiązania nawet dla bardzo skomplikowanych zadań. Syntezie mogą być poddawane zespoły nie w pełni określonych funkcji boolowskich, o wielowartościowych wejściach i o setkach argumentów, a czas obliczeń jest stosunkowo krótki.