Evaluation time estimation for pass transistor logic circuits

This paper describes a mathematical model for the prediction of binary decision diagram (BDD) depth measures, such as the longest path length (LPL) and the average path length (APL). The formal core of the model is a formula for the average LPL and APL over the set of BDD derived from Boolean logic expressions with a given number of variables and product terms. The formula was determined by extensive empirical studies of these measures. The proposed model can provide valuable information about Pass Transistor Logic (PTL) evaluation time for any variable ordering method without building the BDD. Our experimental results show good correlation between the theoretical results and those predicted by the mathematical model, which will greatly reduce the time complexity of applications that use BDDs