Abstract:
In the course of integration of a constantly growing number of gates onto silicon, efficient and reliable tools for electronic design automation (EDA) have become indispensable. Improving the performance of these tools is crucial for keeping pace with the advancements in integration. A lot of these tools share a common basis: algorithms in the Boolean domain. Improving these algorithms requires a sound knowledge of their numeric complexity to enable a thorough performance evaluation. Ternary vectors (TV) and lists of ternary vectors (TVL) are one possible representation of Boolean functions. The focus of this article lies on some basic algorithms on ternary vectors. Measures for worst-case complexities are elaborated. A probabilistic approach is proposed as a method to estimate average complexities.