采用FDDs实现FPRM电路延时和面积优化

Delay and area optimization for FPRM circuits by FDDs

Functional Decision Diagrams(FDDs)是Reed-Muller(RM)展开式的一种图形表达方式,其变量顺序和RM展开式极性共同决定对应电路的延时和面积.通过对FDDs和固定极性RM(FPRM)展开式的研究,提出采用FDDs的FPRM电路延时和面积优化算法.首先根据固定极性特点,利用FDDs建立FPRM电路延时估计模型;然后结合延时估计模型、列表技术和FDDs变量顺序搜索策略,按电路延时和面积对中小规模和大规模电路进行最佳极性和变量顺序搜索;最后对PLA格式的MCNC Benchmark电路进行测试,结果表明该算法对延时和面积的优化效果显著.

Functional Decision Diagrams（FDDs） are a graphical expression for Reed-Muller（RM） expansion,and its variable order and polarity jointly influence the delay and area of the corresponding circuit.By studying FDDs and fixed polarity RM（FPRM） expansion,a delay and area optimization algorithm is presented.Firstly,a delay evaluation model is set up by FDDs.Then by combining the tabular technique and the search strategy of variable order,the optimal polarity and variable order are searched for both medium-scale and large-scale circuits according to the delay and area.Finally,the algorithm is tested with MCNC Benchmarks.The results show that the proposed algorithm is very effective for delay and area optimization.