香农扩展运算

1 前言

        香农扩展（Shannon Expansion）是一种逻辑复制、增加面积、提高频率的时序优化手段。

2 定义

        布尔逻辑可以做如下扩展：

F(a,b,c) = aF(,b,c) + āF(0,b,c)

        从上面的定义可以看到，香农扩展即布尔逻辑扩展，是卡诺逻辑化简的反向运算。香农扩展相当于逻辑复制，可以提高频率；而卡诺逻辑化简相当于资源共享，可以节约面积。

3 举例说明

        香农扩展通过增加MUX，从而缩短了某个优先级高，但是组合路径长的信号的路径时延，从而提高了该关键路径的工作频率。

        设所需运算的逻辑表达式为：

F = ((({8{late}}|in0)+in1)==in2) & en；

        其中，信号in0、in1和in2都是8bit的数据，信号late和信号en是控制信号，信号late是本逻辑运算的关键路径信号，延时最大。

        使用香农扩展：

F = late.F(late=1) + ~late.F(late=0)
= late[((8’b1 + in1) == in2) & en] + ~late[((in0 + in1) == in2) & en]

        这相当于一个以late为选择信号，以late[((8’b1 + in1) == in2) & en]和~late[((in0 + in1) == in2) & en]为两个输入信号的2选1的MUX。因此，late信号的优先级被提高，其信号路径的延时降低，但是其代价是设计的面积增加了，并且需要两个比较运算符。

        未使用香农扩展的Verilog代码如下：

module un_shannon(
    input  [7:0]    in0,in1,in2,
    input           late,en,

    output          out
);

    assign out = ((({8{late}}|in0)+in1)==in2) & en;

endmodule

        使用Synplify Pro 2018.03综合，目标器件为Altera Cyclone V 5CSEMA5F31C6，得到的RTL图如下：

        未使用香农扩展是，从输入PAD late到输出PAD out之间共有4个逻辑单元，五段路径。其综合结果使用1了个8bit或门，1个8bit输入加法器，1个8bit比较器，1个2输入与门。

        使用香农扩展的Verilog代码如下：

module shannon(
    input  [7:0]    in0,in1,in2,
    input           late,en,

    output          out
);

    wire late_eq_0,late_eq_1;

    assign late_eq_0 = ((in0 + in1) == in2) & en;
    assign late_eq_1 = ((8'b1 + in1) == in2) & en;

    assign out = late ? late_eq_1 : late_eq_0;

endmodule

        同样使用Synplify Pro 2018.03综合，目标器件为Altera Cyclone V 5CSEMA5F31C6，得到的RTL图如下：

        使用香农定理后，从输入PAD late到输出PAD out之间共有1个逻辑单元，2段路径。其综合使用了2个8bit输入加法器，2个8bit比较器，2个数据与门和1个2输入选择器。

        可以看出，使用香农扩展后，对于late这一关键路径，消除了3个逻辑层次，从而在一定程度上提高了设计的工作频率。作为提高工作频率的代价，多用了1个加法器和选择器，消耗了更多的面积。

        是否使用香农扩展，关键要看被优化对象的优化目标是面积还是路径。

        告辞。