algorithm - 生成从 0 到 n-1 的 nCk 个数字组合

Question

我在硬件领域工作。我需要生成从 0 到 n-1 的所有 nCk 数字组合。使用软件很容易做到这一点，但这需要使用 HDL - VHDL 来完成。我不能在计算复杂性上花费太多，并且需要以 1 个样本/秒的速率生成(每个组合 1 个时钟周期)。中间内存可用。

例如:- 假设对于 6C4，我需要生成

(1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,4,5) (1,2,4,6) (1 ,2,5,6) (1,3,4,5) (1,3,4,6) (1,3,5,6) (1,4,5,6) (2,3,4, 5) (2,3,4,6) (2,3,5,6) (2,4,5,6) (3,4,5,6)

顺序很重要。

编辑:'k' 和 'n' 总是偶数。考虑到这一点，是否有某种方法可以简化逻辑。

在这种情况下，实体的“n”和“k”输入可能会有所不同(“n”的上限为 16)

Answer 1

这基本上是要求以 M 为基数的 N 位数字(在您的示例中，以 6 为基数的 4 位数字)。

鉴于您有可用的存储空间，您基本上可以像这样定义一个 0..M 计数器:

entity counter is
    port(reset : in std_logic; 
         clock : in std_logic;
         count : inout std_logic_vector(2 downto 0);
         carry : out std_logic);

architecture behavioral of counter is
begin
    process(reset, clock) is
    begin
        if reset = '1' then
            count <= "000";
            carry <= '0';
        else if clock = '1' and clock'event then
            count <= (count + 1) mod 6;
            if count = "000" then
                carry <= '1';
            else
                carry <= '0';
            end if;
        end if;
    end process;
end behavioral;

然后实例化 N 个这些计数器。您需要将系统时钟连接到 N 个计数器右侧一个(最低有效位)的时钟输入。对于每个连续的计数器，您需要将较低有效数字计数器的进位输出连接到下一个较高有效数字计数器的时钟输入。

然后您将有更多的电路来驱动各个计数器的复位线，包括系统复位的或从计数器的进位输出到最高有效位(因此您从 0 开始在系统重置时，当您达到所有数字的限制时也环绕到 0000)。

如果您的最大值不是一个常量，您需要为最大值指定一组输入，并且仅当您的当前计数 = 最大计数时才回绕:

entity counter is
    port (reset : in std_logic;
          clock : in std_logic;
          count : inout std_logic_vector(3 downto 0);
          carry : out std_logic;
          max   : in std_logic_vector(3 downto 0));

-- ...

count <= count + 1;
if count = max then
     count <= "0000";
     carry <= '1';
else
     carry <= '0';
end if;

当然，还有一些其他的小细节——我根据单个数字的最大值 6，“手动”将 counter 的大小设置为 3 位.如果您可能需要很多这些，您可以/可以创建一个通用组件，让您在实例化中指定限制，并且(如果内存可用)计算该计数器范围所需的位数。不过，这往往会使代码有点困惑，我想目前这已经足够了。我还设置了输出小端。如果你想要它的大端，你可以将它改为 std_logic_vector(0 to 2) (至少如果我没记错的话——这似乎是对的，但我已经很久没有这样做了编写任何大端逻辑)。