【HDL系列】除法器(3)——基2 SRT算法
目錄
一、除法表示
二、數(shù)字遞歸算法基礎(chǔ)公式
三、QDS（Quotient Digit Selection）函數(shù)
四、基2 SRT算法
一、除法表示
除法被定義如下：
其中，x是被除數(shù)，d是除數(shù)，q是商，rem是余數(shù)。
商的精度由ulp（unit of last position）來決定:
??? 如果ulp=1, 商q則是整數(shù)；
??? 如果ulp=r^(-n)，n是商數(shù)個(gè)數(shù)，r是所有輸入操作數(shù)的基，此時(shí)商為小數(shù)。
二、數(shù)字遞歸算法基礎(chǔ)公式
在使用數(shù)字遞歸算法（Digit Recurrence Algorithms）進(jìn)行除法操作時(shí)迭代n次，每次迭代中產(chǎn)生基r的商，其中商的最高位先產(chǎn)生。經(jīng)過j+1次迭代后，商表示如下：
經(jīng)過n次迭代后除法完成，產(chǎn)生了n個(gè)商數(shù)，商q表示為：
最終q的誤差需小于ulp，所以：
在第j+1次迭代中，每一步中產(chǎn)生的誤差為：
重新組合上式，兩式各乘以d和r的j+1次得：
以上左式定義一個(gè)新的中間變量w[j+1]如下:
W[j+1]為部分余數(shù)，其遞歸過程如下式所示：
上式是數(shù)字遞歸算法的基礎(chǔ)。
三、QDS（Quotient Digit Selection）函數(shù)
此處部分余數(shù)w[j+1]可以表示為：
因?yàn)閣[j+1]=rw[j]-dq[j+1]; 表示在第j+1次迭代后得到的q[j+1]需使w[j+1]滿足以上條件；
W[j+1]迭代框圖?
W[j+1]迭代框圖是根據(jù)輸入w[j]，r和d聯(lián)合計(jì)算而來，初始的w[j]=x，即被除數(shù)。其中：
Arithmetic Shift Left表示左移余數(shù)或者部分余數(shù)；
Divisor Multiple Generation表示將得到的商值q[j+1]乘以d
Subtraction計(jì)算w[j+1]的結(jié)果，即w[j+1] = r*w[j]-d*q[j+1]
Quotient Digit Selection，簡稱QDS，即商數(shù)選擇，該模塊根據(jù)輸入的部分余數(shù)r*w[j]和除數(shù)d得到商值q[j+1]。
我們來回憶下二進(jìn)制恢復(fù)余數(shù)法（r=2）和二進(jìn)制不恢復(fù)余數(shù)法（r=2）的QDS函數(shù)：
二進(jìn)制恢復(fù)余數(shù)法的QDS函數(shù)：
二進(jìn)制非恢復(fù)余數(shù)法的QDS函數(shù)：
以上恢復(fù)余數(shù)法的商數(shù)據(jù)集為{0,1}，非恢復(fù)余數(shù)法的商數(shù)據(jù)集為{-1,1}。
四、基2 SRT算法
SRT算法是以D.Sweeney,J.E.Robertson和T.D.Tocher三名科學(xué)家的姓氏首字母組合命名而來的算法。他們幾乎在同時(shí)間段各自獨(dú)立發(fā)明了一種非恢復(fù)二進(jìn)制除法的方法。
SRT算法旨在加速非恢復(fù)二進(jìn)制除法，在商數(shù)選擇集中引入了0，且將QDS函數(shù)修改如下：
基2 SRT除法的Robertson圖基2 SRT將0引入到商集中，部分迭代則可只需要移位操作，減少了除法模塊的平均延時(shí)。但它與非恢復(fù)余數(shù)法的問題依舊是2w[j]與-d和+d的比較需要全精度才能得出q值。所以將除數(shù)d歸一化小數(shù)表示至區(qū)間[1/2, 1)，引入新的分界點(diǎn)-1/2和1/2來替代-d和+d，下式可說明-d與+d的小數(shù)取值：
所以QDS將更新如下：
其Robertson圖如下：
基2 SRT除法的Robertson圖，d屬于區(qū)間[1/2, 1)部分和w[j+1]被限制在[-1/2, 1/2)區(qū)間內(nèi)，2w[j]被歸一化且其二進(jìn)制補(bǔ)碼表示如下：
其中u0為符號(hào)位。因此，在{-1,0,1}三個(gè)可能的值中選取合適的商q值，QDS函數(shù)只需要將移位的部分和2w[j]的最高2/3比特與-1/2和1/2比較：
q的選擇有三種情況：
這意味著QDS函數(shù)的實(shí)現(xiàn)只需要幾個(gè)簡單的與門和反相器即可，而不再需要將部分和與全精度的除數(shù)進(jìn)行比較，極大節(jié)省了門電路面積，這也是相比于非恢復(fù)算法的改進(jìn)之處。
五、基2 SRT除法例子
設(shè)被除數(shù)x=69，除數(shù)d=10，求商q和余數(shù)rem？
我們知道：69/10 = 6 … 9
q=6，rem=9
基于以上介紹，我們來看下69/10的基2 SRT除法如下圖：
從圖中可以看出，商q=0110=6,余數(shù)rem=1001=9，與期望一致。
基2 SRT Verilog設(shè)計(jì)較為簡單與以上過程基本類似，而對于速度、性能和面積來說卻還不夠。
?
后期會(huì)有一些本期的補(bǔ)充說明。
謝謝您的閱讀！
參考Arichitectures for Floating-Point Division
更新不易，如果對您有幫助，記得點(diǎn)贊關(guān)注哦。歡迎批評(píng)指正，謝謝鼓勵(lì)！
一起“紙上談芯”，共同學(xué)習(xí):
總結(jié)
以上是生活随笔為你收集整理的【HDL系列】除法器(3)——基2 SRT算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： html的em标签不用斜体,HTML元素
- 下一篇： 企业管理驾驶舱系统设计