专栏首页根究FPGA求余算法的FPGA实现

求余算法的FPGA实现

遇到了一个输入的除数和被除数位宽(64~256)都很大,组合逻辑导致时序不满足要求的问题,根据恢复余数法想出这样一个解决方式:

Y / D =Q……….R

Y:被除数

D:除数

Q:商

R:余数

对于一个n位的被除数Y,m位的除数D,若想求出余数,可通过恢复余数算法实现,个人的理解是这个求商貌似不太好用,求余数倒是好用的很!

其实现方式是,将除数左移到与被除数位宽相同,将移位的结果与被除数进行比较,如果被除数大于等于移位结果,说明商的对应位为1,将被除数减去移位结果得到新一轮的被除数,之后除数继续移位,移位到与新的被除数位宽相同…..当被除数小于D时候即为余数,解释起来有点麻烦,上代码。

以一个被除数位宽为4,除数位宽为2的输入为例:

工程代码:

module chufa(
clk,
rst_n,
en,  //计算使能信号
Y,   //被除数
D,  //除数  
R  //余数
);
input clk;
input rst_n;
input en;
input [3:0]Y;
input [1:0]D;
output reg[3:0]R;  
reg [3:0]state;
parameter S0=4'b0001;
parameter S1=4'b0010;
parameter S2=4'b0100;
parameter S3=4'b1000;
  reg [3:0]Y2,Y3,Y4; 
reg [3:0]D1,D2;
reg o_en;
always@(posedge clk or negedge rst_n)
if(!rst_n)
begin 
 state<=S0;
 o_en<=1'b0;
end 
else begin
case (state)
S0:begin
 o_en<=1'b0;   //余数输出不使能
if(en)begin
 state<=S1;
 D1<=(D<<2);  //移位至与被除数位宽相同,第一次移位操作
end 
end 
S1:
 begin
  D2=(D<<1);   //除数左移一位,第二次移位操作
  if(Y>=D1) 
   Y2<=Y-D1;   //下一次迭代的被除数 
  else  
   Y2<=Y;     
  state<=S2;
 end 
S2:
begin
if(Y2>=D2)
 Y3<=Y2-D2;
else    //最高位没有被整除
 Y3<=Y2;
 state<=S3;
end 
S3:
begin
if(Y3>=D)   //最后一轮的迭代比较
 Y4<=Y3-D;
else     
 Y4<=Y3;
 o_en<=1'b1;
 state<=S0; 
end 
endcase  
end 

always@(posedge clk or negedge rst_n)
if(!rst_n)
R<=4'd0;
else if(o_en)
R<=Y4;
endmodule

仿真代码:

`timescale 1ns / 1ps
module tb();
reg clk;
reg rst_n;
reg en;
reg [3:0]Y;
reg [1:0]D;
wire[3:0]R;

chufa cf(
.clk(clk),
.rst_n(rst_n),
.en(en),  //计算使能信号
.Y(Y),   //被除数
.D(D),  //除数  
.R(R)  //余数
);

initial clk=0;
always #5 clk=~clk;

initial begin
 rst_n=0;
 Y=13;
 en=0;
 D=3;
 #100;
 rst_n=1;
 #100;
 en=1;
 #100;
end 
endmodule

仿真结果:

本文分享自微信公众号 - 根究FPGA(gh_08b5d93f8fa5),作者:叫什么好呢啊

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • glitch-free clock switching circuit

    glitch:毛刺,glitch-free clock switching circuit:无毛刺时钟切换电路,今天讨论的主题就是如何实现时钟的无毛刺切换,本文...

    根究FPGA
  • 时序分析笔记系列(五)、IO约束与时钟约束

    管脚约束就是指管脚分配,指定管脚的PACKAKE_PIN(管脚位置)和PACKAGE_IOSTARD(电平标准)两个属性的值。

    根究FPGA
  • 冒泡排序法三部曲の二冒泡排序法的优化

    在冒泡排序法三部曲の一冒泡排序法的原理之后,其实存在一些可优化的问题,首先就是假如是{1,2,3,6,4}这样的数组,经过一次冒泡之后数组变为{1,2,3...

    根究FPGA
  • 软件工程 活动图、状态图、顺序图实验题

    开始。 学生进入考场。 监考教师核对检查证件,发放试卷。 学生对号入座。 学生开始答题。 学生交卷。 监考教师收取试卷。 结束。

    Debug客栈
  • 死磕 java魔法类之Unsafe解析

    本章是java并发包专题的第一章,但是第一篇写的却不是java并发包中类,而是java中的魔法类sun.misc.Unsafe。

    彤哥
  • 解锁FaceBook隐藏好友和朋友圈

    最近,国外的开源情报(OSINT)爱好者分享了一篇帖子,查找朋友不可见的facebook用户的朋友圈,这篇帖子也在我们的知识星球(开源网络空间情报)中第一时间分...

    FB客服
  • 一图读懂腾讯Q2财报:总收入736.75亿元,同比增长30%

    腾讯大讲堂
  • javascript当中Map Area Shape 和onmousemove的用法

    例 4.2(MapAreaShapeMouseMoveIEFF.html) <html> <head> <title> img hidefocus="true"...

    马克java社区
  • asp.net mvc脚手架代码生成工具

    发现了一个asp.net 脚手架代码生成工具,它是一个免费的工具,自动生成asp.net mvc的CRUD页面,主要特性如下: Uses the LinqToS...

    张善友
  • 13.MySQL(一) 数据库简介mysql安装数据库操作Mysql数据类型存储引擎

    数据库简介 数据库(Database)是按照数据结构来组织、存储和管理数据的仓库 RDBMS 即关系数据库管理系统(Relational Database Ma...

    zhang_derek

扫码关注云+社区

领取腾讯云代金券