Computer Science ›› 2018, Vol. 45 ›› Issue (7): 167-171.doi: 10.11896/j.issn.1002-137X.2018.07.029

• Artificial Intelligence • Previous Articles     Next Articles

Rapid Knowledge Reduction of Large-scale Truth Table Based on Variable Granularity

SONG Bo ,YAN Ji-xiong, CHEN Ze-hua   

  1. College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,China
  • Received:2017-05-30 Online:2018-07-30 Published:2018-07-30

Abstract: In the analysis and design of large-scale logic circuits,the process of obtaining the simplest logic function expression from the large-scale truth table is often complicated.Aiming at this problem,a rapid knowledge reduction algorithmbased on variable granularity for large-scale truth table was proposed in this paper.With the change of the granularity of the input logical variables,the simplest logical function expression is quickly acquired from the large-scale truth table by introducing the marker matrix and the heuristic operator.Then,the algorithm is described in detail through an example,and its correctness is proved mathematically.At last,the comparative experiments of data sets are carried out to further prove the rapidness and effectiveness of the proposed algorithm.

Key words: Knowledge reduction, Large-scale truth table, Logic function, Variable granularity

CLC Number: 

  • TP393
[1]阎石.数字电子技术基础(第五版)[M].北京:高等教育出版社,2006:29-54.
[2]边计年,薛宏熙,苏明.数字系统设计自动化(第二版)[M].北京:清华大学出版社,2005:221-226.
[3]刘宝琴,罗嵘,王德生.数字电路与系统(第2版)[M].北京:清华大学出版社,2007:39-56.
[4]MCCLUSKEY E J.Minimization of Boolean Functions[J].Bell Labs Technical Journal,1958,35(6):1417-1444.
[5]JAINT K,KUSHWAHA D S,MISRA A K.Optimization of the Quine-McCluskey Method for the Minimization of the Boolean Expressions[C]∥International Conference on Autonomic and Autonomous Systems(ICAS 2008).DBLP,2008:165-168.
[6]HUANG J B.Programing implementation of the Quine-McCluskey method for minimization of boolean expression[OL].(2017-06-26). http://pdfs.semanticscholar.org/6cb2/c79bac6bf7ef341276490707b579760361d9.pdf.
[7]BANERJI S.Computer Simulation Codes for the Quine-McCluskey Method of Logic Minimization[OL].(2017-06-26).http://arxiv.org/abs/1404.3349.
[8]MAJUMDER A,CHOWDHURY B,MONDAI A J,et al.Investigation on Quine McCluskey method:A decimal manipulation based novel approach for the minimization of Boolean function[C]∥International Conference on Electronic Design,Computer Networks & Automated Verification.IEEE,2015:18-22.
[9]HUANG X,WU N,ZHANG X.Quine-McCluskey Repair Technique for Evolutionary Design of Combinational Logic Circuits[J].Lecture Notes in Engineering & Computer Science,2015,2(1):674-678.
[10]ASHMOUNIE F,RAMADAN R A,RASHED A A.Espresso for Rule Mining [J].Procedia Computer Science,2014,32:596-603.
[11]WILLER.Restructuring lattice theory:an approach based onhierarchies of concepts[M]//Ordered sets.Springer Netherlands,1982:445-470.
[12]WEI L,QI J J,ZHANG W X.Attribute reduction theory of concept lattice based on decision formalcontexts[J].Science in China (Series E:Information Sciences),2008,38(2):195-208.(in Chinese)
魏玲,祁建军,张文修.决策形式背景的概念格属性约简[J].中国科学(E辑:信息科学),2008,38(2):195-208.
[13]LI J H,MEI C L,KUMAR C A,et al.On rule acquisition in decision formal contexts[J].International Journal of Machine Learning & Cybernetics,2013,4(6):721-731.
[14]LI J H,MEI C,LV Y.Knowledge reduction in decision formal contexts[J].Knowledge-Based Systems,2011,24(5):709-715.
[15]CHEN Z H,YAN J X,CAI J.Formal Concept Analysis Based Parallel Reduction Algorithm for MIMO Truth Table[J].Journal of Electronics and Information Technology,2017,39(9):2259-2265.(in Chinese)
陈泽华,闫继雄,柴晶.基于形式概念分析的多输入多输出真值表并行约简算法[J].电子与信息学报,2017,39(9):2259-2265.
[16]LIANGJ,WANG F,DANG C,et al.A Group Incremental Approach to Feature Selection Applying Rough Set Technique[J].IEEE Transactions on Knowledge & Data Engineering,2014,26(2):294-308.
[17]ZHOUT,YANG X,FANG X,et al.Influencing factors research on CHF at low pressure,low flow conditions in narrow channel based on Rough Set Decision Model[J].Annals of Nuclear Energy,2015,77:161-164.
[18]SHIEHM D,YEH Y E,HUANG C L.Eliciting design know-ledge from affective responses using rough sets and Kansei engineering system[J].Journal of Ambient Intelligence and Huma-nized Computing,2016,7(1):107-120.
[19]DAI J H,TIAN H W,WANG W T,et al.Decision rule mining using classification consistency rate[J].Knowledge-Based Systems,2013,43(2):95-102.
[20]HU S P,ZHANG Q H,YAO L Y.An Algorithm for Rule Extraction based on Changing Granularity[J].Journal of Chongqing University of Posts and Tele-communications(Natural Science Edition),2016,28(6):856-862.(in Chinese)
胡帅鹏,张清华,姚龙洋.一种变粒度的规则提取算法[J].重庆邮电大学学报(自然科学版),2016,28(6):856-862.
[21]CHEN D G,YANG Y,DONG Z.An incremental algorithm for attribute reduction with variable precision rough sets[J].Applied Soft Computing,2016,45:129-149.
[22]JING Y G,LI T R,HUANG J F,et al.An incremental attribute reduction approach based on knowledge granularity under the attribute generalization[J].International Journal of Appro-ximate Reasoning,2016,76:80-95.
[23]ZHANGX,MEI C L,CHEN D G,et al.Multi-confidence rule acquisition and confidence-preserved attribute reduction in interval-valued decision systems[J].International Journal of Appro-ximate Reasoning,2014,55(8):1787-1804.
[24]QIAN Y H,LI S Y,LIANG J Y,et al.Pessimistic rough setbased decisions:A multi-granulation fusion strategy[J].Information Sciences,2014,264(6):196-210.
[25]DOU H L,YANG X B,SONG X N,et al.Decision-theoreticrough set:A multi-cost strategy[J].Knowledge-Based Systems,2016,91:71-83.
[26]CHEN Z H,CAO C Q,XIE G.Granular Matrix Based RapidReduction Algorithmfor Multivariable Truth Table[J].Pattern Recognition and Artificial Intelligence,2013,26(8):745-750.(in Chinese)
陈泽华,曹长青,谢刚.基于粒矩阵的多变量真值表快速约简算法[J].模式识别与人工智能,2013,26(8):745-750.
[27]CHEN Z H,MA H.Granular Matrix Based Rapid Parallel Reduction Algorithm for MIMO Truth Table[J].Journal of Electronics and Information Technology,2015,37(5):1260-1265.(in Chinese)
陈泽华,马贺.基于粒矩阵的多输入多输出真值表快速并行约简算法[J].电子与信息学报,2015,37(5):1260-1265.
[28]University of California.Free software for boolean logic optimization,analysis,and synthesis (Version 1.1.4)[EB/OL].(2012-09-09)[2017-04-19].http://www.sontrak.com.
[1] ZHANG Nan, XU Xin, TONG Xiang-rong, GAO Xue-yi and JIANG Li-li. Distribution Reduction in Inconsistent Interval-valued Decision Systems [J]. Computer Science, 2017, 44(9): 78-82.
[2] GOU Guang-lei and WANG Guo-yin. Approach to Knowledge Reduction Based on Inconsistent Confidential Dominance Principle Relation [J]. Computer Science, 2016, 43(6): 204-207.
[3] MA Li and MI Ju-sheng. Knowledge Reduction under View of Lattice [J]. Computer Science, 2015, 42(6): 79-81.
[4] MA He, ZHANG Yu and CHEN Ze-hua. Rapid Logic Function Reduction Algorithm Based on Granular Computing [J]. Computer Science, 2015, 42(6): 76-78.
[5] LUO Qing-bin,YANG Guo-wu,SHAO Yuan-hua and FAN Fu-you. Judgment of NP-NP Equivalence for 3-bit Reversible Logic Functions via Fixed Polarity Reed-muller Forms [J]. Computer Science, 2013, 40(10): 218-220.
[6] QIAN Jin,MIAO Duo-qian, ZHANG Zchua. Research on Discernibility Matrix Knowledge Reduction Algorithm in Cloud Computing [J]. Computer Science, 2011, 38(8): 193-196.
[7] CHEN Zi-chun,LIU Peng-hui.QIN Ke-yun. Knowledge Reduction of Set-valued Information Systems Based on Dominance Relation [J]. Computer Science, 2009, 36(12): 176-178.
[8] . [J]. Computer Science, 2007, 34(4): 182-184.
[9] . [J]. Computer Science, 2006, 33(7): 179-181.
[10] . [J]. Computer Science, 2006, 33(6): 175-178.
[11] XU Wei-Hua, ZHANG Wen-Xiu (Institute of Information and System Sciences, Faculty of Science, Xi ' an Jiaotong University, Xi ' an 710049). [J]. Computer Science, 2006, 33(2): 182-184.
[12] . [J]. Computer Science, 2005, 32(11): 150-151.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!