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

文章插图

前言这一篇是逻辑电路基础知识的最后一篇。
Don’t CareDon’t Care 可以称作冗余，在电子电路中，它有不同的类型对应不同的表现形式。
首先，我们从例子的角度探索一下冗余是怎么产生的。
输入不可能第一个例子
X = ab ,F = Xb + bY +XY
首先我们对于X和ab进行分析

文章插图

由于X和b存在一定约束关系：X是1时，b一定是1，不能是0
所以对于F存在一些输入并不可能

文章插图

这就是冗余的第一种类型：存在输入不可能在逻辑电路中出现。
那么这个don’t care冗余对F来说究竟有什么影响呢
在不考虑冗余情况下，只要X b Y 存在两个输入为1，输出就是1，现在X为1b必为1，只要X为1或者b Y 同时为1 ，输出就是1 。我们也就可以把原来的逻辑关系简化成 X + bY
也就是don’t care的发现能够让我们简化电路。
所以对于我们而言，要做的就是找到冗余。
在讨论找到冗余方法之前，我们先介绍第二种冗余
输出不影响第二个例子
X = ab ,Y = b + c, F = Xb + bY + XY, Z = FXd
依旧是先寻找 X 和 ab 的关系，以及 Y 和 bc 的关系

文章插图

文章插图

然后是 F 和 X b Y 的关系

文章插图

最后到Z = FXd
首先根据前面F和XbY的关系，我们得到X为1时，F为1，也就是不存在01的输入
接下来我们看看Z和FXd的关系，要想Z为1，FXd都要是1，也就是当Xd有一个不为1或者都不为1时，F不影响输出，而当Xd都为1时，F一定为1，也就是F从始至终都不影响输出。
这就是第二种冗余，输入对输出不影响，所以我们完全可以忽略这一输入达到简化的目的。
简化冗余通过算法找到冗余就是我们接下来要做的事情
在讨论算法之前，我们先明确冗余的特征：在前面的两个例子中，我们分别得到的是基于对输入不可能的冗余，基于对输出无影响的冗余Observability don’t cares 。
对于输入不可能存在两个方面，一个是逻辑约束Satisfiability don’t cares，另一个是环节之间的传递 Controllability don’t cares
基于逻辑约束的冗余，他的特征是在and逻辑门中，输出是1，输入必须全是1，在or逻辑门中，输出是0，输入必须全是0 。也就是这里的冗余是输入所导致的输出和与其输出不符。
因此我们判断冗余的方法就是将输出X当作一个我们可以控制的输入，将原逻辑当作实际输出，当两者不等时，说明这种情况不可能出现，也就是一个冗余。
例子
X = ab + c
X xor (ab + c) = 1 的X a b c就是冗余，那么接下来就是我们的计算了，如何计算一个xor呢，在前面的SAT中，我们提到了类似的方法。我们将式子转化成CNF形式：X’ab + X’c + Xa’c’ + Xb’c’ 。接下来就是对每一个单元进行分析，这里我们使用Boolean Constraint Propagation逻辑约束传递的方法就可以了。
对于环节之间的传递就是当一个环节存在冗余时，他对下一个环节存在影响.那么我们怎么找到这一冗余呢。
例子
X = a + b , Y = ab , F = Xc + Yd + acd
对于 F 来说，受上一环节影响的因素只有X Y，同时F本身具有基于逻辑约束的冗余的可能，所以我们只讨论受上一环节影响，对于X Y 来说，他们具有的冗余特征是X xor (a+b) 和 Y xor ab 。对于 F 来说 a 元素具有逻辑冗余的可能，所以如果在环节冗余中讨论，不得不同时考虑逻辑冗余，因此我们只对 F 中不存在的但是 X Y 中存在的 b 进行分析，分析方法就是遍历，我们需要知道对于任意b存在的冗余。