Terminology

一、Terminology

1.1 Logic (Boolean) function

• Boolean Satisfiability

alt text

• literals, variable, clauses
• minterms, maxterms
• cubes

alt text

bcd' = 1, b' + c' + d = 0, f(a, b, c, d) = 0

• Completely specified logic function

alt text

• Incompletely specified logic function

alt text

• onset

alt text

• offset

alt text

• DCset

alt text

1.2 logic network

• Primary inputs(PI), Primary outputs(PO)
• Logic nodes
• Fanins / Fanouts
• Transitive fain /fanout cone
• Re-convergent paths

alt text

• Cut

alt text

alt text

• Window

alt text

• Bitwise Simulation

alt text

• MFFC (a set of nodes which no paths to PO if target node is removed)

1.3 Representation Overview

• Truth Table(TT) are the natural representation of logic functions

  • Not practical for large functions

  • Still good for functions up to 16 variables

• SOP is widely used in synthesis tools since 1980’s
  • More compact than TT, but not canonical
  • Can be efficiently minimized (SOP minimization by Espresso, ISOP computation) and translated into multi-level forms (algebraic factoring)
• BDD is a useful representation discovered around 1986
  • Canonical (for a given function, there is only one BDD)
  • Very good, but only if (a) it can be constructed, (b) it is not too large
  • Unreliable (non-robust) for many industrial circuits
• AIG is an up-and-coming representation!
  • Compact, easy to construct, can be made “canonical” using a SAT solver
  • Unifies the synthesis/mapping/verification flow
  • The main reason to give this talk

alt text

What Representation to Use? - For small functions (up to 16 inputs) - TT works the best (local transforms, decomposition, factoring, etc.) - For medium-sized functions (16-100 inputs) - In some cases, BDDs are still used (reachability analysis) - Typically, it is better to represent as AIGs - Translate AIG into CNF and use SAT solver for logic manipulation - Sometimes need interpolation or SAT assignment enumeration - For large industrial circuits (>100 inputs, >10,000 gates) - Traditional LN representation is not efficient - AIGs work remarkably well - Lead to efficient synthesis - Are a natural representation for technology mapping - Easy to translate into CNF for SAT solving - Etc

What are Typical Transformations? - Typical transformations of representations - For SOP, minimize cubes/literals - For BDD, minimize nodes/width - For AIG, restructure, minimize nodes/levels - For LN, restructure, minimize area/delay

Referenced

https://cc.ee.ntu.edu.tw/~jhjiang/instruction/courses/fall14-lsv/lec01-abc_2p.pdf