# 高性能整数除法器

**Repository Path**: wirelesssun/HP_INT_DIV

## Basic Information

- **Project Name**: 高性能整数除法器
- **Description**: Verilog编写的高性能整数除法器，具有参数化配置位宽、迭代加速、结果锁存等特性，带有仿真脚本
- **Primary Language**: Verilog
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 4
- **Created**: 2023-06-30
- **Last Updated**: 2023-06-30

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 高性能整数除法器

## 使用说明
### 特性
有符号/无符号除法实时切换  
参数化配置除法器位宽(任何位宽都可以哦)  
除法迭代加速，自动跳过商中的0，每次迭代生成至少1位商  
锁存上一次除法结果，输入相同则直接结束计算  

### 端口说明
**参数化配置除法器位宽**
|名称|默认值|功能|
|-|-|-|
|DIV_WIDTH|32|输入输出数据位宽|

**除法器端口**
|名称|方向|位宽|功能|
|-|-|-|-|
|公共信号|
|clk|输入|[0:0]|时钟输入端口|
|rst_n|输入|[0:0]|异步复位同步释放|
|数据输入|
|su_dived_i|输入|[DIV_WIDTH-1:0]|被除数|
|su_divor_i|输入|[DIV_WIDTH-1:0]|除数|
|signed_en|输入|[0:0]|使能有符号除法，高有效|
|div_in_valid|输入|[0:0]|输入数据有效，除法期间需持续拉高|
|div_in_ready|输出|[0:0]|准备好接收|
|数据输出|
|div_res_data|输出|[DIV_WIDTH-1:0]|商|
|div_rem_data|输出|[DIV_WIDTH-1:0]|余数|
|div_out_valid|输出|[0:0]|输出结果有效|
|div_out_ready|输入|[0:0]|准备好接收|

### 仿真说明
需要安装iverilog v11及以上版本  
Windows:[视频教程](https://www.bilibili.com/video/BV1dS4y1H7zn/)  
Linux:  
```
sudo apt install make git gtkwave gcc g++ bison flex gperf autoconf
git clone -b v11_0 --depth=1 https://gitee.com/xiaowuzxc/iverilog/
cd iverilog
sh autoconf.sh
./configure
make
sudo make install
cd ..
rm -rf iverilog/
```
`/tb`目录提供了Makefile和批处理脚本，分别用于Linux与windows  
Windows: 双击`/tb/make.bat`  
Linux: `/tb`目录下，终端输入`make`   

### 例化模板
```
hp_int_div #(
	.DIV_WIDTH(32)
) inst_hp_int_div (
	.clk           (clk          ),
	.rst_n         (rst_n        ),
	.su_dived_i    (su_dived_i   ),
	.su_divor_i    (su_divor_i   ),
	.signed_en     (signed_en    ),
	.div_in_valid  (div_in_valid ),
	.div_in_ready  (div_in_ready ),
	.div_res_data  (div_res_data ),
	.div_rem_data  (div_rem_data ),
	.div_out_valid (div_out_valid),
	.div_out_ready (div_out_ready)
);
```

## 原理说明
### 符号位的处理方式
高性能整数除法器内核为无符号设计，对于有符号除法，进行以下操作：  
- 剥离被除数、除数的符号位，取绝对值  
- 锁存被除数、除数的符号位  
- 无符号除法  
- 生成无符号商、余数  
- 根据锁存的符号位，生成有符号商、余数  

### 迭代加速原理
围绕被除数、除数的前导0，进行加速  
![迭代加速](/加速迭代原理.svg)  
如图所示，现有被除数A和除数B，它们都是WIDTH位宽度。其中AZ和BZ表示A和B中的前导0部分，AN和BN表示A和B中的有效数字部分。  
注意，被除数A不仅表示初始状态的被除数，A还表示每一次除法迭代产生的中间余数。  
按照传统除法计算方式，一次WIDTH位的除法需要进行WIDTH次迭代，迭代过程既可以左移除数，也可以右移被除数，目的是比较除数和被除数的高位，得到当前位的商和中间余数。第一次除法迭代需要对齐B的最低位和A的最高位，可以将A右移WIDTH-1位，然后比较移位后的A和B，判断中间余数和商。若移位后的A大于B，则最高位的商等于1，中间余数等于A减去左移WIDTH-1位的B；反之，最高位的商等于0，中间余数A等于被除数A。  
显而易见的是，A中存在AZ长度的前导0，在此区间进行比较是无意义的；B中存在BN长度的有效数字，若B左移后A的有效数字比B更短，进行比较是无意义的；他们的“无意义”之处体现在每次迭代结果都是可预测的，当前位的商一定是0，中间余数不变。  
观察A和B，可以发现，第一次有意义的比较和迭代，发生在AN和BN的最高位对齐的时刻，当前位的商和中间余数都由AN和BN的具体值决定。  
将被除数引申至中间余数A，可以发现他们有着相同的规律，即中间余数A的前导0也会成为冗余。至此，可以明确除法器高性能整数除法器的特点，即每次迭代可以跳过前导0带来的冗余。  
本除法器选择右移A比较，左移B产生下一次的中间余数A。每一次迭代， A右移的次数为BZ-AZ，这样可以让AN和BN的最高位对齐，实现最高效的计算。  
最后一次迭代，极有可能AZ小于BZ，此时A不会移位，最低位的商等于0，此时的A作为余数。  

### 临界值的处理方式

|被除数|除数|模式|商|余数|
|-|-|-|-|-|
|x|0|无符号|2^(DIV_WIDTH)-1|x|
|x|0|有符号|-1|x|
|-2^(DIV_WIDTH-1)|-1|有符号|-2^(DIV_WIDTH-1)|0|

### 资源与时序表现
例化参数`DIV_WIDTH`等于32  
|器件|LUT|REG|频率|
|-|-|-|-|
|EG4S20|1083|227|40+MHz|
|GW2A|1081|207|43.9MHz|