【HDL系列】进位保存加法器原理与设计_进位保留加法器-程序员宅基地
技术标签： CSA 进位保存加法器 CSA树形结构 纸上谈芯 3:2 Compressor verilog
目录
一、进位保存加法器
进位保存加法器（Carry Save Adder，CSA）终于开启了读者见面会。在之前介绍的众多加法器的缩写中，CSA众多。比较广为人知的CSA可能是进位保存加法器，所以它是怎样的存在呢？
使用进位保存加法器在执行多个数加法时具有极小的进位传播延迟，它的基本思想即将3个加数的和减少为2个加数的和，将进位c和和s分别计算保存，并且每比特可以独立计算c和s，所以速度极快。
在许多加法计算中，一般有2个以上，或者更多的加数。
如： Sum = A + B + C + D + E + …
最直接的办法是：先将A+B结果计算出来，再与C计算，依次进行，如下图（1）。
对于m个数相加，每个数n比特宽，总共需要m-1次加法。假如使用超前进位加法器LCA的话，直接相加法总共需要的门延迟为O(lg n)；如果使用树形加法器（后期会介绍），门延迟将变为O（lg m * lg n）。
使用进位保存加法器CSA结构则可以将门延迟降到更低，其结构如上图（2）所示，它将3个数相加转换为2个数相加，在树的根部，加数宽度变为O（n+log m），因此如果最后一个加法器用LCA的话，则门延迟为O(lg(n+lg m))。
以（10 + 7 + 12 = 29）为例看看进位保存加法器是啥高级操作：
10的二进制1010；7的二进制111；12的二进制1100；列出如下算式，按列2进制数相加，满2进1，这就是普通的竖式计算，结果为11100，即29。
而进位保存加法器将进位Carry与和Sum分开计算，计算步骤如下：
（1）计算和Sum：每一列数相加，对进制数取模，此处为二进制，如（0+1+0）=1，（0+1+1）=0，（1+1+1）=1。
（2）计算进位Carry：从竖式低位开始计算，低位向高位进位，每一列的数相加对进制数取商。如下式中，（0+1+0）/ 2 = 0 … 1，（1+1+0）/ 2 = 1 … 0，忽略余数。低位向高位传递进位。
（3）如下式子中，3个数的和变成了2个数，Carry和Sum，分别是11100和00001，注意，此处Carry是11100不是1110，因为是低位往高位进位，最低位进位为0，从竖式也可以看出，对Carry和Sum相加，结果仍然是11101，即29。
二、3:2 Compressors
3:2 Compressor是进位保存加法器的一种，它将三个数的和转换为2个数的和，基本行为与第一部分描述的一致，根据算式的行为，列出其真值表如下：
定睛一看，3:2 Compressor就是一个全加器啊！
所以只要将全加器经过如下的变换，就可以将全加器FA生成进位保存加法器CSA，简直换汤不换药，重新包装了一下。
三个32比特的数x，y，z相加，其CSA结构如下：
在使用verilog设计一个算式如Sum = A + B + C + D；则可以设计一个全加器，由全加器组成N比特的CSA结构，将多个数合并，经过两级CSA，最后将进位C[N-1:0]与和Sum[N-1:0]通过一个加法器相加，注意进位传入到任何模块中时，需要将C[N-1:0]乘以2，因为这是它合并后真正的数。
欢迎批评指正，更多阅读，关注“纸上谈芯”，不定期更新，共同学习:
智能推荐
wxWidgets：常用表达式_wxwidget 正则表达式 非数字字符-程序员宅基地
文章浏览阅读282次。wxWidgets：常用表达式wxWidgets：常用表达式不同风味的正则表达式转义Escapes元语法匹配限制和兼容性基本正则表达式正则表达式字符名称wxWidgets：常用表达式一个正则表达式描述字符的字符串。这是一种匹配某些字符串但不匹配其他字符串的模式。不同风味的正则表达式POSIX 定义的正则表达式 (RE) 有两种形式：扩展正则表达式(ERE) 和基本正则表达式(BRE)。ERE 大致是传统egrep 的那些，而 BRE 大致是传统ed 的那些。这个实现增加了第三种风格：高级正则表达式_wxwidget 正则表达式 非数字字符
Java中普通for循环和增强for循环的对比_for循环10万数据需要时间-程序员宅基地
文章浏览阅读3.4k次，点赞5次，收藏11次。Java中普通for循环和增强for循环的对比_for循环10万数据需要时间
学习PCB设计前的知识扫盲_pcb端子设计基础知识-程序员宅基地
文章浏览阅读2.7k次，点赞13次，收藏97次。0.工厂制作PCB线路板流程1.PCB的结构铜层阻焊丝印本质(PCB画电路板到底在画什么)基础工艺指标2.PCB图中的元素元素布局布线叠层设计3.PCB的设计依据原理图原理图元件库4.PCB的设计流程——总结_pcb端子设计基础知识
Python读取Excel内容；将读取的数据转换为list类型便于切片处理；列表的操作方法；pandas处理DataFrame类型数据；pandas操作；Python几种取整的方法_pandas excel list-程序员宅基地
文章浏览阅读4.5k次，点赞5次，收藏19次。Python读取Excel内容；将读取的数据转换为list类型便于切片处理；列表的操作方法；pandas处理DataFrame类型数据_pandas excel list
nginx日志与监控，日志分析_nginx的日志分析-程序员宅基地
文章浏览阅读4.6k次。在分析服务器运行情况和业务数据时，nginx日志是非常可靠的数据来源，而掌握常用的nginx日志分析命令的应用技巧则有着事半功倍的作用，可以快速进行定位和统计。下面是自己在分析nginx日志时常用命令的一些总结。1.利用grep ,wc命令统计某个请求或字符串出现的次数比如我要统计GET /task/showContent接口在某天的调用次数，则可以使用如下命令： cat _nginx的日志分析
ECharts--中国地图（无敌详细）_echarts中国地图-程序员宅基地
文章浏览阅读5.4w次，点赞64次，收藏262次。使用Echarts绘制中国地图，其中地图点信息由JSON文件编写，前端html直接从JSON文件中读取地区数据，渲染到前端即可。详细介绍用到的各个功能！代码直接复制运行即可！_echarts中国地图
随便推点
JVM常用调优参数 ——JVM篇_jvm调优-程序员宅基地
文章浏览阅读1.9w次，点赞50次，收藏366次。JVM常用性能调优参数详解 在学习完整个JVM内容后，其实目标不仅是学习了解整个JVM的基础知识，而是为了进行JVM性能调优做准备，所以以下的内容就是来说说JVM性能调优的知识。一、性能调优 性能调优包含多个层次，比如：架构调优、代码调优、JVM调优、数据库调优、操作系统调优等等。 架构调优和代码调优是JVM调优的基础，其中架构调优是对系统影响最大的。性能调优基本上按照以下步骤进行：明确优化目标发现性能瓶颈性能调优通过监控及数据统计工具获得数据确认是否达到目标二、何时进_jvm调优
三级嵌入式准备（二）_八个gpio引脚最多构成几个按键-程序员宅基地
文章浏览阅读435次，点赞3次，收藏7次。转载来源为https://blog.csdn.net/ReCclay/article/details/79439686 1、嵌入式系统的CPU主要使用的有DSP、ARM以及FPGA。2、DSP适用于数字信号处理的微处理器支持单指令多数据（DIMD）并行处理的指令显著提高音频、视频等数字信号的数据处理效率3、片上系统SOC已成为嵌入式处理器芯片的主流发展趋势它是..._八个gpio引脚最多构成几个按键
OpenStack的容器服务体验-程序员宅基地
文章浏览阅读70次。magnum 是用于 OpenStack 的容器服务。它有以下特点：抽象的容器、节点、服务等集成了用于容器技术的Kubernetes和Docker集成了多租户安全的 Keystone继承了k8s多租户网络安全的 Neutron环境准备在VMware Workstations建台虚拟机，Ubuntu 14.04 LTS，..._openstack 安装好没有容器服务
HDU - 2209 翻纸牌游戏(贪心)_hdu 2209-程序员宅基地
文章浏览阅读420次。 HDU - 2209 翻纸牌游戏 当前的这张牌是否翻转取决于它的前一张牌是否朝上，如果朝上，不翻转，朝下，则翻转，这是贪心的思想，但是，对于第一张牌来说，它的前面没有牌了，所以可以翻转，也可以不翻转，分两种情况来判断，参考的别人的代码 #include<stdio.h>#include<algorithm>#include<string.h>u..._hdu 2209
mysql异常代码c0000005_win7系统因0xc0000005错误导致应用程序无法正常启动的解决方法...-程序员宅基地
文章浏览阅读2k次。很多小伙伴都遇到过win7系统因0xc0000005错误导致应用程序无法正常启动的困惑吧，一些朋友看过网上零散的win7系统因0xc0000005错误导致应用程序无法正常启动的处理方法，并没有完完全全明白win7系统因0xc0000005错误导致应用程序无法正常启动是如何解决的，今天小编准备了简单的解决办法，只需要按照1、右键点击要运行的软件或游戏，在右键菜单中选择“兼容性疑难解答”； 2、让系..._mysql 0xc0000005
UNIX环境高级编程_标准io创建空头文件-程序员宅基地
文章浏览阅读492次。unix环境高级编程笔记_标准io创建空头文件