## Advanced logic design

March 20, 2013 Leave a comment

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 2* ^{n}*-1

M BDD requires

*m*.(2

*-1)*

^{n}Total no. of nodes:

*m*.(2

*-1)+2*

^{n}**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*.(2* ^{n}*-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 2* ^{n }*– 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(2* ^{n }*– 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