硬件串联逻辑电路基础知识介绍(二)

前言第二部分逻辑表达方式及处理算法

什么是booleanrepresentationviabdsandsatbdbinarydecisiondiagramsbdd？

二进制诊断二进制决策图

二进制决策图是表达和操作布尔逻辑的最通用、最有用的数据结构之一。

那么，二进制决策图是什么样的呢？

如图所示，在树状图表中，每个分支都对应于一个输入的固定，从而固定输出。 这也表示了所有状态下输入和输出的对应关系。

但是，这种表示方法随着输入的增加，树层会呈指数函数增加，所以为了简化显然需要几种方法。

忽略节点：如果在某些情况下输入不影响结果，则忽略与该输入对应的两个分支。

如图所示

共享节点：共享节点有两种类型。

第一，因为输出一定为0或1，所以只需要将所有分支的最终输出指向0或1，就可以减少输出的分支。

二是存在如下情况，即，在对于多个输入/输出对应关系进行一些0/1简化之后，从一个分支开始且之后的部分逻辑关系完全匹配。 用同一个树表示这个部分的逻辑关系，只是前置的输入指向不同。

或者，不同的对应关系在最初的部分逻辑关系中可以相同，可以用同一个树表示该部分逻辑关系，只是输出指向不同的节点。

以下图像分别对应于两种情况：第一种类型和第二种类型

除此之外，输入判断的优先顺序对树状图整体的大小有极其重要的影响。

如图所示，首先判断为a_1、a_2、a_3…，然后判断为b_1、b_2、b_3…，则到b_1为止会出现第一个可能的输出，但在n次判断后，在此次判断的分支上出现2 ^ ( )

如果先判断a_1b_1，则一定会减少一个较大的分支。

SAT satisfiability对于逻辑关系，在很多情况下都需要其逻辑关系成立。 例如，在网络报告中z=！ ( F xor G )，我们特意在最后的最后增加了非运算，真才是我们期待的结果。

这既符合现实的逻辑关系，也符合电子逻辑关系。

所以，对某个系统来说，我们有时并不期待所有的结果。 只是，知道这件事在某些条件下能成立，我们只要竭尽全力满足这个条件就可以了。

因此，提出了SAT。

概念提出后，我们要做的就是找到实现该概念的方法。

首先，提出CNF Conjunctive Normal Form，连接的一般方法。

其形式为XXX XXXX XXXX，语言描述为多个命题之和。

为什么选择和的形状呢？

因为如果or逻辑中有一个，我们只要判断或找到那个命题成立，这个逻辑整体就成立。

另外，每个命题都可以转换为和的形式。

AB可以转换为^(a^b )。 这是基于双重否定的消除(不是自己)和摩根定律) ^(AB )=^A ^B )。 ) ab ) C可以转换为AC BC。 这是根据分配率得到的。

我们用和的形式表示所有的逻辑门。 (为了简化显示，全部变换为AB的形式。 ）

z=(x ) [^x z][x ^z]

z=not(x ) [x z][^x ^z]

z=nor(x_1，x_2…x_n ) ) ^x_2 ^z ) ) ^x_2 ^z ) ^x_2 ^z ) ) x_1x_2…x_nz ) )

z=NAND(x_1，x_2….x_n ) ) x_2 z ) ) x_2 z ) ) x_2 z ) ][^x_1 ^x_2 … ^x_n ^z]

z=or(x_1，x_2…x_n ) ) ^x_2 z ) ^x_2 z ) ) ^x_2 z ) )。

z=and(x1，x…x_n ) () x_2 ^z ) ) x_2 ^z ) ) x_1^x_2…^x_nz ) ) ) x ) ) x ) x ) x。

所有逻辑门都可以转换为和形式，因为AB可以转换为和形式。 也就是说，所有的逻辑都可以用和的形式表示

接下来是运算。

关于逻辑电路的运算，已知有递归的反复，即假设输出输入安装。

我们仍然沿用这个方法，但是如果输入太大，这个方法的工程量也会很大，影响使用。

所以我们需要找到简化他的方法。

第一种方法布尔型约束条件事务

我们的目标是结果回归真实。 对于每个逻辑单元，都是“与”逻辑，因此所有输入都必须表示为逻辑单元真。 也就是说，假设对a ^b来说a是1，b是0，a是1，^b是1。

该算法根据给定逻辑单元具有的输入数量确定复杂度

另一种方法是DPLL Algorithm DPLL算法

该算法不是基于和的形式，而是基于乘积的形式[A B][^B C]。 相对于这个形状，可能存在b和b’的形状。 也就是说，一个逻辑单元成立的同时，另一个逻辑单元希望另一个输入在逻辑关系中一定为1。

在上式[A B][^B C]中，可知如果在b中将第一个单元设为1，则第二个单元的c一定为1。

期望的是，假设一个输入，允许更多的小区明确地得到1，或者明确地依赖于某个输入，结果为1。

因此，在选择假设输入对象时，选择单元中出现较多的内容。

此外，根据“与”逻辑，可能会从零开始为零。

因此，如果可以确定某个单元整体的结果为0，则当前假设一定不满足SAT。

根据以上说明，可以得到伪代码

clauses ( if ) clausesisaconsistentsetofliterals (返回真) else if ( clausescontainsanemptyclause )返回假) napopularinputanddpll ( that clauses ) }上的所有内容都是逻辑的。 然后将逻辑应用于电路。

对于上面的所有逻辑，可以认为是下图的电路

也可以是

第一个被称为2级逻辑

第二个是多级逻辑

对电路来说，我们要做的就是把它转换成逻辑。

也就是说，用A BC的形式表示电路的逻辑。

转换的方法是我们接下来讨论的内容。

首先是转换为2级逻辑

逻辑可以用BDD表示，电路可以用TT真值表表示。

和前面逻辑的部分一样，只记录结果为1的输入

首先，必须承认表示同样结果的逻辑的表示是多样的。 其中也包括aa’可以被视为1的要素。

所以，我们有必要明确我们想转换的逻辑关系是电路表示的最简单的关系。

找到最简单的关系的方法是我们需要讨论的内容

既然需要找到逻辑关系，就必须首先理解真值表的矩阵网格显示了什么。

对于ab为00的列来说，是a=0、b=0时的逻辑关系。

同样，对cd的一行来说是c=0，d=0的关系。

ab为00 01，cd为00 01的田的字格是a=0，c=0的关系。

其他矩阵田字格意义相似。

其次，我们要找到可行的逻辑关系并加以简化。

在上图的关系中，bd同时为1，ac为0，ac同时为1，bd为0，结果为1，ab为1cd，结果为0。

我们可以得到逻辑关系a’BC’dab’CD’ABC’d’

那么，对程序来说，如何获得呢？

配合逻辑制约的传达，首先，1行中存在1，1越多越好( 1越多该行的优先顺序越高)，对该行输入逻辑，如果是1则为a，如果不是1则为a’。

对于同一块矩阵乘积运算，采用不同的矩阵和运算。

剩下的就是组合起来实现最优解。

即，相当于a’BC’dab’CD’ABC’d’=BC’( a’dad’) ab’CD’

当然也可以与ad’( b’CBC’) a’BC’d进行组合

这些组合期望将1组合成完整的田字格，但也可以是其他完整的矩阵。

接下来是关于多级逻辑

多级逻辑有更多的环节，如f=ac b、g=fa’c等

我们可以去除环节。 也就是说，可以直接将ac b写入g而不是f，再次更简洁地表示acba’c=BC

当然，作为其中的一个环节，存在f=ab ac ad

我们可以追加一环a。 f=a (卡介苗)

那么，如何用程序来实现这个目标呢？

首先要明确逻辑和数理的关系：

基于前面的分配律的存在，可以将“与”视为乘，将“或”视为加。

这样可以使用数理计算实现逻辑and和or的计算。 但是，数理不能表示非运算。 因此，必须用新的符号表示非运算的结果，忽略与原要素的非关系。

其次是寻找满足简化条件的部分和要素。

首先，是添加章节的方法。 如上例所示，添加部分必须满足的条件是元素多次出现在和格式的逻辑单元中。

要知道如何在算法中找到该元素，需要找到该元素所具有的特征。 首先，那个要素一定会出现在整个逻辑中。 这意味着逻辑中的所有元素可能会多次出现，同时也可能只有逻辑中的元素是可能的。

我们可以试试。

(在此，这个多次出现的要素的集合记为pisor ) )。

提交此元素后，逻辑关系表达式为f=d*qr。 ( d是pisor，q是提出d要素后的逻辑表达式，r是不包含d要素的其他逻辑表达式的集合) ) ) )。

for(eachcubedinpisord ) letc={ cubesinfthatcomtainthisproducttermd } if ) cisempty ) return ) quotient=0， reminder=F ) letc=crossoutliteralsofcubedineachcubeofcif ( disfirstcubewehavelookedatinpisord ) letq=c ) else ) q=r=r。 例如，提取并提取ax和b，如F=axc axd axe bc bd de。 ( c d e

因此，找到某个要素后，也必须分析剩下的逻辑公式

find kernels ( cube-freesopexpressionf ) k=empty for ( eachvariablexinf ) there are atleast2cubesinfthavevariablex { llex } let co=cubethatresultsfromintersectionofallcubesinsthatwillbetheproductofjustthoseliteralsthatappearineachofthesecubesins=

举个例子吧。 F=axc axd axe bc bd de

首先提取a:a(xcxdxe ) bc bd be

然后提取x:ax(cde ) bc bd be

之后省略。

假设先提取x再提取a，结果不也一样吗？

答案是是的。

所以我们使用的方法有冗余。

此外，同一表达式有不同的提取方法，最终结果的表达式可能因提取方法而异

例如a’BC’dab’CD’ABC’d’=BC’( a’dad’) ab’CD’=ad’) b’CBC’) a’BC’d

所以我们必须找到最佳的提取方法。

你怎么处理？

必须找出并提取其出现次数最多的要素，一次提取最大个数的要素。

首先，分析逻辑单元并记录元素出现的次数。

可以记录为如下图所示的格式

2级逻辑

多级逻辑

然后，首先寻找要素最多的逻辑单元，根据逻辑单元中存在的要素寻找尽可能多与相同存在要素匹配的逻辑单元，直到寻找结束，最终提取尽可能多的满足要素，重复上述操作。

【网络安全学习攻略】