Ashenhurst-Curtis Decomposition Using Don’t Cares

Ashenhurst-Curtis decomposition (ACD) is a Boolean decomposition technique widely used in logic synthesis for tasks such as the decomposition of multi-valued relations, the encoding of multi-valued networks, and technology mapping into standard cells for ASICs and lookup tables (LUTs) for FPGAs. A recent truth-table-based implementation of ACD has proven effective for delay-driven LUT mapping while also reducing the number of lookup tables for improved area efficiency. This method offers better runtime performance and a higher decomposition success rate, making ACD a practical and scalable technique for modern synthesis flows. However, it does not leverage the additional flexibility provided by don’t-care conditions. In this paper, we enhance ACD by incorporating controllability don’t-cares extracted from cuts. By exploiting these additional degrees of freedom during decomposition, the proposed method achieves a higher decomposition success rate and a lower average number of LUTs per cut function. Specifically, we demonstrate that the decomposition success rate of practical functions into 6-LUTs increases from 51% to 53.4%, while the average number of LUTs per decomposition decreases from 2.50 to 2.46. Moreover, in cases where state-of-the-art methods struggle to find valid decompositions—particularly with large fixed free sets—our method shows clear improvements. Success rates increase from 16.11% to 23.27% for four late-arriving variables and from 1.58% to 4.44% for five, with only a 1.5× runtime overhead.

Download here