Enhanced 2 <i> ^nd </i> -Order Threshold Function Identification with Application to 2 <i> ^nd </i> -Order Threshold Logic Network Synthesis

Threshold logic is an alternative representation of conventional Boolean logic and re-attracted researchers’ attention in recent years. Previous works have demonstrated that a 2 nd -order threshold logic gate (2-TLG) could have a lower area cost than a 1 st -order TLG (1-TLG) and proposed an integer linear programming (ILP)-based method for identifying 2-TLGs. However, the method could suffer from inefficiency for complex Boolean functions. In this article, we first enhance the ILP-based method for transforming a 1-TLG into a 2-TLG with a lower area cost. We observe that for a 2-TLG, most of the 2 nd -order weights (2-weights) are zero. That is, in the ILP formulation, most of the variables for the 2-weights can be set to zero without quality sacrifice. Thus, to identify the 2-weights that are more likely to be non-zero, we first propose sufficient conditions to derive a 2-TLG from a 1-TLG by extracting 2-weights. We then simplify the ILP formulation by eliminating the non-extracted 2-weights to facilitate the ILP-solving process. Furthermore, we propose a synthesis scheme for 2 nd -order threshold logic based on the enhanced ILP-based method. We leverage the state-of-the-art 1 st -order threshold logic synthesis technique to generate a 1 st -order threshold logic network (1-TLN) first and then transform it into a 2 nd -order TLN (2-TLN). The experimental results demonstrate that when transforming a set of 1-TLGs into 2-TLGs, the enhanced ILP-based method reduces the total CPU time by approximately 31% across all 1-TLGs, with only an average quality loss of 0.07% in terms of the area cost reduction rate. Additionally, when transforming two sets of 1-TLNs with different maximum fanin counts into 2-TLNs, the proposed method achieves average area cost reductions of 8.04% and 22.18%, respectively.