等价型PG逻辑及其在加法器设计中的应用

　　引言

　　在全加器设计中运用PG逻辑是非常普遍的，本文在设计和研究全加器时，根据现有的PG逻辑公式推导出了一种新的逻辑公式，并论证了两者之间的等价关系。这一新的公式能够指导全加器设计中的连线方式，灵活更改连线策略。本文将从基本原理开始逐步引出该公式，对其进行论证，并应用于全加器设计中。

　　全加器设计的

　　基本原理

　　N位全加器将{A_N，……，A₁}、{B_N，……，B₁}和进位输入Cin作为输入，计算得到和{SN，……，S1}以及最高位的进位输出Cout(见图1)。每一位得到的和与进位输出都直接受其上一位的影响，其进位输出也会影响下一位。最终，整个全加器的和与输出都受进位输入Cin的影响。

图1 N位全加器

图2 多位组传播C_in 或者直接产生进位输出

　　全加器最简单的构成方法就是把每一位的进位输出与下一位的进位输入简单地连接起来，得到的就是行波进位全加器。但在快速全加器中，是将加数和被加数中具有相同下标的位分成若干组，即多个多位组，并将各个多位组看作一个整体。通过计算多位组的PG逻辑，在求和之前可预测多位组的进位输出是传播进位输入还是直接产生进位输出。多位组所包括的位在i到j的范围内(见图2)，如果该多位组的进位输出是与进位输入无关的“真”值，那么它就产生了一个进位;如果该多位组的进位输出只有当进位输入为“真”时才进位输出“真”值，那么它就传播了一个进位。对于i≥k≥j，这些信号能够递归地定义为：

　　G_i:j=G_i:k+P_i:kGk-1:j;P_i:j=P_i:kPk-1:j

　　其中 G_i:i≡G_i=AiBi;Pi:i≡P_i=Aii;定义 G₀:0=Cin;P_0:0=0

　　通过观察可知，第i位的进位输出总是与Cin有关，所以有Ci=Ci:0，和Si=Ai臖i臗i-1=Pii臛i-1:0。由此可见，只要算出各位的Pi:i值和Gi:0值，就可以将各位的Si值求出。而其中最关键的就是利用递归公式快速算出各G_i:0值。上述递归表达式可以用如图3所示的电路表示。

图3 递归表达式的对应电路

　　为了能够更加简洁地表达全加器电路结构，可将图3中的电路用图4所示的黑色单元表示，并用图4中的白色单元表示图5所示的G逻辑产生电路。

图4 黑色单元和白色单元

图5 G逻辑产生电路

　　根据递归公式，可以得到各种不同结构的全加器，他们的逻辑级数、扇出、布线通道数、所用单元数等各不相同，在此不再赘述，只给出一种Kogge-Stone树型全加器PG网络，如图6所示。图的上部即是各位的本位Pi:i和Gi:i产生逻辑，中部是PG传播网络，下部是各位的进位输出Ci。这种树型全加器具有理想的逻辑级数和扇出，但是连线复杂，也需要更多的单元。

图6 Kogge-Stone树型全加器PG网络

　　等价型PG逻辑的论证

　　对上文给出的递归表达式进行进一步推导，可得出如下结果：Gi:j=Gi:k+Pi:kGk-1:j=Gi:k+Pi:kGk:j(Gk-1:j可用Gk:j替代)

　　下面给出它的简单推导过程：

　　因为，Gk:j=Gk:k+P_k:kG_k-1:j

　　所以，Gi:k+Pi:kGk:j=Gi:k+Pi:k(Gk:k+Pk:kGk-1:j)=Gi:k+Pi:kGk:k+Pi:kPk:kGk-1:j

　　将Gi:k展开以后，上式=Gi:k+1+Pi:k+1Gk:k+Pi:kGk:k+Pi:kPk:k Gk-1:j

　　因为，Pi:k=Pi:k+1Pk:k=Pi:kPk:k

　　所以，上式

　　=Gi:k+1+Pi:k+1Gk:k(1+Pk:k)+Pi:kGk-1:j

　　=Gi:k+1+Pi:k+1Gk:k+Pi:kGk-1:j

　　=Gi:k+1+Pi:kGk-1:j

　　=Gi:j

　　等价型PG逻辑的运用

　　运用新推导的等价型PG逻辑，可以改变PG传播网络的连接形式，如图7所示，原来某些应该独立连接的节点，现在可以利用等价型逻辑表达式将它们连在一起，比如在图7中的“5：4”和“4：3”两个节点，在图6中它们分别应该按原始公式连接“3：2”和“2：1”两点，现在可以根据新公式将它们都连接到“3：2”,其它节点以此类推。而且，在图7中的“3：0”节点处负载较重，因此可以将“11：4”、“10：4”连接到“4：0”，以减轻“3：0”处的负载。总的说来，改进以后的全加器在布线上可以相对于未改进的电路减少近一半，但负载相对来说也增加了一倍。因此，在实际电路中可以灵活调整连接关系，以平衡布线与负载之间的矛盾，同时对某些负载重的节点需要增加若干反相器，以增大该节点的驱动能力。

图8 改进PG传播网络以后的全加器

　　仿真与验证

　　本文按照等价型PG逻辑的原理编写了如上所述的15位加法器的Verilog描述，并用ModelSim对其进行了仿真，对随机数进行相加，得到了正确的结果，说明在逻辑上该PG逻辑是正确的，如图8所示。其中a、b为两个15位的随机数，ci为随机的进位输入，co为进位输出，sum是最终的和(其最高位是co)。

图8 运用等价型PG逻辑设计的15位加法器的仿真波形

　　结语

　　本文根据现有PG逻辑计算公式，推导出了一种新的与之等价的逻辑表达式。将这一逻辑表达式运用到加法器设计中去，能够改变PG传播网络的结构，减少连线数目，降低布线复杂度，这样会更有利于后端的版图布线。但此方法会相应增大某些节点的负载，势必带来延迟的增加，因此需要精心设计晶体管尺寸或增加节点处的驱动能力，以使电路达到时序要求。

　　在今后的全加器设计中，可以根据具体情况灵活调整PG传播网络的结构，尽量使得布线与负载达到一定程度的平衡。

　　参考文献：

　　1. P.M. Kogge, H.S. Stone. A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Trans, C-22(8): 831-838, Oct. 80

　　2. 汪东,李振涛,毛二坤,李宝锋等译. Neil H.E. Weste, David Harris著. CMOS超大规模集成电路设计(第三版). 北京：中国电力出版社，2006