## Abstract

In an earlier paper, we presented a method by which the communication complexity of a Boolean function could be computed. Also, we showed that finding a partition of the input variables with low communication complexity could be made part of a viable approach to logic synthesis. Unfortunately, the running time to compute the communication complexity of a given partitioning (i.e., the number of compatible classes) using this method is Ω(2”). Also, all possible partitionings were enumerated. Hence, this approach to logic synthesis is practical only for functions with a small number of inputs. In this paper, we present a new method for computing the communication complexity of a given partitioning whose running time is O(p q), where p is the number of implicants (cubes) in the minimum covering of the function and q is the number of different overlapping of those cubes. We also discuss two heuristics for finding a good partition which give encouraging results. Together, these two techniques allow a much larger class of functions to be synthesized.

Original language | English (US) |
---|---|

Pages (from-to) | 545-554 |

Number of pages | 10 |

Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |

Volume | 11 |

Issue number | 5 |

DOIs | |

State | Published - May 1992 |

## All Science Journal Classification (ASJC) codes

- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering