用二进制实现8位数除以3 (11)的硬件
我想在Xilinx设备上创建一个原理图，将任何8位数除以3，以防这件事发生。
例如，硬件接受两个输入(111101)和(11)，并返回两个数字的除法，即010100。
我不需要担心剩余--只是需要商数
回答 2
Stack Overflow用户
发布于 2022-05-09 14:15:49
至少有两种方法适合HW的实现；
multiplication互惠
倒数乘法是从(x*K)>>N计算的，在这里，K可以是ceil(512/3) = 171 0b10101011 = 9 * 19, N = 9。因式分解很有帮助，因为一个数字很容易乘以9= 0b1001和19 = 0b10011。乘9是由一个加法和一个自由移位，乘以19是由2个自由移位(布线)和2个加法。总成本== 3的增加。
- (non)-restoring部门
就像在小学学到的一样，长间隔可以很容易地转换成HW电路。
00101001 = 41
11 -> trial "subtraction" fails, result bit = 0
00101001
11 -> trial subtraction fails, result bit = 0
00101001
11 -> trial subtraction fails = 0
00101001 -> pass = 1
(011)
------
10001 -> pass
11
-----
101 -> fail
11
-----
101 -> pass
11
Result = b0001101 = 13不需要计算实际的试差，因为除数是常数。相反，有一个快速表达式Passed = top|(mid & bottom)。同样，在每一阶段都可以形成这三个输出的逻辑表达式。
从top = 0、mid = input:7、bot = input:6开始，需要迭代超过7个位置，计算R=Result、Top、来自top、mid、bot的中间位置。
The logical expressions for each stage are then
top mid bot R T M B
--------------------------
0 0 0 0 0 0 R = t+mb
0 0 1 0 0 1 T = ~bm+tb
0 1 0 0 1 0 M = ~bt+~t~mb
0 1 1 1 0 0 B = next bit from input
1 0 0 1 0 1
1 0 1 1 1 0
1 1 0 x x x
1 1 1 x x x x = don't care as impossible
- 256x7 LUT使用16位LUTS
完成
还可以使用16位LUTs的层次结构来实现1x256位LUT .32位LUT =多路复用(bits4，LUT0(bits3 3:0)，LUT1(bits3 3:0))；单个256输入LUT将需要16位16位LUT和15位/比特多路复用器，或者1680 LogicElements没有先进的构建块。这假设每个LE可以实现任意16位LUT (4个输入，1个输出)，这在90年代末已经是惯例了。复用器符合这些限制条件，因为它只是一个自定义的3输入逻辑函数，其中16位LUT是一个自定义4输入逻辑函数。
- 256x7位LUT使用内存
有些FPGA确实有专用的LUT部分，在这些情况下，256 x7位LUT可能是一个很好的解决方案。最小的门计数将是7个寄存器(+内存)，但我希望内存访问将引入大量的元素作为驱动程序。
- 拆分LUT由Fuz
就区域而言，这与长除法不相上下。它有较小的延迟，但更大的扇出。
比较
使用典型的FPGA单元的面积估计将类似于使用加法的9+7+13单元，以及可能使用长除法的7x3。
+---------------+-----------------+
| Method | Area |
+---------------+-----------------+
| 1. reciprocal | ~30 |
| 2. division | 21 |
| 3. 16-bit LUT | 1680 |
| 4. 256x8-LUT | 7-100 + Memory |
| 5. Fuz 2xLUT | 22 |
+---------------+-----------------+免责声明:我预计在过去的20年中，逻辑合成器会有一些进展甚至可能有一种可能性，可以手动列出逻辑单元和连接--对Altera来说，我没有这样的运气，逻辑、布局和路由都是由Verilog或VHDL自动合成的，结果往往很尴尬。
Stack Overflow用户
发布于 2022-05-09 16:03:29
一个很好的折衷方案可能是使用一堆查找表。伪代码如下所示：
# look up table for the high part
# returns 7 bit quotient, 2 bit remainder
# in case you have 8 bit luts, you can save
# one LUT by replacing the high bit with x[2]&x[3]
lut_hi(x[4]) =
0000 => 0000000:00
0001 => 0000101:01
0010 => 0001010:10
0011 => 0010000:00
0100 => 0010101:01
0101 => 0011010:10
0110 => 0100000:00
0111 => 0100101:01
1000 => 0101010:10
1001 => 0110000:00
1010 => 0110101:01
1011 => 0111010:10
1100 => 1000000:00
1101 => 1000101:01
1110 => 1001010:10
1111 => 1010000:00
# look up table for the low part
# returns 3 bit quotient, 2 bit remainder
# you can once again save a bit by replacing
# the high bit with x[2]&x[3]
lut_lo(x[4]) =
0000 => 000:00
0001 => 000:01
0010 => 000:10
0011 => 001:00
0100 => 001:01
0101 => 001:10
0110 => 010:00
0111 => 010:01
1000 => 010:10
1001 => 011:00
1010 => 011:01
1011 => 011:10
1100 => 100:00
1101 => 100:01
1110 => 100:10
1111 => 101:00
# combine two remainders into
remainders(a[2], b[2]) =
return a[1]&b[1] | (a[0]|b[0])&(a[1]|b[1])
# divide by 3: look up the two halves, sum them, apply carry
div3(x[8]) =
q_lo:r_lo = lut_lo(x[0:3])
q_hi:r_hi = lut_hi(x[7:4])
return q_lo + q_hi + remainders(r_lo, r_hi)这段代码的工作方式是将数字分成两小部分，将每一小数除以3，然后对商数进行求和。
https://stackoverflow.com/questions/72172637
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号