当前位置: 首页 > news >正文

基于FPGA的数字信号处理(22)--进位保存加法器(Carry Save Adder, CSA)

目录

1、拆解多个数的加法

2、进位保存加法器

3、CSA的优点和缺点

4、CSA电路的实现


         文章总目录点这里:《基于FPGA的数字信号处理》专栏的导航与说明


1、拆解多个数的加法

        考虑3个4bits数相加,10 + 4 + 7 = 21 的过程是这样的:

image-20240427191114236

        其中的红色数字是由低位向高位产生的进位,因为进位值是直接在当前位与3个加数相加,所以我们也可以把进位值拆解出来,改写成如下格式:

image-20240427191349219

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结果进位
abcsumcout
00000
01010
10010
11001
00110
01101
10101
11111

        如果你仔细点观察,就会发现上面的真值表和全加器FA的真值表是一样的,这不就说明CSA就是FA吗?只是FA的进位输入都改成了第3个加数,如下:

image-20240427194749587

        对于3个4bits的加法,就可以用4个CSA来组成:

image-20240427194812026

        可以看到这样结构的加法器的关键路径的延迟是多少呢?一个CSA电路的延迟,也就是一个FA的延迟,如下(3个门电路):

image-20240427194924330

3、CSA的优点和缺点

        上面说了3个数的加法,如果使用CSA电路,那么关键路径的延迟只有3个门电路,而如果使用常规的RCA(行波进位加法器)呢?考虑6个4bits数相加,其一般的电路结构如下:

image-20240427204823137

        如果其中的加法器是RCA,那么该电路的关键路径延迟是3级加法器的延迟。如果采用CSA电路,则其电路结构如下:

image-20240427220537983

        前面说了,CSA电路的延迟也就一个门电路,那么上面电路的关键路径延迟就是 3个门电路 + 最后的加法器 的延迟,假设加法器也是使用的RCA加法器,那么最终的延迟就是 1个RCA的延迟 + 3个门电路 延迟,这显然比3级RCA电路的延迟要小。可以预见的是,随着加数个数的增加,两种电路的延迟差距还会拉大。

        以4比特乘法为例,其竖式计算表示如下:

image-20240430210444307

        ai和bi分别表示A和B的某个bit,aibi表示ai与bi相与,使用与门电路生成,aibi的值只有0和1。S表示AB相乘的结果。每一列使用半加器HA或全加器FA两两相加,其结果表示为Si,每一列每两个数产生的进位将传递至相邻高的一列参与计算。其电路结构如下(其中虚线箭头表示进位传播的路线):

image-20240430210453212

        根据进位传播链,可以看出该电路的关键路径如下:

image-20240430210459616

        红线和紫线是由于累加造成的进位链的最长路径。其中:

  • 红色路径:6个FA + 2个HA

  • 紫色路径:5个FA + 3个HA

        使用进位保留加法器CSA可缩短该进位链的传播延时,其电路结构如下:

image-20240430210508221

        将RCA阵列乘法器的进位连接至斜下角的加法器,CSA结构的阵列乘法器将进位与和分别计算,不必计算该层的进位,省去了行波进位加法器进位链的依赖,只在最后一级通过RCA结构(上图绿色虚框)传递进位合并最后的结果。上图红色是CSA结构的关键路径:3个FA + 3个HA。可见,CSA结构使用相同的资源却有更优的时序性能,当加法个数变多时,这一优势将更大。

        进位保存加法器的优点如下:

  • 进位保存加法器将 3 个数字的加法减少到 2 个数字

  • 由于进位传播级很少,与其他类型的加法器相比,它的功耗较低

  • 该加法器可以一次执行三位加法

  • 无论最终操作完成,下一级都会使用简单的 N 位 RCA。

        进位保存加法器的缺点如下:

  • 在进位保存加法的每一步中,可以立即知道加法结果,但我们不知道加法结果与给定数字相比是更小还是更大。

  • 这种类型的加法器不能解决将 2 个整数相加以生成单个输出的问题。相反,它只是将 3 个整数相加并生成两个整数,因此两个整数的总和等于三个输入的总和。

  • 它对于少数位操作具有高功耗和传播延迟。

4、CSA电路的实现

        接下来,以6个8bits有符号数的加法为例,看如何用CSA的树形结构实现。首先要确定的是,对于单个bit的CSA来说,就是全加器,如下:

image-20240427230436809

        所以它的生成公式是:

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作为电路输出与预期结果的对比值,当二者一致时即拉高这两个信号。这样我们只要观察这个信号,即可知道电路输出是否正确。仿真结果如下:

image-20240430212443654

        可以看到,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的过程。输出得准了,就是知识,输出不准了&#xff0c…...

科普文:微服务之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],[…...

为什么美元债务会越来越多?

美元债务规模持续膨胀,其背后原因复杂多样,可归结为以下几个主要因素: 财政赤字和刺激政策是导致美元债务增加的重要原因。美国政府长期面临财政赤字问题,支出远超收入,为弥补这一缺口,政府不得不大量发行…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

EtherNet/IP转DeviceNet协议网关详解

一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性&#xf…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...