An input variable partitioning algorithm for functional decomposition of a system of Boolean functions based on the tabular method

作者：Afshord Saeid Taghavi^*; Pottosin Yuri; Arasteh Bahman

来源：Discrete Applied Mathematics, 2015, 185: 208-219.

DOI：10.1016/j.dam.2014.12.013

• Boolean functions
• Functional decomposition
• Variable partitioning
• Cover map
• Compact table

Functional decomposition is a fundamental method for the optimization of multi-level logic circuits by breaking down a complex circuit into smaller and hopefully simpler subcircuits. The problem of searching for an appropriate partition of input variables is the first step in the decomposition process, and it is a challenging task in the logic synthesis. The serial, two-block disjoint decomposition of a system of completely specified Boolean functions is investigated. An input variable partitioning algorithm is proposed, which is used for functional decomposition along with a tabular method. It is based on using the ternary matrix cover approach. A method for constructing the cover map that has the structure of the Kamaugh map is also presented. It is used in a step of the tabular method during the decomposition. There is a chance in a decomposable system, to choose such a solution of the task to reduce the circuit size exponentially. The paper emphasizes on obtaining the bestpossible partition in an efficient manner. A set of experiments has been carried out on the generated systems of Boolean functions and standard benchmarks. The results confirm the efficiency and effectiveness of the suggested algorithm along with the ternary matrix cover approach. The obtained solutions are optimal in the most cases, according to a certain criterion.

• 出版日期2015-4-20