Methods of deriving switch networks

Abstract

A method of determining the lowest possible number of serial switches in a pull-up plane or a pull-down plane of a network implementing a logic function. The same method may be used in any multi-value function. Also, the method may be used in generating switch networks to be implemented as standard cells implementations of combinational logic cells. The minimum number of switches can also be used as a criterion for technology mapping devoted to automatic cell generation. The method is based on the use of a covering table to derive a sum of products where individual cubes have a minimum literal count.

1 . A method of deriving a switch network adapted to carry out a multiple-valued function and comprising a network relating to each of the multiple values of the function, the method comprising:
 deriving one potential network for each of the multiple values of the function and using each of a plurality of different methods, and   for each of the multiple values of the function, selecting, as the derived, potential network of the value of the function and of the switch network, one of the derived networks for the value,   
       where the selected networks are derived by different methods. 
     
     
         2 . A method according to  claim 1 , wherein the selecting step comprises selecting as the network relating to the value of the function a derived, potential network having the lowest number of serial switches. 
     
     
         3 . A method according to  claim 1 , wherein the selecting step comprises the steps of:
 estimating a lowest number of serial switches of one or more of the networks by
 deriving a covering table relating to the actual value of the function and having a number of cubes each covering one or more minterms, and 
 determining the lowest number of serial switches of the network as the number of literals in a cube having the largest number of literals and covering a minterm not covered by a cube having a lower number of literals, and 
   selecting the network as a derived, potential network of the value of the function, the network fulfilling a predetermined criterion relating to the number of serial switches therein, the determined lowest number of serial switches, and/or the total number of switches in the potential network relating to the value of the function.   
     
     
         4 . A method according to  claim 3 , wherein the selecting step comprises the step of selecting, as the network relating to the value, the potential, derived network having a number of serially connected switches equal to the determined lowest number of serial switches. 
     
     
         5 . A method according to  claim 3 , wherein the selecting step comprises the step of selecting, as the network relating to the value, the potential, derived network having the lowest total number of switches. 
     
     
         6 . A method according to  claim 1 , wherein the deriving step comprises deriving a potential network by
 deriving a covering table for the pertaining value of the function and representing a number of cubes each covering one or more minterms,   estimating the lowest number of serial switches in the network as the number of literals in a cube having the largest number of literals and covering a minterm not covered by a cube having a lower number of literals, and   deriving the network on the basis of cubes of the covering table having a number of literals smaller than or equal to the estimated lowest number of serial switches of the network, the network having a number of parallel paths, each parallel path being defined by a cube and having a number of serially interconnected switches each having an input corresponding to a literal of the cube.   
     
     
         7 . A method according to  claim 6 , wherein the deriving step comprises deriving the network from only a subset of the cubes of the covering table, where each cube in the subset covers at least one minterm not covered by other cubes of the subset. 
     
     
         8 . A method according to  claim 1 , further comprising the step of improving a selected network by:
 identifying two parallel paths each comprising a switch having the same input and   changing one of the identified paths to share the switch of the other identified path with that input.   
     
     
         9 . A method according to  claim 1 , further comprising the step of improving a selected network by:
 determining an ordering of the inputs of the switches, from lowest to highest,   defining a direction in a path of the network, and   interchanging positions of two switches of the path if a lower order switch is positioned, along the direction, before a higher order switch.   
     
     
         10 . A computer program adapted to control a processor to carry out the method of  claim 1 . 
     
     
         11 . A method of deriving a switch network adapted to carry out a Boolean function and comprising a pull-up network and a pull-down network, the method comprising:
 deriving one potential pull-up network and one potential pull-down network using each of a plurality of different methods,   selecting, as the pull-up network of the switch network, one of the derived pull-up networks, and   selecting, as the pull-down network of the switch network, one of the pull-down networks,   
       where the selected pull-up network and the selected pull-down network are derived by different methods. 
     
     
         12 . A method according to  claim 11 , wherein at least one of the selecting steps comprises selecting as the pull-up/down network a potential pull-up/down network having the lowest number of serial switches. 
     
     
         13 . A method according to  claim 11 , wherein the step of selecting the pull-up network comprises the steps of:
 estimating a lowest number of serial switches in the pull-up network by
 deriving a covering table of the function having a number of cubes each covering one or more minterms, and 
 determining the lowest number of serial switches as the number of literals in a cube having the largest number of literals and covering a minterm not covered by a cube having a lower number of literals, and 
   selecting the pull-up network as a derived, potential pull-up network fulfilling a predetermined criterion relating to the number of serial switches therein, the determined lowest number of serial switches, and/or the total number of switches in the potential pull-up network.   
     
     
         14 . A method according to  claim 11 , wherein the step of selecting the pull-down network comprises the steps of:
 estimating a lowest number of serial switches in the pull-down network by
 deriving a covering table of the inverted function and having a number of cubes each covering one or more minterms, and 
 determining the lowest number of serial switches as the number of literals in a cube having the largest number of literals and covering a minterm not covered by a cube having a lower number of literals, and 
   selecting the pull-down network as a derived, potential pull-down network fulfilling a predetermined criterion relating to the number of serial switches therein, the determined lowest number of serial switches, and/or the total number of switches in the potential pull-down network.   
     
     
         15 . A method according to  claim 13 , wherein the selecting step comprises the step of selecting, as the pull-up/down network, the potential pull-up/down network having a number of serially connected switches equal to the determined lowest number of serial switches. 
     
     
         16 . A method according to  claim 13 , wherein the selecting step comprises the step of selecting, as the pull-up/down network, the potential pull-up/down network having the lowest total number of switches. 
     
     
         17 . A method according to  claim 11 , wherein the deriving step of deriving a potential pull-up network comprises:
 deriving from the function a first covering table having a number of cubes each covering one or more minterms,   estimating the lowest number of serial switches in the pull-up network as the number of literals in a cube of the first covering table having the largest number of literals and covering a minterm not covered by a cube having a lower number of literals, and   deriving the pull-up network on the basis of the cubes of the first covering table having a number of literals smaller than or equal to the estimated lowest number of serial switches of the pull-up network, the network having a number of parallel paths, each parallel path being defined by one cube and having a number of serially interconnected switches each having an input corresponding to a literal of the cube.   
     
     
         18 . A method according to  claim 11 , wherein the deriving step of deriving a potential pull-down network comprises:
 deriving from the inverted function a second covering table having a number of cubes each covering one or more minterms,   estimating the lowest number of serial switches in the pull-down network as the number of literals in a cube of the second covering table having the largest number of literals and covering a minterm not covered by a cube having a lower number of literals, and   deriving the pull-down network on the basis of cubes of the second covering table having a number of literals smaller than or equal to the estimated lowest number of serial switches of the pull-down network, the network having a number of parallel paths, each parallel path being defined by one cube and having a number of serially interconnected switches each having an input corresponding to a literal of the cube.   
     
     
         19 . A method according to  claim 17  or  18 , wherein the deriving step comprises deriving the network from a subset of the cubes of the covering table, where each cube in the subset covers at least one minterm not covered by other cubes in the subset. 
     
     
         20 . A method according to  claim 11 , further comprising the steps of improving a selected network by:
 identifying two parallel paths each comprising a switch having the same input and   changing one of the identified paths to share the switch of the other identified path with that input.   
     
     
         21 . A method according to  claim 11 , further comprising the steps of improving a selected network by:
 determining an ordering of the inputs of the switches, from lowest to highest,   defining a direction in a path of the network, and   interchanging positions of two switches of the path if a lower order switch is positioned, along the direction, before a higher order switch.   
     
     
         22 . A computer program adapted to control a processor to carry out the method according to  claim 11 .