Source: http://www.google.com/patents/US6901573?dq=6,272,646
Timestamp: 2014-08-29 12:28:58
Document Index: 329588552

Matched Legal Cases: ['art+1', 'art 510', 'art 520', 'art 530', 'art 540', 'art 510', 'art 520', 'art 510', 'art 530', 'art 510', 'art 520', 'art 520', 'art 530', 'art 540', 'art 540']

Patent US6901573 - Method for evaluating logic functions by logic circuits having optimized ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsA method for creating a logic circuit with an optimized number of AND/OR switches, which evaluates a logic function defined in a high-level description. Through analyzing the dependency relationship among operators used to define the logic function, the present invention may simplify the functional steps...http://www.google.com/patents/US6901573?utm_source=gb-gplus-sharePatent US6901573 - Method for evaluating logic functions by logic circuits having optimized number of and/or switchesAdvanced Patent SearchPublication numberUS6901573 B2Publication typeGrantApplication numberUS 10/382,036Publication dateMay 31, 2005Filing dateMar 5, 2003Priority dateMar 5, 2003Fee statusPaidAlso published asUS7328423, US20040177330, US20050149302Publication number10382036, 382036, US 6901573 B2, US 6901573B2, US-B2-6901573, US6901573 B2, US6901573B2InventorsAndrey A. Nikitin, Alexander E. AndreevOriginal AssigneeLsi Logic CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (3), Referenced by (1), Classifications (6), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetMethod for evaluating logic functions by logic circuits having optimized number of and/or switchesUS 6901573 B2Abstract A method for creating a logic circuit with an optimized number of AND/OR switches, which evaluates a logic function defined in a high-level description. Through analyzing the dependency relationship among operators used to define the logic function, the present invention may simplify the functional steps used in the high-level description to define the logic function and thus create a logic circuit with an optimized number of AND/OR switches.
1. A method for creating a logic circuit with an optimized number of AND/OR switches to evaluate a logic function FUNC(x,y), comprising steps of:
(a) defining said logic function FUNC(x,y) in terms of control inputs x1, x2, . . . , xn, n>1, data inputs y1, y2, . . . , ym, m>1, and at least one operator OPi, i={overscore (1, N)}, {overscore (1, N)}=1, 2, 3, . . . , N, each of said at least one operator OPi being an IF-operator, an EQ-operator, or a SEQ-operator; (b) evaluating dependency relationship among said at least one operator OPi; and (c) creating said logic circuit based on said dependency relationship; wherein said step (b) comprises: (b1) evaluating Termi(x) for said each of said at least one operator OPi, wherein Termi(x)=1 when OPpar(i) is a SEQ-operator, Termi(x)=xj when OPpar(1) is an IF-operator with control input xj and OPi is a positive child, and Termi(x)=xj if OPpar(i) is an IF-operator with control input xj and OPi is a negative child; (b2) evaluating a set AllParents(1)={par0(1), par1(1), . . . , pard(1)()} for said each of said at least one operator OPi; (b3) evaluating a set AllParentsBeforeSeq(1)={par0(1), par1(1), . . . , parseq(1)−1(1)} for said each of said at least one operator OPi; (b4) evaluating a set AllSeqParents(1)={parseq(1)(1), parseq(seq(1))(1), . . . , pard(i)(i)} for said each of said at least one operator OPi; and (b5) evaluating a set common(i,s)=pard(i,s)(s) for said each of said at least one operator OPi and OPs. 2. The method of claim 1, wherein said step (c) comprises:
(c1) creating a first part of said logic circuit, said first part consists of AND gates only and has said Termi(x) as inputs and TermBeforeSeqi(x) as outputs, wherein TermBeforeSeq i ⁡ ( x ) = ⩓ t ∈ AllParentsBeforeSeq ⁡ ( i ) ⁢ Term i ⁡ ( x ) , i = 1 , N _ (c2) creating a second part of said logic circuit, said second part consists of AND gates only and has said TermBeforeSeqi(x) as inputs and Condi(x) as outputs, wherein Cond i ⁡ ( x ) = ⩓ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ TermBeforeSeq i ⁡ ( x ) , i = 1 , N _ (c3) creating a third part of said logic circuit, said third part consists of AND gates, OR gates, and NOR gates, and has said TermBeforeSeqi(x) and said Condi(x) as inputs and Valj(x) as outputs, wherein Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⩓ s > i s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ { ⩓ t ∈ { s } ⋃ AllSeqParents ⁡ ( s ) t < common ⁡ ( i , s ) ⁢ TermBeforeSeq i ⁡ ( x ) } ] (c4) creating a fourth part of said logic circuit, said fourth part consists of OR gates only and has said Valj(x) as inputs and said FUNC(x,y) as outputs, wherein FUNC ⁡ ( x , y ) = ⩔ j = 1 m ⁢ Val j ⁡ ( x ) � y j . 3. The method of claim 2, wherein said step (a) comprises defining said logic function FUNC(x,y) in a C++ code.
4. The method of claim 2, wherein said logic function FUNC(x,y) is a Boolean function, wherein each of said control inputs, each of said data inputs, and each of said logic function FUNC(x,y) is a one-bit value chosen from 0 and 1.
5. The method of claim 2, wherein each of said control inputs is a one-bit value chosen from 0 and 1, and each of said data inputs is a one-bit value or a multi-bit value and is an integer belonging to a set {0, 1, . . . , 2k−1}.
6. A method for creating a logic circuit with an optimized number of AND/OR switches to evaluate a logic function FUNC(x,y), comprising steps of:
(a) defining said logic function FUNC(x,y) in terms of control input x1, x2, . . . , xn, n>1, data inputs y1, y2, . . . , ym, m>1, and at least one operator OPi, i={overscore (1, N)}, {overscore (1, N)}N=1, 2, 3, . . . , N, each of said at least one operator OPi being an IF-operator, an EQ-operator, or a SWITCH-operator; (b) evaluating dependency relationship among said at least one operator OPi; and (c) creating said logic circuit based on said dependency relationship; wherein said step (b) comprises: (b1) evaluating Termi(x) for said each of said at least one operator OPi, wherein Termi(x)=1 when OPpar(i) is a SEQ-operator, and Termi(x)=(xj==As) when said operator OPi is a SWITCH-operator; (b2) evaluating a set AllParents(1)={par0(1), par1(1), . . . , pard(i)(i)} for said each of said at least one operator OPi; (b3) evaluating a set AllParentsBeforeSeq(1)={par0(1), par1(1), . . . , parseq(1)−1(1)} for said each of said at least one operator OPi; (b4) evaluating a set AllSeqParents(1)={parseq(1)(1), parseq(seq(1))(1), . . . , pard(1)(i)} for said each of said at least one operator OPi; and (b5) evaluating a set common(i,s)=pard(i,s)(s) for said each of said at least one operator OPi and OPs. 7. The method of claim 6, wherein said step (c) comprises:
(c1) creating a first part of said logic circuit, said first part consists of AND gates only and has said Termi(x) as inputs and TermBeforeSeq1(x) as outputs, wherein TermBeforeSeq i ⁡ ( x ) = ⩓ t ∈ AllParentsBeforeSeq ⁡ ( i ) ⁢ Term i ⁡ ( x ) , i = 1 , N _ (c2) creating a second part of said logic circuit, said second part consists of AND gates only and has said TermBeforeSeqi(x) as inputs and Condi(x) as outputs, wherein Cond i ⁡ ( x ) = ⩓ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ TermBeforeSeq i ⁡ ( x ) , i = 1 , N _ (c3) creating a third part of said logic circuit, said third part consists of AND gates, OR gates, and NOR gates, and has said TermBeforeSeqi(x) and said Condi(x) as inputs and Valj(x) as outputs, wherein Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⩓ s > i s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ { ⩓ t ∈ { s } ⋃ AllSeqParents ⁡ ( s ) t < common ⁡ ( i , s ) ⁢ TermBeforeSeq i ⁡ ( x ) } ] (c4) creating a fourth part of said logic circuit, said fourth part consists of OR gates only and has said Valj(x) as inputs and said FUNC(x,y) as outputs, wherein FUNC ⁡ ( x , y ) = ⩔ j = 1 m ⁢ Val j ⁡ ( x ) � y j . 8. The method of claim 7, wherein said step (a) comprises defining said logic function FUNC(x,y) in a C++ code.
9. The method of claim 7, wherein at least one of said control inputs is a multi-bit value.
10. A computer-readable medium having computer-executable instructions for performing a method for creating a logic circuit with an optimized number of AND/OR switches to evaluate a logic function FUNC(x,y), said method comprising steps of:
(a) defining said logic function FUNC(x,y) in terms of control inputs x1, x2, . . . , xn, n>1, data inputs y1, y2, . . . , ym, m>1, and at least one operator OPi, i={overscore (1, N)}, {overscore (1, N)}=1, 2, 3, . . . , N, each of said at least one operator OPi being an IF-operator, an EQ-operator, or a SEQ-operator; (b) evaluating dependency relationship among said at least one operator OPi; and (c) creating said logic circuit based on said dependency relationship; wherein said step (b) comprises: (b1) evaluating Termi(x) for said each of said at least one operator OPi, wherein Termi(x)=1 when OPpar(i) is a SEQ-operator, Termi(x)=xj when OPpar(1) is an IF-operator with control input xj and OPi is a positive child, and Termi(x)=xj if OPpar(i) is an IF-operator with control input xj and OPi is a negative child; (b2) evaluating a set AllParents(1)={par0(1), par1(1), . . . , pard(1)(1)} for said each of said at least one operator OPi; (b3) evaluating a set AllParentsBeforeSeq(1)={par0(1), par1(1), . . . , parseq(1)−1(1)} for said each of said at least one operator OPi; (b4) evaluating a set AllSeqParents(1)={parseq(1)(1), parseq(seq(1))(1), . . . , pard(i)(1)} for said each of said at least one operator OPi; and (b5) evaluating a set common(i,s)=pard(i,s)(s) for said each of said at least one operator OPi and OPs. 11. The computer-readable medium of claim 10, wherein said step (c) comprises:
(c1) creating a first part of said logic circuit, said first part consists of AND gates only and has said Termi(x) as inputs and TermBeforeSeqi(x) as outputs, wherein TermBeforeSeq i ⁡ ( x ) = ⩓ t ∈ AllParentsBeforeSeq ⁡ ( i ) ⁢ Term i ⁡ ( x ) , i = 1 , N _ (c2) creating a second part of said logic circuit, said second part consists of AND gates only and has said TermBeforeSeq1(x) as inputs and Cond1(x) as outputs, wherein Cond i ⁡ ( x ) = ⩓ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ TermBeforeSeq i ⁡ ( x ) , i = 1 , N _ (c3) creating a third part of said logic circuit, said third part consists of AND gates, OR gates, and NOR gates, and has said TermBeforeSeq1(x) and said Cond1(x) as inputs and Valj(x) as outputs, wherein Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⩓ s > i s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ { ⩔ t ∈ { s } ⋃ AllSeqParents ⁡ ( s ) t < common ⁡ ( i , s ) ⁢ TermBeforeSeq i ⁡ ( x ) } ] (c4) creating a fourth part of said logic circuit, said fourth part consists of OR gates only and has said Valj(x) as inputs and said FUNC(x,y) as outputs, wherein FUNC ⁡ ( x , y ) = ⩔ j = 1 m ⁢ Val j ⁡ ( x ) � y j . 12. The computer-readable medium of claim 11, wherein said step (a) comprises defining said logic function FUNC(x,y) in a C++ code.
13. The computer-readable medium of claim 11, wherein said logic function FUNC(x,y) is a Boolean function, and each of said control inputs, each of said data inputs, and each of said logic function FUNC(x,y) is a one-bit value chosen from 0 and 1.
14. The computer-readable medium of claim 11, wherein each of said control inputs is a one-bit value chosen from 0 and 1, and each of said data inputs is a one-bit value or a multi-bit value and is an integer belonging to a set {0, 1, . . . , 2k−1}.
15. A computer-readable medium having computer-executable instructions for performing a method for creating a logic circuit with an optimized number of AND/OR switches to evaluate a logic function FUNC(x,y), said method comprising steps of:
(a) defining said logic function FUNC(x,y) in terms of control input x1, x2, . . . , xn, n>1, data inputs y1, y2, . . . , ym, m>1, and at least one operator OPi, i={overscore (1,N)}, {overscore (1, N)}=1, 2, 3, . . . , N, each of said at least one operator OPi being an IF-operator, an EQ-operator, or a SWITCH-operator; (b) evaluating dependency relationship among said at least one operator OPi; and (c) creating said logic circuit based on said dependency relationship; wherein said step (b) comprises: (b1) evaluating Termi(x) for said each of said at least one operator OPi, wherein Termi(x)=1 when OPpar(1) is a SEQ-operator, and Termi(x)=(xj==As) when said operator OPi is a SWITCH-operator; (b2) evaluating a set AllParents(1)={par0(1), par1(1), . . . , pard(1)(1)} for said each of said at least one operator OPi; (b3) evaluating a set AllParentsBeforeSeq(1)={par0(1), par1(1), . . . , parseq(1)−1(1)} for said each of said at least one operator OPi; (b4) evaluating a set AllSeqParents(1)={parseq(1)(1), parseq(seq(1))(1), . . . , pard(1)(1)} for said each of said at least one operator OPi; and (b5) evaluating a set common(i,s)=pard(i,s)(s) for said each of said least one operator OPi and OPs. 16. The computer-readable medium of claim 15, wherein said step (c) comprises:
(c1) creating a first part of said logic circuit, said first part consists of AND gates only and has said Termi(x) as inputs and TermBeforeSeqi(x) as outputs, wherein TermBeforeSeq i ⁡ ( x ) = ⩓ t ∈ AllParentsBeforeSeq ⁡ ( i ) ⁢ Term i ⁡ ( x ) , i = 1 , N _ (c2) creating a second part of said logic circuit, said second part onsists of AND gates only and has said TermBeforeSeqi(x) as inputs and Condi(x) as outputs, wherein Cond i ⁡ ( x ) = ⩓ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ TermBeforeSeq i ⁡ ( x ) , i = 1 , N _ (c3) creating a third part of said logic circuit, said third part consists of AND gates, OR gates, and NOR gates, and has said TermBeforeSeqi(x) and said Cond1(x) as inputs and Valj(x) as outputs, wherein Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⩓ s > i s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ { ⩓ t ∈ { s } ⋃ AllSeqParents ⁡ ( s ) t < common ⁡ ( i , s ) ⁢ TermBeforeSeq i ⁡ ( x ) } ] (c4) creating a fourth part of said logic circuit, said fourth part consists of OR gates only and has said Valj(x) as inputs and said FUNC(x,y) as outputs, wherein FUNC ⁡ ( x , y ) = ⩔ j = 1 m ⁢ Val j ⁡ ( x ) � y j . 17. The computer-readable medium of claim 16, wherein said step (a) comprises defining said logic function FUNC(x,y) in a C++ code.
18. The computer-readable medium of claim 16, wherein at least one of said control inputs is a multi-bit value.
19. An apparatus for creating a logic circuit with an optimized number of AND/OR switches to evaluate a logic function FUNC(x,y), comprising:
(a) means for defining said logic function FUNC(x,y) in terms of control inputs x1, x2, . . . , xn, n>1, data inputs y1, y2, . . . , ym, m>1, and at least one operator OPi, i={overscore (1, N)}, {overscore (1, N)}=1, 2, 3, . . . , N, each of said at least one operator OPi being an IF-operator, an EQ-operator, or a SEQ-operator; (b) means for evaluating dependency relationship among said at least one operator OPi; and (c) means for creating said logic circuit based on said dependency relationship; wherein said means for evaluating comprises: (b1) means for evaluating Termi(x) for said each of said at least one operator OPi, wherein Term1(x)=1 when OPpar(i) is a SEQ-operator, Termi(x)=xj when OPpar(1) is an IF-operator with control input xj and OPi is a positive child, and Termi(x) =xj if OPpar(1) is an IF-operator with control input xj and OPi is a negative child; (b2) means for evaluating a set AllParents(1)={par0(1), par1(1), . . . , pard(i)(i)} for said each of said at least one operator OPi; (b3) means for evaluating a set AllParentsBeforeSeq(i)={par0(1), par1(l), . . . , parseq(i)−1(1)}-for said each of said at least one operator OPi, and (b4) means for evaluating a set AllSeqParents(1)={parseq(1)(1), parseq(seq(1))(1), . . . , pard(i)(1)} for said each of said at least one operator OPi; and (b5) means for evaluating a set common(i,s)=parh(i,s)(s) for said each of said at least one operator OPi and OPs. 20. The apparatus of claim 19, wherein said means for creating comprises:
(c1) means for creating a first part of said logic circuit, said first part consists of AND gates only and has said Termi(x) as inputs and TermBeforeSeqi(x) as outputs, wherein TermBeforeSeq i ⁡ ( x ) = ⩓ t ∈ AllParentsBeforeSeq ⁡ ( i ) ⁢ Term i ⁡ ( x ) , i = 1 , N _ (c2) means for creating a second part of said logic circuit, said second part consists of AND gates only and has said TermBeforeSeqi(x) as inputs and Condi(x) as outputs, wherein Cond i ⁡ ( x ) = ⩓ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ TermBeforeSeq i ⁡ ( x ) , i = 1 , N _ (c3) means for creating a third part of said logic circuit, said third part consists of AND gates, OR gates, and NOR gates, and has said TermBeforeSeqi(x) and said Cond1(x) as inputs and Valj(x) as outputs, wherein Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⩓ s > i s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ { ⩓ t ∈ { s } ⋃ AllSeqParents ⁡ ( s ) t < common ⁡ ( i , s ) ⁢ TermBeforeSeq i ⁡ ( x ) } ] (c4) means for creating a fourth part of said logic circuit, said fourth part consists of OR gates only and has said Valj(x) as inputs and said FUNC(x,y) as outputs, wherein FUNC ⁡ ( x , y ) = ⩔ j = 1 m ⁢ Val j ⁡ ( x ) � y j . 21. The apparatus of claim 20, wherein said means for defining comprises means for defining said logic function FUNC(x,y) in a C++ code.
22. The apparatus of claim 20, wherein said logic function FUNC(x,y) is a Boolean function, and each of said control inputs, each of said data inputs, and each of said logic function FUNC(x,y) is a one-bit value chosen from 0 and 1.
23. The apparatus of claim 20, wherein each of said control inputs is a one-bit value chosen from 0 and 1, and each of said data inputs is a one-bit value or a multi-bit value and is an integer belonging to a set {0, 1, . . . , 2k−1}.
As shown in FIG. 1, an exemplary logic function FUNC is determined by means of C++ functions. Inputs x1, x2, . . . , xn, y1, y2, . . . , ym, n≧1, m≧1 may take values of only 0 (low) and 1 (high). Inputs x1, x2, . . . ,xn may be called control inputs, and inputs y1, y2, . . . , ym may be called data inputs.
1) IF-operators, which may be defined as follows:
i�(xi) positive_operator else negative_operator or if(xi) negative_operator else positive_operator
( represents a NOT function). It should be noted that the else option may be absent without departing from the spirit and scope of the present invention.
Before the description of the method of the present invention, the following terms may be defined. The operators �positive_operator� and �negative_operator�, as discussed previously, are called children of the IF-operator, and the operators �child_operator1�, �child_operator2�, . . . �child operatorK� are called children of the SEQ-operator. The operator �positive_operator� is called a positive child of the IF-operator, and the operator �negative_operator� is called a negative child of the IF-operator. The IF-operator is called a parent of operators �positive_operator� and �negative operator�, and the SEQ-operator is called a parent of operators �child_operator1�, �child_operator2�, . . . �child operatorK�. The input xi is called control input of the IF-operator.
Let us enumerate all the operators of a C++ program in the order of the operator's presence in the C++ code as shown in FIG. 3. Preferably, the number 1 is always assigned to the top-level SEQ-operator. This operator is the only operator that has no parent. Operators 2 and 9 are children of operator 1. The operator 3 is a positive child of the operator 2, the operator 4 is a child of the operator 3, and continuing likewise. Thus all the operators have a unique number op={overscore (1, N)}.
For example, OPi may be an operator with number i. For each i={overscore (1, N)} par(i) may be a number of the parent of the operator OP i. We may assign par(1)=1.
For purposes of the following discussion, x may be denoted as equal to (x1, x2, . . . , xn), and instead of denoting each Boolean function that depends from variables x1, x2, . . . , xn as �(x1, x2, . . . , xn), the function may be written as �(x) for the sake of simplifying the discussion.
Define a function Termi(x), i={overscore (1, N)}:
a) Termi(x) 1 if OPpar(i) is a SEQ-operator; b) Termi(x)=xj if OPpar(i) is an IF-operator with control input xj and OPi is a positive child; c) Termi(x)=xj if OPpar(i) is an IF-operator with control input xj and OPi is a negative child.
(Def. 1) The present discussion will now refer to the process of execution of the C++ program. During this process, all the operators are executed in the order of the operator's enumeration. For example, after the execution of the operator OPi, the operator OPi+1 may be executed. Preferably, the only exception that breaks this order occurs when executing an IF-operator. After the execution of IF-operator, the process may jump to one of two operators; negative child or positive child. If the process jumps to the positive child, the negative child is not executed (and vise versa). Thus, for each set of values of the control inputs x1, x2, . . . , xn some of the operators are executed and others are not executed. Let Condi(x) be a Boolean function that takes value 1 if and only if the operator OPi is executed when the input values are x1, x2, . . . , xn. Thus, the following is true.
Condi(x)=Condpar(i)(x)ΛTermi(x) Equation (1)
(Λ represents an AND function). It should be noted that the considered Boolean function FUNC(x,y) may take only the next values 0, y1, y2, . . . , ym. Let Valk(x), k={overscore (1,m)} be a Boolean function that may take value 1 if and only if FUNC(x,y)=yj, therefore the following may be written. FUNC ⁡ ( x , y ) = ⩔ j = 1 m ⁢ Val j ⁡ ( x ) � y j Equation ⁢ ⁢ ( 2 ) (the middle dot �.� represents an AND function, V represents an OR function).
Let Yj,j={overscore (1,m)} be a set of numbers of all operators with type result=y j and Y = ⋃ j = 1 m ⁢ Y j (∪ sets a theoretic union).
FUNC(x,y) may be equal to yj when and only when the operator OPi, iεYj, executes and for every s>i, s ε Y\Yj, operator OPs does not execute. (ε sets membership; \ sets a theoretic complement).
Consequently, the following may be written: Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⁢ ⩓ s > i , s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ Cond s ⁡ ( x ) ] Denote Boolean Function
BothCondi,s(x)=Condi(x)ΛConds(x), 1≦i≦s≦N Using this function, the following may be written: Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⁢ ⩓ s > i , s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ BothCond i , s ⁡ ( x ) ] Equation ⁢ ⁢ ( 3 ) Denote par0(i)=i, part+1(i)=par(part(i)), i={overscore (1,N)}, t≧0. For each i={overscore (1N)} consider the next sequence par 0(i), par1(i), par2(i), . . . Let d(i)≧0 be a minimal number so that part(i)=1 for each t≧d(i). The magnitude d(i) may be determined as a depth of the operator OPi in the C++ program.
For each i={overscore (1, N)} define the set
Using Equation (1), the following may be determined: Cond i ⁡ ( x ) = ⩓ t ∈ AllParents ⁡ ( i ) ⁢ Term i ⁡ ( x ) Equation ⁢ ⁢ ( 4 ) Let seq(i)≧1 be a minimal number so that the operator OPparseq(i)(i) is a SEQ-operator and define the set
AllParentsBeforeSeq(i)={par0(i), par1(i), . . . , parseq(i)−1(i)} (Def. 3)
Thus, the following may be determined: AllParents ⁡ ( i ) = ⋃ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ AllParentsBeforeSeq ⁡ ( t ) Equation ⁢ ⁢ ( 5 ) Determine TermBeforeSeq i ⁡ ( x ) = ⩓ t ∈ AllParentsBeforeSeq ⁡ ( i ) ⁢ Term i ⁡ ( x ) , i = 1 , N _ Equation ⁢ ⁢ ( 6 ) Consequently, using Equations (4), (5) and (6), the following may be determined: Cond i ⁡ ( x ) = ⩓ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ TermBeforeSeq i ⁡ ( x ) , i = 1 , N _ Equation ⁢ ⁢ ( 7 ) Consider the function ContrCondi,s(x), 1≦i≦s≦N and two sequences of parents:
par0(i), par1(i), . . . , pard(i)(i) par0(s), par1(s), . . . , pard(s)(s)
pard(i)+d(i,s)−d(s)(i), . . . , pard(i)(i)
pard(i,s)(s), . . . , pard(s)(s)
common(i,s)=pard(i,s)(s) (Def. 5)
If the operator OPcommon(i,s) is a SEQ-operator, the following may be written: BothCond i , s ⁡ ( x ) = Cond i ⁡ ( x ) ⩓ ⩓ t ∈ { s } ⋃ AllSeqParents ⁡ ( s ) t < common ⁡ ( i , s ) ⁢ TermBeforeSeq i ⁡ ( x ) Equation ⁢ ⁢ ( 8 ) The foregoing Equations (1)-(8) define the Boolean circuit that evaluates the considered Boolean function FUNC(x,y). These eight equations may be rewritten as the following four equations: TermBeforeSeq i ⁡ ( x ) = ⩓ t ∈ AllParentsBeforeSeq ⁡ ( i ) ⁢ Term i ⁡ ( x ) , i = 1 , N _ Equation ⁢ ⁢ ( 6 ) Cond i ⁡ ( x ) = ⩓ t ∈ { i } ⋃ AllSeqParents ⁡ ( i ) ⁢ TermBeforeSeq i ⁡ ( x ) , i = 1 , N _ Equation ⁢ ⁢ ( 7 ) Val j ⁡ ( x ) = ⩔ i ∈ Y j ⁢ [ Cond i ⁡ ( x ) � ⩓ s > i s ∈ Y ⁢ \ ⁢ Y j ⁢ ⫬ { ⩓ t ∈ { s } ⋃ AllSeqParents ⁡ ( s ) t < common ⁡ ( i , s ) ⁢ TermBeforeSeq i ⁡ ( x ) } ] Equation ⁢ ⁢ ( 9 ) FUNC ⁡ ( x , y ) = ⩔ j = 1 m ⁢ Val j ⁡ ( x ) � y j Equation ⁢ ⁢ ( 2 ) As shown in FIG. 5, a Boolean circuit 500 may be created according to Equations (6), (7), (9), and (2) to evaluate a logic function FUNC(x,y). The Boolean circuit 500 may include a first part 510 which may consist of AND gates only, a second part 520 which may consist of AND gates only, a third part 530 which may consist of at least one of AND, OR, and NOT gates, and a fourth part 540 which may consist of OR gates only. The first part 510 may have Termsi(x) as inputs and may output TermBeforeSeqi(x). The relationship between Termi(x) and TermBeforeSeqi(x) may be defined in Equation (6). The second part 520 may have TermBeforeSeqi(x), which may be the outputs of the first part 510, as inputs and may output Condi(x). The relationship between TermBeforeSeqi(x) and Condi(x) may be defined in Equation (7). The third part 530 may have both TermBeforeSeqi(x), which may be the outputs of the first part 510 and the inputs of the second part 520, and Condi(x), which may be the outputs of the second part 520, as inputs. The third part 530 may output Valj(x), which may be the inputs of the fourth part 540. The relationship between Valj(x) and TermBeforeSeqi(x) and Condi(x) may be defined in Equation (9). The fourth part 540 may have Valj(x) as inputs and may output FUNC(x,y). The relationship between FUNC(x,y) and Valj(x) may be defined in Equation (2).
FIG. 6 is a flow chart depicting a process 600 of evaluating a log function by a logic circuit with an optimized number of AND/OR switches created according to an exemplary embodiment of the present invention. The process 600 starts with Step 602 at which a logic function FUNC(x,y) may be defined in terms of IF-operators, EQ-operators, and SEQ-operators. Next, at Step 604, all possible sets are evaluated. For example, Termi(x) is evaluated for each operator OPi according to Def. 1; AllParents(i) is evaluated for each operator OPi according to Def. 2; AllParentsBeforeSeq(i) is evaluated for each operator OPi according to Def. 3; AllSeqParents(i) is evaluated for each operator OPi according to Def. 4; and common(i,s) is evaluated for each operators OPi and OPs according to Def. 5.
switch (xj) { case A1: OPi1; case A2: OPi2; ........... case Ak: OPik; } where A1, A2, . . . , Ak are constants, and OPi1, OPi2, . . . , OPik are operators chosen from EQ, SEQ, IF, and SWITCH operators. Operators OPi1, OPi2, . . . , OPik are called children of the considered SWITCH operator, and the considered SWITCH operator is a parent of Operators OPi1, OPi2, . . . , OPik.
That is, Termis(x)=1 if the value of control input xj=As. Otherwise, Termis(x) 0.
Termt(x)=(x[0])Λ(x[1])Λ(x[2])
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5557797 *Dec 12, 1995Sep 17, 1996Ricoh Company, Ltd.Scheduling method for automatically developing hardware patterns for integrated circuitsUS6433588 *Aug 29, 2001Aug 13, 2002Hitachi, Ltd.Logic circuit including combined pass transistor and CMOS circuits and a method of synthesizing the logic circuitUS6728939 *Jan 8, 2002Apr 27, 2004Siemens AktiengesellschaftMethod of circuit verification in digital design* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7328423 *Feb 10, 2005Feb 5, 2008Lsi Logic CorporationMethod for evaluating logic functions by logic circuits having optimized number of and/or switches* Cited by examinerClassifications U.S. Classification716/103, 716/104International ClassificationG06F17/50, G06F17/10Cooperative ClassificationG06F17/505European ClassificationG06F17/50D2Legal EventsDateCodeEventDescriptionJun 6, 2014ASAssignmentFree format text: CHANGE OF NAME;ASSIGNOR:LSI LOGIC CORPORATION;REEL/FRAME:033102/0270Owner name: LSI CORPORATION, CALIFORNIAEffective date: 20070406May 8, 2014ASAssignmentEffective date: 20140506Owner name: DEUTSCHE BANK AG NEW YORK BRANCH, AS COLLATERAL AGFree format text: PATENT SECURITY AGREEMENT;ASSIGNORS:LSI CORPORATION;AGERE SYSTEMS LLC;REEL/FRAME:032856/0031Sep 28, 2012FPAYFee paymentYear of fee payment: 8Nov 25, 2008FPAYFee paymentYear of fee payment: 4Mar 5, 2003ASAssignmentOwner name: LSI LOGIC CORPORATION, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:NIKITIN, ANDREY A.;ANDREEV, ALEXANDER E.;REEL/FRAME:013849/0577;SIGNING DATES FROM 20030226 TO 20030303Owner name: LSI LOGIC CORPORATION 1551 MCCARTHY BLVD.MILPITAS,Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:NIKITIN, ANDREY A. /AR;REEL/FRAME:013849/0577;SIGNING DATES FROM 20030226 TO 20030303RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google