加法器的设计_加法器设计

一、半加器

半加器是用于计算2个一个bit的二进制数a与b的和，输出结果是sum（s）和进位carry（c）。在多bit数的计算中，进位c将作为下一相邻bit的加法运算中。单个半加器的计算结果是2c+s。
真值表：

逻辑表达式：

Verilog描述为：

module half_adder(
	input a,
	input b,
	output c,
	output s
);
assign c = a&b;
assign s = a^b;
endmodule
1
2
3
4
5
6
7
8
9

电路图如下：

二、全加器

全加器不同于半加器是，全加器带有进位cin。输入为a，b，cin，输出为sum（s），进位carry（c），均是单bit信号。
s为a、b、cin三个单bit数的和，cout为a，b，cin三个数超过2后的进位。
真值表

逻辑表达式：

verilog描述：

module full_add(
	input a,
	input b,
	input cin,
	output cout,
	output s
);
assign s = a^b^cin;
assign cout = a&b | (cin & (a^b));
endmodule
1
2
3
4
5
6
7
8
9
10

电路图：
表示符号：

三、行波进位加法器

N-bit加法器可以根据1-bit全加器组合而成。每个全加器的输出进位cout作为下一个全加器的输入进位cin，这种加法器称为行波进位加法器（Ripple-carry addr，简称RCA），如一个16bit加法器的结构如下所示，其中A、B为16bit的加数，S为A+B的和，c16为该加法器的输出：
由上图所知可以得到进位c16的结果依赖于c15,c14,c13,…c2,c1,c0，对于32bit，64bit等加法器，进位链将显得更加长。所以，行波进位加法器设计简单，只需要级联全加器即可，但它的缺点在于超长的进位链，限制了加法器的性能。

module rca #(width=16)(
	input [width-1:0] A,
	input [width-1:0] B,
	output [width-1:0] sum,
	output cout
);
wire [width:0] temp;
assign temp[0] = 0;

genvar i;
for(i=0;i<width;i=i+1) begin
	full_addr full_addr_inst(
							.a(A[i]),
							.b(B[i]),
							.cin(temp[i]),
							.cout(temp[i+1]),
							.s(sum[i])
							);
end
endmodule
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

行波进位加法器关键路径分析：
Nbit行波进位加法器可以由N个全加器级联而成，电路的延时包括门延迟和线延迟等，
从输入a，b，cin到输出s和cout，有以下路径：
（1）a—>s：经过xor1，xor2两个门电路
（2）a—>s：经过xor1，xor2两个门电路
（3）cin—>s：经过xor2一个门电路
（4）a—>cout：经过xor1，and1，or1三个门电路
（5）b—>cout：经过xor1，and1，or1三个门电路
（6）cin—>cout：经过and2、or1两个门电路

由以上六条路径可知，从a，b，cin输入数据准备好，到所有的s和cout完成，a或b到cout共有三个门电路延迟，是全加器的最长路径，且s不参与下一级全加器运算，cout作为下一个cin输入继续计算下一级的s和cout。

由N个全加器级联的行波进位加法器除了第一个进位c1有三个门延迟外，剩余N-1个全加器生成进位需要2个门电路延迟，所以N比特行波进位加法器最长路径共有（3+（N-1）*2）=2N+1个门电路延迟，上图的红色描绘的路径即最长路劲。

四、超前进位加法器

超前进位加法器（Lookahead Carry Adder，简称LCA）
对于更宽的加法器N，行波进位加法器关键路径越长，限制了加法器的性能，对于高速处理器是个极大的瓶颈。超前进位加法器优化改进行波进位加法器的关键路径，RCA的缺点在于第k位的进位Ck必须依赖与前一级的Ck-1，所以最高位的进位将必须等待之前所有级进位计算完毕后才能计算出结果。
超前进位加法器的思想是并行计算进位Ck

观察上式s和c，将共有部分定义为如下：

将LCA加法器重写如下：

其中：

上面的式子，门级电路图如下，就是个半加器

4bitLCA加法器，其进位链与和公式分别计算如下：

结构图如下：
对于大比特会造成电路极大的扇出和扇入。
可以根据4比特LCA级联而成，如16比特LCA可由如下图级联而成（属RLCA）：
递归超前进位加法器（Recursive Lookahead Carry Adder，简称RLCA）

LCA进位c4的门电路图

LCA输出S3门电路图

RCA的缺点在于关键路径长，限制了速度，性能不高；LCA关键路径短，速度快，进位链计算依赖少，但对于位宽较大的加法器，PG和进位生成逻辑大，存在较大扇入扇出，变化信号多，会有较多的glitch，且面积与复杂度比同等的RCA大。

以下参数化LCA基于4比特LCA设计，width可参数化定义为4的倍数，如20,24,32等。

五、进位旁边加法器

进位旁路加法器（Carry Skip Adder，CSA），也称Carry Bypass Adder。CSA也是另外一种加法器-----进位保存加法器（Carry Save Adder）的简称。

上面所述的行波进位加法器RCA，第k位的进位Ck必须等待之前的Ck-1的结果才能计算出来，如下图进位C16必须等到前一级全加器的C15输出才可以计算，所以行波进位加法器的特点便是超长的进位传播链。

进位旁路加法器的思想在于加速进位链的传播，在某种情况下，到达第i位的进位无需等待第i-1位进位。在16bitRCA中，最长的进位链为c0->c1->c2–…->c16，也就是说，每一位全加器都有进位，这条路径也是最长的关键路径。进位旁边加法器通过加入旁路逻辑来缩短这条最长路径，该旁路逻辑由2选1数据选择器，第x级进位和第y级进位和进位bypass信号组成。

CSA结构如上，紫色部分为数据选择器，橙色部分为数据选择信号，数据来源为进位C0和第三全加器的进位输出。

当P3&P2&P1&P0=1时C4=C0；进位C0直接传播至C4，而不需要再经过4级全加器的延迟，这就是进位旁路加法器的核心。

C4 = G3 + G2P3 + G1P3P2 + G0P3P2P1 + c0P3P2P1P0

当P3&P2&P1&P0=1时，则P3=P2=P1=P0=1，所以C4生成的逻辑如下：

C4 = G3 + G2 + G1 + G0 +c0
在超前进位加法器中有如下定义：

P是a与b异或的结果，只有a=0，b=1或者a=1，b=0时，P才可能等于1，而G=ab，所以只要P=1，则G一定为0，所以G3=G2=G1=G0=0.

最后的结论与上述一致：当P3&P2&P1&P0=1时，C4的生成逻辑最终变成C4=c0。

进位旁路加法器关键路径与优化
将Nbit加法器，以mbit为一组，分成N/m组，如下式16bit进位旁路加法器，N=16，m=4，共有4组，该16bitCSA由4个全加器组成的Block，进位逻辑Skip logic和2选1数据选择器三部分组成。
以上关键路径发生在：
（1）c0走第一级Block，经过4级全加器，进位从bit0到bit3生成C4
（2）中间进位经过bypass逻辑
（3）最后一级走Block逻辑，经过4级全加器，进位从bit12到bit15生成C16。

基于此结构通用的关键路径延迟公式为：
Tsetup：A、B低位到第一级Block的时间
tcarry：每个进位传播Bloack中全加器产生进位的时间
Tskip：进位通过skip逻辑的时间
Tsum：从最后个进位到s输出的时间

为什么最长的delay会是中间两级路径，如果加法器全部走Block逻辑，应该延迟更长？其实走最长的路径，中间路径会被旁路，也就是执行0111_1111_1111_1111+0000_0000_0000_0001的情况。第一级产生进位后，中间两级被旁路，最后一级经过RCA进位链，也就是下图中红色描绘出的路径图。

module full_adder_cska(
    input a,
    input b,
    input cin,
    output cout,
    output s,
    output p
);

assign s = a ^ b ^ cin;
assign cout = a & b | (cin & (a ^ b));
assign p = a ^ b;

endmodule

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

module cska_4bit #(width=4) (
    input  [width-1:0] op1,
    input  [width-1:0] op2,
    input  cin,
    output [width-1:0] sum,
    output cout
);

wire [width-1:0] p;
wire [width:0] c;
wire sel;

assign c[0] = cin;
//full adder and p generator
genvar i;
for( i=0; i<width; i=i+1) begin
    full_adder_cska u_full_adder_cska(
        .a   ( op1[i]   ),
        .b   ( op2[i]   ),
        .cin ( c[i]     ),
        .cout( c[i+1]   ),
        .s   ( sum[i]   ),
        .p   ( p[i]     )
    );
end

//carry bypass
assign sel = p[0] & p[1] & p[2] & p[3];
assign cout = sel ? cin : c[width];


endmodule

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

module cska #(width=16) (
    input  [width-1:0] op1,
    input  [width-1:0] op2,
    output [width-1:0] sum,
    output cout
);

wire [width>>2:0] c;
assign c[0] = 0;
assign cout = c[width>>2];

genvar i;
generate 
    for( i=0; i<width>>2; i=i+1) begin
        cska_4bit u_cska_4bit (
            .op1( op1[i*4+3:i*4] ),
            .op2( op2[i*4+3:i*4] ),
            .cin( c[i] ),
            .sum( sum[i*4+3:i*4] ),
            .cout( c[i+1])
        );
    end
endgenerate

endmodule

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

六、进位选择加法器

进位选择加法器（Carry Select Adder）由2个行波进位加法器和1个选择器构成，其中一个RCA加法器假定进位为0，另一个RCA加法器假定进位为1，其结构如下：
由4个蓝色全加器组成的RCA，假定进位输入c0=0；由4个绿色全加器组成的RCA假定进位输入c0=1。如果来自低级的进位cin=0，则选择蓝色RCA的进位c4作为该加法器的进位输出；如果来自低级的进位cin为1，则选择绿色RCA的进位的c4作为该加法器的进位输出，同时cin作为选择器选择信号，控制s0~s3的输出是来自蓝色RCA还是绿色RCA。

如下图16bit进位选择加法器，以4bit进位选择加法器为结构级联，每一级的进位可以同时经过4个全加器延迟同时生成，而选择信号在经过最低位的4bitRCA后生效，经过三个数据选择器的延迟，C16就会生成。所以相比于同等16bit的行波进位加法器，进位选择加法器极大的提高了速度，是面积换取速度设计的典型代表。红色描绘路径是关键路径。

进位选择加法器的总结：
优势：对于更大位宽加法器高位进位不取决于进位传播，速度快。但正确的输出必须等待正确的进位选择信号输出。

劣势：电路面积花费巨大，对于N比特加法器，需要几乎比RCA翻倍的全加器个数和许多多余的数据选择器。

对于N比特进位选择加法器构成的基础块，其大小可以相同，也可以不同，即其中RCA全加器个数可以不同。

基于4bitRCA模块，加入数据选择器，构成基础4bit进位选择加法器，由4bit进位选择加法器级联4级搭建成为16bit进位选择加法器，第一级进位延迟为4个全加器个1个输出选择器。

//two RCAs and Carry and sum select
genvar i;
generate
for(i=0;i<width>>2;i=i+1) begin
	if(i=0) begin
		csea_4bit u1(
			.op1(op1[3:0]),
			.op2(op2[3:0]),
			.cin(cin),
			.sum(sum_sel0[3:0]),
			cout(select[1])
		);
	end
	else begin
		csea_4bit u1(
			.op1(op1[i*4+3:i*4]),
			.op2(op2[i*4+3:i*4]),
			.cin(1'b0),
			.sum(sum_Sel0[i*4+3:i*4]),
			.cout(c_sel0[i+1])
		);
		
		csea_4bit u1(
			.op1(op1[i*4+3:i*4]),
			.op2(op2[i*4+3:i*4]),
			.cin(1'b0),
			.sum(sum_Sel1[i*4+3:i*4]),
			.cout(c_sel1[i+1])
		);
		assign select[i+1] = select[i] ? c_sel1[i+1] : c_sel0[i+1];
		assign sum[i*4+3:i*4] = select[i] ? sum_sel1[i*4+3:i*4] : sum_sel0[i*4+3:i*4];
	end
end

endgenerate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

七、进位保存加法器

进位保存加法器（Carry Save Adder，CSA），使用进位保存加法器在执行多个数加法时具有绩效的进位传播延迟，基本思想是将3个加数的和减少为2个加数的和，将进位c和和s分别计算保存，并且每bit可以独立计算c和s，所以速度极快。

如： Sum= A + B + C + D…
最直接的办法是：先将A+B计算出来，再与C计算，依次如下：
对于m个数相加，每个数n比特宽，总共需要m-1次加法。
使用进位保存加法器CSA结构则可以将门级延迟降到更低，其结构如上图（2）所示，它将3个数相加转换为2个数相加，在数的根部，加数的宽度为n+logm。

10的二进制1010；7的二进制111；12的二进制1100；列出如下算式，按列2进制数相加，满2进1，这就是普通的竖式计算，结果为11100，即29。
而进位保存加法器将进位Carry与和Sum分开计算，计算步骤如下：

（1）计算和Sum：每一列数相加，对进制数取模，此处为二进制，如（0+1+0）=1，（0+1+1）=0，（1+1+1）=1。

（2）计算进位Carry：从竖式低位开始计算，低位向高位进位，每一列的数相加对进制数取商。如下式中，（0+1+0）/ 2 = 0 … 1，（1+1+0）/ 2 = 1 … 0，忽略余数。低位向高位传递进位。

（3）如下式子中，3个数的和变成了2个数，Carry和Sum，分别是11100和00001，注意，此处Carry是11100不是1110，因为是低位往高位进位，最低位进位为0，从竖式也可以看出，对Carry和Sum相加，结果仍然是11101，即29。