WIXLIB

1. Brief Review of Cube Calculus2. Simple Combinational Operators3. Complex Combinational Operators4. Sequential Operators5. Multi-valued Operations6. Patterns of Operations7. General Patterns of Operations andHorizontal Microprogramming 8. Why we need CCM?

Cube Calculusfor CCM

Overview Of This Lecture A Brief Review of Cube Calculus. Summary of Cube Calculus operations. Positional notation concept for CubeCalculus operations. Summary of Positional notation concept forCube Calculus operations. Why we need a Cube Calculus Machine?

Brief ReviewOf CubeCalculus

Representation of cubes in(Binary logic) For the function f(a,b,c,d) A B a’bc’ ac’d we have two cubes (a’bc’and ac’d) Cube is a Product ofliterals. In binary logic, they can be representedas A a{0} .b{1} .c{0} .d{0,1} andB a{1} .b{0,1} .c{0} .d{1}

General Representation ofcubes in (n valued logic) A x1s1A. x2s2A xnsnA B x1s1B. x2s2B .xnsnB where x1s1A .xnsnA.,x1s1B, . xnsnB are literals. n is the number of variables. siA, siB are true sets of literal xi . An example of a ternary logic is:A x1{0}. x2{0,2}. x3{1}. x4{1,2}B x1{1}. x2{1}. x3{2} . x4{0,1}

CubeCalculusOperations

Cube Calculus OperationsThe cube calculus operations are classified as : Simple Combinational operations (e.g. Intersection,SuperCube ). Complex Combinational operations (e.g. Prime,Consensus, Cofactor). Sequential operations (e.g. Crosslink, Sharp(non-disjoint),Sharp (disjoint)). Let us discuss these operations.

SimpleCombinationalCubeOperations

Simple Combinational Operations Defined as a SINGLE set operationon all pairs of true sets andproduces one resultant cube. Intersection and Supercube aresimple combinational cubeoperations.

Example OfBinaryFunction

Kmap representation ofIntersection B ab A bc’ Set theory :B ab abx a{1}b{1}c{0,1} A bc’ xbc’ a{0,1}b{1}c{0} B A a{1} {0,1}b{1} {1}c{0,1} {0} abc’

Kmap representation ofIntersectionA x2*xA3B x1*xB2 Fig 1: Input Cubes Aand B to beIntersected. Here– A x2*x3– B x1*x2x1*x2 *x3 Fig 2:Resultant CubeC A B x1*x2 *x3

Kmap representation ofSupercube A and B has 3variables.B bc’A ab B bc’ In set theory A abxB xbc’ A B b

K-map representation ofSuper cube Input Cubes A and Bto be supercubed.A x1’x2’x4B x1x3x4C A B x4A x1’x2’x4B x1x3x4 Resultant CubeC A B x4

Examples OfMulti-ValuedFunctions

K-map representation ofSupercubeSupercube For 4 valued inputlogic. Input Cubes A and Bto be supercubed.A a01b1. B a12b2 Resultant CubeC A B a012b12

K-map representation ofIntersection For 4 valued inputlogic. Input Cubes A and Bfor Intersection.A a12b12. B a2b012 Resultant CubeC A B a2b12

Definitions ofSimpleCombinationalCube Operations

Intersection of two cubes :Is the largest cube thatis included in both A and B.Supercube of two cubes :Is the smallest cubethat includes both cubes.

Simple Combinational Operation Intersection operation mathematically isdefined asA s BA s BssA B x1 1 1 xn n n if siA siB otherwise. Union operation mathematically is defined asA s BA s BssA B x1 1 1 xn n n

ComplexCombinationalCubeOperations

Complex combinationalcube operations They have two set operations and one set relation. All variables whose pair of true sets satisfy a relation are said tobe SpecialVariables. Two set operations are called before(bef) and active(act),theactive set operation is applied on true sets of special variables andbefore set operation to others All Combinational cube operations (Complex and Simple)produce one resultant cube, all special variables taken at a time. The examples are prime operation, cofactor operation,consensus operation.

Examples ofComplexCombinationalCube Operations

Example OfBinary Function

Example of consensus operation A & B have 4 binaryvariables– A x1x2x3’– B x1x2’ Steps: find the set relationsiA siB . If satisfied then it is a specialvariable. Active operation (siA siB)applied to special variables. And to remaining variables(before variables) the setoperator siA siB is applied

Explanation ofconsensusoperation In set theoryA x1{1}x2{1}x3{0}x4{0,1}B x1{1}x2{0}x3{0,1}x4{0,1} Applying the set relation siA siB on all the true set of variables x1 is a special variable and to x1 active operation (siA siB) isapplied and to x2 ,x3 ,x4 before set operator (siA siB ) is applied A * B x1{1} x3{0} x1x3’

Example of prime operationprime A&B has 4binary variablesA x1’x2x3x4B x1x3’Step 1:1 Find intersectionoperation(set relation) onall true sets(siA siB ) Step 2:2 If the set relation issatisfied apply active setoperation(siA siB ) elsebefore set operation( siA ).

Explanation of theExample Using set theoryB x1{1} x2{0,1}x3{0}x4{0,1}A x1{0}x2{1}x3{1}x4{1}Step 1. Find if set relation (siA siB ) is satisfied or not x2 and x4 are special variables.Step 2. As the given set relation is satisfied.for thevariables x2 and x4 to these variables active set operation(siA siB ) is applied and to the others (x1 , x3 ) before setoperation ( siA ) is applied A’B x1{0}x3{1} x1’x3.

Example of cofactor operation A and B have 4 binaryvariables.This is cofactor of cube A with respect to cube B(variable x1)– A x1x2x3– B x1 Steps: Find siA siB(If satisfied specialvariable) Apply U(Universal set(0,1))for special variablesandsiA siB for others

ExplanationSet theory:A x1{1}x2{1}x3{1}x4{0,1}B x1{1}x2{0,1}x3{0,1}x4{0,1} Testing the relation siA siB for the variables. x1 and x4 arespecial variables. Universal set operator applied to thesevariables. To the rest of the variables the intersection operation is applied. The result is x2 x3. In K-map apply the intersection operator and remove the special variables.

Example OfMulti-ValuedFunction

K-map representation of ConsensusAB A X 01234 Y01 B X012 Y23 A*B X 01234Y01*X012Y23 X012 Y0123

Definitions ofComplexCombinationalCube Operations

General Descriptionof Consensus CubeOperation

Complex combinational cubeoperation The consensus operation on cubes A and B is defined asA B when distance (A,B) 0A*B when distance (A,B) 1A *basic B when distance (A,B) 1 where A *basic B BA s1BA sk-1BAsks1sk-1skx1 .xk-1xk A sk 1BA snBsk 1snxk 1 xn. Set relation: siA siB , if satisfied, a special variable Active set operation : siA siB Before set operation : siA siB

Complex combinationalcube operation Applications of consensus operator:– For finding prime implicants (Used for twolevel logic minimization),– three level,– multilevel minimization,– and machine learning.

GeneralDescription ofCofactor CubeOperation

Complex combinational cubeoperationCofactor operation of two cubes A and B isA B A basic B when A B otherwise Set relation for cofactor operation siA siBActive set operator U (Universal set(0,1))Before set operator siA siB Application: Used in functional decomposition.

reviewApplications ofCrosslink

And we all know that the answer is that we arelooking for two cubes as shown down here,so that our function is to be expressed in the ESOPform as follows: f E!D

GeneralDescription ofPrimeOperation

Complex combinational cubeoperations Prime operation of two cubes A and B is defined ass1A xsk-1Ax skA skBxsk 1A .x snAk-1kk 1nrelation : siA siB is applied to trueA’B x1where setif satisfied active set operation is appliedelse before set operation is applied. Active set operation(act):siA siB Before set operation(bef): siA Application: Used in ESOP minimization .sets and

SequentialCubeOperations

Sequential cube operations They have three set operations and one set relation. All variables whose pair of true sets satisfy a relation are said tobe SpecialVariables. Three set operations are called before(bef),active(act) andafter(aft) The active set operation is applied on true sets of special variable The before set operation to variables before the special variable The after set operation to variables after the special variable. Every special variable is taken once at a time.

Sequential cube operations All sequentialcube operationsproduce ‘n’resultant cubes, wheren is the number of special variables. The examples are:sharp operation,–cross link operation.–

Examples ofSequentialCubeOperations

Example OfBinary Function

Let us consider the following example, wherethe relation operation is SA SB ϕ

Cubes A and B are of 4 variablesLet us consider the following two cubes,Cube A x1 x2 x3’ x1{1}*x2{1}*x3{0} *x4{0,1}Cube B x1 x2’ x1{1}*x2{0}*x3{0,1} *x4{0,1}

These two variables (x1 and x3) are the so calledspecial variables , and we find them out by checkingthe relation between every literal in both cubes for arelation which is for the crosslink ( is the intersectionbetween these two variables is empty?).Cube ACube Bx1{0}x2{0,1} x1{1}x2{0,1}x3{0} x4{0,1} x3{1} x4{0,1}We can see that the intersection is empty for only X1 and X3therefore they are special variables.variables

Example of crosslinkoperation A and B has 4 binaryvariables. A x1’x3’ x1{0}x2{0,1}x3{0}x4{0,1 B x1x3 x1{1}x2{0,1}x3{1}x4{0,1} A c B x1’x3’ x1x3 x3’ x1

Example Cubes :x1{0}x2{0,1} x3{0}x4{0,1}x1{1}x2{0,1}x3{1} x4{0,1}Set Relation: siA siB ϕ x1 and x3 are special variables. Act: siA siB, Bef: siA, Aft: siB x1{0} {1}x2{0,1} x3{0}x4{0,1} andx1 {1}x2{0,1} x3{0} {1} x4{0,1} Two resultant cubes one for each specialvariable. A B x3’ x1

Complex crosslink example A,B,C,D are 4cubes F A B C D F A B E F F G H

Example ofnondisjointsharp A and B has 4 binaryvariables. A x3’ x1{0,1}x2{0,1}x3{0}x4{0,1} B x2x4 x1{0,1}x2{1}x3{0,1}x4{1} Set relation: (siA siB)– 1.x1{0,1} x2{0,1}n( {1}} x3{0}x4{0,1}Act: siA siB, Bef: siA, Aft:siA– 2. x1{0,1}x2{0,1} x3{0} x4{0,1}n( {1}}Act: siA siB, Bef: siA,Aft: siA A # B x2’x3’ x3 ’x4’

Example ofdisjoint sharp A and B has 4 binary variables. A x3’ x1{0,1}x2{0,1}x3{0}x4{0,1} B x2x4 x1{0,1}x2{1}x3{0,1}x4{1}Set relation: (siA siB)x1{0,1}n{0,1}x2{0,1}n( {1}}x3{0}x4{0,1} Act: siA ( siB),Bef: siA, Aft: siA siBx1{0,1}n{0,1}x2{0,1}n{1}x3{0}n{0,1} x4 {0,1}n( {1}}Act: siA ( siB), Bef: siA,Aft: siA siB A #d B x2’x3’ x2x3 ’x4’

Example OfMulti-ValuedFunctions

Example of crosslink operation Let A x0y1 andB x3y3crosslink X and Y arespecial variables. x{0}U {3} y1 and x {3} y{1} {3} Resultant cubes:x03y1 x3y13

Definitions ofSequential CubeOperations

General Descriptionof Nondisjoint sharpOperation

Sequential cube operations. The nondisjoint sharp operation on cubes A and BA#B Awhen A B when A B A #basic B otherwises1A xsk-1Ax skA ( skB)xsk 1A .x snA fork-1kk 1n A #basic B x1such that k 1, .n for which the set relation is true. Set relation: (siA siB).Active set operation: siA ( siB),After set operation: siA,Before set operation: siA Used in tautology problem.

GeneralDescription ofdisjoint sharpoperation

Sequential cube operations. The disjoint sharp operation on cubes A and BA#dB Awhen A B when A B A #dbasic B otherwiseAA skA ( skB)AAs1sk-1sk 1snx1 xk-1xkxk 1 .xn A #dbasic B for such that k 1, .n for which the set relation is true. Set relation: (siA siB)Active set operation: siA ( siB),After set operation: siA siB ,Before set operation: siA Used in tautology problem, conversions between SOPand ESOP representations

General Descriptionof CrosslinkOperation

Sequential cube operations. Generalized equation of Crosslink operation:BB skA skBAAs1sk-1sk 1snx1 xk-1xkxk 1 .xnA B where k 1, .n for which the set relation is true. Set relation:relation siA siB ,Active set operation : siA siB,After set operation : siB,Before set operation : siA.Used in the minimization of logic function onEXOR logic, Generalized Reed-Muller form.

So the solution is to find these two cubes out (Cubes E, D).Let us see how the crosslink operation does that!!!Here is the K map for the original function againHere if we think about it, we are looking for literals, in which theintersection of these literals in both cubes is empty, that isX1 and X3,Because in the firstcube we have

Summaryof theCube CalculusOperations

Summary of cubecalculus operations

PositionalNotation