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 Modified Reconstructability Analysis (MRA) and Ashenhurst-Curtis (AC) decomposition methods for decomposing 3-variable NPN-classified Boolean functions. MRA is a novel decomposition technique within the framework of set-theoretic Reconstructability Analysis. It is shown that MRA is superior to conventional Reconstructability Analysis (CRA) in decomposing NPN functions. MRA is also compared to AC using two complexity measures: log-functionality, suitable for machine learning, and the count of two-input gates, suitable for circuit design. MRA is superior to AC using the log-functionality measure and is comparable to AC using the gate count measure. The paper discusses the classification of logic functions, complexity measures, and decomposition methods. It introduces the NPN-classification of three-variable Boolean functions and the log-functionality complexity measure. The paper also presents the Ashenhurst-Curtis decomposition method and compares it with MRA. The results show that MRA decomposes more NPN classes than AC. For circuit design, MRA is superior to AC when considering the cost of inverters, but AC is superior when not considering inverters. The paper concludes that MRA is superior to both AC and CRA for decomposing 3-variable NPN-classified Boolean functions. MRA provides a simpler or equal complexity decomposition compared to CRA. While both AC and MRA decompose some but not all NPN classes, MRA decomposes more classes and thus more Boolean functions than AC. The paper also discusses future work, including the investigation of MRA decomposition for logic relations, multi-valued, and fuzzy functions.This paper compares Modified Reconstructability Analysis (MRA) and Ashenhurst-Curtis (AC) decomposition methods for decomposing 3-variable NPN-classified Boolean functions. MRA is a novel decomposition technique within the framework of set-theoretic Reconstructability Analysis. It is shown that MRA is superior to conventional Reconstructability Analysis (CRA) in decomposing NPN functions. MRA is also compared to AC using two complexity measures: log-functionality, suitable for machine learning, and the count of two-input gates, suitable for circuit design. MRA is superior to AC using the log-functionality measure and is comparable to AC using the gate count measure. The paper discusses the classification of logic functions, complexity measures, and decomposition methods. It introduces the NPN-classification of three-variable Boolean functions and the log-functionality complexity measure. The paper also presents the Ashenhurst-Curtis decomposition method and compares it with MRA. The results show that MRA decomposes more NPN classes than AC. For circuit design, MRA is superior to AC when considering the cost of inverters, but AC is superior when not considering inverters. The paper concludes that MRA is superior to both AC and CRA for decomposing 3-variable NPN-classified Boolean functions. MRA provides a simpler or equal complexity decomposition compared to CRA. While both AC and MRA decompose some but not all NPN classes, MRA decomposes more classes and thus more Boolean functions than AC. The paper also discusses future work, including the investigation of MRA decomposition for logic relations, multi-valued, and fuzzy functions.
Reach us at info@study.space
[slides and audio] A comparison of modified reconstructability analysis and Ashenhurst%E2%80%90Curtis decomposition of Boolean functions