逻辑优化-rewrite

简介

逻辑综合中的rewrite算法是一种常见的优化算法，其主要作用是通过对逻辑电路的布尔函数进行等效变换，从而达到优化电路面积、时序和功耗等目的。本文将对rewrite算法进行详细介绍，并附带Verilog代码示例。

一、算法原理

rewrite算法的核心思想是通过布尔代数中的等价变换来达到电路优化的目的。具体而言，算法将电路的原始布尔函数通过一系列等价变换转化为更简单的布尔函数，从而达到优化的目的。

二、算法流程

rewrite算法的流程如下所示：

1. 输入电路的原始布尔函数；
2. 根据规则库中定义的等价变换规则，将原始布尔函数转化为一个或多个新的布尔函数；
3. 对新的布尔函数重复上述步骤，直到布尔函数无法继续化简为止；
4. 输出化简后的布尔函数。

具体来说，rewrite算法通过一系列等价变换规则将布尔函数转化为其等效的形式，如下所示：

同一律： A+A=A； A*1=A；
零元素： A+0=A； A*0=0；
吸收律： A+AB=A； A(A+B)=A；
分配律： A*(B+C)=AB+AC；
德摩根定律： ~(A+B)=~A~B； ~(AB)=~A+~B；
布尔恒等式： A+~A=1； A*~A=0；
交换律： A+B=B+A； AB=BA；
结合律： A+(B+C)=(A+B)+C； A*(BC)=(AB)*C；
分配律的逆定理： (A+B)C=(AC)+(B*C)；
吸收律的逆定理： A+(AB)=A； A(A+B)=A。

通过这些等价变换规则，rewrite算法可以将一个布尔函数化简为其最简形式，从而达到电路优化的目的。

3. 示例

假设我们有一个简单的逻辑电路，其功能等价于两个输入a和b做异或运算，输出结果为c：

module xor_gate(input a, b, output c);assign c = a ^ b;
endmodule

我们可以使用逻辑综合中的rewrite算法对这个电路进行优化，从而得到一个更为简单的电路。

具体来说，我们可以应用一个rewrite规则：将异或门替换为两个AND门、一个OR门和两个NOT门的等效电路。下面是应用这个规则后的Verilog代码：

module xor_to_and_or(input a, b, output c);wire not_a, not_b, and_a_b, and_not_a_not_b, or_a_b;assign not_a = ~a;assign not_b = ~b;assign and_a_b = a & b;assign and_not_a_not_b = not_a & not_b;assign or_a_b = and_not_a_not_b | and_a_b;assign c = ~or_a_b;
endmodule

然后，我们可以在原始的xor_gate模块中，使用新的xor_to_and_or模块来实现优化后的电路，如下所示：

module xor_gate(input a, b, output c);xor_to_and_or rule(.a(a), .b(b), .c(c));
endmodule

通过这个优化，我们将一个异或门转化为了两个AND门、一个OR门和两个NOT门的电路结构，从而实现了对电路的优化，事实上这是一个反向的优化。当然，这只是一个简单的例子，实际应用中rewrite算法的规则和应用方法可能会更加复杂和多样化，需要根据具体的设计需求和约束来确定。同时，需要注意电路优化可能会对电路的性能、功耗、可靠性等方面产生影响，需要进行综合分析和评估。