一种减少数字逻辑电路面积的方法

摘要

本发明公开了一种减少数字逻辑电路面积的方法，通过利用异或操作的特性，生成特定的乘积项添加到被优化函数中，由于新的乘积项的加入，可以使原来逻辑不相邻的乘积项因添加项的插入而逻辑相邻，从而实现逻辑的优化，其优点在于判明存在广义海明距为2的二个乘积项后，并不马上将这二个乘积项构成一个异或表达式，而是先产生相应的添加项，然后通过相应的评估方法来判断添加项是否适合函数的简化。因为逻辑函数的复杂程度与对应的数字电路的复杂程度密切有关，简单的逻辑函数往往对应着较小的电路面积，通过简化逻辑函数的方法达到了减少数字逻辑电路面积的目的。

主权项

1.一种减少数字逻辑电路面积的方法，其特征在于待优化的逻辑函数定义为f，f优化后的函数定义为； f的乘积项的集合定义为；若中含有w个乘积项，其中任意一个乘积项定义为；表示乘积项的维数，即对于一个含有n个变量的函数，如果逻辑函数f的某个乘积项含有m个变量，m≤n，则的维数为；并且令的初始值为“0”；具体步骤为：步骤A．定义广义海明距：对于一个给定的含有n个变量的逻辑函数f，它的任意两个乘积项为，其中i和j都不大于w；乘积项和之间的广义海明距表示各输入变量在和中取值的差异；广义海明距大小等于同时符合下面2个条件的变量的个数：①、变量在和中都出现；②、变量在和中取值形式为互补；步骤B．在乘积项的集合中任选一个乘积项；找出与乘积项广义海明距为2的所有乘积项，复制这些乘积项，得到一个与的广义海明距都为2的乘积项集合，定义为；步骤C．令乘积项集合对应的逻辑函数为，在中任选一个乘积项，由和分别生成的二个添加乘积项，定义为和；其中生成的方法如下：①、按照广义海明距的定义，确定导致和的广义海明距为2的两个变量的位置，记为和；②、比较和的维数，选取维数较小的乘积项来产生添加乘积项，如果乘积项和乘积项的维数一样，则任取一个；③、第一个添加乘积项等于将选中的乘积项中的第位变量取反；第二个添加乘积项等于将选中的乘积项的第位变量取反；对进行如下运算，并将添加到函数中，得到，；对执行如下运算，并将添加到函数中，得到，；步骤D．定义函数，并令；用公知布尔函数二级优化方法优化，得到优化结果为，并判断是否具有如下特性：（1）、是否比更加简单；（2）、定义和为的二个乘积项；判断添加的乘积项是否同时仅被和包含；如果同时具有上面（1）和（2）两个特征，则从集合中删去被乘积项和完全覆盖的乘积项，并将函数更新成为，删除，删除，并执行步骤E；否则用公知布尔函数二级优化方法优化，得到优化结果为，并判断是否具有如下特性：（3）、是否比更加简单；（4）、定义和为的二个乘积项；判断添加的乘积项是否同时仅被和包含；如果同时具有上面（3）和（4）两个特征，则从集合中删去被乘积项和完全覆盖的乘积项，并将函数更新成为，删除，删除，并执行步骤E；如果乘积项不符合特征（1）和（2）或者乘积项不符合特征（3）和（4），则从集合中删去乘积项，然后执行步骤C寻找另外一个和的广义海明距为2的乘积项；如果比较了中的所有乘积项都没有符合特征（1）和（2）或者符合特征（3）和（4），则将乘积项从中删除，并将函数更新为，删除，删除，执行步骤E；步骤E. 如果中包含的乘积项的个数大于1，则执行步骤B到步骤D；如果中只包含了1个乘积项，则原逻辑函数f的最终简化结果为；如果为空集，则得到原逻辑函数f的最终简化结果。