# Very Large Scale Integration CAD — Part I — Logic

Это конспект очередного курса, который я прошел на Coursera. Курс называется VLSI CAD Part I: Logic от Иллинойсского университета в Урбане-Шампейне. Автор курса — Rob A. Rutenbar. Курс посвящен комбинационной логике: минимизации логических функций, оптимизации логических схем и пр. Ниже, как обычно, краткий набор ключевых слов и тезисов, которые помогут мне (или тому, кто пройдет этот курс) быстро восстановить его в памяти.

## Shannon Cofactors Fx Fx’

Shannon Expansion `F = x*Fx + x'Fx'`
`dF/dx = Fx XOR Fx'`
universal quantification `(forany x F)[y z w ...] = Fx * Fx'`
existential quantification `(exists x F)[y z w ...] = Fx + Fx'`
Network `F(a, b, c)` repair: replace suspected gate with MUX and connect through `EXNOR` gate with the known good version of logic. Now `(forany abc F)[d0 d1 d2 d3]` will give you the right data inputs for the MUX.

## Positional Cube Notation (PCN)

x  = 01
x' = 10
don't care = 11
a  b  c     a  b  c
Example: F(a, b, c) = ab' + bc' = [01 10 11], [11 01 10]
Fa = [11 10 11], [11 01 10]
Fa' = [11 01 10]

Unate function: SOP (sum of prodicts) has each literal in exactly one polarity.
Otherwise the function is called binate.
Recursive tautology checking: pick «the most binate variable» to make unate cofactors. Check each cofactor for tautology.
`[11 11 11] = tautology`

—————————————————————-

## Binary Decision Diagrams (BDD)

x1
/  \
/    \
x2      x2
/  \    /  \
x3  x3  x3  x3
\   |  |   /
\  |  |  /
1 0  1 0

Reduced Ordered BDD (ROBDD)
Merge equivalent leaves
Merge isomorphic nodes (i. e. with same variable and identical children)
Eliminate redundant tests
Software utility: kbdd (eval, verify, satisfy, etc.)
Satisfiablity problem is easily solved with BDDs (if there is a path from 1 to the top of BDD).
BDD sharing, multi-rooted BDD
Each logical operation produces a new BDD: bdd OP(bdd F, bdd G);
Variable ordering selection heuristic: related inputs should be near each other in order; groups of inputs that can determine function by themselves should be (i) close together, and (ii) near the top of BDD.

—————————————————————-

## SAT — Satisfiablity

Find a combination of inputs that makes F(x, y, z, w, …) = 1 or prove that there’s no such combination.
Usage: network repair: find d0, d1, d2, d3 MUX data inputs such that for any a, b exnor = 1 …gives us Z(d0, d1, d2, d3) function.
Conjunctive Normal Form (CNF) — Product of Sums (POS)
Example of CNF: F = (a + c)(b + c)(a’ + b’ + c’)
Solving SAT problem: «Boolean Constraint Propagation (BCP)» go through BDD recursively to find a branch leading to 1.
Software utility: MiniSAT

## Gate consistency function

Consistency function for z = !x: (x + z)(x’ + z’)
Simple formulas for getting CNF for all common logic gates: NOR, OR, NAND, AND, NOT.
Consistency function for a boolean logic network: give names to all nodes and build a product of all consistency functions for all nodes.
SAT function for a boolean logic network equals its consistency function times its output.

—————————————————————-

## 2-Level Minimization of logic network

«Prime implicant» or just «a prime» — a cube (product term) that cannot be made any bigger.
Reduce-Expand-Irredundant Optimization Loop.
Karnaugh map.

2. Expand each cube to be prime (by removing literals from it and seeng if the cube is still covered by the function).
3. Remove redundant cubes.
4. Reduce: shrink each cube as much as possible (some cubes may become nonprime).
5. go to step 2

Software utility: ESPRESSO

## Expansion algorithm

Assuming we have a function F.
Build cube cover for F’ (use URP complement algorithm or a Karnaugh map) — this is called the «OFF set».
Build a «blocking matrix»:
row headers — literals in the cube that we want to expand
column headers — cubes in F’
put 1 in the cells where polarity of a [literal] is different from that in the [cube]
Covering problem: find the rows that together touch all columns.
Now you may remove from the cube that you want to expand all literals that are not in the cover.

—————————————————————-

## Multilevel logic

Fewer gates than 2-Level logic.
Boolean Logic Network: each node is 2-level logic.
Goal: save literals.
It’s all about extracting common divisors from several nodes.
Transit to algebraic model: get rid of complements (x’) — replace them with new variables: `F = ab + a'x + b'y. Let R=a' Let S=b'. F = ab + Rx + Sy.`
Algebraic division algorithm F = Q*D + R
Q = ? R = ?
Example:

F = axc + axd + axe + bc + bd + de  D = ax + b
------------
| ax   b
------------
axc |  c   -
axd |  d   -
axe |  e   -
bc  |  -   c
bd  |  -   d
de  |  -   -
------------
{c d e} inersect {c d} = {c d}
F = (c + d)(ax + b) + axe + de

## Good divisors must be looked for among kernels

A cube-free kernel of F is a quotient obtained by dividing F by a single cube (co-kernel).
By-definition a «cube-free» expression has no divisors that leave no remainder.
Example: `F = abc + abd + bcd`
Co-kernels: `ab, b`
Kernels: `c+d, ac + ad + cd`

## Brayton & McMullen theorem

Expressions F, G have a common multiple-cube divisor d
if and only if
there are kernels k1 of F and k2 of G
such that `d = k1 inersect k2` (i. e. SOP form with common cubes in it)
and d is an expression with at least 2 cubes in it.

If F has a kernel K2 that itself has a kernel K1 which has a kernel K0
then K1 and K0 are also kernels of F. So look for kernels recursively.
Potential co-kernel of F is a cube contained in at least two cubes of F.

—————————————————————-

## Looking for multiple-cube common divisors

Suppose we have two functions P and Q.

P = af + bf + ag + cg + ade + bde + cde
Q = af + bf + ace + bce

Find all kernels for P and Q.
Make a Co-Kernel—Cube Matrix:

---------------+-------------------------
|  Cubes from all kernels
Kernels        | a  b  c  ce  de  f  g
---------------+-------------------------
(P) de + f + g | .  .  .  .   1   1  1
(P) de + f     | .  .  .  .   1   1  .
(P) a + b + c  | 1  1  1  .   .   .  .     (*)
(P) a + b      | 1  1  .  .   .   .  .     (*)
(P) de + g     | .  .  .  .   1   .  1
(P) a + c      | 1  .  1  .   .   .  .
(Q) ce + f     | .  .  .  1   .   1  .
(Q) a + b      | 1  1  .  .   .   .  .     (*)
(*)(*)

Find prime rectangle cover (*).
The common divisor is `(a + b)`.
Count the number of literals saved.

—————————————————————-

## Implicit Don’t Cares (DCs)

Make simplifications of the logical expressions in your boolean logic network based on the so called «implicit don’t cares» that exist in every multilevel logic network.
You can set 0 or 1 to the Karnaugh map cell that contains a don’t care whichever halps you to minimize the function.

Satisfiability Don’t Cares (SDC) — impossible combinations of inputs and outputs of a specific network node.
Example: node X

X = a + b
SDC(X) = X ^ (a + b) = X'a + X'b + Xa'b'

Controllability Don’t Cares (CDC) — patterns that cannot happen at inputs to a network node.
Suppose node `F = F(x1, x2, ..., xn)`
`CDC(F) = (for any var not used in F)[SDC(x1) + SDC(x2) + ... SDC(xn)]`
(Univerally quantify away all variables that are not used in the node F)

Observability Don’t Cares (ODC) — patterns input to node that make network outputs insensitive to output of the node.
We have node F(a, b) and node Z(a, b, c, F).
`ODC(F) = patterns of (a, b) that make Z insensitive to F's value i.e. dF/dZ=0.`
`ODC(F) = (for any var not used in F)[dF/dZ=0]`

If there are many nodes Z1, Z2, …, Zn dependent on F:
`ODC(F) = patterns that are unobservable at all outputs Z1, Z2, ..., Zn.`