首页 > 其他分享 >基于FPGA的数字信号处理（19）--行波进位加法器

基于FPGA的数字信号处理（19）--行波进位加法器

时间：2024-07-29 09:26:07浏览次数：14  
标签：行波 cout FPGA 19 sum WIDTH 加法器 加法 进位

1、10进制加法是如何实现的？

        10进制加法是大家在小学就学过的内容，不过在这里我还是帮大家回忆一下。考虑2个2位数的10进制加法，例如：15 + 28 = 43，它的运算过程如下：

image-20240426153428462

个位两数相加，结果为5 + 8 = 13，结果的1作为进位传递到十位，而3则作为和的低位保留

十位的两数相加同时加上来自低位的进位1，即1 + 2 + 1 = 4，且没有向高位产生进位

        因为没有产生进位也可以看做是产生了数值为0的进位，所以我们把十位和个位都添加上来自低位的进位，以及去往高位的进位，如下：

image-20240426153604608

        这样的两位数加法，实际上就拆解成两个加法器的级联了。单个加法器和2进制全加器一样，可以计算2个1位数的加法，同时接受来自低位的进位，以及产生向高位的进位，就像这样：

image-20240426153911874

2、行波进位加法器RCA

        同10进制加法相加类似，2个多bits的2进制数相加，也可以通过这种级联的形式来构成。考虑2个4bits数的加法，每个全加器都可以处理它对应位数的两个数的加法，同时接收来自低级的进位，并向高位产生进位，所以它的结构是这样的：

image-20240426154209316

        这样的加法器叫做 行波进位加法器 或 纹波进位加法器（Ripple Carry Adder,RCA），这个取名大概是因为它的进位传递是一级一级往外（前）扩散的，就好像水面泛起的波纹一样。

        以两个4bits数相加为例：5 + 6 = 11，即 0101 + 0110 = 1011，它的过程如下：

image-20240426155144935

        根据RCA的结构，可以很快地写出它的Verilog实现形式：

//使用多个全加器级联构建RCA加法器
module rca(
    input   [3:0]   x,      //加数1
    input   [3:0]   y,      //加数2
    input           cin,    //来自低位的进位
    output  [3:0]   sum,    //和
    output          cout    //向高位的进位
);
​
wire    c1,c2,c3;           //进位连接
​
//例化全加器来构建RCA加法器
full_adder  u0(
    .x      (x[0]),
    .y      (y[0]), 
    .sum    (sum[0]),
    .cin    (cin),
    .cout   (c1)
);
full_adder  u1(
    .x      (x[1]),
    .y      (y[1]), 
    .sum    (sum[1]),
    .cin    (c1),
    .cout   (c2)
);
full_adder  u2(
    .x      (x[2]),
    .y      (y[2]), 
    .sum    (sum[2]),
    .cin    (c2),
    .cout   (c3)
);
full_adder  u3(
    .x      (x[3]),
    .y      (y[3]), 
    .sum    (sum[3]),
    .cin    (c3),
    .cout   (cout)
);
​
endmodule

        这里记得把全加器的代码也要添加进工程。生成的示意图如下（虽然这个排布不能很好地看出来层次结构，但确实没错）：

image-20240426160920178

        然后写个TB测试一下这个加法器电路，因为4个bits即16×16=256种情况，加上低位进位的两种情况，也才256×2=512种情况，所以可以用穷举法来测试：

`timescale 1ns/1ns              //时间刻度：单位1ns,精度1ns
​
module tb_rca();            
​
//定义变量  
reg     [3:0]   x;      //加数1
reg     [3:0]   y;      //加数2
reg             cin;    //来自低位的进位
wire    [3:0]   sum;    //和
wire            cout;   //向高位进位
​
reg [3:0]   sum_real;   //和的真实值，作为对比
reg         cout_real;  //向高位进位的真实值，作为对比
wire        sum_flag;   //sum正确标志信号
wire        cout_flag;  //cout正确标志信号
​
assign sum_flag  = sum  == sum_real;    //和的结果正确时拉高该信号
assign cout_flag = cout == cout_real;   //进位结果正确时拉高该信号
​
integer z,i,j;  //循环变量
​
//设置初始化条件
initial begin
    //初始化
    x =1'b0;    
    y =1'b0;    
    cin =1'b0;  
    //穷举所有情况
    for(z=0;z<=1;z=z+1)begin
        cin = z;
        for(i=0;i<16;i=i+1)begin
            x = i;
            for(j=0;j<16;j=j+1)begin
                y = j;
                if((i+j+z)>15)begin                 //如果加法的结果产生了进位
                    sum_real = (i+j+z) - 16;        //减掉进位值
                    cout_real = 1;                  //向高位的进位为1
                end
                else begin                          //如果加法的结果没有产生了进位
                    sum_real = i+j+z;               //结果就是加法本身
                    cout_real = 0;                  //向高位的进位为0
                end
                #5;             
            end 
        end
    end
    #10 $stop();    //结束仿真  
end
​
//例化被测试模块
rca u_rca(
    .x      (x),
    .y      (y),    
    .sum    (sum),
    .cin    (cin),
    .cout   (cout)
);
    
endmodule

        TB中分别用3个嵌套的循环将所有情况穷举出来，即cin=0~1、x=0~15和y=0~15的所有情况。加法运算的预期结果也是很容易就可以找出来的，就是在TB中直接写加法就行。接着构建了两个标志向量sum_flag和cout_flag作为电路输出与预期正确结果的对比值，当二者一致时即拉高这两个信号。这样我们只要观察这两个信号，即可知道电路输出是否正确。仿真结果如下：

image-20240426161105042

        可以看到，sum_flag和cout_flag都是一直拉高的，说明电路输出正确。

3、RCA加法器的缺陷

        因为RCA的结构是从低到高依次级联的，所以它的进位链特别长，比如加法 1111 + 0000 + 1（最后的1表示来自低位的进位即cin），它的进位从最低位开始，需要经过4级全加器才能传递到最高级，如下：

image-20240426161537866

        这条进位cin传递的路径也是拖垮整个电路速度的关键路径（Critical Path），它的长度（延迟）为 4*全加器 的延迟。可以预见，随着加法器位宽的增加，这条路径也会越来越长，所以RCA不适合位宽很大的加法，因为它的延迟实在是太高了。

        以RCA的基础组成部分全加器FA为例，它的结构是这样的：

image-20240426201523357

        图中的红色路径就是关键路径，即延迟最高的路径，它由 1个异或门延迟 + 1个与门延迟 + 1个或门延迟 + 布线延迟 组成，若忽略布线延迟（和门电路延迟比起来，布线延迟相对较小），并将3种门电路的延迟都近似看做同一个数值的话，则单个全加器的延迟是 3个门电路延迟。

        这么说，从直观上感觉多个全加器构成的行波进位加法器的关键路径延迟应该是 3×全加器数量（即加法位宽），比如两个4bits数相加，其关键路径延迟应该是 4×3=12个门电路延迟，但实际上不是，我们看下具体结构：

image-20240426202724901

        除了在第一个全加器有3个门电路的延迟外，后面经过的全加器都只有两个门电路的延迟，所以总共的延迟是 3 + 3*2 = 9个，由此可以推广到Nbits数，其延迟为 3 + 2×（N - 1） = 2N + 1 个门电路。

        在RCA的基础上，工程师们又设计了很多种其他的加法器结构，它们的延迟较之RCA加法器有了显著的降低，其中比较有名的一种加法器是 超前进位加法器（Lookahead Carry Adder），我们将在下一篇文章介绍它。

4、RCA加法器的参数化设计

        在上面的内容种，对RCA的举例是两个4bits数相加实现的形式，为了满足不同位宽的加法，这里也给出参数化设计形式的Verilog代码：

//使用多个全加器级联构建RCA加法器
module rca 
#(
    parameter integer WIDTH = 4
)
(
    input   [WIDTH-1:0] x,      //加数1
    input   [WIDTH-1:0] y,      //加数2
    input               cin,    //来自低位的进位
    output  [WIDTH-1:0] sum,    //和
    output              cout    //向高位的进位
);
​
wire [WIDTH:0] c_wire;          //用来连线传递的进位变量
​
assign c_wire[0] = cin;         //最低位是输入的进位
assign cout = c_wire[WIDTH];    //最高位是输出的进位
​
//用generate来例化多个模块   
genvar i;    
generate
    for(i=0;i<WIDTH;i=i+1)
    begin:full_adder
        full_adder u_full_adder(
            .x      (x[i]       ),
            .y      (y[i]       ),
            .sum    (sum[i]     ),
            .cin    (c_wire[i]  ),
            .cout   (c_wire[i+1])
        );
    end
endgenerate  
​
endmodule

配套的TB也改成参数化形式：

`timescale 1ns/1ns              //时间刻度：单位1ns,精度1ns
​
module tb_rca();
​
parameter integer WIDTH = 'd4;          
​
//定义变量  
reg     [WIDTH-1:0] x;      //加数1
reg     [WIDTH-1:0] y;      //加数2
reg                 cin;    //来自低位的进位
wire    [WIDTH-1:0] sum;    //和
wire                cout;   //向高位进位
​
reg [WIDTH-1:0] sum_real;   //和的真实值，作为对比
reg             cout_real;  //向高位进位的真实值，作为对比
wire            sum_flag;   //sum正确标志信号
wire            cout_flag;  //cout正确标志信号
​
assign sum_flag  = sum  == sum_real;    //和的结果正确时拉高该信号
assign cout_flag = cout == cout_real;   //进位结果正确时拉高该信号
​
integer z,i,j;  //循环变量
​
//设置初始化条件
initial begin
    //初始化
    x = 0;  
    y = 0;  
    cin = 0;    
    //穷举所有情况
    for(z=0;z<=1;z=z+1)begin
        cin = z;
        for(i=0;i<(2**WIDTH);i=i+1)begin
            x = i;
            for(j=0;j<(2**WIDTH);j=j+1)begin
                y = j;
                if((i+j+z)>(2**WIDTH-1))begin           //如果加法的结果产生了进位
                    sum_real = (i+j+z) - (2**WIDTH);    //减掉进位值
                    cout_real = 1;                      //向高位的进位为1
                end 
                else begin                              //如果加法的结果没有产生了进位
                    sum_real = i+j+z;                   //结果就是加法本身
                    cout_real = 0;                      //向高位的进位为0
                end
                #5;             
            end 
        end
    end
    #10 $stop();    //结束仿真  
end
​
//例化被测试模块
rca #(
    .WIDTH  (WIDTH)
)
u_rca(
    .x      (x),
    .y      (y),    
    .sum    (sum),
    .cin    (cin),
    .cout   (cout)
);
    
endmodule

（1）把位宽width改成4

        生成的4bits加法的RCA示意图：

image-20240428155131457

        仿真结果证明电路设计无误：

image-20240428155210128

（2）把位宽width改成8

        生成的8bits加法的RCA示意图：

image-20240428155239697

        仿真结果证明电路设计无误：

image-20240428155307270

5、RCA加法器的时序性能

        为了探究RCA加法器的时序性能，需要再原有代码的基础上，做一些小小的改变：在输入和输出分别添加上寄存器。如下：

//使用多个全加器级联构建RCA加法器
module rca 
#(
    parameter integer WIDTH = 32
)
(
    input               clk,
    input   [WIDTH-1:0] x,      //加数1
    input   [WIDTH-1:0] y,      //加数2
    input               cin,    //来自低位的进位
    output  [WIDTH-1:0] sum,    //和
    output              cout    //向高位的进位
);
​
reg                 cin_r,cout_r;
reg     [WIDTH-1:0] x_r,y_r,sum_r;
​
wire    [WIDTH:0]   c_wire;         //用来连线传递的进位变量
wire    [WIDTH-1:0] sum_w;          //用来连线传递和
​
​
//输入寄存
always@(posedge clk)begin
    x_r <= x;
    y_r <= y;
    cin_r <= cin;
end
​
assign c_wire[0] = cin_r;       //最低位是输入的进位 
​
//输出寄存
always@(posedge clk)begin
    sum_r <= sum_w;
    cout_r <= c_wire[WIDTH];    //最高位是输出的进位
end
​
assign sum = sum_r;
assign cout = cout_r;
​
//用generate来例化多个模块   
genvar i;    
generate
    for(i=0;i<WIDTH;i=i+1)
    begin:full_adder
        full_adder u_full_adder(
            .x      (x_r[i]     ),
            .y      (y_r[i]     ),
            .sum    (sum_w[i]   ),
            .cin    (c_wire[i]  ),
            .cout   (c_wire[i+1])
        );
    end
endgenerate  
​
endmodule

        分别例化4位加法，8位加法，16位加法和32位加法，记录它们的逻辑级数logic levels、最差建立时间裕量WNS和电路面积，并算出最大运行频率Fmax。如下：

4位8位16位32位
WNS(ns)8.7778.1556.9174.429
Fmax(Mhz)818542324180
logic levels(级)24816
电路面积（不考虑FF）4 LUT8 LUT16 LUT32 LUT

        从上表可以看到：

  • 随着加法器位宽的增加，逻辑级数也越来越大，这是导致时序性能变差的直接原因

  • 时序性能从818M相关性地降低到180M，需要说明的是这里的最大频率Fmax只能作为一个参考，因为我整个工程只添加了这么一个加法器，而且Fmax一般还和FGPA的器件强挂钩，一般的器件肯定是跑不到800M的，这里我们主要是观察这个频率降低的趋势

  • 电路面积上是几位加法就用几个LUT（因为1个全加器用1个LUT），而且都是直接级联的

        作为参考，我们不使用任何加法器，就直接用加法运算符 + 来实现加法，电路就让综合工具vivado来自动生成，代码如下：

//直接写加法，看Vivado综合的结果
module rca 
#(
    parameter integer WIDTH = 32
)
(
    input               clk,
    input   [WIDTH-1:0] x,      //加数1
    input   [WIDTH-1:0] y,      //加数2
    input               cin,    //来自低位的进位
    output  [WIDTH-1:0] sum,    //和
    output              cout    //向高位的进位
);
​
reg                 cin_r,cout_r;
reg     [WIDTH-1:0] x_r,y_r,sum_r;
​
wire    [WIDTH-1:0] sum_w;
wire                cout_w;
​
//输入寄存
always@(posedge clk)begin
    x_r <= x;
    y_r <= y;
    cin_r <= cin;
end
​
assign {cout_w,sum_w} = x_r + y_r + cin_r; //直接写加法
​
//输出寄存
always@(posedge clk)begin
    sum_r <= sum_w;
    cout_r <= cout_w;
end
​
//端口连接
assign sum = sum_r;
assign cout = cout_r;
​
endmodule

        看看时序性能如何：

4位8位16位32位
WNS(ns)8.7778.7558.6578.461
Fmax(Mhz)818803745650
logic levels(级)2359
电路面积（不考虑FF）4 LUT8 LUT + 3 CARRY416 LUT + 5 CARRY432 LUT + 9 CARRY4

        从上表可以看到：

  • vivado综合出来的加法电路在时序性能上明显比RCA电路要强

  • 逻辑级数的增加并没有RCA电路那么明显，哪怕是32位的加法也只有9级逻辑层级。这也是它频率能跑很高的直接原因

  • 4位加法使用的电路面积和RCA是一样的，因为位宽较小，综合工具直接用LUT而不是CARRY4来生成电路，二者在小位宽时的时序性能差不多

  • 之所以大位宽加法的时序性能仍然比较好是因为综合工具使用CARRY4来实现加法，这种结构的加法电路有很快的进位速度，而且可以合并很多个进位链上的LUT从而减少逻辑级数

  • CARRY4的使用尽管可以提高时序性能，但是也会增大一部分电路面积。当然了，拿这点面积来换性能的提升，还是十分划算的

如果你不了解CARRY4，可以看看这篇文章：从底层结构开始学习FPGA（7）----进位链CARRY4

或者看看这个专栏：从底层结构开始学习FPGA

6、总结

        行波进位加法器RCA结构简单，进位链长，时序性能差，在实际应用尤其是FPGA设计中基本不会使用。对于FPGA设计来说，如今的综合工具已经非常智能了，一般的加法还是不要自己设计加法器了，直接让综合工具生成或者用IP就行。

标签：行波,cout,FPGA,19,sum,WIDTH,加法器,加法,进位
From： https://blog.csdn.net/wuzhikaidetb/article/details/140762462

相关文章

  • [米联客-安路飞龙DR1-FPSOC] FPGA基础篇连载-01 软件工具环境搭建
    ​ 软件版本：Anlogic-TD5.9.1-DR1_ES1.1操作系统：WIN1064bit硬件平台：适用安路(Anlogic)FPGA登录"米联客"FPGA社区 http://www.uisrc.com 视频课程、答疑解惑！本教程使用了米联客-MLK-L1-CZ06-DR1M90G开发板，购买链接:https://milianke.tmall.com/​1代码编辑vscode工具软件......
  • BUUCTF 6.[第五空间2019 决赛]PWN5 1
    拿到题目，先运行一下很明显地出现了一个重复我们的输入，以及一个判断的过程，那么我们可以猜测可能会有栈溢出漏洞，让我们继续保护是开了一个canary以及nx，大概率就不是栈溢出漏洞了，因为canary的存在会使栈溢出非常麻烦。我们看一下IDA存在栈溢出漏洞，但是由于长度不够，我们无法......
  • 实现畅捷通T+19.0基础资料与单据的互传
    功能：自动下载基础资料商品、供应商、客户、部门、自定义字段、仓库信息到地磅软件，供软件新增单据使用；地磅软件数据流程走完，自动上传采购与销售单据到畅捷通；注意点：用友所有产品的接口都在云上，无论是私有云还是公有云产品，都需要在云上注册开发者创建应用对接，必须提供一个公网可访问......
  • 19、flask-进阶-内置对象
    内置对象g对象:global全局对象g对象是专门用来保存用户的数据的g对象在一次请求中的所有的代码的地方都是可以使用的突变变量存储位置的限制，为函数传递添加了新的方式，比如我们在before_request产生一个数据在后面需要使用，可以保存在g对象中，就可以在其他视图中使用这个数......
  • CF1119H Triple
    异或卷积，把一个三元组\(\{a_i,b_i,c_i\}\)转化为\(F_i[a_i]=x\)，\(F_i[b_i]=y\)，\(F_i[c_i]=z\)的幂级数，将\(\prod\limits_{i=1}^n\text{FWT}(F_i)\)执行\(\text{IFWT}\)即可考虑从每个幂级数只有\(3\)个非零值入手优化，设\(c(i,j)\)表示异或卷积的变换系数，即\(\text{......
  • BUUCTF 4.ciscn_2019_n_1
    拿到题目首先先运行程序我们发现给了我们一个数字，我们猜测应该是一个条件判断的程序，然后我们检查一下保护机制我们发现只开了NX（不可执行）保护，那我们直接看IDA就行了。main函数只是设定了无缓冲模式，以及调用了一个func函数，然后我们看一下我们可以看到gets和我们想要的flag，......
  • FPGA FIFO IP核（3）- 仿真
    仿真思路如何在写入标志信号（写入请求信号）有效时将数据写入到FIFO中？在调用模块代码中，pi_flag每四个时钟周期产生一个有效信号，即写请求信号。每次当pi_data检测到pi_flag信号有效时加1，从0~255循环变化。实现效果就是在pi_flag有效时将pi_data写入到FIFO中。读请求信号rdreq......
  • 【Go】基于 Go 1.19 的站点模板爬虫【实战演练版】
    0.前言Go语言，也被称为Golang，是由Google开发的一种开源编程语言，它在2009年首次发布，并在2012年正式开源。Go语言被设计用来简化大型软件的开发，特别注重并发编程和内存安全。0.1特点静态类型：Go是静态类型语言，这意味着类型在编译时已经确定，有助于在编译阶段捕捉错误......
  • Python面试宝典第19题：最小路径和
    题目        给定一个包含非负整数的mxn网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。        示例1：输入：grid=[[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径1→3→1→1→1的总......
  • 每日一题- CF1995D
    唐氏小状压#include<bits/stdc++.h>usingnamespacestd;#definelowbit(x)(x&-(x))intt,n,c,k,cnt[(1<<18)+5][35];boolf[(1<<18)+5];chars[(1<<18)+5];intcalc(intx){ intres=0; while(x)x^=lowbit(x),res++; returnres;}voidi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99