给定输出频率，创建一个具有最小布尔函数的真值表

Question

我有一个带有 8 个输入和 3 个输出的黑匣子，我想为它们编写最小化的布尔函数。我知道如何简化给定真值表的布尔表达式，但我没有真值表。我只知道每个输出组合应该在 2^8 个输入组合中出现多少次。 例如（组合 x 256 次中的次数）： 000×51， 001×62， 010×61， 011×56， 100×14， 101×10， 110×2， 111×0。

我想用这些组合填充真值表，以便最小化输出函数，并且进行详尽的研究是不可行的，所以我正在寻找其他方法。 这是一个已知的优化问题吗？ 在我的第一次尝试中，我使用了 2 的幂组来获得更大的立方体，这样 SOP 就会最小化一点，但这种方法取决于我如何处理问题以及另一个人可以获得不同的函数。因此，我尝试在一些启发式算法中自动化该方法，但我无法做到。 您对替代方法或如何开发启发式方法有建议吗？ 谢谢

Answer 1

首先，定义您的优化标准。
这可能是最小项的数量或逻辑门的数量。

然后，从按给定顺序排序的表格开始：

  0: 00000000 000
     ....
 50: 00110010 000
 51: 00110011 001
     ....
112: 01110000 001
113: 01110001 010
     ....
173: 10101101 010
174: 10101110 011
     ....
229: 11100101 011
230: 11100110 100
     .....
243: 11110011 100
244: 11110100 101
     ....
253: 11111101 101
254: 11111110 110
255: 11111111 110

贪婪优化循环：

Perform an optimization run with a tool like Espresso and register the resulting optimization level.

Repeat until timeout:

    Pick two random rows with different output sections and swap their order.

    Perform another optimization run.    
    Keep the changed order, if it was "better" than the previous one.    
    Undo the swap, if not.

具有八个输入和三个输出的可能布尔函数的数量是巨大的。每次运行Espresso需要几秒钟或更长时间。所以，这个方法肯定是很慢的。