超前进位加法以及对应FPGA Carry Logic进位链的理解

1 加法器 1.1 半加器

两个二进制数，不考虑进位输入。

真值表：

ABOCO0000011010101101

{ O = A ‾ B + A B ‾ = A ⨁ B C O = A B \left\{ \begin{aligned} O &=& \overline{A}B+A\overline{B}&= A \bigoplus B \\ CO &=& AB & \end{aligned} \right. ⎩⎨⎧​OCO​==​AB+ABAB​=A⨁B​

1.2 全加器

考虑进位输入。

真值表：

CIABOCO0000000110010100110110010101011100111111

{ O = A ⨁ B ⨁ C I C O = A B + C I ( A ⨁ B ) \left\{ \begin{aligned} O & = A\bigoplus B \bigoplus CI \\ CO & = AB + CI(A\bigoplus B) \end{aligned} \right. ⎩⎨⎧​OCO​=A⨁B⨁CI=AB+CI(A⨁B)​

1 超前进位原理

为什么要超前进位？ 进位信号逐级传递很耗时间，超前进位在相加运算之前就知道加法器的进位输入。

第i位的进位一定是两个加数中小于i的位数决定的。所以进位一定可以通过加数唯一确定。

由全加器进位 C O i = A i B i + C I i ( A i ⨁ B i ) CO_i = A_iB_i + CI_i(A_i \bigoplus B_i) COi​=Ai​Bi​+CIi​(Ai​⨁Bi​) 知，两种情况产生进位：

• A i B i A_iB_i Ai​Bi​=1
• A i ⨁ B i A_i \bigoplus B_i Ai​⨁Bi​=1 以及 CI_i=1

所以这里的+是逻辑

令： { 进 位 生 成 ( g e n e r a t e ) 函 数 D I i = A i B i 进 位 传 送 ( p r o p a g a t e ) 函 数 S i = A i ⨁ B i \left\{ \begin{aligned} 进位生成(generate)函数 DI_i &= A_iB_i \\ 进位传送(propagate)函数 S_i &= A_i \bigoplus B_i \end{aligned} \right. ⎩⎨⎧​进位生成(generate)函数DIi​进位传送(propagate)函数Si​​=Ai​Bi​=Ai​⨁Bi​​

即：

C O i = D I i + S i C I i CO_i = DI_i + S_i CI_i COi​=DIi​+Si​CIi​

将上式展开：

C O i = D I i + S i C I i = D I i + S i ( D I i − 1 + S i − 1 C I i − 1 ) = . . . = D I i + S i D I i − 1 + S i D I i − 1 D I i − 2 + . . . + S i S i − 1 . . . S 1 D I 0 + S i S i − 1 . . . S 0 C I 0 \begin{aligned} CO_i &= DI_i + S_i CI_i \\ &= DI_i + S_i(DI_{i-1} + S_{i-1} CI_{i-1}) \\ &= ...\\ &= DI_i + S_iDI_{i-1} + S_iDI_{i-1}DI_{i-2} + ... +S_iS_{i-1}...S_1DI0 + S_iS_{i-1}...S_0CI_0 \\ \end{aligned} COi​​=DIi​+Si​CIi​=DIi​+Si​(DIi−1​+Si−1​CIi−1​)=...=DIi​+Si​DIi−1​+Si​DIi−1​DIi−2​+...+Si​Si−1​...S1​DI0+Si​Si−1​...S0​CI0​​

2 Xilinx fpga的超前进位逻辑

7系列FPGA的CLB有两个分离的进位链（每个slice各一个），进位链可级联形成更宽的加减逻辑。

进位链向上运行，每各slice高度为4位。对于每一位，都有一个进位数据选择器(MUXCY)和一个专用的异或门，用于用选定的进位位加/减操作数。专用进位路径和进位数据选择器(MUXCY)也可用于级联函数生成器，以实现更广泛的逻辑函数。

Device视图的SLICEL：

SLICEL示意图：

Carry Logic示意图:

输入：

• 进位链的DI0-DI3输入对应进位生成函数 D I i DI_i DIi​。

  • 来源于LUT6的O6输出

• S0-S4输入对应进位传送函数 S i S_i Si​

  • 来源于LUT6的O5输出
  • 或来源于DILICE的BYSADI输入

• CYINIT

  • 进位链的第一位输入
    • 0 ：代表加
    • 1 ：代表减
    • AX：动态控制

• CIN:

  • 级联中的上一级输入

输出：

• O0-O3：
  • 运算结果
• CO0-CO3:
  • 每位的进位输出
  • 级联中本级的输出

1 加

假设这是第一级，则进位链的第一位由CYINIT输入，当实现加法时，CYINIT = 0。

FSDIA实现超前进位的时候：使用前级的LUT6实现进位生成函数和进位传送函数

结果输出： { O i = S i ⨁ C O i − 1 = ( A i ⨁ B i ) ⨁ C O i − 1 i = 1 , 2 , 3 O 0 = S 0 ⨁ 0 = A 0 ⨁ B 0 \left\{ \begin{aligned} O_i &= S_i \bigoplus CO_{i-1} &= &(A_i \bigoplus B_i)\bigoplus CO_{i-1}\quad i=1,2,3 \\ O_0 &= S_0 \bigoplus 0 &= &A_0 \bigoplus B_0 \\ \end{aligned} \right. ⎩⎨⎧​Oi​O0​​=Si​⨁COi−1​=S0​⨁0​==​(Ai​⨁Bi​)⨁COi−1​i=1,2,3A0​⨁B0​​

进位输出：

首先，看看DI和S所有的情况：

AB-DI=ABS=A+B00-0001-0110-0111-10

可以看到，只有三种取值，且DI与S不会同时取1。

所以，根据公式 C O = D I + S C I CO=DI+S CI CO=DI+SCI。可将S作为选择信号： { C O = D I , S = 0 C O = C I , S = 1 D I 与 C I 不 同 时 取 1 \left\{ \begin{aligned} CO = DI \quad,S=0 \\ CO = CI \quad,S=1 \\ DI与CI不同时取1 \end{aligned} \right. ⎩⎪⎨⎪⎧​CO=DI,S=0CO=CI,S=1DI与CI不同时取1​ 当S=0，选择DI输出，当S=1，选择CI输出。因为DI与S不会同时取1，是可以实现表达式的。

真值表：

CIDISCO=DI+S CI00 0000 1001 0110 0010 1111 01

2 减

当实现减法时，运算为补码加。

CYINIT = 1，运算前逻辑取反之后加一，即取补码。

修改记录

20220322修订，更改了 + 映射成 | 或者 ⨁ \bigoplus ⨁ 模糊的问题。