一，内容介绍
加法器是数字电路中的最基础电路之一，也是CPU的核心功能之一。
在这个专栏，我会把所有我知道的数字电路的加法器相关模型都实现一遍并解释其原理。
编程使用的语言为Verilog，代码风格为强迫症系列风格。
加法器系列链接：
上一篇：
koggle-stone加法器设计
目前：brent-kung加法器设计
下一篇：
从加法器到计算单元
二，brent-kung加法器设计原理
brent-kung加法器是树形结构，由Richard P.Brent 和 H.T.Kung教授于上世纪80年代提出。设计的思想类似于超前进位加法器，但是brent和kung教授充分的考虑了开销和电路结构本身的拓扑学特性，针对性的升级了超前进位加法器的性能，使其达到了N比特加法器延迟正比于logN, 面积正比于N的效果。
下面介绍一下原理：
以下代码摘自前文：
超前进位加法器
carry[0] = p[0] + q[0]*c_i
carry[1] = p[1] + p[0]*q[1] + q[1]*q[0]*c_i
carry[2] = p[2] + p[1]*q[2] + p[0]*q[1]*q[2] + q[2]*q[1]*q[0]*c_i
carry[3] = p[3] + p[2]*q[3] + p[1]*q[2]*q[3] + p[0]*q[1]*q[2]*q[3] +
q[3]*q[2]*q[1]*q[0]*c_i
根据超前进位加法器的进位满足下列关系式：
carry[i] = a[i]*b[i] + (a[i] + b[i])*carry[i-1]
若设 p[i] = a[i] * b[i]; q[i] = a[i] + b[i]
则上式可变换为
c[0] = p[0] + q[0]*c_i (c_i = 0) = p[0]
c[1] = p[1] + p[0]*q[1]
. . .
c[i] = p[i] + q[i]*p[i-1] + ... + p[0]*q[1]*...*q[i]
定义组合运算
(p[i],q[i])O(p[i-1],q[i-1]) = (p[i] + q[i]*p[i-1], q[i]*q[i-1]);
显然，我们构造出的纯q[i]计算项就是我们超前进位计算中的最后一个带cin的子项
我们可以将输入的进位cin表示为q[i:0]序列的最初起始项；
p[i:0]的最初起始项为0；
超前进位的逻辑计算部分可以用新定义的组合运算的两个输出相加：
(p[0],q[0])O(0,cin) = {p[0],q[0]*cin} = {P(0),Q[0]}
carry[0] = p[0] + q[0]*cin;
(p[i],q[i])O(P(i-1),Q[i-1]) = {p[i] + q[i]*P(i-1),q[i]Q[i-1]}
= {P(i),Q[i]}
carry[i] = P(i) + Q(i);
我们定义的运算()O()满足交换律律，(a)O(b)O(c) = (c)O(a)O(b)
因此可以作为一个计算单元节点，形成树状结构
三，3输入的brent-kung加法器的verilog设计
根据第二章内容，我们可以先使用组合逻辑表示运算：()O()
mpdule GENE_PQ (input p_1,q_1,p_0,q_0,
output wire P,Q);
assign P = p_1 | (q_0 & p_0);
assign Q = q_1 & q_0;
endmodule
当我们设计的加法器有进位的时候，我们可以设计一个双层树形结构：
从而将顺序进行的进位运算压缩为2级进位计算，即压缩了运算时间，又压缩了总逻辑面积。
下面我们使用上面的模块实现一个三输入的brent-kung加法器
module B_KA #(parameter WIDTH = 3)(
input [WIDTH-1:0] a_i,b_i,
input c_i,
output wire [WIDTH:0] c_o
);
wire [WIDTH-1:0] q,p,carry;
wire [1:0] level_0_p,level_0_q;
wire [1:0] level_1_p,level_1_q;
assign p = a_i & b_i;
assign q = a_i | b_i;
GEN_PQ level_0_tree_u0 (
.p_1(p[0]), .q_1(q[0]), .p_0(1'b0), .q_0(c_i),
.P(level_0_p[0]), .Q(level_0_q[0])
);
GEN_PQ level_0_tree_u1 (
.p_1(p[2]), .q_1(q[2]), .p_0(p[1]), .q_0(q[1]),
.P(level_0_p[1]), .Q(level_0_q[1])
);
GEN_PQ level_1_tree_u0 (
.p_1(p[1]), .q_1(q[1]),
.p_0(level_0_p[0]), .q_0(level_0_q[0]),
.P(level_1_p[0]), .Q(level_1_q[0])
);
GEN_PQ level_1_tree_u1 (
.p_1(level_0_p[1]), .q_1(level_0_q[1]),
.p_0(level_0_p[0]), .q_0(level_0_q[0]),
.P(level_1_p[1]), .Q(level_1_q[1])
);
assign carry[0] = level_0_p[0] | level_0_q[0];
assign carry[1] = level_1_p[0] | level_1_q[0];
assign carry[2] = level_1_p[1] | level_1_q[1];
assign c_o[3] = carry[2];
assign c_o[2:0] = a_i ^ b_i ^ {carry[1:0],c_i};
endmodule
我们可以用这种方式进行无限拓展，比如7bit的brent-kung加法器
可以优化为3级树状结构，15bit的brent-kung加法器为4级树状结构 . . .
brent-kung加法器主要展示了一种在电路上无法直接减少面积增加速度的情况下，进行数学上的抽象建模并优化结构的思路。二进制可以表示一切函数关系，这是二进制的完备性，因此我们可以把一切电路问题优化为数学问题进而求解，这种一种非常重要的思路。