Advanced logic design

BDD is the graph representation & minimization of logic function.
Boolean expression consists of millions of products.
Any number of functions can be handled by BDDs.
Logic Simulators has been constructed by BDDs.
MIT invented Flash Memory by help of BDDs.

Function:
On the basis of output function:
1) Single output function
2) Multiple output function
On the basis of input values:
1) Two valued function
2) Multiple valued function

Multiple Output Function:
1) is faster
2) cost minimization
cost can be reduced by sharing internal gate.

Logic Function:
Special type of representation.
BDD is the compact form
BDD is derived from Binary Decision Tree

Two rules for constructing a compact BDD is known as BDD reduction rules.
1) Node Elemination
2) Node Sharing

Reduction rules as well as ordering is important to construct BDD
1) Reduction rule
2) Ordering of input variable in the BDD.

Types of BDD for multi-output function:
1) Shared BDD (SBDD)
2) Multi-terminal BDD (MTBDD)
3) Shared MTBDD (SMTBDD)

SBDD + MTBDD = SMTBDD

Comparison:
SBDD: slower(Speed), Smaller(Size)
MTBDD: Faster(speed), Larger(size)

MTBDD is a tidy structure.

Maximum number of nodes to construct an SBDD with m functions of n input variable?
1 BDD requires        2n-1
M BDD requires      m.(2n-1)
Total no. of nodes:  m.(2n-1)+2

SBDD:
What is the total time required for m function n input?
To get result from 1 BDD for 1 function = n times
To get result from m BDD for m function = m.n times

Theorem 1: Let m be the no. of functions and n be the no. of input variable than the maximum no. of nodes is an SBDD is m.(2n-1)+2

Theorem 2: Let m be the number of functions and n be the number of input variables in an SBDD, then the maximum time requires the output result O(m.n)

MTBDD:
Theorem 1: Let m be the no. of functions and n be the no. of input variables. Let r be the no. of distinct output patterns in an MTBDD. Then the maximum no of nodes in an MTBDD is 2n – 1 + r

Theorem 2: O(n) no. of time required to get the output.

SMTBDD:
Time: O(m/2.n) = O(mn/2)
No. of nodes: m/2(2n – 1) + r

BDD fo charactiristic functions(CFs)
Heuristic Algorithm
Step 1: Dependency Matrix
Step 2: Pair Dependency Matrix
Step 3: Calculation of weight of the pair
Step 4: Weighted completed graph

Midterm Exam Syllabus

Definition of BDDs
Application of BDDs
Representation of BDDs
Minimization of BDDs
Advantage/Disadvantage of BDDs
Reduction rules for constructing a compact BDD
Algorithm for finding the ordering of input variable
Types of BDDs
What is multiple output function
What are the advantage/disadvantage of multi output function
SBDD, MTBDD, SMTBDD
BDD for charactiristic function
Uper bounds & Evaluation time of all BDDs
Comparison among BDDs
Proof of upper bounds & evaluation time of all BDDs.