学习日志之synthesis and optimization（6）——逻辑优化

发布日期：2024-06-10 07:15浏览次数：50

minterm: 立体卡诺图的顶点，表示的是在真值表中输出为1的点

implicant: 由minterm组成，一个implicant中可以蕴含多个minterm，按照合并同类项的原则进行合并

cover: implicant的合集

minimum cover: 用最少的impliment表示的boolean函数（全局最优）
irredundant cover: 这里虽然不是用implicant最少的cover但是其是有包括所有的minterm的，而且去掉其中任意一个都会造成有没有被包含进去的implicant（局部最优）
irredundant cover with 1implicant：？？？？（弱局部最优）

逻辑上的优化目的就是要寻找到minimum cover

逻辑优化算法主要有两类：exact（这个得出的结果质量好，接近全局最小），approximate（这个效率高）。前者花在建立prime table上的资源很多，而后者不需要。这个优化问题由于最终需要找的是Min.covers，然而可能的cover会有很多种情况。为了效率我们可以引入一个Quine's theorem来对寻找的范围进行缩减。

Quine's theorem: Min.cover一定存在于PRIME cover中

prime cover: 这个是全部由prime implicant组成的cover

prime implicant: 不被其他implicant包含的implicant

关于这个prime implicant的理解如下所示：

问题描述：2-level optimization中就是要寻找一个X向量，使得其满足 $A\cdot X\geq 1$ ，并且 $\left | A \right |_{l_{1}\cdot norm}$ 是最小的（X中的元素加起来和最小）

这里X是一个列向量，其中的元素表示的是所有可能的Prime implicant是否包含在cover中如果包含，则值为1，若不包含，则值为0

A是一个就是一个记录Prime Implicant的矩阵，跟Prime Table一个意思

其行（row）表示minterm的个数

列（column）表示prime implicant的个数

当prime implicant j 包含了minterm i的时候这个（i，j）处的元素值就为1

在这里 $A\cdot X\geq 1$ 的意义理解如下图所示

EXACT

Exact类的方法最大的特点是一定需要一个Prime table来支持后面的步骤

1. Petrick method

这个方法基于boolean algebra，不在计算机上实现，一般是用于手算，因为后面的步骤需要自己计算得到优化的结果。

首先列prime table，在cube中找出所有的minterm记为行，将自己画的cover中所有的implicant记为列，在表中如果说第j列的implicant包含了第i行的minterm那么（i,j）这个点就记为1，如下所示为上面例子中的Prime table

然后横着看每一行的minterm，看哪些implicant里包含了这个minterm将所有包含的implicant给与起来，即可得：

$m_{0}: \alpha$

$m_{1}: \alpha + \beta$

$m_{5}: \beta +\gamma$

$m_{6}: \delta$

$m_{7}: \gamma +\delta$

既然所有的minterm都包括在了cover中，那么上面这些全部或起来就不会是0

即： $\alpha \left ( \alpha +\beta \right )\left ( \beta +\gamma \right )\delta \left ( \gamma +\delta \right )= 1$

然后将这个化简可以得到下面的结果：

$\left \{ \alpha \left ( \alpha +\beta \right )\right \}\left ( \beta +\gamma \right )\left \{ \delta \left ( \gamma +\delta \right )\right \}= 1$

$\Rightarrow \alpha \left ( \beta +\gamma \right )\delta$

$\Rightarrow \alpha \beta \delta +\alpha \gamma \delta$

注：这里的 $\alpha$ 和 $\delta$ 是essential prime implicant，因为这两包含了其它implicant都不包含的部分，因此要将所有的minterm都cover进来就一定会需要这两个implicants，在此就表达出在所有解中一定会存在，而反观 $\beta$ 和 $\gamma$ 只要二者取其一即可。

所以可得出最终的结果又两种分别为

2. Quine & Mc.Clisky

在描述这个方法之前首先定我们的function是一个4输入单输出的函数。其输入分别为x,y,w,z。接下来的步骤中我们可以换一种思路从真值表中得到我们需要的prime table，这也是电脑可以做的事情。

我们在真值表中找出on-set(即输出为1的那些项)然后放入一个表中，其列为输入，行为minterm。

然后，在这个表中我们一个一个比较，将所有hamming distance为1的Minterm统统合并（这个和后面espresso算法是一样的，即将minterm升级一下，使其包括更多的minterm。这一步在espresso中叫做expanding。而在kanaugh map中就是找相邻2,4,8个的合并）

随后就可以得到下图，下图左边是合并的结果，合并之后一定会多一个不关心的位。如果没有合并的，就放在前一个表中就好，然后再没有合并的所有的implicant中选出能cover所有minterm的那些Implicant作为prime implicant