1

我正在用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-map，除了我有一百个输入，手动优化根本不实用。

这是k-map的示例，与我上面的示例无关

示例 kmap

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

4

1 回答 1

1

所以你有一大组长度N位的字符串（其中N大约是 100），你想要一个简单的逻辑表达式来匹配这些字符串而不是其他字符串？

您可以尝试编写一个程序来为您构建 Kernaugh 地图。这将是一个有趣的练习。我不太记得 Kernaugh 地图，但我认为行和列上的标签使用格雷码排列。

或者，您可以尝试让手工制作的 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）。

用于寻找或然位​​的公式的蛮力算法将是：

  1. 选择下一个可能的位i。
  2. 将 S 分为 S0（bit i= 0 的子集）和 S1（bit i= 1 的子集）。
  3. 递归地分别找到 S0 和 S1 的公式 f0 和 f1。
  4. S 的公式是(~b[i] & f0) | (b[i] & f1)。

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

实际上，您可以跳过上面的第一个建议并在所有位上运行它。始终为 1 或 0 的位只会产生 S0 或 S1 为空的琐碎情况。

这个相当混乱的 Python 代码通过一些优化来执行算法。 注意它没有经过太多测试，不一定能产生最佳输出！

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-map 样式的构造：在每一步，始终为 0 或始终为 1 位的集合定义了地图上的一个矩形。找到那个集合，一次处理它们（例如作为一个紧凑的公式~b[0] & ~b[1] & ~b[2]），然后对剩余的位进行递归。您需要跟踪哪些位位置已被处理，而不是使用i.

（实际上，现在我想起来了，对于最佳公式，您还需要通过一次选择一堆相关位来巧妙地进行分区。一个有趣的问题......）

于 2012-05-22T22:48:31.500 回答