计算机科学 ›› 2018, Vol. 45 ›› Issue (7): 167-171.doi: 10.11896/j.issn.1002-137X.2018.07.029

• 人工智能 • 上一篇    下一篇

基于变粒度的大规模真值表快速知识约简

宋波,闫继雄,陈泽华   

  1. 太原理工大学信息工程学院 太原030024
  • 收稿日期:2017-05-30 出版日期:2018-07-30 发布日期:2018-07-30
  • 作者简介:宋 波(1991-),男,硕士,CCF会员,主要研究方向为粗糙集、形式概念分析;闫继雄(1992-),男,硕士,主要研究方向为粗糙集、形式概念分析;陈泽华(1974-),女,博士,教授,CCF高级会员,主要研究方向为粒计算、工业大数据、智能信息处理及应用,E-mail:zehuachen@163.com(通信作者)。
  • 基金资助:
    本文受国家自然科学基金(61402319,61403273),山西省自然科学基金项目(2014021022-4)资助。

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

中图分类号: 

  • 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] 张楠,许鑫,童向荣,高学义,姜丽丽.
不协调区间值决策系统的分布约简
Distribution Reduction in Inconsistent Interval-valued Decision Systems
计算机科学, 2017, 44(9): 78-82. https://doi.org/10.11896/j.issn.1002-137X.2017.09.016
[2] 苟光磊,王国胤.
基于不协调置信优势原理关系的知识约简
Approach to Knowledge Reduction Based on Inconsistent Confidential Dominance Principle Relation
计算机科学, 2016, 43(6): 204-207. https://doi.org/10.11896/j.issn.1002-137X.2016.06.041
[3] 马丽,米据生.
格观念下的知识约简
Knowledge Reduction under View of Lattice
计算机科学, 2015, 42(6): 79-81. https://doi.org/10.11896/j.issn.1002-137X.2015.06.018
[4] 马贺,张裕,陈泽华.
基于粒计算的逻辑函数快速粒约简算法
Rapid Logic Function Reduction Algorithm Based on Granular Computing
计算机科学, 2015, 42(6): 76-78. https://doi.org/10.11896/j.issn.1002-137X.2015.06.017
[5] 罗庆斌,杨国武,邵院华,樊富有.
基于固定极Reed Muller展开式的3阶可逆
Judgment of NP-NP Equivalence for 3-bit Reversible Logic Functions via Fixed Polarity Reed-muller Forms
计算机科学, 2013, 40(10): 218-220.
[6] 钱进,苗夺谦,张泽华.
云计算环境下差别矩阵知识约简算法研究
Research on Discernibility Matrix Knowledge Reduction Algorithm in Cloud Computing
计算机科学, 2011, 38(8): 193-196.
[7] 张明,唐振民,徐维艳,杨习贝.
可变粒度粗糙集
Variable Granulation Rough Set
计算机科学, 2011, 38(10): 220-222.
[8] 陈子春,刘鹏惠,秦克云.
集值信息系统基于优势关系下的知识约简
Knowledge Reduction of Set-valued Information Systems Based on Dominance Relation
计算机科学, 2009, 36(12): 176-178.
[9] .
集值决策信息系统的知识约简与规则提取

计算机科学, 2007, 34(4): 182-184.
[10] .
集值决策信息系统的知识约简与属性特征

计算机科学, 2006, 33(7): 179-181.
[11] .
基于不可约元的概念格属性特征识别方法

计算机科学, 2006, 33(6): 175-178.
[12] 徐伟华 张文修.
基于优势关系下不协调目标信息系统的知识约简

计算机科学, 2006, 33(2): 182-184.
[13] .
关于贝叶斯粗糙集模型的知识约简

计算机科学, 2005, 32(11): 150-151.
[14] .
一种启发式知识约简算法

计算机科学, 2005, 32(10): 135-138.
[15] 张继福 李银花 郑链.
基于属性约简的恒星光谱数据分类规则挖掘系统研究

计算机科学, 2004, 31(10): 118-120.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!