Editing Logic synthesis (section)

== History ==
The roots of logic synthesis can be traced to the treatment of logic by [[George Boole]] (1815 to 1864), in what is now termed [[Boolean algebra (logic)|Boolean algebra]]. In 1938, [[Claude Elwood Shannon|Claude Shannon]] showed that the two-valued [[Boolean algebra]] can describe the operation of switching circuits.  In the early days, '''logic design''' involved manipulating the [[truth table]] representations as [[Karnaugh map]]s. The Karnaugh map-based minimization of logic is guided by a set of rules on how entries in the maps can be combined. A human designer can typically only work with Karnaugh maps containing up to four to six variables.

The first step toward automation of [[logic minimization]] was the introduction of the [[Quine&ndash;McCluskey algorithm]] that could be implemented on a computer. This exact minimization technique presented the notion of prime implicants and minimum cost covers that would become the cornerstone of [[two-level minimization]]. Nowadays, the much more efficient [[Espresso heuristic logic minimizer]] has become the standard tool for this operation.{{update inline|date=May 2017|reason=This correctly describes the situation around 1995. We need to expand this to include the changes of the past twenty years.}} Another area of early research was in state minimization and encoding of [[finite-state machine]]s (FSMs), a task that was the bane of designers. The applications for logic synthesis lay primarily in digital computer design. Hence, [[IBM]] and [[Bell Labs]] played a pivotal role in the early automation of logic synthesis. The evolution from [[discrete logic]] components to [[programmable logic array]]s (PLAs) hastened the need for efficient two-level minimization, since minimizing terms in a two-level representation reduces the area in a PLA.

Two-level logic circuits are of limited importance in a [[very-large-scale integration]] (VLSI) design; most designs use multiple levels of logic. Almost any circuit representation in RTL or Behavioural Description is a multi-level representation. An early system that was used to design multilevel circuits was LSS from IBM. It used local transformations to simplify logic. Work on LSS and the Yorktown Silicon Compiler spurred rapid research progress in logic synthesis in the 1980s. Several universities contributed by making their research available to the public, most notably SIS from [[University of California, Berkeley]], RASP from [[University of California, Los Angeles]] and BOLD from [[University of Colorado, Boulder]]. Within a decade, the technology migrated to commercial logic synthesis products offered by electronic design automation companies.