Создание nCk комбинаций чисел от 0 до n-1

Question

Я работаю в аппаратном домене. Мне нужно сгенерировать все nCk комбинации чисел от 0 до n-1. Это легко сделать с помощью программного обеспечения, но это нужно делать с использованием HDL - VHDL. Я не могу много тратить на вычислительную сложность и должен генерировать со скоростью 1 образец/секунда (1 clk цикл за комбинацию). Доступна промежуточная память.

Например: - пусть для 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' всегда равны. Есть ли способ упростить логику, принимая это во внимание.

В этом случае «п» и «K» входные данные для объекта может изменяться («п» с верхним пределом 16)

Answer 1

В основном это просят N-значное число в базовой-M (в вашем примере, 4-значное основание 6).

Учитывая, что у вас есть в хранилище, вы можете в основном определить 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; 

Есть, конечно, , несколько других мелких деталей - я установил размер counter в 3 бита «вручную», исходя из максимального значения 6 для отдельной цифры. Если вам, вероятно, понадобится много таких, вы можете/могли бы создать общий компонент, который позволяет указать ограничение в экземпляре и (если память служит) вычислить количество бит, необходимое для этого диапазона счетчика. Это, как правило, немного запутывает код, и я предполагаю, что это адекватно на данный момент. Я также установил его с выходом little endian. Если вы хотите это big-endian, вы бы вместо этого изменили его на std_logic_vector(0 to 2) (по крайней мере, если я правильно помню - это кажется правильным, но я давно не писал какую-либо большую логику).