不完全规定函数的启发式ESOP最小化算法
|
摘要
对不完全规定函数的无关项进行合理赋值,有助于降低其积之异或和(Exclusive-or Sum of Products,ESOP)表示的复杂度.提出一种边实施无关项赋值边进行ESOP化简的不完全规定函数的启发式ESOP最小化算法.该算法采用立方体集合表示函数,首先借助前瞻策略根据立方体间的邻近关系在ReedMuller域实施无关项赋值,然后使用Exorlink运算进行ESOP化简,并对不能降低ESOP复杂度的无关项赋值采用回溯策略进行回溯.使用一组不同规模的MCNC(Microelectronics Center of North China)不完全规定函数对算法进行验证的结果表明,所提算法能够减少ESOP的立方体数以及文字数,并且能够适用于输入数较多的不完全规定函数.
For incompletely specified functions,reasonable don't care(DC)assignment can help reduce the complexity of their exclusive-or sum of products(ESOP)forms.A heuristic ESOP minimization algorithm which incorporates DC assignment into the process of ESOP reduction was proposed for incompletely specified functions.By using cubes set to represent functions,the proposed algorithm first carries out DC assignment in Reed-Muller domain according to the adjacent relations between cubes with the help of look-ahead strategy,then performs ESOP reduction by using Exorlink operations,and applies back trace strategy to those DC assignments that can not reduce the complexity of ESOP.A set of incompletely specified functions from MCNC was used to validate the proposed algorithm.Results show that the proposed algorithm can reduce the number of cubes and the number of literals of ESOP,and can be applied to incompletely specified functions with many inputs.
For incompletely specified functions,reasonable don't care(DC)assignment can help reduce the complexity of their exclusive-or sum of products(ESOP)forms.A heuristic ESOP minimization algorithm which incorporates DC assignment into the process of ESOP reduction was proposed for incompletely specified functions.By using cubes set to represent functions,the proposed algorithm first carries out DC assignment in Reed-Muller domain according to the adjacent relations between cubes with the help of look-ahead strategy,then performs ESOP reduction by using Exorlink operations,and applies back trace strategy to those DC assignments that can not reduce the complexity of ESOP.A set of incompletely specified functions from MCNC was used to validate the proposed algorithm.Results show that the proposed algorithm can reduce the number of cubes and the number of literals of ESOP,and can be applied to incompletely specified functions with many inputs.
引文
[1]卜登立,江建慧.基于对偶逻辑的混合极性RM电路极性转换和优化方法[J].电子学报,2015,43(1):79-85.Bu Dengli,Jiang Jianhui.Dual logic based polarity conversion and optimization of mixed polarity RM circuits[J].Acta Electronica Sinica,2015,43(1):79-85.(in Chinese)
[2]Rahaman H,Das D K,Bhattacharya B B.Testable design of AND-EXOR logic networks with universal test sets[J].Computers and Electrical Engineering,2009,35(5):644-658.
[3]Monteiro C,Takahashi Y,Sekine T.Low-power secure S-box circuit using charge-sharing symmetric adiabatic logic for advanced encryption standard hardware design[J].IET Circuits,Devices&Systems,2015,9(5):362-369.
[4]卜登立.快速启发式ESOP电路面积优化算法[J].计算机辅助设计与图形学学报,2015,27(11):2161-2168.Bu Dengli.Fast heuristic area optimization algorithm for ESOP circuits[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(11):2161-2168.(in Chinese)
[5]Shafaei A,Saeedi M,Pedram M.Cofactor sharing for reversible logic synthesis[J].ACM Journal on Emerging Technologies in Computing Systems,2014,11(2):1-21.
[6]Datta K,Gokhale A,Sengupta I,et al.An ESOPbased reversible circuit synthesis flow using simulated annealing[J].Applied Computation and Security Systems,2015,305:131-144.
[7]Mishchenko A,Perkowski M.Fast heuristic minimization of exclusive-sums-of-products[C].Proceedings of the 5th Reed-Muller Workshop,Mississippi,2001:241-249.
[8]张巧文,汪鹏君,胡江.基于分层超立方体的精确ESOP最小化[J].计算机辅助设计与图形学学报,2016,28(1):172-179.Zhang Qiaowen,Wang Pengjun,Hu Jiang.Exact minimization of ESOP expressions based on hierarchical hypercube[J].Journal of Computer-Aided Design&Computer Graphics,2016,28(1):172-179.(in Chinese)
[9]Hirayama T,Nishitani Y.Exact minimization of ANDEXOR expressions of practical benchmark functions[J].Journal of Circuits,Systems,and Computers,2009,18(3):465-486.
[10]Chang K H,Bertacco V,Markov I L,et al.Logic synthesis and circuit customization using extensive external don't-cares[J].ACM Transactions on Design Automation of Electronic Systems,2010,15(3):1-26.
[11]Sampson M,Kalathas M,Voudouris D,et al.Exact ESOP expression for incompletely specified functions[J].Integration,the VLSI Journal,2012,45(2):197-204.
[12]汪迪生,汪鹏君.包含无关项的MPRM展开式最小化算法[J].浙江大学学报(理学版),2014,41(1):38-42.Wang Disheng,Wang Pengjun.Algorithm about minimization of MPRM expansions including don't care terms[J].Journal of Zhejiang University(Science Edition),2014,41(1):38-42.(in Chinese)
[13]Brand D,Bergamaschi R A,Stok L.Don't cares in synthesis:theoretical pitfalls and practical solutions[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(4):285-304.
[2]Rahaman H,Das D K,Bhattacharya B B.Testable design of AND-EXOR logic networks with universal test sets[J].Computers and Electrical Engineering,2009,35(5):644-658.
[3]Monteiro C,Takahashi Y,Sekine T.Low-power secure S-box circuit using charge-sharing symmetric adiabatic logic for advanced encryption standard hardware design[J].IET Circuits,Devices&Systems,2015,9(5):362-369.
[4]卜登立.快速启发式ESOP电路面积优化算法[J].计算机辅助设计与图形学学报,2015,27(11):2161-2168.Bu Dengli.Fast heuristic area optimization algorithm for ESOP circuits[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(11):2161-2168.(in Chinese)
[5]Shafaei A,Saeedi M,Pedram M.Cofactor sharing for reversible logic synthesis[J].ACM Journal on Emerging Technologies in Computing Systems,2014,11(2):1-21.
[6]Datta K,Gokhale A,Sengupta I,et al.An ESOPbased reversible circuit synthesis flow using simulated annealing[J].Applied Computation and Security Systems,2015,305:131-144.
[7]Mishchenko A,Perkowski M.Fast heuristic minimization of exclusive-sums-of-products[C].Proceedings of the 5th Reed-Muller Workshop,Mississippi,2001:241-249.
[8]张巧文,汪鹏君,胡江.基于分层超立方体的精确ESOP最小化[J].计算机辅助设计与图形学学报,2016,28(1):172-179.Zhang Qiaowen,Wang Pengjun,Hu Jiang.Exact minimization of ESOP expressions based on hierarchical hypercube[J].Journal of Computer-Aided Design&Computer Graphics,2016,28(1):172-179.(in Chinese)
[9]Hirayama T,Nishitani Y.Exact minimization of ANDEXOR expressions of practical benchmark functions[J].Journal of Circuits,Systems,and Computers,2009,18(3):465-486.
[10]Chang K H,Bertacco V,Markov I L,et al.Logic synthesis and circuit customization using extensive external don't-cares[J].ACM Transactions on Design Automation of Electronic Systems,2010,15(3):1-26.
[11]Sampson M,Kalathas M,Voudouris D,et al.Exact ESOP expression for incompletely specified functions[J].Integration,the VLSI Journal,2012,45(2):197-204.
[12]汪迪生,汪鹏君.包含无关项的MPRM展开式最小化算法[J].浙江大学学报(理学版),2014,41(1):38-42.Wang Disheng,Wang Pengjun.Algorithm about minimization of MPRM expansions including don't care terms[J].Journal of Zhejiang University(Science Edition),2014,41(1):38-42.(in Chinese)
[13]Brand D,Bergamaschi R A,Stok L.Don't cares in synthesis:theoretical pitfalls and practical solutions[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(4):285-304.