整数除以 3 的简单方法

Question

我正在从事一个项目，即在 FPGA 上制作一个简单的音乐播放器。它从 PC 中获取指定格式的音乐文件并循环大声播放。

我们需要实现标准音符长度，即颤音表示半拍，最小音符表示 2 拍等。目前我们有一个 table 的节拍长度，以不同的时钟周期数表示BPM 值。我们需要将它们乘以这些音符长度以产生正确的时钟周期。唯一的问题是 Tuplet，这是一个完整节拍的三分之一。

在不实现成熟的除法电路的情况下，是否可以使用任何数学技巧将一个整数大约除以 3？

Answer 1

除以 3 等于乘以 1/3 (=0.33333)。 0.3333 可以表示为两个或更多（取决于所需的精度）（左）移位输入值的加法。

input*2^-a + input*2^-b + input*2^-c ...

只需为 a、b、c 找到合适的值...

这适用于（几乎）所有部门。

Answer 2

以下是 Hank Warren 的 Hacker's Delight 中部分代码的 VHDL 翻译。它将一个无符号整数除以常数值 3，仅使用移位、加法和乘以常数值 3 和 5（也可以简化为移位和加法）。

-- q is quotient, d is dividend
q := (d srl 2) + (d srl 4); -- q = d*0.0101 (approx)
q := q + (q srl 4); -- q = d*0.01010101
q := q + (q srl 8);
q := q + (q srl 16);
r := resize(d - q * 3, 32); -- 0 <= r <= 15.
q := resize(q + (5 * (r + 1) srl 4), 32);

Answer 3

如果长度为LEN的无符号值需要整数除以3（x / 3）的精确结果，则可以使用一些小技巧来使用截断整数运算。 1/3 的常量的长度应为 LEN + 1 并应添加 1。然后可以在之后使用截断。伪代码为：

C = 2 ** (LEN + 1) / 3 + 1
y = (x * C) / 2 ** (LEN + 1)

显示和测试所有值的算法的 Python 函数是：

def div_by_3_test(LEN):
    DIVISOR = 3
    C = 2 ** (LEN + 1) // DIVISOR + 1
    for x in range(2 ** LEN):
        if (x * C) // 2 ** (LEN + 1) != x // DIVISOR: exit('Failed')

实现此功能的 VHDL 模块：

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity div_by_3 is
  generic(
    LEN : natural := 12);
  port(
    x_i   : in  std_logic_vector(LEN - 1 downto 0);
    y_o   : out std_logic_vector(LEN - 1 downto 0));
end entity;

architecture syn of div_by_3 is
  -- Constant to multiply, basically 1/3, but adding 1 to avoid error
  constant C : std_logic_vector(LEN - 1 + 1 downto 0) :=
    std_logic_vector(to_unsigned(2 ** (LEN + 1) / 3 + 1, LEN + 1));
  -- Intermediate, with length as 2 * LEN + 1
  signal t : std_logic_vector(2 * LEN + 1 - 1 downto 0);
begin
  -- Intermediate with full length result
  t <= std_logic_vector(unsigned(C) * unsigned(x_i));
  -- Result after truncation for division by LEN + 1
  y_o <= t(2 * LEN + 1 - 1 downto LEN + 1);
end architecture;

优点是 LEN 位数除以 3 可以在一个周期内仅使用单个 2 * LEN + 1 位乘法。

可以添加寄存器以允许流水线进行高速设计。

请注意，任何除数都可以采用类似的方案，但 C 的长度必须为 LEN + ceil(log2(DIVISOR))，并相应地缩放 C。请参阅 https://math.stackexchange.com/q/2444306/275980 关于数学基础。

Answer 4

如dieli所述，乘以0.333333。

但是，不要使用 2 的几个负次方（即 a、b、c、..），只需将 1/3 乘以 2 的某个大次方即可，例如2^24 * (1/3) = 5592405。将时钟周期和 5592405 相乘后，除以 2^24.

B = (时钟周期)*5592405

结果=B/2^24

B 的大小取决于时钟周期的最大大小，可以通过

计算

B 的最大寄存器大小 = ((log10((时钟周期的最大大小)*5592405)/log10(2)) + 0.5) 的整数

整数除以 3 的简单方法

Easy way of dividing an integer by 3

vhdl

boolean-logic

circuit