forahead adder 超前进位加法器_超前进位加法器本位和

数电书上说道超前进位加法器，没有仔细讲。上网搜了这篇资料，摘抄下来

串行进位加法器需要一级一级的进位，进位延迟很大。先行进位加法器（也叫超前进位加法器）可以有效的减少进位延迟。

    设二进制加法器的第i位输入为Xi, Yi, 输出为Si, 进位输入为Ci，进位输出为Ci+1

则有

         Si = Xi⊕Yi⊕Ci

      Ci+1  = Xi·Yi + Xi·Ci + Yi·Ci = Xi·Yi + (Xi + Yi)·Ci

令Gi = Xi·Yi,     Pi = Xi+Yi

则Ci+1  = Gi + Pi·Ci

当Xi和Yi都为1时，Gi = 1，产生进位Ci+1 = 1

当Xi和Yi有一个为1时，Pi = 1，传递进位Ci+1 = Ci

    因此Gi 定义为进位产生信号，Pi定义为进位传递信号。Gi的优先级比Pi高，也就是说：当Gi = 1时（当然此时也有 Pi = 1 ），无条件产生进位，而不管Ci是多少;

当Gi=0而Pi=1时，进位输出为Ci, 跟Ci之前的逻辑有关。

    下面推导4位超前进位加法器。设4位加数和被加数为A 和 B，进位输入为Cin, 进位输出为Cout, 对于第i位的进位产生Gi = Ai·Bi , 进位传递 Pi=Ai+Bi , i=0,1,2,3

于是这各级进位输出，递归的展开Ci ，有：

C0 = Cin

C1=G0 + P0·C0

C2=G1 + P1·C1 = G1 + P1·（G0 + P0·C0）=G1 + P1·G0 + P1·P0 ▪C0

C3=G2 + P2·C2 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0

C4=G3 + P3·C3 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·C0

Cout=C4

    由此可以看出，各级的进位彼此独立产生，只与输入数据和Cin有关，将各级间的进位级联传播给去掉了，因此减小了进位产生的延迟。

    每个等式与只有三级延迟的电路对应，第一级延迟对应进位产生信号和进位传递信号，后两级延迟对应上面的积之和，这可由Synplify综合后的RTL电路看到。

同时由真值表可以简单的得出第i位的和为：

            Si = Xi⊕Yi⊕Ci = (Xi·Yi)⊕(Xi+Yi)⊕Ci = Gi⊕Pi⊕Ci

    根据上面的式子便可以设计出超前进位加法器。按照《数字系统设计与Verilog HDL》中的方法，用Verilog编写了4位超前进位加法器，代码如下：

 1 module add_ahead(a,b,sum,cin,cout
 2     );
 3 input [3:0] a,b;
 4 input cin;
 5 output [3:0] sum;
 6 output cout;
 7 wire c1,c2,c3;//各级进位输出
 8 wire [3:0] g,p;
 9 
10 //产生第 0 位的本位值和进位输出
11 assign g[0]= a[0]& b[0];
12 assign p[0]= a[0]| b[0];
13 assign sum[0]= g[0]^p[0]^cin;
14 assign c1=g[0]|(p[0]&cin);
15 
16 //产生第 1 位的本位值和进位输出
17 assign g[1]= a[1]& b[1];
18 assign p[1]= a[1]| b[1];
19 assign sum[1]= g[1]^p[1]^c1;
20 assign c2=g[1]|(p[1]&c1);
21 
22 //产生第 2 位的本位值和进位输出
23 assign g[2]= a[2]& b[2];
24 assign p[2]= a[2]| b[2];
25 assign sum[2]= g[2]^p[2]^c2;
26 assign c3=g[2]|(p[2]&c2);
27 
28 //产生第 3 位（最高位）的本位值和进位输出
29 assign g[3]= a[3]& b[3];
30 assign p[3]= a[3]| b[3];
31 assign sum[3]= g[3]^p[3]^c3;
32 assign cout=g[3]|(p[3]&c3);
33 
34 endmodule

这段代码在实现c2,c3,cout的时候，仍然用了前一级的进位，我开始以为综合器会自动展开，但是用Synplify综合后发现，每一位的进位仍然与前一位的进位输出有关。于是将上面计算c2,c3,cout的代码用上面展开后的公式实现，如下：

1 assign c2=g[1]|(p[1]&g[0])|(p[1]&p[0]&cin);
2 assign c3=g[2]|(p[2]&g[1])|(p[2]&p[1]&g[0])|(p[2]&p[1]&p[0]&cin);
3 assign cout=g[3]|(p[3]&g[2])|(p[3]&p[2]&g[1])|(p[3]&p[2]&p[1]&g[0])|(p[3]&p[2]&p[1]&p[0]&cin)；

再用Synplify综合，发现c1,c2,c3,cout都只与初始进位和输出数据有关，各级进位间不存在进位延迟了。

 修改后的程度用Modelsim仿真结果正确。

其实比较好理解，就是如果按照正常的加法进行进位，如果使用逻辑电路，那么第一次的进位会加到第二次的进位上，第二次的进位会加到第三次上，这样实际上第一次的进位会一直传递到最后一次的进位上，这样必然会导致较大的延迟，delay。而如果采用时序电路的话，那么就会需要几次进位，就延迟几个周期之后才能输出数据，这样的latency较大。

采用了超前进位的方法就把刚才的情况避免了，因为超前进位归纳了进位的特点，每一次的进位都和之前的进位无关，只和之前的p和g的结果有关，而这些p和g的结果是可以通过一个时钟周期就计算出来的，即1）一个时钟周期内，计算出所有的p，g  2）第二个时钟周期内，计算出所有的c 3）第三个时钟周期，计算出所有的s。并且如果对很长的数进行加法，可以拆成小的位数进行相加。即64bit的加法操作可以拆成32bit的加法操作。