Please wait a minute...
浙江大学学报(工学版)
J4  2012, Vol. 46 Issue (11): 2089-2096    DOI: 10.3785/j.issn.1008-973X.2012.11.022
电信技术     
适合RM逻辑实现的逻辑搜索和拆分算法
王伦耀1,2, 夏银水2,陈偕雄1
1. 浙江大学 信电系, 浙江 杭州 310029； 2. 宁波大学 信息科学与工程学院, 浙江 宁波 315211
Search and Decomposition Algorithm for RM
Logic Implementation
WANG Lun-yao1,2 , XIA Yin-shui2 , CHEN Xie-xiong1
1. Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310029, China;
2. Faculty of Information Science and Engineering, Ningbo University, Ningbo 315211, China
 全文: PDF  HTML
摘要：

针对以往算法在搜索适合Reed-Muller(RM)逻辑实现的逻辑子覆盖中存在的不足,提出基于不相交乘积项的搜索方法.该方法通过将逻辑函数转化为不相交乘积项的集合,并搜索符合约束条件的不相交乘积项的多数覆盖以及根据乘积项之间的位操作结果,将逻辑函数拆分成二部分,使之分别适合RM逻辑实现和传统布尔逻辑实现.提出的算法用C编程实现,并用MCNC电路测试.实验结果表明,相比于以往的方法,提出的算法能够有效扩大搜索范围,并且具有运行速度快且对逻辑函数的输入变量数量不敏感等特点.
Abstract:

With the deficiency of the published algorithms in searching and extracting the sub-cover suitable for Reed-Muller (RM) logic implementation in the cover of a logic function, an algorithm based on the disjointed cubes was proposed. By searching the majority cubes of the disjointed cubes and checking the results of the bit-wise operation of the cubes, the whole cover of the function was divided into two sub-covers, one for RM logic implementation and the other for the traditional Boolean logic implementation. The proposed algorithm was implemented using C and tested with MCNC benchmarks.  Compared to the reported methods, the searching capacity of the proposed algorithm is extended and its computing efficiency is improved. Further, the number of variables of the function has little effect on the speed of the proposed algorithm．
出版日期: 2012-12-11
:  TP 17  
基金资助:

国家自然科学基金重点资助项目（61131001）；国家自然科学基金资助项目（61228015）；国家教育部博士点基金资助（20113305110001）；浙江省自然科学基金资助项目（LY12F01014）.
通讯作者: 陈偕雄，男，教授.     E-mail: paul0595@hotmail.com
作者简介: 王伦耀（1972 -），男，副教授，从事数字逻辑电路综合与优化研究.E-mail: wanglunyao@nbu.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

王伦耀, 夏银水,陈偕雄. 适合RM逻辑实现的逻辑搜索和拆分算法[J]. J4, 2012, 46(11): 2089-2096.

WANG Lun-yao , XIA Yin-shui , CHEN Xie-xiong. Search and Decomposition Algorithm for RM
Logic Implementation. J4, 2012, 46(11): 2089-2096.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2012.11.022    或    http://www.zjujournals.com/eng/CN/Y2012/V46/I11/2089

［1］ MCGEER P C, SANGHAVI J V, BRAYTON R K, et al. ESPRESSO SIGNATURE: a new exact minimizer for logic functions ［J］. IEEE Transactions on Very Large Scale integration (VLSI) Systems, 1993, 1(4): 432-440．
［2］ Berkeley Logic synthesis and Verification Group. ABC:Asystem for sequential synthesis and verification \
[EB/OL\].\
[2011-10-17\]．http://www.eecs.bcrkeley.edu/~alanmi/abc/.
［3］ WANG Lunyao, XIA Yinshui, Chen Xiexiong, et al. ReedMuller function optimization techniques with onset table［J］. Journal of Zhejiang University ScienceC, 2011, 12(4):288-296．
［4］ JANKOVIC D, STANKOVIC R S, MORAGA C. Optimization of polynomial expressions by using the extended dual polarity ［J］. IEEE Transactions on Computers, 2009, 58(12): 1710-1725．
［5］ PRADHAN S N, CHATTOPADHYAY S, Twolevel ANDXOR networks synthesis with areapower tradeoff ［J］. International Journal of Computer Science and Network Security, 2008, 8(9): 365-375．
［6］ NAVI K; MAEEN M, FOROUTAN V, et al. A novel lowpower fulladder cell for low voltage ［J］. The VLSI Journal of Integration, 2009,42(4):457-467．
［7］ MUMA K, CHEN Dongdong, CHOI Younhee, et al. Combining ESOP minimization with BDDbased decomposition for improved FPGA synthesis ［J］. Canadian Journal of Electrical and Computer Engineering, 2008, 33(3): 77-182．
［8］ REDDY S M. Easily testable realization for logic functions ［J］. IEEE Transaction on Computers, 1971, C21(11): 1183-1188．
［9］ DUBROVA E, BENGTSSON T. An algorithm for detecting XORtype logic ［C］∥ Proceeding of 5th International Workshop of Applications of ReedMuller Expansion in Circuit Design. Starkville, Mississippi, USA, ［s. 1.］, IEEE, 2001: 271-276．
［10］ XIA Yinshui, SUN Fei, MAO Keyi. A detection method for logic functions suitable for duallogic synthesis ［J］. Progress in Natural Science, 2009, 19: 1311-1315．
［11］ 夏银水, 毛科益, 叶锡恩. 逻辑函数适合双逻辑实现的探测算法［J］. 计算机辅助设计与图形学报,2007,19(12):1522-1527．
XIA Yinshui, MAO Keyi, YE Xien. Detection algorithm for logic functions to benefit from dual logic implementation ［J］. Journal of ComputerAided Design & Computer Graphics, 2007, 19(12): 1522-1527.
［12］ WANG Lunyao, XIA Yinshui, Chen Xiexiong. Logic detection algorithm for dual logic implementations based on majority cubes［C］∥ The International Conference on Computer Application and System Modeling. Taiyuan, China: ［s. n.］, IEEE, 2010 ,14:503-507．
［13］ 叶锡恩, 毛科益, 夏银水. 基于乘积项的双逻辑实现探测算法［J］. 电子学报, 2009, 37(5): 961-965．
YE Xien, MAO Keyi, XIA Yinshui. Algorithms for detecting dual logic based on product term［J］. Acta Electronis Sinica, 2009. 37(5):961-965.
［14］ SUN Fei, XIA Yinshui. BDD based detection algorithm or XORtype logic［C］∥ 11th IEEE International Conference on Communication Technology Proceedings. Hangzhou: ［s. n.］, 2008: 351-354．
［15］ TRAN A, WANG J. Decomposition method for minimisation of ReedMuller polynomials in mixed polarity［J］. IEE ProceedingE, 1993, 140(1): 65-68．
［16］ WANG L, ALMAINI A E A. Optimisation of ReedMuller PLA implementations［J］. IEE ProceedingCircuits Devices and Systems, 2002, 149(2): 119-128．
［17］ 边计年, 薛宏熙, 苏明, 等. 数字系统设计自动化［M］. 清华大学出版社, 2005:209-215．
［18］ JASSANI B A Al, URQUHART N, ALMAINI A E A. Manipulation and optimization techniques for Boolean logic［J］. IET Computers & Digital Techniques, 2010, 4(3): 227-239．
No related articles found!