二硬件安全系列逻辑电路基础知识介绍( 二 ) _电路基础知识

z=NOT(x) [x + z][^x+^z]
z=NOR(x_1,x_2…x_n) [(^x_1+^z)(^x_2+^z)…(^x_n+^z)][x_1+x_2+…+x_n+z]
z=NAND(x_1,x_2….x_n) [(x_1+z)(x_2+z)…(x_n+z)][^x_1+^x_2+…+^x_n+^z]
z=OR(x_1,x_2…x_n) [(^x_1+z)(^x_2+z)…(^x_n+z)][x_1+x_2+…+x_n+^z]
z=AND(x1,x…x_n) [(x_1+^z)(x_2+^z)…(x_n+^z)][^x_1+^x_2+…+^x_n+z]
由于AB可以转化成和的形式，所以所有逻辑门可以转化为和的形式，也就是说所有逻辑都可以用和的形式表示
接下来是运算。
对于逻辑电路的运算，我们已知的运算就是递归重复，也就是假设输入实现得到输出。我们依旧沿用这一方法，但是，当输入过大时，这一方法工程量也会大，从而影响使用。所以我们需要寻找方法简化他。
第一个方法Boolean Constraint Propagation逻辑约束传递
我们目标是结果返回为真，对于每一个逻辑单元，由于是and逻辑，所以我们需要所有输入在逻辑单元中是真的表述，也就是对于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 。所以我们在选择假设输入对象时，选择在单元中出现更多的。
除此之外，基于and逻辑，有零出零。所以一旦可以确定某一单元整体结果为0，那么当前假设一定不满足SAT 。
基于上述描述，我们可以得到伪代码
DPLL(clauses){ if (clauses is a consistent set of literals){ return true } else if(clauses contains an empty clause){ return false } else{ assign a popular input and DPLL(that clauses) }}上面的所有内容都是逻辑上的，接下来我们将逻辑应用到电路中。对于上面的所有逻辑，我们可以认为是如下图的电路

文章插图

也可以是

文章插图

第一种叫做2-level logic
第二种叫做multi-level logic
对于电路来说，我们要做的是把它转化成逻辑。也就是用A+BC这种形式表示电路逻辑。
转化的方式就是我们接下来要讨论的内容。
首先是针对2-level logic的转化
对于逻辑我们可以用BDD表示，对于电路我们用TT真值表表示。

文章插图

和前面逻辑部分相似，我们只记录结果为1的输入
首先，我们必须承认表示相同结果的逻辑的表示可以是多样的，其中包括a+a’可以当作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结果才为1，ac同时为1且bd为0结果才为1，ab为1cd为0结果为0 。我们可以得到逻辑关系a’bc’d+ab’cd’+abc’d’