基本原理

若想得到$\frac{y}{x}$的商和余数，一种最直观的想法就是不断地用$y$减掉$x$，直到$y<x$为止，写成伪代码如下

z = 0
while y<x:y -= xz += 1

这种算实在是太低效了，为了用更短的循环计算出结果，我们可以参考小学时候学的长除法算式，按位计算。即从$y$的高位中截取和$x$等长的部分，当二者都用10进制表示时，就是做一次十以内的除法，而这个十以内的除法仍然按照上面的连续减法实现。这样一来，如果$y$比$x$多$N$位，则计算次数从原来的$10^N$成功降到了$10N$，优化效果拉满。

而众所周知，硬件电路中只有$01$，也就是说$y,x$都应该用二进制来表示，如此一来，在进行高位比较时，只需做一次减法即可。从而将$10N$次的减法计算，降低到了${\log }_2(10N)$，这就是移位相减算法，其算法流程为

1. 取$y$的高位数据，位宽和$x$相同。
2. 将$y$高位数据与$x$作比较，如果前者不小于后者，则当前位的商为$1$，两者做差得到第一步的余数；否则商为$0$，将前者直接作为余数。
3. 将上一步中的余数与$y$剩余最高位 1bit 数据拼接成新的数据，再和$x$做比较。可以得到新的商和余数。
4. 重复过程$3$，直到$y$最低位数据也参与计算。

确定除数最高位

尽管verilog中的数据会事先声明长度，但在除法计算时，必须先找到除数真正的最高位，例如$y=4^{\prime }b1111$，$x=4^{\prime }b0001$，二者的商很明显是$4^{\prime }b1111$，但默认$x$长度是4位，则结果为$1$，显然是错的。

下面就是查找最高位的算法，在循环时用到了组合逻辑。

reg start;            //外部给入的开始计算的信号
reg leftDone;	        //找到最高位
reg [31:0] y;
reg [31:0] x;
reg [7:0]  rL;        //x真正的最高位，realLeft
reg signed [7:0] iL;  //用于rL迭代
reg found;				    //标记是否找到最高位parameter xLeft = 31;always@(negedge rst or posedge clk)beginif(!rst)leftDone <= 0;else if (leftDone)leftDone <= 1'b0;else if (start) beginfound = 1'b0;for(iL = xLeft; iL>=0; iL = iL -1)beginif(!found && x[iL])beginrL = iL;found = 1'b1;endendleftDone <= 1'b1;	end
end

其中

• 【start】为外部传来的信号，表示开始计算
• 【leftDone】为1时，表示找到了$x$的最高位，从而开启移位相减算法。这个信号只有一个时钟周期是1，即移位相减算法只需开启一次。
• 【found】为for循环的标志位，当其为1时跳出循环。

移位相减

在找到$x$的最高位之后，就可以开启移位相减法了，代码如下

reg [39:0] res;
reg divStart;			  //开始除法
reg calcDone;
reg [20:0] rem;			//余数，其中20位有效
reg [4:0] iDiv;			//除法器位数parameter resLen = 40;
parameter yLeft = 39;	//sx最高位always@(negedge rst or posedge clk) beginif(!rst)beginres <= 0;calcDone <= 0;divStart <= 0;iDiv <= resLen;end else beginif(calcDone)calcDone <= 0;else if(leftDone)begindivStart <= 1;rem <= y >> (yLeft-rL);   //当前余数iDiv <= yLeft-rL;         //iDiv 初始化end else if(divStart) beginif(iDiv==0)begindivStart <= 0;calcDone <= 1;end else if(iDiv > 0)beginif(rem >= x) beginres[iDiv] <= 1'b1;rem <= ((rem-x)<<1) + y[iDiv-1];end else beginres[iDiv] <= 1'b0;rem <= (rem<<1) + y[iDiv-1];endendiDiv <= iDiv -1;endend
end

其中

• 【divStart】为1时，可以进行移位。其开启方式为leftDone为1，即确认查找到$x$的最高位之后。
• 【calcDone】为计算成功的标志位，与leftDone一样，也只有一个时钟周期是1。该信号用于输出给其他模块。
• 【rem】为移位相减的临时除数，本算法并不会保留余数。
• 【iDiv-1】为$y$被纳入计算的最低位。

移位相减的核心代码如下，其基本逻辑是，若当前余数大于$x$，则在res对应的位上置1，同时将rem-x与$y$的下一位合并，作为接下来与$x$相比较的数；若当前余数小于$x$，则在res对应的位上置0，并将rem与$y$的下一位合并。

if(rem >= x) beginres[iDiv] <= 1'b1;rem <= ((rem-x)<<1) + y[iDiv-1];
end else beginres[iDiv] <= 1'b0;rem <= (rem<<1) + y[iDiv-1];
end