cisen
commented
2 years ago 从底层结构开始学习FPGA----进位链CARRY4
https://wuzhikai.blog.csdn.net/article/details/125156420
一、半加器与全加器
FPGA底层的CARRY4本质上就是用来实现最基本的加、减法运算的，在了解CARRY4之前，我们需要对1bit以及多bit的二进制加法及其FPGA实现做一个了解。
1bit的二进制加法可以分为两类：无底层进位的半加器与有底层进位的全加器。减法运算本质上仍是一种加法运算，在二进制电路中采用加上负数的补码实现。
1.1、半加器
半加器电路是指对两个输入数据位相加，输出一个结果位和进位，没有进位输入的加法器电路。
半加器有两个1位2进制数输入，输出1个进位、1个结果位。真值表如下：
| A | B | Carry | Sum |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
从真值表，我们可以推断出其实现：
结果 S = A ^ B； 进位 C = AB；
映射到电路就是一个2输入异或门加一个2输入与门：
1.2、全加器
全加器是在半加器的基础上的升级版，除了加数和被加数加和外还要加上前上一级传进来的进位信号。全加器真值表为：
| A | B | Cin | Cout | Sum |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
从真值表，我们可以推断出其实现：
结果 S= A ^ B ^ Cin； 进位 C = (A&B) | (Cin & (A^B) ； 映射到电路的实现：
比半加器要复杂一些，构成为2个异或门+2个与门+1个或门。
二、多bit加法（以4bit为例）
有了单个bit的二进制加法电路（全加器）后，我们就可以通过级联来实现多bit的二进制加法了，但是多个全加器如何级联则是一个需要考虑的问题。
2.1、串行（行波）进位加法器（RCA）
进行两个4bit的二进制数相加，就要用到4个全加器。那么在进行加法运算时，首先准备好的是1号全加器的3个input。而2、3、4号全加器的Cin全部来自前一个全加器的Cout，只有等到1号全加器运算完毕，2、3、4号全加器才能依次进行进位运算，最终得到结果。 这样进位输出，像波浪一样，依次从低位到高位传递， 最终产生结果的加法器，也因此得名为行波进位加法器（Ripple-Carry Adder，RCA）。
RCA的优点是电路布局简单，设计方便， 我们只要设计好了全加器，连接起来就构成了多位的加法器。 但是缺点也很明显，也就是高位的运算必须等待低位的运算完成， 这样造成了整个加法器的延迟时间很长。将4bit的RCA内部结构全部打开，就得到了如图所示的4-bit RCA的门电路图。要对一个电路的性能进行分析，我们就要找出其中的最长路径。 也就是找出所有的从输入到输出的电路连接中，经过的门数最多的那一条，也称为关键路径。
我们来做一个简单的分析， 对于最低位的全加器，它在A、B和Cin都已经准备好。其实，输入信号进入到这块电路之后，在连接线上传递需要花时间。 称为线延迟，而经过这样的门，也需要花时间，称为门延迟。
对于第一个全加器，它的最长路径，是红色线标记的那条。
那么，假设经过一个门电路的延迟时间为T，那么经过4个全加器所需要的总延迟时间就是：2T x 4 + T(第一个全加器产生3个T) = 9T。所以推出，经过n个全加器所产生的总延迟时间为2T x n + T = (2n+1)T。从此可以看出来RCA电路的最大问题就是组合逻辑延迟太高。
2.2、超前进位加法器（Carry-Lookahead Adder，CLA）
用前一个全加器的参数来表示后面的进位输出（Cout），即：
由此来表示4个全加器的进位输出为：
最终需要得到的是C4，经过换算，C4=G3+P3·G2+P3·P2·G1+P3·P2·P1·G0+P3·P2·P1·P0·C0，而这些参数，全部已知！并不需要前一个全加器运算输出，就可以提前计算进位输出， 用这样的方法实现了加法器就被称为超前进位加法器（Carry-Lookahead Adder，CLA）。
重新绘制CLA的布线方式：
CLA的方式获得了较短的组合逻辑延迟，但是电路的面积却大了非常的多，这就是FPGA设计中非常经典的“面积换时间”。
同时需要注意的是，上面的门电路实现仅仅是求得C4，而如果要同时求C3 C2 C1的话，电路面积还会增大许多。
所以在FPGA内部会是使用CLA这种方式来实现加法器吗？答案是也不是。
三、进位链CARRY4
Xilinx FPGA底层的加法器（进位链）CARRY4是一种超前进位的加法器，但是为了面积与普适性其实现原理与上述的CLA电路还是有一点区别。
每个SLICE中都有1个（每个CLB则有2个）CARRY4用来实现进位逻辑，不同的进位链可级联以形成更宽的加/减逻辑：
3.1、端口
先来看下CARRY的整体构成及其端口：
端口含义：
CI：是上一个 CARRY4 的进位输出，位宽为1；可级联构成更大的加法逻辑 CYINT：是进位的初始化值，位宽为1；0为加法，1为减法 DI：是数据的输入（可以是两个加数的任意一个，至于为什么后面再解释），位宽为4； SI：是两个加数的异或结果，位宽为4； O：是加法结果输出，位宽为4； CO：是进位输出，位宽为4；（这里的进位代表每一位加法的进位，比如CO0代表最低位的加法进位，而CO3则代表最高位的加法进位，这样就可以同样实现小于4bit的加减法）
3.2、内部组成 仅仅只看端口无法理解CARRY4是如何实现进位算法的，接下来看下内部的具体实现：
从上图可以看到，实际上CARRY4是分为相同的4个部分的，每个部分都用MUX2加异或门来实现进位逻辑。
这里需要说明的是，上述MUX2的实现逻辑均为：S = 0，结果为左侧输入； S = 1，结果为则右侧输入。
一步一步来看：
（一：O0、CO0）
最底层的结果O0等于S0异或CIN，S0则为两个加数的异或，也就是O0 = A0 ^ B0^ CIN。
若S0 = 0，则意味着两个加数相等，即00或11，此时O0的结果与CIN一致。若S0 = 1，则意味着两个加数不相等，即01或10，此时O0的结果与CIN相反。
当S0 = 0，则意味着两个加数相等，即00或11，此时MUX2选择DI0作为进位CO0的结果。若DI0为0，则意味着A0，B0，CO0都为0；若DI0为1，则意味着A0，B0，CO0都为1；
当S0 = 1，则意味着两个加数不相等，即01或10，此时MUX2选择CIN作为进位CO0的结果。若CIN为0，则意味着A0，B0，CIN为100，此时不需要进位，与CIN相等；若CIN为1，则意味着A0，B0，CIN为101，此时需要进位，仍与CIN相等；
省略（O1、CO1），（O2、CO2）的推断过程······
（四：O3、CO3）
结果O3等于S3异或CO2，S3则为两个加数的异或，也就是O3 = A3 ^ B3 ^ CO2。
若S3 = 0，则意味着两个加数相等，即00或11，此时O3的结果与CO2一致。
若S3 = 1，则意味着两个加数不相等，即01或10，此时O3的结果与CO2相反。 当S3 = 0，则意味着两个加数相等，即00或11，此时MUX2选择DI3作为进位CO3的结果。若DI3为0，则意味着A3，B3，CO3都为0；若DI3为1，则意味着A3，B3，CO3都为1；
当S3 = 1，则意味着两个加数不相等，即01或10，此时MUX2选择CO2作为进位CO3的结果。若CO2为0，则意味着A3，B3，CO2为100，此时不需要进位，与CO2相等；若CO2为1，则意味着A3，B3，CO2为101，此时需要进位，仍与CO2相等；
这样的结构看起来很像行波进位加法器RCA，最高层的进位需要从最底层一步步往上传递，实则不然。
可以举例，假如两个加数的最高位A3，B3为00或11，即S3=0时，此时的CO3直接等于DI3（因为00+0不进位和11+1要进位），也就是A3或者说B3（相等的），此时就不需要从下一层传递进位信号过来参与运算，这一情况出现的概率为50%。而另外50%的情况A3,B3不相等，即01或10（S3=1）时，此时的CO3取决于CO2（因为10或01+1进位；+0则不进位）。在次高位到最低位的情况均与上述一致。 也就是说只有在最极端的情况下，才需要在每一位考虑来自下一级的进位（如1010+0101，也就是每一位的两个加数均不一致），此时的进位组合逻辑是可能存在的最长组合逻辑路径。但是这种架构和上述的超前进位加法器比起来，其面积减少了非常多，仅使用了4个MUX2 + 4个XOR门，且这8个门电路均位于CLB的同一个SLICE里边，不同与传统的门电路的延迟，其线延迟可以控制得非常小。
3.3、推断
为什么说其本质还是超前进位加法器，我们可以从其逻辑式入手进行推断：
对于CARRY4，S=a ^ b端口D可以任选a、b输入当中的一个，如选择b
输出端：那么O端即表示输出端：O = S ^ cin = a ^ b ^ cin
进位端： CO=(a^b)'b +(a^b)cin //多路复用器：y=s’b+scin =(a’b+ab’)‘b+(a^b)cin =(a’b)’(ab’)‘b+(a^b)cin =(a+b’)(a’+b)b+(a^b)cin =(ab+b’b)(a’+b)+(a^b)cin =ab(a’+b)+(a^b)cin =(a^b)cin+ab
假设有十进制的4bit数 4 + 8 =12，则二进制为 0100 + 1000 = 1100，用CARRY4的端口：
异或S = A ^ B = 0100 ^ 1000 = 1100 进位：CO0 = DI0 = B0 = 0；CO1 = DI1 = B1 = 0；CO2 = CO1 = 0；CO3= CO2 = 0，所以进位CO= 0000，与实际相符 位结果：O0 = S0 ^ CIN = 0 ^ 0=0；O1 = S1 ^ CO0 = 0 ^ 0=0；O2 = S2 ^ CO1 = 1 ^ 0=1；O3 = S3 ^ CO2 = 1 ^ 0=1；所以位结果O = 1100，也与实际相符
3.4、测试实例
接下来写个简单的实例测试一下（2个8位数相加）：
module test(
input [7:0] A,
input [7:0] B,
output [7:0] S
);
assign S = A + B;
endmodule 由于是8bit的加法，所以其综合结果是2个CARRY4级联组成。
`timescale 1ns / 1ns
module tb_test();
reg [7:0] A;
reg [7:0] B;
wire [7:0] S;
//例化test模块
test test_inst(
.A (A),
.B (B),
.S (S)
);
initial begin
A =0;
B =0;
#200 $finish;
end
always #10 begin
A ={$random }%64;
B ={$random }%64;
end
endmodule测试结果不说了，一目了然：
半加器
半加器（half adder）的功能是将两个一位二进制数相加。它具有两个输入和两个输出，两个输入分别为 A、B，代表着等待相加的两个数，输出为 Sum、Carry；Sum代表加的结果，Carry 代表进位逻辑；
半加器的真值表为：
加法器电路主要的构成元件由 XOR（异或门）构成，XOR 的真值表为：
所以一个半加器可以由一个异或门和一个与门组成：
半加器的简化图为：
全加器
全加器（full adder）将两个一位二进制数相加，并根据接收到的低位进位信号，输出和、进位输出。全加器的三个输入信号为两个加数 A、B 和低位进位 Cin
全加器真值表为：
全加器的逻辑电路为：
全加器的简化图为：
https://mp.weixin.qq.com/s?__biz=MzU4ODY5ODU5Ng==&mid=2247484814&idx=2&sn=50e88aa4d31f565e5fb79c68c2e8b184&chksm=fdd98305caae0a13844b203cff070746ce4207095b8506307ef025cb1ee5fc63d8a878589877&mpshare=1&scene=1&srcid=&sharer_sharetime=1593652247921&sharer_shareid=7c50f8876d9a3e936cca6717fa56a0fb&key=835f76b9f6281b48b82072c29cd6ebe45dc90afaef3c373988ec9bc95387cefbecfd8d7a3b330e09d90737ffbdae2667b5f3e9f2f73dc854de581e5afba38b18121d5da9675cf8ce50ea46fd3e921e59&ascene=1&uin=MTk0NTA2NDc2OA%3D%3D&devicetype=Windows+10+x64&version=62090523&lang=zh_CN&exportkey=AbGO3RPltJLDtldPLJ89RNE%3D&pass_ticket=ylPvJp%2BB87C9q0KMhjIu5PYH4UZdX31SvETumdZg%2BXsF%2FOM23SxRPIjgrFQcauAZ
影响FPGA时序的进位链（Carry Chain）， 你用对了么？
在FPGA中我们写的最多的逻辑是什么？相信对大部分朋友来说应该都是计数器，从最初板卡的测试时我们会闪烁LED，到复杂的AXI总线中产生地址或者last等信号，都会用到计数器，使用计数器那必然会用到进位链。
可能很多刚开始接触FPGA的同学没听过进位链，也就是Carry Chain，我们这里再回顾一下。FPGA的三个主要资源为：
可编程I/O资源 布线资源 其中，CLB在FPGA中最为丰富，在7系列的FPGA中，一个CLB中有两个Slice，Slice中包含4个LUT6、3个数据选择器MUX、两个独立进位链（Carry4，Ultrascale是CARRY8）和8个触发器。
首先，我们来看下Carry Chain的结构原理，其输入输出接口如下：
其中，
Carry4的内部结构如下图所示：
这里我们要先解释一下FPGA中利用Carry Chain实现加法的原理，比如两个加数分别为a = 4'b1000和b=4'b1100，其结果应该是8+12=20。
加法最终的输出结果为：{CO3,O3,O2,O1,O0} = 5'b10100 = 20。进位输出在CARRY4的内部也使用到了，因此有4个bit的进位输出CO，但输出给下一级的只是CO[3]。
再来看完下面的例子就更清晰了。Example的代码如下：
综合之后的电路如下：
在本程序中，加数为din_a和din_b，图中
1表示CARRY4的进位输出到下一级的进入输入； 2表示输入的一个加数din_a（换成din_b也是可以的）； 3表示第二级输入的DI端口，因为第二级CARRY是通过第一级的进位输出进行累加，因此该接口为0； 4表示输入两个加数的异或结果。 可以看出，当进行两个8bit的数据进行加法操作时，会使用两个CARRY4级联，那如果是对48位的数据进行相加，那就会用到12个的CARRY4的级联，这样明显就会使逻辑延迟过大，很容易造成时序不收敛。(这里需要注意的是，在Vivado的默认设置下，如果进行的是12bit以下的数据加1'b1的操作，那么Vivado综合的结果并不会使用CARYY4，而是使用LUT来实现加法器)。
那如何解决这种问题呢？我们可以把加法操作进行拆解，比如拆解成3个16bit的计数器，那这样就会只有4个CARRY4的级联，时序情况就好了很多。
对比程序如下：
打开综合后的schematic后可以发现，在dout2的输出中，每4个CARRY4后都会有一级的触发器，这样时序就会好很多，但这样做的代价是LUT会增加。
对于不同的位宽的数据，我们后面会给出一个通用的Verilog代码，朋友们可以关注github的Rex1168账户，过几天我们会把程序放到GitHub上，供大家免费下载。