A Comparison of Modified Reconstructability Analysis and Ashenhurst-Curtis Decomposition of Boolean Functions

A Comparison of Modified Reconstructability Analysis and Ashenhurst-Curtis Decomposition of Boolean Functions

2004 | Anas Al-Rabadi, Marek Perkowski, Martin Zwick
This paper compares the Modified Reconstructability Analysis (MRA) and Ashenhurst-Curtis (AC) decompositions of Boolean functions, focusing on 3-variable NPN-classified functions. MRA is a novel technique within set-theoretic Reconstructability Analysis, which decomposes more NPN functions compared to conventional Reconstructability Analysis (CRA). The comparison uses two complexity measures: log-functionality, suitable for machine learning, and the count of two-input gates, suitable for circuit design. MRA outperforms AC using the log-functionality measure and is comparable to AC using the two-input gate count, but different from it. The paper also discusses the NPN-classification of logic functions, the complexity measures used, and the AC decomposition method. The results show that MRA decomposes more NPN classes and functions than AC, and in some cases, it yields simpler or equal complexity decompositions compared to CRA. The paper concludes by highlighting the advantages of MRA over AC in terms of decomposability and complexity, and suggests future research directions, including the application of MRA to reversible logic and quantum computing.This paper compares the Modified Reconstructability Analysis (MRA) and Ashenhurst-Curtis (AC) decompositions of Boolean functions, focusing on 3-variable NPN-classified functions. MRA is a novel technique within set-theoretic Reconstructability Analysis, which decomposes more NPN functions compared to conventional Reconstructability Analysis (CRA). The comparison uses two complexity measures: log-functionality, suitable for machine learning, and the count of two-input gates, suitable for circuit design. MRA outperforms AC using the log-functionality measure and is comparable to AC using the two-input gate count, but different from it. The paper also discusses the NPN-classification of logic functions, the complexity measures used, and the AC decomposition method. The results show that MRA decomposes more NPN classes and functions than AC, and in some cases, it yields simpler or equal complexity decompositions compared to CRA. The paper concludes by highlighting the advantages of MRA over AC in terms of decomposability and complexity, and suggests future research directions, including the application of MRA to reversible logic and quantum computing.
Reach us at info@study.space