Verilog编程-11. 加法器和减法器设计

1. 背景

加法器分为半加器（Half Adder, HA）、全加器（Full Adder, FA）、行波进位加法器（Ripple Carry Adder, RCA）、超前进位加法器（Lookahead Carry Adder, LCA）和进位保存加法器（Carry Save Adder, CSA）。

1.1 半加器和全加器

半加器只有输入a和b，以及输出sum和进位cout，均为单比特信号，没有输入进位cin；全加器不同于半加器的地方是，全加器带有输入进位cin，且均为单比特信号。半加器和全加器的行为级和数据流级Verilog描述如下所示：

// 半加器，行为级描述
{cout, sum} = a + b;
// 半加器，数据流级描述
sum = a ^ b;
cout = a & b;

// 全加器，行为级描述
{cout, sum} = a + b + cin;
// 全加器，数据流级描述
sum = a ^ b ^ cin;
cout = (a & b) | (a ^ b) & cin;
// 或者为以下描述
cout = (a & b) | (a & cin) | (b & cin)

这里放半加器和全加器的门级电路图，在./image/blog/adder文件夹中

1.2 行波进位加法器

N-bit加法器可以由N个1-bit加法器串联而成，每一bit的输出进位cout作为下一bit的输入进位cin，这种加法器结构称为行波进位加法器。对于更宽bit的加法器，行波进位加法器关键路径太长，限制了加法器的性能，对于高速处理器是一个极大的瓶颈。

1.3 超前进位加法器

RCA的缺点是第k位的输入进位Ckin必须依赖于前一级的输出进位Ckout，而超前进位加法器的思路就是并行计算进位Ckin，以达到缩短关键路径，提升性能的目的。

1.4 进位保存加法器

进位保存加法器在执行多个数加法时具有极小的进位传播延时，它的基本思想是将3个加数的和减少为2个加数的和，将进位cout和sum分别计算保存，并且每bit可以独立计算cout以及sum，所以速度极快。CSA在Wallace树乘法器中有重要应用。进位保存加法器又叫3-2压缩器(3:2 Compressor)，即输入三个数据，输出两个数据（sum以及cout），其基本结构就是一个全加器。同样的还有4-2压缩器，4-2压缩器的效率是优于3-2压缩器的，但是4-2压缩器的内部的逻辑结构比3-2压缩器复杂，这也是用面积换性能的体现。CSA加法器结构由全加器组成，只是将sum以及cout分别保存，所以叫进位保存加法器，由CSA这种形式组成的加法器，叫Wallace树，并且如上所述，除了3-2压缩，还有4-2压缩。CSA适用于多个数相加的情况，例如在乘法中，有多个部分积相加，这种情况就很适合使用CSA。在多个数相加的情形下，CSA的效率是高于普通的加法器的。

3:2 Compressor是进位保存加法器的一种，将3个数的和转换为2个数的和，通过其真值表可以看出，1bit的3:2 Compressor就是一个1bit全加器，可以将全加器FA直接变成进位保存加法器CSA。但是在多bit的情况下，全加器低位的进位需要传递到高位参与运算，也就产生了进位链，造成了延迟；而对于多bit 3:2 Compressor来说，没有进位链，所有的进位都是独立的，不需要参加高位的运算，这就是为什么CSA要比FA要快的原因。

这里放单比特FA和CSA示意图

这里放多bit CSA的示意图

加法器还有更多的基本设计方式，例如进位旁路加法器(Carry Skip Adder, CSA)、进位选择加法器(Carry Select Adder, CSA)等，详情可见硬件加法器原理与设计小结，本篇文章只介绍RCA、LCA和CSA这S三种设计方法。

加法器和减法器的硬件结构可以混合使用，并且分为行波进位，超前进位和进位保存三种方式。加法器和减法器设计的难点之一是减法对于进位的处理和加法有些不同，在加法中属于进位，而在减法中则属于向高位的借位，这一点在后续有具体的细节展现。设计的难点之二是输入为有符号数时对于结果的判断，这一点可参照这篇文章 Verilog编程-4中对于溢出的描述。

2. 设计思路

RCA中门延迟最长的是进位的传递，其串联的方式决定了其进位传递的缓慢，这种较长的关键路径，限制了加法器的性能。

LCA通常采用多个小规模的LCA串联拼接而成，因为采用完全的超前进位，例如32bit的LCA，根据公式则需要32输入的与门和或门了，而这样的门电路扇入扇出过大，变化信号过多，很容易产生毛刺，同时电路的面积与复杂度会很大，不利于设计。通常情况下会设计4-bit LCA，然后通过串联来实现宽bit的加法。

3. 代码

4. 仿真结果

5. 参考

减法器原理和设计

半加器、全加器和行波进位加法器原理和设计

超前进位加法器原理和设计

进位保存加法器原理和设计