带整数关系表达式的布尔表达式化简方法研究
|
摘要
布尔表达式化简是一个NP问题,求给定布尔表达式的最简等价式的系统性算法是一个仍待解决的问题。布尔表达式的化简在逻辑电路的优化设计、开关代数及编码设计中都有很多应用。
为了减少硬件设计中的输入变量,缩短硬件实现过程中的时间延迟,现有的方法一般仅考虑对布尔表达式实行化简,目前尚没有发现对带有整数关系表达式的布尔表达式化简方面的研究。
本文的工作以描述和寻找带有整数关系表达式的布尔表达式的若干类可以化简的情形为出发点,目标是找到若干可以化简的类,将可以化简的情形加以描述并结合实例说明所给方法的正确性、可行性。
本文工作的主要结果是：
(1)含加减运算的布尔表达式,根据关系运算符“=,≠,≥,>,≤,<”进行分类,实现了形如f=(R11∧R12∧…∧R1n)∨…∨(Rm1∧Rm2∧…∧Rmn)的表达式的化简,其中Rij表示Aij=Bij,Aij>Bij,Aij≥Bij或Aij≠Bij且Aij和Bij代表整数表达式。
(2)含乘法运算的带有整数关系表达式的布尔表达式,利用关系运算符分类后,根据表达式的形式能否化为范式形式展开进一步讨论,文中给出形如CiXi=±Xj±Cj和Xi*Xj>Xi-Xj+1等若干可以化简的类。
(3)含除法运算的带有整数关系表达式的布尔表达式,文中给出形如Ci/Cj=Ck/Cl、Xi/Xj>Xk/Xl和Ci/Xi≥Xi±1等若干可以化简的类。
本文工作的结果虽然是初步的有待于进一步研究,但我们相信它为布尔表达式化简提供了一个可供选择的方法并且对逻辑电路的优化具有积极性的作用。
The simplification of Boolean expression is an NP problem, and the Systemic algorithm of getting its simplest equivalent formula is still a problem. Simplifications of Boolean expressions can be applied to the optimization of logic circuits, switching algebra and the code of design.
In order to reduce the number of input variables and shorten the time delay during hardware implementations, the existing methods in general only consider the simplification of Boolean expression, and there is not any research discovered so far dealing with the simplification of Boolean expression with integer relation expressions.
This paper starts with the description and searching for the simplification of Boolean expression with integeral relational expressions, and aiming to find the groups can be simplified and to describe them, then to illustrate the feasibility of the method provided by using examples.
The main results of this paper are as follows:
Firstly, Boolean expression with addition and subtration can be classified by the relational operators such as "=,≠,≥,>,≤,<". Thus the simplification of the following expression can be realized:f=(R11∧R12∧…∧R1n)∨…∨(Rm1∧Rm2∧…∧Rmn) among which Rij is the intergral relational expression, it represents the formula Aij=Bij, Aij>Bij,Aij≥Bij or Aij≠Bij, as well as Aij and Bij are integral expressions.
Secondly, this paper provide certain classes simplification of Boolean expression with multiplicatin, such as,CiXi=±Xj±Cj and Xi*Xj>Xi-Xj+1.
Finally, Boolean expression with division such as Ci/Cj=Ck/Cl, Xi/Xj>Xk/Xl and Ci/Xi≥Xi±1 also can be simplified in this paper.
Although the results in this paper are only primary and they are further to be studied, we believe that it can be used as an optional method for simplification of the Boolean expression and that it is of positivity to the optimization of Logical Circuit.
为了减少硬件设计中的输入变量,缩短硬件实现过程中的时间延迟,现有的方法一般仅考虑对布尔表达式实行化简,目前尚没有发现对带有整数关系表达式的布尔表达式化简方面的研究。
本文的工作以描述和寻找带有整数关系表达式的布尔表达式的若干类可以化简的情形为出发点,目标是找到若干可以化简的类,将可以化简的情形加以描述并结合实例说明所给方法的正确性、可行性。
本文工作的主要结果是：
(1)含加减运算的布尔表达式,根据关系运算符“=,≠,≥,>,≤,<”进行分类,实现了形如f=(R11∧R12∧…∧R1n)∨…∨(Rm1∧Rm2∧…∧Rmn)的表达式的化简,其中Rij表示Aij=Bij,Aij>Bij,Aij≥Bij或Aij≠Bij且Aij和Bij代表整数表达式。
(2)含乘法运算的带有整数关系表达式的布尔表达式,利用关系运算符分类后,根据表达式的形式能否化为范式形式展开进一步讨论,文中给出形如CiXi=±Xj±Cj和Xi*Xj>Xi-Xj+1等若干可以化简的类。
(3)含除法运算的带有整数关系表达式的布尔表达式,文中给出形如Ci/Cj=Ck/Cl、Xi/Xj>Xk/Xl和Ci/Xi≥Xi±1等若干可以化简的类。
本文工作的结果虽然是初步的有待于进一步研究,但我们相信它为布尔表达式化简提供了一个可供选择的方法并且对逻辑电路的优化具有积极性的作用。
The simplification of Boolean expression is an NP problem, and the Systemic algorithm of getting its simplest equivalent formula is still a problem. Simplifications of Boolean expressions can be applied to the optimization of logic circuits, switching algebra and the code of design.
In order to reduce the number of input variables and shorten the time delay during hardware implementations, the existing methods in general only consider the simplification of Boolean expression, and there is not any research discovered so far dealing with the simplification of Boolean expression with integer relation expressions.
This paper starts with the description and searching for the simplification of Boolean expression with integeral relational expressions, and aiming to find the groups can be simplified and to describe them, then to illustrate the feasibility of the method provided by using examples.
The main results of this paper are as follows:
Firstly, Boolean expression with addition and subtration can be classified by the relational operators such as "=,≠,≥,>,≤,<". Thus the simplification of the following expression can be realized:f=(R11∧R12∧…∧R1n)∨…∨(Rm1∧Rm2∧…∧Rmn) among which Rij is the intergral relational expression, it represents the formula Aij=Bij, Aij>Bij,Aij≥Bij or Aij≠Bij, as well as Aij and Bij are integral expressions.
Secondly, this paper provide certain classes simplification of Boolean expression with multiplicatin, such as,CiXi=±Xj±Cj and Xi*Xj>Xi-Xj+1.
Finally, Boolean expression with division such as Ci/Cj=Ck/Cl, Xi/Xj>Xk/Xl and Ci/Xi≥Xi±1 also can be simplified in this paper.
Although the results in this paper are only primary and they are further to be studied, we believe that it can be used as an optional method for simplification of the Boolean expression and that it is of positivity to the optimization of Logical Circuit.
引文
[1]杨炳儒.布尔代数及其泛化结构.北京：科学出版社,2008年8月第1版.
[2]毛法尧.数字逻辑.北京：高等教育出版社,2000年7月第1版.
[3]G. Birkhoff. Mathematics and Computer Science. Publication:Amerrian Scientist, Volume 63, issue 1,pp83-91,1975.1.
[4]程永上,张家超.布尔表达式化简的一种算法实现.连云港职业技术学院学报,1999.3：35-37.
[5]H. Kumamoto, E. J. Henley. Probabilistic Risk Assessment and Management for Engineers and Scientists [J]. IEEE PRESS,2nd,1996.
[6]Raghu Ramakrishnan, Johannes Gehrke. Database Management Systems. Second Edition. McGraw-Hill Companies, Inc.2000.
[7]Nils J. Nilsson. Artificial Intelligence, A New Systhesis. Morgan Kaufmann Publishers, Inc.1998.
[8]G. De Micheli. Synthesis and Optimization of Digital Circuit. McGraw-Hill,1994.7.
[9]Kuo-Hua Wang, T. T. Hwang. Boolean Matching for Incompletely Specified Function. IEEE Trans. Computer-Aided Designed,1997,16(2):160-168.
[10]K. C. Chen. Boolean Matching Based on Boolean Unification in:proc. of,Euro, DAC'93, 346-351.
[11]Y. T. Li, S. Sarma. Boolean Matching Using Binary Decision Diagrams With Application to Logic Synthesis and Verification in:proc. of ICCD'92,452-458.
[12]刘建军,吕英.一种快速的布尔函数极小化方法.计算机工程与设计,1997年10月第18卷第5期：60-62.
[13]任春玲,刘晓平.矩阵化方法在布尔表达式化简中的应用.计算机技术与应用进展,2004：1174-1177.
[14]张丰信.关于多变量开关函数化简的问题.计算机学报,1991,14(1)：57-62.
[15]洪家荣,毛成江.一个基于问题分解的布尔函数极小化方法.电子学报,1991年第19卷第4期：84-88.
[16]谢应泰.化简布尔式的一个图论方法.成都大学自然科学学报,1993.1：37-41.
[17]刘明业.数字系统设计自动化.北京：电子工业出版社,1991年第1版.
[18]沈小丰,喻兰,沈钰.逻辑代数.北京：科技出版社,2008年1月第1版.
[19]同济大学数学教研室.线性代数.北京：高等教育出版,1999年6月第3版.
[20]同济大学应用数学系.工程数学上册(数值分析与矩阵论).上海：同济大学出版社,2002年8月第1版.
[21]David C. Lay. Linear Algebra and Its Applications(Third Edition). Beijing:Publishing House of Electronics Industry,2000.3.
[22]Howard Anton, Chris Rorres. Elementary linear algebra:application version. United State of America:Von Hoffman Press, Inc.2000.
[23]Roger A. Horn, Charles R. Johnson. Matrix Analysis. Beijing:Posts & Telecom Press,2005.9.
[24]Y. Q. Guo, K. P. Shum, G. T. Xu. Linear Algebra. Beijing:Science Press.
[25]Bernard Kolman, David R. Hill. Introductory Linear Algebra an Applied First Course. Beijing: Higher Education Press,2005.7.
[26]S. K. Jain, A. D. Gunawardena. Linear Algebra:An Interactive Approach. Beijing:China Machine Press,2003.7.
[27]Stephen H. Friedberg, Arnold J. Insel, Lawrence E. Spence. Linear Algebra. Beijing:Higher Education Press,2005.6.
[28]王桂松,吴密霞,贾忠贞.矩阵不等式.北京：科技出版社,2006年5月第2版.
[29]K. A. Bartlett, R. K. Brayton et. Multilevel Logic Minimization Using Implicit Don't Cares. IEEE Trans. Computer-Aided Designed, June 1988,7(6):723-740.
[30]M. Aagaard, M. Leeser. PBS:proven Boolean simplification. Computer-Aided Design of Integrated circuit and systems,1994, pp:459-470.
[31]Chin Kui Fern, Suaidi M. K. Simplification of Boolean function on simplification rules. Research and Development,2002, pp:87-89.
[32]Prasad P, Beg A, Singh A.K. Effect of Quine-McCluskey simplification on Boolean space complexity. Innovative Technologies in Intelligent Systems and Industrial Applications,2009, pp: 165-170.
[33]Besslich P. W. Simplification of single-output Boolean Functions by Exact Direct Cover Algorithm Based on Cube Algebra. The International Conferrence on Computer as a Tool,2007, pp: 427-431.
[34]刘永才.带无关小项的电路化简的布尔方法.自然杂志,1990,13(8)：536.
[35]曾献君,何熠,叶以正.布尔函数二级逻辑极小化的快速算法.微电子学与计算机,1992年第10期：9-11.
[36]王万兴.逻辑函数的组合项化简法.上海理工大学学报,2000年第22卷第2期：185-188.
[37]刘光远,苑森淼,董立岩.基于数值计算的布尔表达式约简工具.计算机工程与应用,2007,43(12)：83-103.
[38]王德才,徐建国,吴哲辉等.布尔表达式的化简与并行排序网络验证.计算机工程与设计,2009,30(14)：3322-3325.
[39]杨旭超,李文豪.基于generalized dominator的BDD布尔表达式优化分解.电脑知识与技术：学术交流,2006年第3期：172-173.
[40]胥学金.多变量逻辑函数的表格化简方法探讨.西南科技大学高教研究,2004年第2期：33-38.
[41]关治,路金甫.数值方法.北京：清华大学出版社,2006年2月第1版.
[42]孙吉贵,杨凤杰,欧阳丹彤等.离散数学.北京：高等教育出版社,2002年8月第2版.
[43]何华灿,王华,刘永怀等.泛逻辑学原理.北京：科学出版社,2001年8月第1版.
[44]戴梅萼,史嘉权.微型计算机技术及应用.北京：清华大学出版社,2003年3月第2版.
[45]唐朔飞.计算机组成原理.北京：高等教育出版社,2003年3月第2版.
[2]毛法尧.数字逻辑.北京：高等教育出版社,2000年7月第1版.
[3]G. Birkhoff. Mathematics and Computer Science. Publication:Amerrian Scientist, Volume 63, issue 1,pp83-91,1975.1.
[4]程永上,张家超.布尔表达式化简的一种算法实现.连云港职业技术学院学报,1999.3：35-37.
[5]H. Kumamoto, E. J. Henley. Probabilistic Risk Assessment and Management for Engineers and Scientists [J]. IEEE PRESS,2nd,1996.
[6]Raghu Ramakrishnan, Johannes Gehrke. Database Management Systems. Second Edition. McGraw-Hill Companies, Inc.2000.
[7]Nils J. Nilsson. Artificial Intelligence, A New Systhesis. Morgan Kaufmann Publishers, Inc.1998.
[8]G. De Micheli. Synthesis and Optimization of Digital Circuit. McGraw-Hill,1994.7.
[9]Kuo-Hua Wang, T. T. Hwang. Boolean Matching for Incompletely Specified Function. IEEE Trans. Computer-Aided Designed,1997,16(2):160-168.
[10]K. C. Chen. Boolean Matching Based on Boolean Unification in:proc. of,Euro, DAC'93, 346-351.
[11]Y. T. Li, S. Sarma. Boolean Matching Using Binary Decision Diagrams With Application to Logic Synthesis and Verification in:proc. of ICCD'92,452-458.
[12]刘建军,吕英.一种快速的布尔函数极小化方法.计算机工程与设计,1997年10月第18卷第5期：60-62.
[13]任春玲,刘晓平.矩阵化方法在布尔表达式化简中的应用.计算机技术与应用进展,2004：1174-1177.
[14]张丰信.关于多变量开关函数化简的问题.计算机学报,1991,14(1)：57-62.
[15]洪家荣,毛成江.一个基于问题分解的布尔函数极小化方法.电子学报,1991年第19卷第4期：84-88.
[16]谢应泰.化简布尔式的一个图论方法.成都大学自然科学学报,1993.1：37-41.
[17]刘明业.数字系统设计自动化.北京：电子工业出版社,1991年第1版.
[18]沈小丰,喻兰,沈钰.逻辑代数.北京：科技出版社,2008年1月第1版.
[19]同济大学数学教研室.线性代数.北京：高等教育出版,1999年6月第3版.
[20]同济大学应用数学系.工程数学上册(数值分析与矩阵论).上海：同济大学出版社,2002年8月第1版.
[21]David C. Lay. Linear Algebra and Its Applications(Third Edition). Beijing:Publishing House of Electronics Industry,2000.3.
[22]Howard Anton, Chris Rorres. Elementary linear algebra:application version. United State of America:Von Hoffman Press, Inc.2000.
[23]Roger A. Horn, Charles R. Johnson. Matrix Analysis. Beijing:Posts & Telecom Press,2005.9.
[24]Y. Q. Guo, K. P. Shum, G. T. Xu. Linear Algebra. Beijing:Science Press.
[25]Bernard Kolman, David R. Hill. Introductory Linear Algebra an Applied First Course. Beijing: Higher Education Press,2005.7.
[26]S. K. Jain, A. D. Gunawardena. Linear Algebra:An Interactive Approach. Beijing:China Machine Press,2003.7.
[27]Stephen H. Friedberg, Arnold J. Insel, Lawrence E. Spence. Linear Algebra. Beijing:Higher Education Press,2005.6.
[28]王桂松,吴密霞,贾忠贞.矩阵不等式.北京：科技出版社,2006年5月第2版.
[29]K. A. Bartlett, R. K. Brayton et. Multilevel Logic Minimization Using Implicit Don't Cares. IEEE Trans. Computer-Aided Designed, June 1988,7(6):723-740.
[30]M. Aagaard, M. Leeser. PBS:proven Boolean simplification. Computer-Aided Design of Integrated circuit and systems,1994, pp:459-470.
[31]Chin Kui Fern, Suaidi M. K. Simplification of Boolean function on simplification rules. Research and Development,2002, pp:87-89.
[32]Prasad P, Beg A, Singh A.K. Effect of Quine-McCluskey simplification on Boolean space complexity. Innovative Technologies in Intelligent Systems and Industrial Applications,2009, pp: 165-170.
[33]Besslich P. W. Simplification of single-output Boolean Functions by Exact Direct Cover Algorithm Based on Cube Algebra. The International Conferrence on Computer as a Tool,2007, pp: 427-431.
[34]刘永才.带无关小项的电路化简的布尔方法.自然杂志,1990,13(8)：536.
[35]曾献君,何熠,叶以正.布尔函数二级逻辑极小化的快速算法.微电子学与计算机,1992年第10期：9-11.
[36]王万兴.逻辑函数的组合项化简法.上海理工大学学报,2000年第22卷第2期：185-188.
[37]刘光远,苑森淼,董立岩.基于数值计算的布尔表达式约简工具.计算机工程与应用,2007,43(12)：83-103.
[38]王德才,徐建国,吴哲辉等.布尔表达式的化简与并行排序网络验证.计算机工程与设计,2009,30(14)：3322-3325.
[39]杨旭超,李文豪.基于generalized dominator的BDD布尔表达式优化分解.电脑知识与技术：学术交流,2006年第3期：172-173.
[40]胥学金.多变量逻辑函数的表格化简方法探讨.西南科技大学高教研究,2004年第2期：33-38.
[41]关治,路金甫.数值方法.北京：清华大学出版社,2006年2月第1版.
[42]孙吉贵,杨凤杰,欧阳丹彤等.离散数学.北京：高等教育出版社,2002年8月第2版.
[43]何华灿,王华,刘永怀等.泛逻辑学原理.北京：科学出版社,2001年8月第1版.
[44]戴梅萼,史嘉权.微型计算机技术及应用.北京：清华大学出版社,2003年3月第2版.
[45]唐朔飞.计算机组成原理.北京：高等教育出版社,2003年3月第2版.