基于粒计算的逻辑函数快速粒约简算法-论文.pdf

《基于粒计算的逻辑函数快速粒约简算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第42卷第6期计算机科学Vo1．42No．62015年6月ComputerScienceJune2015基于粒计算的逻辑函数快速粒约简算法马贺张裕陈泽华(太原理工大学信息工程学院太原030024)摘要逻辑函数是描述数字电路中输入变量与输出变量之间逻辑因果关系的重要工具，研究逻辑函数的约简具有重要的理论和实际意义。针对计算机化简逻辑函数普遍存在的算法复杂度高、运算速度慢的问题，将粒计算思想与启发式搜索相结合来约简逻辑函数。首先将逻辑函数转化为最小项之和的表达形式，按照粒度由粗到细的次序，在不同粒度下的知识空间中利用吸收律和最小项之间的统计信息求取信息粒，当所

2、有信息粒对应的最小项覆盖论域时，算法结束。算法由MATLAB编程实现。通过计算实例和算法复杂度分析证明了算法的快速性和有效性。关键词粒计算，启发式搜索，逻辑函数，知识约简中图法分类号TP393文献标识码ADOI10．11896／j．issn．1002—137X．2015．6．017RapidLogicFunctionReductionAlgorithmBasedonGranularComputingMAHeZHANGYUCHENZe-hua(DepartmentofInformationEngineering，TaiyuanUniversityofTech

3、nology，Taiyuan030024，China)AbstractMultivariablelogicfunctionisanimportanttoolinthedigitalcircuitthatdescribesthecausalrelationshipbe—tweeninputandoutputvariables．Theresearchonmultivariablelogicfunctionreductionplaysanimportantroleintheo—reticalandpracticalsignificance．Howeverther

4、eisnoeffectivemeanswith1OWcomplexity．Inthiswork，wefirstdecom—posedthemultivariablelogicfunctionintodifferentknowledgespacesandfoundheuristicinforrnation．Thenweusedtheimplicitstatisticalinformationtoreduettheinformationgranulesindifferentknowledgespaces．Finallyweconstructedtheresul

5、ts．Thuswefinallyproposedanalgorithmtothemultivariablelogicfunction(itisalsoavailabletotheonesthatcontainthe‘don’tcareterm’)，andthenreductedandrealizeditinMATLABTheeffectiSobvious．KeywordsGranularcomputing，Heuristicsearch，Multivariablelogicfunction，Knowledgereduction象成为与具体领域无关的方法和策

6、略l_1，其核心思想是将要1引言求解的问题分而治之，再将所得到的结果进行合并。粒计算在数字电路中，逻辑函数是描述输入变量与输出变量之分层粒化思想、多粒度空间的各种运算以及对问题的求解方间的逻辑因果关系的重要工具。逻辑函数的每一种表达方式式符合人类从各个角度分析问题、求解问题的认知规律。都对应一种具体的电路结构，逻辑函数的约简能够减少电路本文提出了一种基于粒计算的快速粒约简算法，并用元器件个数，降低电路复杂性和功耗，提高电路可靠性。MATLAB实现，达到了快速约简多变量逻辑函数的目的。传统的逻辑函数化简方法主要有公式化简法、卡诺图化首先将逻辑函数转化为最小项

7、表达式之和的形式，并写出其简法以及基于卡诺图法的QM化简法等。然而，公式化简法对应的数字最小项，然后按照粒度由粗到细的次序，在不同粒要求灵活运用布尔代数的各种规则且化简方法没有一定的规度下利用最小项间的统计信息求取信息粒，设置停止条件，算律可循。卡诺图化简法简单明了，容易理解，但不适合化简输法结束时即可得到最终约简结果。入变量数大于5的逻辑函数。以上两种方法都不利于程序的2预备知识实现_】]。Q-M算法的指导思想是利用相邻项的合并化简逻辑函数，规律性强，可利用计算机进行编程，但很繁琐，尤其是定义1(逻辑函数)[1]如果以逻辑变量作为输入，以运变量数目多时，

8、工作量很大_2]。因此学者们提出了一些改进算结果作为输出，那么当输