优化逻辑的工具？

Question

我正在用java编写一个处理器模拟器，控制信号非常麻烦。是否有以下生成逻辑的工具：

二进制逻辑：

input[0]: 00001
input[1]: 00000
input[2]: 00010
input[3]: 00011

产出：

if(input.subString(0,3) == "000") 
    //do something;

基本上，输出找到输入的公共部分。在上面的例子中，它的意思是“以000开头的任何东西都会做一些事情”，而不管它的00000, 00001, 00010, 00011是否

优化类似于k-映射，除了我有100个输入外，手工优化是不实际的。

下面是一个k-map的例子，与我在上面的例子无关。

​

​

输出不必使用java语法，任何简化的逻辑语句都可以。

Answer 1

因此，您有一大组长度为N位的字符串( N大约为100)，您想要一个简单的逻辑表达式来匹配这些字符串，而不是其他字符串吗？

您可以尝试制作一个程序，为您构建Kernaugh地图。这将是一个有趣的练习。我不太记得克诺地图，但是我认为行和列上的标签是用灰色代码排列的。

或者你可以试着让这个问题在手工制作的克诺地图上更容易处理。对于每个字符串，查找所有字符串共有的位元。然后打印一张剩余位位置的列表，供人类构建地图。

一些Python代码：

str_len = 5
strs = [
     [0,0,0,0,1],
     [0,0,0,0,0],
     [0,0,0,1,0],
     [0,0,0,1,1],
]
for i in range(str_len):
    if all([x[i] for x in strs]):
        print 'Bit %d is 1' % i
    elif not any([x[i] for x in strs]):
        print 'Bit %d is 0' % i
    else:
        print 'Bit %d is contingent' % i

在这一点上，您可以尝试考虑如何对B剩余的偶然位进行编码。在本例中，所有情况都包括在内(您可以检测到这是一个特例--例如N = 2^B)。

一种为偶合位寻找公式的蛮力算法是：

i.

• Divide

• 将下一个附带位1).

• Recursively S选择为S0 (位i =0的子集)和S1 (位i = (~b[i] & f0) | (b[i] & f1).

的子集)，找到S的S0和S1 respectively.

• The公式的f0和f1公式是(~b[i] & f0) | (b[i] & f1).

。

有一些优化。简单的是S0或S1是空的--然后忽略结果公式的分支。另一种情况是，所有可能的组合都在一个集合中(类似于上面的示例)；在这种情况下，公式不需要引用位。最难的是找到一个很好的顺序来迭代其中的位。按照顺序天真地去做可能会导致一个不太理想的公式。

实际上，您可以跳过上面的第一个建议，并对所有的部分进行运行。总是为1或0的位只会产生S0或S1为空的琐碎情况。

这个相当混乱的Python代码通过一些优化来执行算法。N.B. --测试不多，也不一定能产生最佳输出！

def get_formula(S, i=0):
    # Special case where it's an empty set -- return a tautology
    if len(S) == 0:
        return '1'

    remaining_bits = len(S[0]) - i

    # Special case where no bits are left
    if remaining_bits <= 0:
        return '1'

    # Partition the set
    S0 = filter(lambda x: x[i] == 0, S)
    S1 = filter(lambda x: x[i] == 1, S)

    f0 = get_formula(S0, i+1)
    f1 = get_formula(S1, i+1)

    # Special cases where one subset is empty
    # Also special case for subformula being tautology
    if len(S1) == 0:
        if f0 == '1':
            return '~b[%d]' % i
        return '~b[%d] & (%s)' % (i, f0)
    if len(S0) == 0:
        if f1 == '1':
            return 'b[%d]' % i
        return 'b[%d] & (%s)' % (i, f1)

    # Special cases where one or both subformulas was a tautology
    if f0 == '1' and f1 == '1':
        return '1'
    if f0 == '1':
        return '~b[%d] | b[%d] & (%s)' % (i, i, f1)
    if f1 == '1':
        return '~b[%d] & (%s) | b[%d]' % (i, f0, 1)

    # General case
    return '~b[%d] & (%s) | b[%d] & (%s)' % (i, f0, i, f1)


strs = [
     [0,0,0,0,1],
     [0,0,0,0,0],
     [0,0,0,1,0],
     [0,0,0,1,1],
]

print get_formula(strs)

最后，我认为，要使这段代码找到更好的公式，一种方法是在S中提前扫描始终为0或始终为1的位，并尽早处理它们。每个子集中剩余的意外情况位将被推入深度嵌套的子公式中，与过早处理时相比，它们将形成较少的冗余公式。我认为这实际上将模拟Kernaugh映射样式的构造:在每一步中，始终为0或始终为1位的集合在映射上定义一个矩形。找到该集合，立即处理它们(例如，作为一个紧凑的公式~b[0] & ~b[1] & ~b[2])，然后对其余的位进行递归。您需要跟踪哪些位位置已经被处理，而不是按照使用i的顺序执行。

(实际上，现在我来考虑一下，对于最优的公式，您还需要通过一次选择一组相关位来灵活地划分。一个有趣的问题.)