FPGA除法器算法汇总

引言

FPGA编译软件中“/”是可以综合的，软件自行调用匹配相关除法器模块实现除法，通常此除法器完成一次运算需要耗费18个时钟周期。赋值缓存一个时钟周期，移位减法16个时钟周期，输出一个时钟周期。为了优化除法资源和速度，满足更多需求，可以自行设计除法器算法。本文收集整理FPGA除法器常用的算法

方案一 移位相减法

原理：A=B*Q+R; 其中A为被除数，B为除数，Q为商数，R为余数。根据二进制下数值的左右移位等同于此数与2的n次幂的乘法，左移n位后低补零结果等于原数值与2的n次幂的乘积，右移n位后高位补零结果等于原数值除以2的n次幂的结果。利用这个移位的性质，可以实现快速的除法运算。

任意一个是十进制整数可以表示为二进制数的形式，根据二进制左右移位相当于对2的乘除的原理实现A=B*Q+R; 可以由最高位或最低位开始，任意截取连续的几位数据去做运算，相当于原数据进行移位后进行的运算，运算结果只需要再进行逆向的移位操作即可得到正确的结果。

例如：当A=(1011)2 B(0110)2 , 按照上述原理，进行除法运算；

第1步：从A的最高位开始，取最高位1，右移3为到最低位为0001，与被除数0110做比较和减法操作，得到该步骤Qt=0000, Qt左移3位得Qt(3)=0; 余数R=A-B*Qt=1000。

第2步：取A的次高位0得0000，0000+Qt=1000，右移2为到最低位为0010，与被除数0110做比较和减法操作，得到该步骤Qt=0000, Qt左移2位得Qt(2)=0; 余数R=A-B*Qt=1000。

第3步：从A的次次高位1得0010，0010+Qt=1010，右移1为到最低位为0101，与被除数0110做比较和减法操作，得到该步骤Qt=0000, Qt左移1位得Qt(2)=0; 余数R=A-B*Qt=1010。

第4步：从A的次次次高位1得0001，0001+Qt，右移1为到最低位为1011，与被除数0110做比较和减法操作，得到该步骤Qt=0001, Qt左移0位得Qt(2)=1; 余数R=A-B*Qt=0101。

硬件编译简要算法：（采用数据提取、移位、叠加以及合并，全部移位实现）

第一步：数据预处理

1. 被除数A 扩展至其原来宽度2倍，高位补0，例如 A=1011, 则A_KUO=00001011。

2. 被除数B 扩展至其原来宽度2倍，低位补0，例如 B=0011, 则B_KUO=00110000。

3. 商Qt。

第二步：迭代

1. 迭代第1次， A_KUO 左移1位，低位补零，取移位后高半部分数据，A_KUO_h 与被除数B做比较（相当于0001与0011比较）。如果A_KUO_h>B， 则商加Qt=1，否则Qt=0, A_KUO_h=A_KUO_h-B*Qt。此时用Qt取代A_KUO(0)=Qt; 新的A_KUO_H旧的A_KUO_H。

2. 重复步骤4 步，直至数据A的所有位都经过轮询。最后，运算完毕的A_KUO的低半部分即为商，高半部分即为余数。

上述过程只阐述了无符号运算的办法，有符号预算与此方法相同，只是在运算前先将有符号数转换成无符号数运算并提取原数据符号。

总结：该方案迭代除数的数据宽度的位数。

方案二 累加相减法

原理： 采用A=B*Q+R， 从B从0开始进行累加相乘，通过判断R的符号位确定除法商和余数。

方案三 旋转变换法（线性旋转）

原理： 采用A=B*Q+R , 具体参考旋转算法；

方案四 牛顿迭代法（开方法）

a/b相当于计算a*(1/b)，为了使用快速平方根的算法，可以进一步变形为 a\times(1/\sqrt{b})\times(1/\sqrt{b})

a/b 相当求 求 1/(\sqrt{b}) 就是求方程 1/x^2-a=0 的解：