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 predetermined multiple-valued function and comprising a network for each of the multiple values of the function, the method comprising:
 for at least one of the networks relating to a value of the function:
 deriving a covering table for the pertaining value of the function and having 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 relating to the value of the function, 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. 
   
     
     
         2 . A method according to  claim 1 , 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 of the subset. 
     
     
         3 . A method according to  claim 1 , wherein the deriving step comprises the steps of:
 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.   
     
     
         4 . A method according to  claim 1 , wherein the deriving step comprises the steps of:
 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.   
     
     
         5 . A method of deriving a switch network adapted to carry out a predetermined Boolean function and comprising a pull-up network and a pull-down network, the method comprising:
 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,   deriving the pull-up network on the basis of 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,   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.   
     
     
         6 . A method according to  claim 5 , 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 of the subset. 
     
     
         7 . A method according to  claim 5 , wherein the deriving step comprises the steps of:
 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.   
     
     
         8 . A method according to  claim 5 , wherein the deriving step comprises the steps of:
 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.   
     
     
         9 . A computer program adapted to control a processor to carry out the method according to  claim 5 .