【HDL系列】除法器(3)——基2 SRT算法
目录
一、除法表示
二、数字递归算法基础公式
三、QDS（Quotient Digit Selection）函数
四、基2 SRT算法
一、除法表示
除法被定义如下：
其中，x是被除数，d是除数，q是商，rem是余数。
商的精度由ulp（unit of last position）来决定:
如果ulp=1, 商q则是整数；
如果ulp=r^(-n)，n是商数个数，r是所有输入操作数的基，此时商为小数。
二、数字递归算法基础公式
在使用数字递归算法（Digit Recurrence Algorithms）进行除法操作时迭代n次，每次迭代中产生基r的商，其中商的最高位先产生。经过j+1次迭代后，商表示如下：
经过n次迭代后除法完成，产生了n个商数，商q表示为：
最终q的误差需小于ulp，所以：
在第j+1次迭代中，每一步中产生的误差为：
重新组合上式，两式各乘以d和r的j+1次得：
以上左式定义一个新的中间变量w[j+1]如下:
W[j+1]为部分余数，其递归过程如下式所示：
上式是数字递归算法的基础。
三、QDS（Quotient Digit Selection）函数
此处部分余数w[j+1]可以表示为：
因为w[j+1]=rw[j]-dq[j+1]; 表示在第j+1次迭代后得到的q[j+1]需使w[j+1]满足以上条件；
W[j+1]迭代框图
W[j+1]迭代框图是根据输入w[j]，r和d联合计算而来，初始的w[j]=x，即被除数。其中：
Arithmetic Shift Left表示左移余数或者部分余数；
Divisor Multiple Generation表示将得到的商值q[j+1]乘以d
Subtraction计算w[j+1]的结果，即w[j+1] = r*w[j]-d*q[j+1]
Quotient Digit Selection，简称QDS，即商数选择，该模块根据输入的部分余数r*w[j]和除数d得到商值q[j+1]。
我们来回忆下二进制恢复余数法（r=2）和二进制不恢复余数法（r=2）的QDS函数：
二进制恢复余数法的QDS函数：
二进制非恢复余数法的QDS函数：
以上恢复余数法的商数据集为{0,1}，非恢复余数法的商数据集为{-1,1}。
四、基2 SRT算法
SRT算法是以D.Sweeney,J.E.Robertson和T.D.Tocher三名科学家的姓氏首字母组合命名而来的算法。他们几乎在同时间段各自独立发明了一种非恢复二进制除法的方法。
SRT算法旨在加速非恢复二进制除法，在商数选择集中引入了0，且将QDS函数修改如下：
基2 SRT除法的Robertson图基2 SRT将0引入到商集中，部分迭代则可只需要移位操作，减少了除法模块的平均延时。但它与非恢复余数法的问题依旧是2w[j]与-d和+d的比较需要全精度才能得出q值。所以将除数d归一化小数表示至区间[1/2, 1)，引入新的分界点-1/2和1/2来替代-d和+d，下式可说明-d与+d的小数取值：
所以QDS将更新如下：
其Robertson图如下：
基2 SRT除法的Robertson图，d属于区间[1/2, 1)部分和w[j+1]被限制在[-1/2, 1/2)区间内，2w[j]被归一化且其二进制补码表示如下：
其中u0为符号位。因此，在{-1,0,1}三个可能的值中选取合适的商q值，QDS函数只需要将移位的部分和2w[j]的最高2/3比特与-1/2和1/2比较：
q的选择有三种情况：
这意味着QDS函数的实现只需要几个简单的与门和反相器即可，而不再需要将部分和与全精度的除数进行比较，极大节省了门电路面积，这也是相比于非恢复算法的改进之处。
五、基2 SRT除法例子
设被除数x=69，除数d=10，求商q和余数rem？
我们知道：69/10 = 6 … 9
q=6，rem=9
基于以上介绍，我们来看下69/10的基2 SRT除法如下图：
从图中可以看出，商q=0110=6,余数rem=1001=9，与期望一致。
基2 SRT Verilog设计较为简单与以上过程基本类似，而对于速度、性能和面积来说却还不够。
后期会有一些本期的补充说明。
谢谢您的阅读！
参考Arichitectures for Floating-Point Division
更新不易，如果对您有帮助，记得点赞关注哦。欢迎批评指正，谢谢鼓励！
一起“纸上谈芯”，共同学习:
总结
以上是生活随笔为你收集整理的【HDL系列】除法器(3)——基2 SRT算法的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： html的em标签不用斜体,HTML元素
- 下一篇： 我的编程之路点滴记录（四）