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

Question

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

例如，硬件采用两个输入 (111101) 和 (11) 和 returns 两个数字的除法，即 010100。

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

Answer 1

至少有两种方法适用于硬件实现；

倒数乘法

倒数乘法是从 (x*K)>>N 计算得出的，在这种情况下 K 可能是 ceil(512/3) = 171 0b10101011 = 9 * 19, N = 9。分解有帮助，因为一个数字很容易乘以 9 = 0b1001 和 19 = 0b10011。乘以 9 是通过一次加法和一次自由移位完成的，乘以 19 是通过 2 次自由移位（接线）和 2 次加法完成的。总成本 == 3 次添加。

(非)-恢复分裂

就像小学学的一样，很长的除法可以很容易的转换成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 个位置，从 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 位 LUT 的层次结构实现 1x256 位 LUT。 32 位 LUT = 多路复用（位[4]，LUT0（位[3:0]），LUT1（位[3:0]））；单个 256 条目 LUT 需要 16 个 16 位 LUT 和每位 15 个多路复用器，或者 1680 个没有高级构建块的 LogicElements。这假设每个 LE 都可以实现任意 16 位 LUT（4 个输入，1 个输出），这在 90 年代后期已经成为惯例。多路复用器符合这些限制，因为它只是一个自定义的 3 输入逻辑函数，而 16 位 LUT 是一个自定义的 4 输入逻辑函数。

256x7 位 LUT 使用内存

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

通过 Fuz 拆分 LUT

Area-wise这与长除法不相上下。它具有更小的延迟，但更大的扇出。

比较

使用加法方法使用典型的 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，然后对商求和。

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

Implementing hardware that divides an 8 bit number by 3 (11) in binary

assembly

integer-division

xilinx

hardware-programming

xilinx-ise