Generate nCk combinations of numbers from 0 to n-1

Question

I am working in hardware domain. I need to generate all nCk combinations of numbers from 0 to n-1. It is easy to do it using software but this is to be done using HDL - VHDL. I cannot spend much on computational complexity and need to generate at the rate of 1 sample/second (1 clk cycle per combination). Intermediate memory is available.

Eg:- suppose for 6C4, I need to generate

(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)

Order is important.

Edit: 'k' and 'n' are always even. Is there some way to simplify the logic taking this into consideration.

In this case 'n' and 'k' inputs to the entity may vary('n' with a upper limit of 16)

Answer 1

This is basically asking for an N-digit number in base-M (in your example, 4-digit base 6).

Given that you have storage available, you can basically define a 0..M counter something like this:

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;

Then you instantiate N of those counters. You'll wire the system clock to the clock input of the right-hand one (least significant digit) of the N counters. For each successive counter, you'll wire the carry out from the less significant digit's counter to the clock input of the next more significant digit's counter.

You'll then have one more bit of circuitry to drive the reset lines of the individual counters from the inclusive-or of the system reset and the carry-out from the counter for the most significant bit (so you start from 0 at system reset, and also wrap around to 0000 when you reach the limit for all digits).

If your maximum isn't a constant, you need to specify a set of inputs for the maximum, and only wrap around when your current count = the maximum count:

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;

There are, of course, a few other minor details--I've set the size of counter to 3 bits "by hand", based on a maximum value of 6 for an individual digit. If you're likely to need a lot of these, you can/could create a generic component that lets you specify the limit in the instantiation and (if memory serves) compute the number of bits necessary for that range of counter. That tends to obfuscate the code a bit though, and I'd guess this is adequate for the moment. I've also set it up with the output little endian. If you want it big-endian, you'd change it to a std_logic_vector(0 to 2) instead (at least if I recall correctly--it seems right, but it's been a long time since I wrote any big-endian logic).