实现将 8 位数字除以 3 (11) 的二进制硬件

Question

我想在 Xilinx 设备上创建一个将任何 8 位数字除以 3 的原理图，以防万一。

例如，硬件接受两个输入 (111101) 和 (11)，并返回两个数字的除法，即 010100。

我不需要担心余数 - 只需要商

Answer 1

至少有两种方法适合硬件实施；

1. 倒数乘法

倒数乘法是根据

(x*K)>>N

计算的，在本例中

K

可以是

ceil(512/3) = 171 0b10101011 = 9 * 19, N = 9

。因式分解很有帮助，因为数字很容易乘以 9 = 0b1001 和 19 = 0b10011。乘以 9 是通过 1 次加法和 1 次自由移位完成的，乘以 19 是通过 2 次自由移位（连线）和 2 次加法完成的。总成本 == 3 添加。

2. （非）-恢复分裂

就像小学时学到的那样，长除法可以轻松转换为硬件电路。

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个位置，从

top

、

mid

、

bot

计算R=Result、Top、Mid。

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

3. 使用 16 位 LUTS 完成 256x7 LUT

还可以使用 16 位 LUT 层次结构来实现 1x256 位 LUT。 32 位 LUT = 多路复用(bits[4], LUT0(bits[3:0]), LUT1(bits[3:0]));单个 256 条目 LUT 将需要 16 个 16 位 LUT 和每位 15 个多路复用器，或者在没有高级构建块的情况下需要 1680 个 LogicElement。这假设每个 LE 可以实现任意 16 位 LUT（4 个输入，1 个输出），正如 90 年代末已经习惯的那样。多路复用器满足这些限制，因为它只是一个自定义的 3 输入逻辑函数，而 16 位 LUT 是一个自定义的 4 输入逻辑函数。

4. 使用内存的256x7位LUT

一些 FPGA 确实有专用的 LUT 部分，在这些情况下，256x7 位 LUT 可能是一个很好的解决方案。最小门数为 7 个寄存器（+内存），但我希望内存访问能够引入大量元素作为驱动程序。

5. Fuz 分割 LUT

就面积而言，这与长除法相当。它具有较小的延迟，但较大的扇出。

比较

使用典型 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 年里逻辑合成器会取得一些进步——人们可能可以使用 System-C 生成一个好的分频器。甚至可能有可能手动布局逻辑单元和连接——在 Altera 中我没有这样的运气，逻辑、布局和布线是从 Verilog 或 VHDL 自动合成的，通常会产生令人尴尬的结果。

Answer 2

一个好的折衷方案可能是使用一堆查找表。伪代码如下所示：

# 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，然后将商相加。

Answer 3

硬件除以 3有不同的方法。

一种是从“标准数组除法器”开始，并简化为除数 3。

我勾画了一个“one-hot”实现；对于 8 位被除数，在右侧添加另一个位对，省略 LSB 进位/余数逻辑（“最右边的水平与或反转门”）。
falstad.com Circuitjs 的单热除以 3：

但是你可以“使用标准组件”（例如减法器，或者加法器+反相器）来计算“精确”除以 3 - 问题是：精确除法 意味着仅适用于 3 的倍数。