复杂性

在这一页上

文摘介绍背景相关工作结论缩写数据可用性的利益冲突作者的贡献确认引用版权相关文章

特殊的问题

复杂系统建模在工程行业4.0

把这个特殊的问题

研究文章|开放获取

体积2021年| 文章的ID5525539| https://doi.org/10.1155/2021/5525539

CoCEC:自动组合电路等价性检查器基于交互式定理验证

原来受汗 ,¹ Farrukh Aslam汗 ,² Abdelouahid Derhab ,² 和Adi Alhudhaif ³

学术编辑器: 慧华陈

收到了 2021年1月21日

接受 2021年5月04

发表 2021年5月26日

文摘

检查两个布尔函数的等价或组合电路建模为布尔函数,通常是当需要可靠的和正确的硬件组件。最常见的等价性检验方法都是基于仿真和模型检查,这是限制由于受欢迎的内存和状态爆炸问题。此外,这些工具通常不是用户友好的,从而使其乏味检查大型公式或等效的电路。一个替代方法是使用数学工具,称为交互式定理验证,证明两个回路的等效;然而,这需要人类努力和专业知识来编写多个输出函数和执行互动的等价性证明。在这篇文章中,我们(1)定义两个简单的,一个正式的和非正式的,门电路级硬件描述语言,(2)设计和开发一个正式的自动组合电路等价性检查器(CoCEC)工具,和(3)测试和评估我们的工具。工具CoCEC基于种定理验证公鸡,然而它检查电路的等价描述纯自动通过人性化的用户界面。它返回一个机器可读证明(术语)电路的等效或反例的不平等。接口允许用户输入或负载两个电路描述写在一个简单的和自然的风格。它自动证明,在几秒钟,电路的等效多达45个变量(3.5 州)。CoCEC数学基础,可靠,快速,易于使用。这个工具的目的是使用数字逻辑电路设计师,逻辑学家、学生和教师在数字逻辑设计课程。

1。介绍

电子系统的设计或操作的数学函数,系统通常是表示和转换成不同的形式。在数字逻辑电路的设计过程,电路可能代表一个布尔函数的形式,简化使用不同的方法,如数学操作和卡诺图的方法。的简化函数表示逻辑电路更少数量的逻辑组件,它导致一个紧凑、经济、高效的硬件产品。然而,简化电路的行为的正确性必须证明,确保操作过程不改变电路的目的的行为。这样一个系统的功能验证通常被称为等价性检查(1,2]。

复杂性的增加和软件和硬件系统的临界,复杂的需要,可靠,正式这种系统的分析工具也增加(3,4]。一个共同的方法来检查两个电路或函数的等价模型检查(5- - - - - -7]。模型检查器可能进入一个循环由于状态爆炸问题7),检查大型模型与成千上万的国家不是用户友好的8,9),单调乏味,而且容易出错。另一种形式的正式的方法是使用交互式定理验证(itp),如公鸡(10),伊莎贝尔/假日[11],ACL2 [12]。这种形式的正式方法检查数字电路的正确性13图中描述1。正式的模型电路的测试和安全利益或可靠性属性输入一样定理给出了一个定理验证(如公鸡系统),和一个数学证明电路满足属性的模型进行交互。

交互式定理验证解决状态爆炸等问题使用终止检查器,过滤掉无尽的功能。然而,证明策略,如破坏在公鸡,可以提高内存爆炸问题,如果使用不当。一个公鸡证明脚本形式破坏 ;自毁 ;自毁自毁 ;汽车。,在哪里是一个布尔变量,将创建子目标在一个时间和内存大爆炸n。此外,交互式定理证明是更强大的比模型检查(14),但它需要人类的帮助来证明定理。

存在的和受欢迎的正式工具理性对组合电路和布尔函数;然而,他们并不是自动(公鸡,伊莎贝尔/假日,等等),面对状态爆炸问题(模型检查器),很难或无法生成反例(公鸡,ACL2等)或要求专业知识编码逻辑公式(Z3、笨蛋二世等)(见表1)。解决布尔可满足性(sat)可以检查合取范式(CNF)公式并检查是否公式是一致的。sat是有用的工具,但它们不是一样强大和富有表现力的基于高阶逻辑证明助理(如伊莎贝尔/假日)和结构(如公鸡)的微积分。另一种类型的正式工具自动化定理指出,支持自动推理归纳逻辑理论。一个这样的工具是ACL2 [12),这是一个逻辑编程语言用来模拟对计算机系统和理性。ACL2是完全自动的和更加可伸缩;然而,它需要专业知识和技能写或编码逻辑公式的语法。用图和变频器(AIG)代表布尔函数,例如,函数将aig和 ,一起实现,它需要两个变量作为参数。

在本文中,我们提出并开发一个工具叫CoCEC结合多种方法的优势(自动证明使用ITP工具)进行了组合电路的等价性检查。用c++开发的工具CoCEC,检查组合电路的等价,返回其等价的证明,或产生一个反例。CoCEC接受以用户友好的风格和自动检查它们的等效电路使用交互式定理证明方法没有用户指导。它创建一个公鸡证明脚本为每一个等价性检验和证明对象对测试,如果电路是等价的;否则,它将返回一个反例。我们定义了两个描述语言:第一个是用来描述电路在一个简单和自然风格,另一种是用于描述电路在公鸡使正式的高阶逻辑推理。本文的主要贡献包括以下组件的开发和集成:(我)定义了两个门电路级描述语言。第一个目的是描述电路在一个简单和自然风格,而另一个目的是使正式的推理。(2)翻译是自动转换电路设计开发描述第一语言在第二语言等价的描述。(3)证明检查器开发,正式检查两个电路的等价描述。它要么生成证明对象(术语)的平等或不平等产生一个反例。(iv)广泛的实验进行检查工具的健壮性和性能。

我们的工具的源代码(Windows和Ubuntu平台)是网上https://github.com/wilstef/cocec。

本文的其余部分组织如下:在下一节(部分2),一个简短的介绍布尔代数和公鸡证明助理。讨论了两种描述语言的语法部分3。CoCEC工具的主要组件中所描述的部分4。工具测试部分5,它的性能是评价部分6。一个简短的调查文献给出的部分7。部分8结论本文未来的研究方向。

2。动机和背景

工具CoCEC检查功能对等的两个组合电路作为输入,在公鸡翻译成正式表示,有公鸡的等价定理验证的证据。在本节中,讨论了CoCEC背后的动机通过比较它的简单性和易用性与一些其他类似的工具。CoCEC中使用的两种描述语言是基于布尔代数;因此,布尔代数的基本知识和公鸡交互式定理验证是理解我们的工具的操作所必需的。

2.1。动机

CoCEC接受两个门电路级描述在第一语言和第二语言生成等价的代码。此外,CoCEC自动检查他们的平等或不平等。除了继承了交互式定理证明的好处,CoCEC工具很简单,容易使用,和兼容许多当代工具,同时,它解决了等价问题的顺序的几秒钟。瞥见CoCEC从容的可用性如表所示1;编码逻辑功能检查他们的等效很容易在CoCEC工具相比Z3 [8),笨蛋二世(9],ACL2 [12]。此外,输入语法CoCEC直接接受布尔表达式中使用流行的文本书籍数字逻辑设计(15]。CoCEC之上构建交互式定理验证公鸡,尽管它自动证明了等价的两个函数没有人类的帮助。

2.2。布尔代数

布尔代数,由布尔(16),是一个代数,包括一组值,+和两个二进制操作值的设置,和六个亨廷顿(17假设的证据。香农(18)定义了一个两价的版本的代数模型和描述的属性转换电路。香农的代数的两个值是1和0,它包括两个二进制操作规范与一元补操作,如表所示2。

2.3。公鸡的助理

香农的两值的布尔代数中的布尔函数可用于模型逻辑电路,如图2。这个函数模型和门代表了产品的电路操作(表2)和非门操作(表代表了补充2)。当逻辑电路和功能如图表示2,他们可以操作,可以表示不同的性质,证明了使用基于布尔代数的工具和技术。

正式对电脑系统原因,被测试的系统和目标属性形式化的逻辑定理验证(如公鸡(10)和伊莎贝尔/假日(11])。证据证明语言的助理是用来创建一个证明(模型)系统满足财产。证据证明检查器的助理是用来检查如果证明是有效的。描述正式系统和使用证据证明助理,一个数字系统正式定义并合理的使用证明助理公鸡。在这个正式的系统,数字电感nat使用公鸡关键字定义为一个数据类型归纳有两个构造函数构造这种类型(行1 - 3,图的元素3)。定义类型的nat州nat O(0),如果nnat,年代n也是nat。这个术语(年代(S (S O))),例如,是一个数字在nat (4)。

指定的数字后,函数可以定义来操纵它们。递归函数添加(5 - 9行)的数字得到两个数字n和米并返回它们的和。它返回第二个参数米如果第一个参数是O,它返回(添加米),如果第一个参数是表单的年代。一个引理add_n_o添加nO =n适用于任何的价值n是说,证明在图3(第11 - 16行)。这个引理证明归纳建设的第一个参数n。在证明过程中,证明专家协助公鸡工具交互式地提供它的命令称为策略(12到16行)。

3所示。描述语言

为了描述组合电路在一个简单和自然风格,我们定义了一个简单的输入描述语言来表示电路在大门口的水平。正式启用交互式环境证据推理,逻辑电路必须使用公鸡符号描述。为了这个目的,一个简单的正式描述语言的定义和嵌入到公鸡证明助理代表逻辑电路。

3.1。输入描述语言

工具CoCEC旨在提供一个易于使用的用户界面,便于描述逻辑电路。代表user-familiar风格组合电路,定义一个简单的描述语言。这种语言支持和动机的描述是课本(15)数字逻辑和计算机设计和工具(19,20.]。它的语法是语法定义的生产图中列出4。

语法规则生产状态,所有英文字母(大写和小写)和数字(0和1)逻辑电路。(非)括号电路及其总和,产品,和补充也电路。最后,一系列电路(由“:”)也(multioutput)组合电路。组合电路,加法器,可以定义在这个语言如下: 。这种风格的电路表示用于输入电路描述直接进入CoCEC的用户界面。

来描述电路模块(在传统风格。txt文件),图中给出了更加结构化的语法5。一个电路的定义开始关键字模块和结束与终端模块开始。每个输出函数被定义为一个布尔函数,以关键字开始输出。像许多其他编程语言,允许单一和多行注释,每一个语句(输出函数)与分号终止。输出定义的顺序很重要:函数定义的最重要的一点是第一,而最低有效位定义。模块图5描述了全加器电路和两个输出和携带。

3.2。输出描述语言

输入描述语言没有一个正式的基础,因此不适合正式的推理。启用正式使用ITP推理,一个正式的描述语言中定义的逻辑公鸡。前面定义的布尔代数(21)是专门针对组合电路的重新定义和定义。第一部分,一组两个元素,在公鸡定义数据类型使用关键字归纳bool,正如在图6(第1行)。这种类型的两个成员,真与假,代表这两个值的布尔代数。

下一步是定义二进制操作的两个值bool类型。第一次手术+(总和)被定义为一个公鸡函数和在图3 - 7行6。函数和被两个参数(两个bool类型的值),然后返回假值如果输入参数都是假的,返回true,否则。类似的,第二个二进制操作(产品)所定义的函数prod(第四行,图6)。如果这个函数的两个输入值是真的,它将返回true;否则,它对其他输入值返回false。此外,一元运算补充定义的函数不是(15 - 19行)。它反转输入值(返回true给假的,反之亦然)。如果真和假的值替换为数字1和0,分别,这些函数将按照事实表(表2节)2.2。最后,组合电路被描述为一个布尔值列表(第21行),在一点一点的头是最重要的,而尾部的最后一点是最低有效位。

构造函数和功能(操作)名称麻烦写,特别是,当组合电路描述。幸运的是,公鸡提供了速记符号与符号替换英文名字。这三个操作,刺激,而不是用中缀表示法+表示, ,和一个前缀表示法 ,分别(图7),最高和最低优先级。公鸡项之和x(戳x(不y)),例如,用表示x+x , y,在那里y被评为第一,紧随其后的是产品,然后执行和操作。类似地,组合电路被定义为以分号分隔的布尔函数的列表包含在括号中。正式的符号只是提出了可用于描述组合电路的公鸡。全加器的组合电路如图5例如,在公鸡符号编码,如图8。和对应的函数定义,而尾巴代表携带。

4所示。CoCEC架构

正式的工具CoCEC接受两个组合电路描述. txt文件中定义的输入描述语言。另外,两个电路的描述也可以两个文本框中输入的主窗口。的前端CoCEC检查(语法错误)并将输入传递到其他组件的工具。CoCEC一起翻译的组件的输入电路表示在输出语言,生成公鸡脚本,并正式确认是否这两个电路是等价的。它生成一个对象如果电路等效或一个反例,证明并非如此。图显示的图解视图工具CoCEC图所示9,其组件的细节在下面几节中给出。的所有组件CoCEC正式的语义,使它成为一个严格的、可靠的工具。

4.1。用户界面

CoCEC工具有一个简单的用户界面(图10)。它由两个文本框,用于描述两个电路。或者,用户可以将现有描述. txt文件加载到相应的文本框,单击load按钮。这个按钮检查等价触发器的主要代码的工具,它在后台运行操作输入的文本(或加载)进盒子。该工具通过单击按钮关闭关闭或者点击十字架在窗口的右上角。

当进入任何电路的描述/加载是不规范的,用户单击按钮时检查等价,该工具将显示一个消息框有意义的错误消息,以及光标移动到错误的文本框。如果描述都是完整的,他们给出了作为输入到下一个组件。

4.2。语法检查器

语法检查器(检查程序图11syntaxchecker和图书馆。cpp在源代码中)是一个词法分析程序,对用户输入的文本解析器。它首先进行预处理的描述(删除评论和关键字),然后创建电路描述形式 ,在哪里代表个人遵循语法定义布尔函数图4。接下来,它确保输入电路描述的语法,语法所定义的生产图4,是正确的。换句话说,语法检查器实现了图中定义的规则11。检查过滤掉不规范的文本和通过文本框的格式良好的电路描述。

格式良好的逻辑电路的输入规则,定义的部分2.2,在图11。大小写英文字母(标识符)和二进制数字1和0(逻辑值)电路根据规则T-ID和t值,分别。补充的词也是一个有效期内(规则T-COMPL)。总和+和产品(默认操作符)的两个有效电路也有效的电路(规则T-SUM和T-PROD)。所有括号电路也电路(规则T-PAREN)和序列的电路也是一个电路。这些规则执行的函数check_syntax_circuit syntaxchecker.cpp库。检查程序,例如,接受和但是不接受 , ,等等。

4.3。中间表示发电机

中间表示(IR)发电机是一个转换的电路描述mini-compiler输入语言的等价描述输出语言。逻辑电路描述图中给出的规则11是完整的(有效的);然而,一个人不能机械地思考它,因为它不符合语法定理验证可接受。这种表示方法的目的是为人类提供一个易于使用的界面,允许他们进入逻辑电路描述在一个更自然的方式。相反,电路输出描述语言中定义的部分3不同的用户可以输入(在输入语言)。为了填补这一空缺,翻译(irgenerator。cpp文件)是书面翻译来自用户的输入一个等价的中间的公鸡表示函数在正式版本的输入语言。翻译直接出现,但它需要识别标记包括标识符,操作符和分隔符括号。特别是,翻译”前缀后缀补充符号和插入操作员任意两项之间没有中缀表示法很难处理。

图中的推理规则12定义可接受的电路描述的形式化的语言输出。这些规则描述公鸡定义部分3并使两者之间的比较电路表示简单的(注意图中突出显示的文本12)。0和1的逻辑值替换为逻辑假和真值,分别。作为一个例子来描述上述规则,电路+ 1是公鸡的翻译定义x , y+(相当于术语和刺激x(不y)))。

4.4。代码生成器

译者创造符合正式输出的电路描述语言的语法定义在图6(部分3)。检查任何两个电路的等价描述红外发生器输出的,一个完整的脚本需要发展的证据。公鸡定理验证是一个互动的工具,因此,脚本可以创建一个交互式证明;然而,它需要正式的验证技术和乏味的进行等价的正式证明每两个功能。这个翻译是由代码生成器模块(codegenerator自动化。cpp文件)。

两值的代数,只有两个逻辑值,每一个标识符可以指定这些值中的一个。在这么正式的证明,案例分析证明方法是理想:通过评估检查函数的等价为每个标识符取两个值中的一个。公鸡脚本生成器模块CoCEC自动化这个过程。生成器生成脚本并将其存储在proofscript公鸡证据。v文件(公鸡证明检查器的输入)。文件proofscript。v包含代码导入一个公鸡库包含正式的定义,定理语句(或一组定理语句序列电路),和证明的定理。定理(s)状态(s),这两个电路描述(收到红外发生器)是等价的任何值的标识符描述。脚本是一个证明,证明两个的确是功能等效电路描述。等价性检查的一个例子证明定理如图的共识13。

证明脚本为每个生成等价性检查可能是不同的在两个地方,高亮显示在图13。标识符的列表(12行)和身体的定理声明(13号线)变化对每一个测试。左边和右边的部分身体的描述描述1和2,分别来自上层模块(红外发生器)。对12和15行标识符的列表是来自两个描述的尸体由逗号“,”隔开。证明对15 - 19行命令关闭重复一种公鸡策略DestructMatchArg证明。策略DestructMatchArg递归地使用模式匹配在布尔操作符刺激和求和,然后解决目标通过案例分析变量。它因此简化了子目标和关闭应用公鸡的自反性策略。Qed,显示和打印策略用于调试和错误报告和部分将更详细地讨论5。显示和打印策略仅用于调试从最终证明脚本中删除。

4.5。证明检查器

一旦证明脚本,公鸡语法后,生成,公鸡可以机械地检查其正确性的证明检查器。证明检查器模块图9(文件proofchecker.cpp)自动化这个过程通过使用系统命令在c++中。检查程序运行公鸡工具,给出了脚本收到前一个组件作为输入到公鸡证明检查器。最后一个命令的脚本(第21行,图13)保存证明公鸡库如果关闭;否则,它打印错误消息错误:试图拯救一个不完整的证据。基于公鸡的结果证明检查器,CoCEC证明检查器显示给用户电路是否(我)相当于:创建并添加proofobject证明对象文件。txt或(2)不是等价的:创建并添加了一个反例的反例。txt文件,或(3)返回一个语法/类型错误造成的错误的翻译(达到这个状态只有在没有或不兼容的(除了公鸡8.8)版本安装)

模块图9讨论到目前为止翻译有效的电路描述(模块)的一种格式(输入语言)在另一个有效的电路描述格式(公鸡脚本)。这种工具通常被称为编译器或解释器(23]。CoCEC的翻译工具是用来翻译从一个数学表示另一个,不是一种独立的编程语言的一部分,是直接(手动)不使用标准的工具和技术来实现。不管方法用于开发这样一个翻译,这是非常重要的,以确保工具的正确性;那么就必须确认CoCEC生成正确的代码(见部分5)。

4.6。反例的一代

创建正确的公鸡证明脚本后,CoCEC工具创建一个证明对象(术语)使用战术显示如果描述相等;否则,它会生成一个反例。公鸡证据的证明对象自动生成脚本使用战术显示;然而,翻译是设计和编写创建一个反例。战术显示第一个等待目标proofobject补充道。txt如果前面的命令(15 - 19行,图13)无法关闭它。第一个目标遇到无法关闭,并生成一个反例。开放与逻辑的变量值(真或假),导致不平等的左右两侧,替换为相应的值在最初的身体功能。作为一个例子,一个反例的测试x+x y! =y是真的+真的假的!= false,这应该被视为x= true,y= false,x+x y! =y。

5。测试

检查工具的健壮性CoCEC,必须验证结果的正确性。作为目标语言是公鸡类型检查器,所有的翻译被公鸡编译器进行形式化描述。公鸡编译器只接受格式良好的代码,从而确保只有正确的翻译由CoCEC处理工具。如果工具显示描述是平等或不平等,那么它必须保证他们的确是平等或不平等的。在前一种情况下,CoCEC工具给公鸡举证对象和脚本,用户可以使用公鸡检查确认,而在后一种情况下,将返回一个反例。在错误的情况下,CoCEC不仅返回一个详细的错误消息,还错误的公鸡脚本,这又可以使用公鸡检查检查。

第16 - 19行公鸡策略重复在(在图13)对17和18行重复的策略,直到关闭的证据。Qed,公鸡命令显示和打印用于更新四个文件的内容,哪些在一起用于确定三种可能性之一,如表所示3。三种可能性(最右三列在表3)(1)生成的代码是不正确的(例如,语法或类型错误引入了),(2)函数是等价的证明关闭,或(3)函数并不等价,并重复返回没有关闭的证据。这些文件的内容(左列、表3)用于最后的决定显示给用户,创建一个反例。命令显示文件proofobject补充道。txt当前等待目标(或没有如果证明已经被前关闭策略)。战术Qed将证明脚本添加到公鸡库供以后推荐如果一切都很好;否则,它将一个错误消息添加到文件coqerror.txt。命令打印boolean_equivalence_0 proofobject将公鸡证明项添加到文件。txt(这是执行只有在公鸡证明由战术早些时候关闭)。策略假设boolean_equivalence_0打印打印等待假设前题,如果有的话,没有证明。

四组实验测试的工具是广泛(见下一节),每组包括实验检查45双函数的等价与二进制变量1 - 45。此外,它是测试大量的例子从数字逻辑设计教材15)和利用我们的本科生在数字逻辑设计课程。

6。绩效评估

CoCEC工具的主要优势是能够自动使用交互式证明了组合电路的等价性证明助理。CoCEC工具,例如,可以使用由学生学习数字逻辑设计课程正式验证给定的布尔函数的等价对其简化的函数。无论使用的简化算法,无论是卡诺图,表格的方法,或逻辑操作,功能对等的原始和简化版本可以检查。使用交互式自动证明等价证明助理继承互动证明助理的好处,同时,它有自动检定装置的自动功能。自动检定装置,如模型检测工具,处理布尔逻辑,有缺点:他们必须贯穿所有的状态空间来决定是否适用于所有情况的断言。定理证明,人类的支持,相反,可以证明使用感应系统,否则,将是棘手的14]。CoCEC工具旨在自动解决等价证明脚本中生成交互式检查问题证明助理公鸡。证明了定理都不需要人的帮助,性能下降,预计如果公鸡战术使用效率低下。

使用的语言策略在公鸡24),一个特殊的定义策略,策略适用于自毁在我们的目标是发现当一个特定的模式。策略DestructMatchArg (DestructMatchArg策略是由迈克尔Soegtrop coq-club 5月08年,2018),稍微编辑从原始版本,模式匹配的目标和策略适用于破坏了二元运算符+和条款 ,自反性和汽车紧随其后。破坏的一个简单的应用程序策略,没有适当的治疗如前所述,在每一个变量创建太多的目标保持在内存中同时往往导致内存爆炸;销毁45变量在函数将创建子目标。在一个实验中,系统花了超过14秒11个变量,虽然它没有换取20多个变量(内存爆炸)。仔细和重复控制应用程序内DestructMatchArg重复关闭目标有效地一个接一个,没有打开和检查所有的情况下。

使用分治法的规则,DestructMatchArg替换一个变量的两个逻辑值和等效简化,并检查其是否可以解决;否则,它重复其他变量的案例分析,直到目标是关闭或所有情况下一个接一个。这将改善性能,它可以证明的等效电路有超过45个变量(超过3.5可能的情况下)只有一个半第二。检查CoCEC对电路的性能与45变量与英特尔酷睿i5 Windows机器上,2.60 GHz处理器对(图四组不同的方程14)。每一次,45变量的实验进行了描述。CoCEC检查语法类似描述的平等只是几分之一秒(黑线),虽然花费了不到两秒检查交换财产(红线)。第三组实验测试进行随机(电路描述双手动创建的,随机性引入通过编写一个表达式的每一对相反的顺序和添加一个语法描述语法不同的)描述,,不到14秒检查电路45输入变量的平等。最后,对类似的实验进行不平等的电路描述。不等式的证明在大约7秒钟45-variable不平等对的描述。这些测试表明,CoCEC工具可以有效地用于检查复杂的平等45变量描述。

两个函数的等价性检验、模型或电路在文献中一直得到广泛的研究。最近,汗et al。22)建立一个正式的模型布尔代数的公鸡证明助理。他们的模型可用于交互式地证明布尔函数或逻辑电路的等效建模为布尔函数。最常见的方法是模拟硬件描述函数的等价性检查/描述在模拟器等风投25和伊卡洛斯26通过给所有可能的输入。这些方法是半自动的,并且不是由于缺乏可靠的数学基础。相反,形式验证方法(1),如模型检查(5,6,27和定理证明28在文献中,更受欢迎。正式的工具,如ACL2、公鸡和伊莎贝尔/假日已经很成熟,强大,和业内更受欢迎;然而,本文的重点是提供一个专门的工具检查逻辑的等价公式简单易用,自动的,和强大的(的底层逻辑),可以生成反例。还有其他形式对等检查工具,如保形和FormalPro [29日,30.),但他们是用于等价性检查在RTL级,而CoCEC门口的目的是检查等效水平。这些工具都是专有的和操作在不同级别的电路比CoCEC表示;因此,与CoCEC比较是不可能的。此外,这两个工具都是基于交互式证明助理,这是更强大的比自动化的解决者。

7.1。正式的硬件验证

形式验证技术和工具可以用来验证没有硬件故障的系统组件。我们指的是(31日)的详细比较正式的硬件设计方法和基于仿真方法的等价性检查和验证。卡巴特和Wojcik32)建议使用自动检定装置的合成和组合逻辑的验证。作者重写逻辑解调用于规范的简化电路结构。最密切相关的工具是笨蛋二世的儿子9和解决者Z38]。笨蛋是一个自动等价性检查器基于验证Prover9证明等价和Mace4寻找一个反例33]。背后的证明检查器常春藤笨蛋二世是基于一阶逻辑,而公鸡是微积分的基础上建设,哪个更强大,比一阶逻辑表达。检查等价用轻佻的人很麻烦:它需要解释清楚输入使用括号,乏味,尤其是对于大型的描述。此外,每个测试都需要正确选择给定的一组假设的假设。Z3是一个低级软件分析和验证工具开发的微软检查逻辑公式的可满足性。Z3、多用途的工具,需要编程技能编码公式Z3语言语法。所有这些工具都是基于交互式定理证明和与现有工具兼容。这些工具不能直接应用于检查课本中的等价的例子(15]或公式生成的其他工具(20.]。CoCEC,恰恰相反,是基于交互式定理证明额外的优势(14)和接受输入的自然风格,不需要任何编程技能。

在业界,自动化定理验证更广泛使用;然而,他们是远远落后于证明助理的能力和表达能力。模型checking-based工具可以用来检查函数的等价性;然而,他们是有限的流行状态爆炸(7,34)问题。证明助理包括自动化和交互式定理验证的优点。助理目前证据调查和鼓励对硬件验证(35,36]。在这个方向,Meredith et al。37)定义可执行语义Verilog HDL和嵌入式的定理验证莫德(38使用重写逻辑作为底层逻辑)。灵感来自[37汗,et al。28]介绍了硬件描述语言,称为VeriFormal。VeriFormal正式版本的硬件描述语言Verilog,深深植根于伊莎贝尔/假日定理验证。Braibant和Chlipala39)定义了一个语言Fe-Si公鸡,根深蒂固的版本功能blackspec硬件描述语言。生产proof-carrying代码,爱et al。40)实现框架和形式化的Verilog synthesizable子集助理公鸡的证据。哈桑et al。36)引入了一个正式的框架的高阶逻辑定理验证假日。他们的框架是用于证明的可靠性属性组合电路。这些研究的贡献主要是关注于检查可靠性属性。CoCEC使功能对等在强大和富有表现力的公鸡叫的微积分归纳的逻辑结构(35]。此外,大多数的研究贡献解决在高水平的抽象和形式验证是基于半自动工具。我们的工具CoCEC,相反,分析逻辑电路在大门口水平和完全是自动的。交互式定理证明方法是一种可行的选择但代价的努力和专业知识协助定理验证所需的工具。在更高级别的,比如在RTL级,形式验证是同样重要的是,但我们考虑正交工作目标电路在大门口的水平。

7.2。工具检查等价的布尔表达式

操作的布尔函数,已经开发出了许多工具在文献中。南方et al。41创建了一个数据库的布尔函数。他们可以证明工具之间的布尔函数的性质,可以将不同形式的功能。另一个工具,WolframAlpha的计算引擎42),用于将逻辑函数给出真值表和其他输入最小的形式。此外,WolframAlpha的维恩图和逻辑电路产生相应的输入函数。这台发动机已经被公司TutorVista包括作为一个布尔代数计算器。为了简化布尔函数,另一个工具(43)开发。这个工具使用卡诺图地图(44减少文字的数量,在布尔函数。它的函数作为一个符号序列或真值表(六个变量)。

最近的一个工具来操作布尔函数是328 (19]。该工具328接受一个函数作为真值表并返回输出卡诺图,布尔函数和逻辑电路。它支持eight-variable布尔函数,可以生成函数作为产品或产品的金额之和的形式。进一步开发工具来简化布尔函数。精益和Marxel开发了一种解算器QMSolver [20.)简化布尔函数。基于Quine-McCluskey算法,解决者QMSolver获得小项的数量指标(以空格分隔),并返回一个简化的函数。这最后的输出工具可以直接给CoCEC工具。这些布尔函数工具检查两个电路的等价描述,没有正式的语义。

8。结论

逻辑门符号是用来描述逻辑电路在大门口水平在电子设计自动化的过程。通常操纵电路描述产生功耗小,小,和廉价的逻辑电路组件。确保所需的功能是保存,功能对等的两个描述往往是理想的。在这篇文章中,一个正式的开发工具CoCEC自动证明两个组合电路的等价描述。CoCEC工具是建立在正式的布尔代数框架开发的公鸡定理验证。它接受电路描述自然风格和公鸡符号转换成等价的描述。我们的工具自动创建等价的证明,可以检查机械。如果功能不等效电路描述,生成一个反例。CoCEC解决的等价问题超过十亿个国家在短短几秒钟。由实验工具的健壮性测试函数对45变量。

工具目前支持uniliteral变量,应该扩展到接受多个字母组成的变量。此外,CoCEC产生一个反例;然而,它可以很容易地扩展到生成多个或全部(如果有的话)的反例。

缩写

CoCEC:	组合电路等价性检查器
国际旅游业伙伴关系:	交互式定理验证
ACL2:	应用Common Lisp的计算逻辑
假日:	高阶逻辑
CNF:	合取范式。

数据可用性