# 恢复余数除法器

## 恢复余数除法器

### 算法描述

1. 将除数向左位移直到比被除数大
2. 执行被除数减除数操作，得余数，并将商向左移位1位，空位补1
3. 若余数大于0，除数向右移位1位。如余数小于0，余数加当前除数，商最后一位置0，除数向右移位1位
4. 重复到2，只到除数比最初的除数小

### RTL代码

RTL代码就是使用了大量的`if`语句完成了以上的算法描述，其中

• 为了使移位后的除数确保大于被除数，直接将除数放到一个位宽WIDTH*3的寄存器的前WIDTH位
• `divisor_move >= '{divisor_lock}`用于当移位除数小于原除数时停止
• `(divisor_move > '{remainder_r}) && (dout == 'b0)`用于当出现第一个1时才开始保存结果
```module restore_divider #(
parameter WIDTH = 4
)(
input clk,    // Clock
input rst_n,  // Asynchronous reset active low

input [WIDTH * 2 - 1:0]dividend,
input [WIDTH - 1:0]divisor,

input din_valid,

output reg [2 * WIDTH - 1:0]dout,
output [WIDTH - 1:0]remainder
);

reg [2 * WIDTH:0]remainder_r;
reg [3 * WIDTH - 1:0]divisor_move;
reg [WIDTH - 1:0]divisor_lock;
always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
//初始化
{remainder_r,divisor_lock,divisor_move,dout} <= 'b0;
end else begin
if(din_valid == 1'b1) begin
//锁存输入，3倍WIDTH的宽度用于保证移位后的除数大于被除数
remainder_r[WIDTH * 2 - 1:0] <= dividend;
remainder_r[2 * WIDTH] <= 'b0;
divisor_move[3 * WIDTH - 1:2 * WIDTH] <= divisor;
divisor_move[2 * WIDTH - 1:0] <= 'b0;
divisor_lock <= divisor;
dout <= 'b0;
end else if((divisor_move > '{remainder_r}) && (dout == 'b0)) begin
//开始条件
remainder_r <= remainder_r;
dout <= 'b0;
divisor_move <= divisor_move >> 1;
divisor_lock <= divisor_lock;
end else if(divisor_move >= '{divisor_lock}) begin
if(remainder_r[2 * WIDTH] == 1'b0) begin //执行减法
remainder_r <= remainder_r - divisor_move;
dout <= {dout[2 * WIDTH - 2:0],1'b1};
// divisor_move <= divisor_move >> 1;
divisor_lock <= divisor_lock;
if(remainder_r >= divisor_move) begin
divisor_move <= divisor_move >> 1;
end else begin
divisor_move <= divisor_move;
end
end else begin  //恢复余数
remainder_r <= remainder_r + divisor_move;
dout <= {dout[2 * WIDTH - 1:1],1'b0};
divisor_move <= divisor_move >> 1;
divisor_lock <= divisor_lock;
end
end else begin
remainder_r <= remainder_r;
divisor_lock <= divisor_lock;
divisor_move <= divisor_move;
dout <= dout;
end
end
end

assign remainder = remainder_r[WIDTH - 1:0];

endmodule```

### 测试平台

```module tb_divider (
);

parameter WIDTH = 4;

logic clk;    // Clock
logic rst_n;  // Asynchronous reset active low
logic [2 * WIDTH - 1:0]dividend;
logic [WIDTH - 1:0]divisor;

logic din_valid;

logic [2 * WIDTH - 1:0]dout;
logic [WIDTH - 1:0]remainder;

restore_divider #(
.WIDTH(WIDTH)
) dut (
.clk(clk),    // Clock
.rst_n(rst_n),  // Asynchronous reset active low

.dividend(dividend),
.divisor(divisor),

.din_valid(din_valid),

.dout(dout),
.remainder(remainder)
);

initial begin
clk = 'b0;
forever begin
#50 clk = ~clk;
end
end

initial begin
rst_n = 1'b1;
# 5 rst_n = 'b0;
#10 rst_n = 1'b1;
end

logic [2 * WIDTH - 1:0]dout_exp;
logic [WIDTH - 1:0]remainder_exp;
initial begin
{dividend,divisor,din_valid} = 'b0;
forever begin
@(negedge clk);
dividend = (2 * WIDTH)'(\$urandom_range(0,2 ** (2 * WIDTH)));
divisor = (WIDTH)'(\$urandom_range(1,2 ** WIDTH - 1));
din_valid = 1'b1;

remainder_exp = dividend % divisor;
dout_exp = (dividend - remainder_exp) / divisor;

repeat(5 * WIDTH) begin
@(negedge clk);
din_valid = 'b0;
end
if((remainder == remainder_exp) && (dout_exp == dout)) begin
\$display("successfully");
end else begin
\$display("failed");
\$stop;
end
end
end

endmodule```

0 条评论

• ### 移位相减除法器

移位相减除法器 基本算法 与使用移位相加实现加法一样，移位减法可以实现除法，基本算法如下描述 将除数向左移位直到比被除数大 使用移位后的除数与被除数比较，若除数...

• ### 不恢复余数除法器

不恢复余数除法器 基本算法 不恢复余数除法器的基本算法来自于恢复余数除法器，区别在于当余数变负时不停下恢复余数而是继续运行迭代，并在迭代中加上移位后除数而不是减...

• ### 不恢复余数除法器

不恢复余数除法器 基本算法 不恢复余数除法器的基本算法来自于恢复余数除法器，区别在于当余数变负时不停下恢复余数而是继续运行迭代，并在迭代中加上移位后除数而不是减...

• ### C1WPF制作OLAP Cube浏览工具

经过前期一段时间对WPF的学习了解，相信大家对WPF有了一定的了解。今天我们一起来了解使用Component One（简称C1）的WPF控件制作C...

• ### 构建ASP.NET MVC4+EF5+EasyUI+Unity2.x注入的后台管理系统（10）-系统菜单栏[附源码]

似乎我们需要更多的模块了，我们有一个样例程序，可以帮助我们以后的系统开发做很多对照，我们稍后还有系统日志和系统异常的记录，这时浏览发生了困难，我们这一节来完成一...

• ### 自建node的简单cli——san-cli

公司的业务有部分需要兼容IE8，虽然公司内部已有相应的框架，但是百度的San还是引起了个人的兴趣，奈何San这个东西，一年多了配套还有待完善，为了快速构建项目，...

• ### 毫无还手之力！OpenAI人工智能5v5击败超凡5玩家（6600水平）

2017 年 8 月，OpenAI 在 Dota2 TI 决赛现场以 1 对 1 solo 的方式击败了「Dota 2」世界顶级玩家。今年 6 月份，OpenA...

• ### HAWQ技术解析（七） —— 存储分布

在HAWQ中创建一个表时，应该预先对数据如何分布、表的存储选项、数据导入导出方式和其它HAWQ特性做出选择，这些都将对数据库性能有极大影响。理解...

• ### OpenAI成立新公司，前YC总裁担纲CEO，马斯克退出

OpenAI 非营利部门负责管理 OpenAI LP，主持学者和研究人员等教育计划，并负责政策实施。

• ### 从开放到封闭，资金压力正在侵蚀OpenAI

作为由钢铁直男Elon Musk和YC创始人Sam Altman等人共同创立的项目，OpenAI尽管成立只有4年的时间，但已经成长为在AI研究领域媲美于Goog...