基于FPGA的数字信号处理(22)--进位保存加法器(Carry Save Adder, CSA)
目录
1、拆解多个数的加法
2、进位保存加法器
3、CSA的优点和缺点
4、CSA电路的实现
文章总目录点这里:《基于FPGA的数字信号处理》专栏的导航与说明
1、拆解多个数的加法
考虑3个4bits数相加,10 + 4 + 7 = 21 的过程是这样的:
其中的红色数字是由低位向高位产生的进位,因为进位值是直接在当前位与3个加数相加,所以我们也可以把进位值拆解出来,改写成如下格式:
cout是低位产生的进位。例如,最低位的3个值是0/0/1,所以产生了向高位的进位0;次低位的3个值是1/0/1,所以产生了向高位的进位1。
sum是不考虑进位值时3个数相加的和。例如,最低位的3个值是0/0/1,所以该位的和为1;次低位的3个值是1/0/1,所以该位的和为0。
这样分别产生了进位cout = 01100,和sum=1001,二者相加后的结果就是最终3个数的和即21。这种方法相当于把3个数的加法转换成了2个数的加法。
2、进位保存加法器
上面这种将3个数的加法转换成两个数加法形式的电路就叫做 进位保存加法器(Carry Save Adder, CSA)。
当3个数中有2个或3个1时就会向高位产生进位,而和的值则和1的个数相关,奇数个1时和为1,偶数个1时和为0,所以它的真值表如下:
加数1 | 加数2 | 加数3 | 结果 | 进位 |
---|---|---|---|---|
a | b | c | sum | cout |
0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 0 |
1 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
如果你仔细点观察,就会发现上面的真值表和全加器FA的真值表是一样的,这不就说明CSA就是FA吗?只是FA的进位输入都改成了第3个加数,如下:
对于3个4bits的加法,就可以用4个CSA来组成:
可以看到这样结构的加法器的关键路径的延迟是多少呢?一个CSA电路的延迟,也就是一个FA的延迟,如下(3个门电路):
3、CSA的优点和缺点
上面说了3个数的加法,如果使用CSA电路,那么关键路径的延迟只有3个门电路,而如果使用常规的RCA(行波进位加法器)呢?考虑6个4bits数相加,其一般的电路结构如下:
如果其中的加法器是RCA,那么该电路的关键路径延迟是3级加法器的延迟。如果采用CSA电路,则其电路结构如下:
前面说了,CSA电路的延迟也就一个门电路,那么上面电路的关键路径延迟就是 3个门电路 + 最后的加法器 的延迟,假设加法器也是使用的RCA加法器,那么最终的延迟就是 1个RCA的延迟 + 3个门电路 延迟,这显然比3级RCA电路的延迟要小。可以预见的是,随着加数个数的增加,两种电路的延迟差距还会拉大。
以4比特乘法为例,其竖式计算表示如下:
ai和bi分别表示A和B的某个bit,aibi表示ai与bi相与,使用与门电路生成,aibi的值只有0和1。S表示AB相乘的结果。每一列使用半加器HA或全加器FA两两相加,其结果表示为Si,每一列每两个数产生的进位将传递至相邻高的一列参与计算。其电路结构如下(其中虚线箭头表示进位传播的路线):
根据进位传播链,可以看出该电路的关键路径如下:
红线和紫线是由于累加造成的进位链的最长路径。其中:
-
红色路径:6个FA + 2个HA
-
紫色路径:5个FA + 3个HA
使用进位保留加法器CSA可缩短该进位链的传播延时,其电路结构如下:
将RCA阵列乘法器的进位连接至斜下角的加法器,CSA结构的阵列乘法器将进位与和分别计算,不必计算该层的进位,省去了行波进位加法器进位链的依赖,只在最后一级通过RCA结构(上图绿色虚框)传递进位合并最后的结果。上图红色是CSA结构的关键路径:3个FA + 3个HA。可见,CSA结构使用相同的资源却有更优的时序性能,当加法个数变多时,这一优势将更大。
进位保存加法器的优点如下:
-
进位保存加法器将 3 个数字的加法减少到 2 个数字
-
由于进位传播级很少,与其他类型的加法器相比,它的功耗较低
-
该加法器可以一次执行三位加法
-
无论最终操作完成,下一级都会使用简单的 N 位 RCA。
进位保存加法器的缺点如下:
-
在进位保存加法的每一步中,可以立即知道加法结果,但我们不知道加法结果与给定数字相比是更小还是更大。
-
这种类型的加法器不能解决将 2 个整数相加以生成单个输出的问题。相反,它只是将 3 个整数相加并生成两个整数,因此两个整数的总和等于三个输入的总和。
-
它对于少数位操作具有高功耗和传播延迟。
4、CSA电路的实现
接下来,以6个8bits有符号数的加法为例,看如何用CSA的树形结构实现。首先要确定的是,对于单个bit的CSA来说,就是全加器,如下:
所以它的生成公式是:
s = in1 ^ in2 ^ in3; c = (in1&in2) | (in1&in3) | (in2&in2) ;
第1级有2个CSA电路,它们实现3个8bits的加法。第1个CSA的输入是3个加数a,b,c,输出是8bit的和csa11_s 跟 进位csa11_c,需要注意的是进位csa11_c在参与下级加法的时候要左移1bit(即乘2),因为它是向高位的进位。代码如下:
//第1级的第1个 CSA
assign csa11_in1 = a;
assign csa11_in2 = b;
assign csa11_in3 = c;
assign csa11_s = csa11_in1 ^ csa11_in2 ^ csa11_in3;
assign csa11_c = (csa11_in1 & csa11_in2) | (csa11_in1 & csa11_in3) | (csa11_in2 & csa11_in3);
第2个CSA的输入是3个加数d,e,f,输出是8bit的和csa12_s 跟 进位csa12_c,需要注意的是进位csa12_c在参与下级加法的时候要左移1bit(即乘2),因为它是向高位的进位。代码如下:
//第1级的第2个 CSA
assign csa12_in1 = d;
assign csa12_in2 = e;
assign csa12_in3 = f;
assign csa12_s = csa12_in1 ^ csa12_in2 ^ csa12_in3;
assign csa12_c = (csa12_in1 & csa12_in2) | (csa12_in1 & csa12_in3) | (csa12_in2 & csa12_in3);
第2级只有1个CSA,它的输入是第1级第1个CSA的两个输出和第2个CSA的一个输出,因为输入中有两个数是上级CSA产生的进位,所以需要左移1位,这样原本的8bits加法就变成了9bits加法。输出是9bit的和csa21_s 跟 进位csa21_c,需要注意的是进位csa21_c在参与下级加法的时候要左移1bit(即乘2),因为它是向高位的进位。代码如下:
//第2级的CSA
assign csa21_in1 = {csa11_c,1'b0}; //左移1比特
assign csa21_in2 = {csa11_s[7],csa11_s}; //为了适配csa21_in1,在高位补符号位
assign csa21_in3 = {csa12_s[7],csa12_s}; //为了适配csa21_in1,在高位补符号位
assign csa21_s = csa21_in1 ^ csa21_in2 ^ csa21_in3;
assign csa21_c = (csa21_in1 & csa21_in2) | (csa21_in1 & csa21_in3) | (csa21_in2 & csa21_in3);
第3级只有1个CSA,它的输入是第2级的CSA的两个输出和第1级的第2个CSA的一个输出,因为输入中有1个数是上级CSA产生的进位,所以需要左移1位,这样原本的9bits加法就变成了10bits加法。输出是10bit的和csa31_s 跟 进位csa31_c,需要注意的是进位csa31_c在参与下级加法的时候要左移1bit(即乘2),因为它是向高位的进位。代码如下:
//第3级的CSA
assign csa31_in1 = {csa21_c,1'b0}; //左移1比特
assign csa31_in2 = {csa21_s[8],csa21_s}; //为了适配csa31_in1,在高位补符号位
assign csa31_in3 = {csa12_c[7],csa12_c,1'b0}; //左移1bit,在高位补符号位
assign csa31_s = csa31_in1 ^ csa31_in2 ^ csa31_in3;
assign csa31_c = (csa31_in1 & csa31_in2) | (csa31_in1 & csa31_in3) | (csa31_in2 & csa31_in3);
经过3级CSA产生的 和csa31_s 跟 进位csa31_c就是6个数相加的结果,但是它不是一个直接表示的数值,而是拆成了两部分的冗余结果,所以我们还需要设计一个加法,来将这两个数相加,这样得到的结果最是最终的6个数的加法结果。这里仍然要注意,进位需要左移1bit(乘2),如下:
//第4级加法-------------------------------------------------------------------------------------
//把 和 + 进位,得到最终的加法结果。因为进位要左移1位,所以和也要在高位补符号位
assign sum = {csa31_c,1'b0} + {csa31_s[9],csa31_s};
综上,总体的RTL代码如下:
//CSA的生成公式:
// s = in1 ^ in2 ^ in3;
// c = (in1&in2) | (in1&in3) | (in2&in3) ;
module csa(input [7 :0] a,b,c,d,e,f,output [10:0] sum_1
);
//----------------------------------------------------------
//定义有关wire
wire [7:0] csa11_in1,csa11_in2,csa11_in3;
wire [7:0] csa12_in1,csa12_in2,csa12_in3;
wire [7:0] csa11_s,csa11_c;
wire [7:0] csa12_s,csa12_c;
//第1级的第1个 CSA
assign csa11_in1 = a;
assign csa11_in2 = b;
assign csa11_in3 = c;
assign csa11_s = csa11_in1 ^ csa11_in2 ^ csa11_in3;
assign csa11_c = (csa11_in1 & csa11_in2) | (csa11_in1 & csa11_in3) | (csa11_in2 & csa11_in3);
//第1级的第2个 CSA
assign csa12_in1 = d;
assign csa12_in2 = e;
assign csa12_in3 = f;
assign csa12_s = csa12_in1 ^ csa12_in2 ^ csa12_in3;
assign csa12_c = (csa12_in1 & csa12_in2) | (csa12_in1 & csa12_in3) | (csa12_in2 & csa12_in3);
//第2级-------------------------------------------------------------------------------------
//定义有关wire,因为上级的进位是往高位进位,所以需要左移1比特,即cout是9bits,
//为了适配,其他输入也要在高位补符号位到9bits
wire [8:0] csa21_in1,csa21_in2,csa21_in3;
wire [8:0] csa21_s,csa21_c;
//第2级的CSA
assign csa21_in1 = {csa11_c,1'b0}; //左移1比特
assign csa21_in2 = {csa11_s[7],csa11_s}; //为了适配csa21_in1,在高位补符号位
assign csa21_in3 = {csa12_s[7],csa12_s}; //为了适配csa21_in1,在高位补符号位
assign csa21_s = csa21_in1 ^ csa21_in2 ^ csa21_in3;
assign csa21_c = (csa21_in1 & csa21_in2) | (csa21_in1 & csa21_in3) | (csa21_in2 & csa21_in3);
//第3级-------------------------------------------------------------------------------------
//定义有关wire,因为上级的进位是往高位进位,所以需要左移1比特,即cout是10bits,
//为了适配,其他输入也要在高位补符号位到10bits
wire [9:0] csa31_in1,csa31_in2,csa31_in3;
wire [9:0] csa31_s,csa31_c;
//第3级的CSA
assign csa31_in1 = {csa21_c,1'b0}; //左移1比特
assign csa31_in2 = {csa21_s[8],csa21_s}; //为了适配csa31_in1,在高位补符号位
assign csa31_in3 = {csa12_c[7],csa12_c,1'b0}; //左移1bit,在高位补符号位
assign csa31_s = csa31_in1 ^ csa31_in2 ^ csa31_in3;
assign csa31_c = (csa31_in1 & csa31_in2) | (csa31_in1 & csa31_in3) | (csa31_in2 & csa31_in3);
//第4级加法-------------------------------------------------------------------------------------
//把 和 + 进位,得到最终的加法结果。因为进位要左移1位,所以和也要在高位补符号位
assign sum_1 = {csa31_c,1'b0} + {csa31_s[9],csa31_s};
endmodule
接下来写个TB测试一下电路,因为可能的输入太多了,一共有(2^8)^6 = 2^48 = 281,474,976,710,656种情况,显然不可能遍历完,所以我们采用随机测试的方式。通过生成数组随机向量来对电路进行测试:
module tb_test();reg signed [7 :0] a,b,c,d,e,f;
wire [10:0] sum;
wire sum_flag; //结果比对正确时拉高
wire signed [10:0] sum_real;
assign sum_real = a + b + c + d + e + f; //预期的正确结果
assign sum_flag = sum == sum_real; //判断电路输出是否与预期输出一致
initial begin//赋初值a = 0;b = 0;c = 0;d = 0;e = 0;f = 0;#5;repeat(1024)begin //设定向量个数//生成随机向量a = $random();b = $random();c = $random();d = $random(); e = $random(); f = $random(); #5;end#10 $stop(); //结束仿真
end//例化被测试模块
csa u_csa(.a (a ),.b (b ),.c (c ),.d (d ),.e (e ),.f (f ), .sum (sum )
);
endmodule
加法运算的预期结果也是很容易就可以找出来的,就是在TB中直接写加法就行。接着构建了向量sum_flag作为电路输出与预期结果的对比值,当二者一致时即拉高这两个信号。这样我们只要观察这个信号,即可知道电路输出是否正确。仿真结果如下:
可以看到,sum_flag都是一直拉高的,说明电路输出正确。
相关文章:

基于FPGA的数字信号处理(22)--进位保存加法器(Carry Save Adder, CSA)
目录 1、拆解多个数的加法 2、进位保存加法器 3、CSA的优点和缺点 4、CSA电路的实现 文章总目录点这里:《基于FPGA的数字信号处理》专栏的导航与说明 1、拆解多个数的加法 考虑3个4bits数相加,10 4 7 21 的过程是这样的: 其中的红色数…...

idea使用free流程,2024idea、2023idea都可以安装免费使用
1.先到官网下载,这里选择win系统的,点击下图的.exe https://www.jetbrains.com/idea/download/?sectionwindows 2.下载好后基本上就是一直点击“下一步”到直到安装好,安装好后先打开软件后关闭退出 3.下载配配套资料 链接: https://pan.ba…...

设计模式 之 —— 抽象工厂模式
目录 什么是抽象工厂模式? 定义 特点 抽象工厂模式(java代码示例) 首先定义第一个接口 实现第一个接口的类 定义第二个接口 实现第二个接口的类 * 创建抽象工厂类 创建扩展了 AbstractFactory 的工厂类 饮料工厂 食物工厂 * 创建一个…...

计量经济学(十六)--一文读懂和学会医学统计学中的四种检验方法
1. 统计学是什么? 统计学是应用数学的一个分支,主要通过利用概率论建立数学模型,收集所观察系统的数据,进行量化的分析、总结,并进而进行推断和预测,为相关决策提供依据和参考。它被广泛的应用在各门学科之上,从物理和社会科学到人文科学,甚至被用来工商业及政府的情报…...
解析 C# Dictionary 代码
entries用于存储当前每个节点的数据,其中四个字段分别表示: hashCode:key对应的hash值next:处理hash冲突,可以理解为是一个链表结构,邻接表key:存储的keyvalue:存储的value bucket…...
如何利用人工智能提升工作效率
在当今这个信息爆炸的时代,我们每天都被大量的工作任务所困扰。然而,随着人工智能技术的不断发展,我们可以通过一些智能工具来提升我们的工作效率。在这篇文章中,我将分享一些关于如何利用人工智能提升工作效率的建议。 首先&…...

Linux驱动开发—Linux内核定时器概念和使用详解,实现基于定时器的字符驱动
文章目录 内核定时器概念在Linux驱动模块中使用定时器软定时器(Soft Timers)jiffies 含义高精度定时器(High Resolution Timers) 实现倒计时字符设备驱动 内核定时器概念 在 Linux 内核中,定时器是用来管理和调度延迟…...
mysql数据库:数据库,表和列的基本概念
mysql:数据库,表和列的基本概念以及导入和导出文件 数据库的概念和用途 数据库是一个有组织的数据集合,它们被存储在计算机上以便于管理和访问。数据库的主要目的是为了存储和管理数据,同时使数据能够被高效地访问、检索和更新。数…...
Nextjs 使用 graphql,并且接入多个节点
写在前面 随着区块链技术的流行,也促进了 subgraph 工具的兴起。那么如何在前端接入 graphql 节点就成了关键,其接入方式既存在与 restful 接口相类似的方式,也有其独特接入风格。本文将介绍如何接入 graphql 以及如何应对多个 graphql 节点…...
小结——知识注入
所谓知识注入,其实不该脱离于LLM的基础工作原理,然后空谈抽象概念。 知识,也就是你问他问题,他能输出正确的回答,这只是一个简单的输出token的过程。输出得准了,就是知识,输出不准了,…...

科普文:微服务之Spring Cloud Alibaba组件Nacos一致性协议Distro+Raft概叙
一、概要 Nacos是阿里开放的一款中间件,它主要提供三种功能:持久化节点注册,非持久化节点注册和配置管理。 二、一致性协议 - AP/CP Nacos不是纯粹的AP服务,也不是纯粹的CP服务,而是两者同时支持。 这要从服务注册…...

python合并音视频-通过ffmpeg合并音视频
🌈所属专栏:【python】✨作者主页: Mr.Zwq✔️个人简介:一个正在努力学技术的Python领域创作者,擅长爬虫,逆向,全栈方向,专注基础和实战分享,欢迎咨询! 您的…...

Yolov8添加ConvNetV1和V2模块
Yolov8添加ConvNet模块 1 ConvNet系列相关内容 (1)2022 论文地址:A ConvNet for the 2020s Code Link 如下图所示,精度、效率、尺寸都很不错。 论文的摘要如下: 视觉识别的“咆哮的 20 年代”始于视觉注意力 &…...
十个常见的 Python 脚本 (详细介绍 + 代码举例)
1. 批量重命名文件 介绍: 该脚本用于批量重命名指定目录下的文件,例如将所有 ".txt" 文件重命名为 ".md" 文件。 import osdef batch_rename(directory, old_ext, new_ext):"""批量重命名文件扩展名。Args:directory: 要处理…...

【C语言】详解feof函数和ferror函数
文章目录 前言1. feof1.1 feof函数原型1.2 正确利用函数特性读写文件1.2.1 针对文本文件1.2.2 针对二进制文件 1.3 feof函数的原理1.4 feof函数实例演示 2. ferror2.1 ferror函数原型 前言 或许我们曾在网络上看过有关于feof函数,都说这个函数是检查文件是否已经读…...
ValueListenableBuilder 和 addListener 在 ChangeNotifier的区别
1、前言 ValueListenableBuilder 和 addListener 在 ChangeNotifier 中有不同的用途和用法,适用于不同的场景。它们的主要区别在于它们如何监听和响应状态变化,以及它们的用法和特性。 2、ValueListenableBuilder用法 ValueListenableBuilder 是一个 …...

ScriptEcho:AI赋能的前端代码生成神器
ScriptEcho:AI赋能的前端代码生成神器 在前端开发中,如果你总是觉得写代码太费时费力,那么 ScriptEcho 将成为你的救星。这个 AI 代码生成平台不仅能帮你省下大量时间,还能让你轻松愉快地写出生产级代码。本文将带你了解 ScriptEc…...

TypeError: ‘float’ object is not iterable 深度解析
TypeError: ‘float’ object is not iterable 深度解析与实战指南 在Python编程中,TypeError: float object is not iterable是一个常见的错误,通常发生在尝试对浮点数(float)进行迭代操作时。这个错误表明代码中存在类型使用不…...
灵茶八题 - 子序列 +w+
灵茶八题 - 子序列 w 题目描述 给你一个长为 n n n 的数组 a a a,输出它的所有非空子序列的元素和的元素和。 例如 a [ 1 , 2 , 3 ] a[1,2,3] a[1,2,3] 有七个非空子序列 [ 1 ] , [ 2 ] , [ 3 ] , [ 1 , 2 ] , [ 1 , 3 ] , [ 2 , 3 ] , [ 1 , 2 , 3 ] [1],[…...
为什么美元债务会越来越多?
美元债务规模持续膨胀,其背后原因复杂多样,可归结为以下几个主要因素: 财政赤字和刺激政策是导致美元债务增加的重要原因。美国政府长期面临财政赤字问题,支出远超收入,为弥补这一缺口,政府不得不大量发行…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)
起因 为了实现在报销流程中,发票不能重用的限制,发票上传后,希望能读出发票号,并记录发票号已用,下次不再可用于报销。 基于上面的需求,研究了OCR 的方式和读PDF的方式,实际是可行的ÿ…...
6.计算机网络核心知识点精要手册
计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法:数据与控制信息的结构或格式,如同语言中的语法规则语义:控制信息的具体含义和响应方式,规定通信双方"说什么"同步:事件执行的顺序与时序…...
接口 RESTful 中的超媒体:REST 架构的灵魂驱动
在 RESTful 架构中,** 超媒体(Hypermedia)** 是一个核心概念,它体现了 REST 的 “表述性状态转移(Representational State Transfer)” 的本质,也是区分 “真 RESTful API” 与 “伪 RESTful AP…...

英国云服务器上安装宝塔面板(BT Panel)
在英国云服务器上安装宝塔面板(BT Panel) 是完全可行的,尤其适合需要远程管理Linux服务器、快速部署网站、数据库、FTP、SSL证书等服务的用户。宝塔面板以其可视化操作界面和强大的功能广受国内用户欢迎,虽然官方主要面向中国大陆…...