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

摘 要：全加器实现的基本原理是基于进位传播和进位产生的PG逻辑。根据现有的PG逻辑计算公式，本文推导出一种新的等价型逻辑表达式，并验证了其正确性。将该等价型逻辑表达式用于全加器的设计中，能够改变原有的全加器结构，并改变布线通道的连线数目和连线方式。原文位置

关键词：全加器;PG逻辑;连线;负载

引言

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

全加器设计的

基本原理

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

　　图1 N位全加器

 

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

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

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

　　其中 Gi:i≡Gi=AiBi;Pi:i≡Pi=Aii;定义 G0:0=Cin;P0:0=0

通过观察可知，第i位的进位输出总是与Cin有关，所以有Ci=Ci:0，和Si=Ai臖i臗i-1=Pii臛i-1:0。由此可见，只要算出各位的Pi:i值和Gi:0值，就可以将各位的Si值求出。而其中最关键的就是利用递归公式快速算出各Gi: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+Pk:kGk-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逻辑的原理编写