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

1 加法器 1.1 半加器

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

真值表：

A B O CO 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1

{ 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 全加器

考虑进位输入。

真值表：

CI A B O CO 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

{ 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=AiBi+CIi(Ai⨁Bi) 知，两种情况产生进位：

• A i B i A_iB_i AiBi=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=AiBi=Ai⨁Bi

即：

C O i = D I i + S i C I i CO_i = DI_i + S_i CI_i COi=DIi+SiCIi

将上式展开：

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+SiCIi=DIi+Si(DIi−1+Si−1CIi−1)=...=DIi+SiDIi−1+SiDIi−1DIi−2+...+SiSi−1...S1DI0+SiSi−1...S0CI0

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. ⎩⎨⎧OiO0=Si⨁COi−1=S0⨁0==(Ai⨁Bi)⨁COi−1i=1,2,3A0⨁B0

进位输出：

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

A B - DI=AB S=A+B 0 0 - 0 0 0 1 - 0 1 1 0 - 0 1 1 1 - 1 0

可以看到，只有三种取值，且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，是可以实现表达式的。

真值表：

CI DI S CO=DI+S CI 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 1

2 减

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

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

修改记录

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