逻辑优化基础-bi-decomposition

简介

bi-decomposition是逻辑综合中用于简化布尔函数的一种技术。其思想是将函数分成两个较小的函数，每个函数仅取决于所选变量的一个值。这些较小的函数可以使用简单的逻辑门（如AND、OR和NOT门）来实现，然后组合以获得原始函数的输出。这可能会导致原始布尔函数的更简单和更有效的实现。

bi-decomposition的过程涉及选择一个变量进行分割，根据该变量的值创建两个函数，然后使用以下恒等式将原始函数表示为这些较小函数的组合：

F = F1B + F0B'

其中F是原始函数，F1是选定变量为1时的函数，F0是选定变量为0时的函数，B是选定的变量。这个恒等式是代数的分配律的布尔版本，它允许我们将原始函数F表示为两个较小函数的和，每个函数仅取决于所选变量的一个值。

一旦我们使用较小函数表达了原始函数，我们就可以使用简单的逻辑门来实现这些较小函数，然后将它们组合以获得原始函数的输出。这可能会导致原始布尔函数的更简单和更有效的实现，因为较小的函数可能使用更少的逻辑门更容易实现。

bi-decomposition是逻辑综合中简化和优化布尔函数的一种强大技术。当原始函数复杂且难以使用直接方法实现时，一般可以尝试使用bi-decomposition。

示例

假设考虑这样一个布尔函数：

F(A, B, C, D) = A'B + AB'C + BCD

应用bi-decomposition到该函数的第一步是选择一个变量进行分割。让我们选择变量B进行分割，这意味着我们基于B的值创建两个函数：一个函数其中B为1（我们称其为F1），另一个函数其中B为0（我们称其为F0）。这些函数可以写成：

F1(B=1) = A'C + CD
F0(B=0) = A'

接下来，我们需要找到一种用F1和F0的方式来表达原始函数F的方法。我们可以使用以下恒等式：

F = F1B + F0B'

在这种情况下，我们可以写成：

F = (A'C + CD)B + A'B'

这就是相对于变量B的F的 bi-decomposition。同理我们也可以得到基于变量 C的 bi-decomposition 表达式：

F(A, B, C, D) = A'B + AB'C + BCDF1(C=1) = A'B + AB' + BD
F0(C=0) = A'BF = F1C + F0C' = (A'B + AB' + BD)C + A'BC'

实际上，如果我们再调用一个rewrite算法，还可以变换为以下形式：

F = F1C + F0C' = (A^B + BD)C + A'BC'

---

以上是对于 bi-decomposition的基础介绍，欢迎指正错误。