algorithmmemory-managementvhdlmemory-addresscodesynthesis

Memory addressing method to allocate memory (static-hardware) for values corresponding to 'nCk' combination of values from 0 to n-1


I need to find a memory addressing method to allocate memory (static-hardware) for values corresponding to 'nCk' combination of values from 0 to n-1.

Assuming 'n' as 6 and 'k' as 4, I need to store values (8 or 16 bit) corresponding to combinations:

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

Once I have the 'k' (4 here) digits, I should be able to directly access the element corresponding to the 'k' tuple.

Any lower index of the k tuple will be less than the higher indices and none of the indices are equal.

Is it possible to generate an addressing scheme to store and retrieve such data without searching? This needs to be done with minimum computation while address is generated and minimum amount of memory possible. (I think that some memory will be wasted irrespective of the method.)

I thought of linear hashing with different constants for different indices but that leads to a lot of memory loss or high computation complexity for calculating the constants.

Any suggestion regarding this problem will be of great help.

Example:

(combination -> corresponding value in memory)

([(1,2,3,4)->14], [(1,2,3,5)->3], [(1,2,3,6)->-4], [(1,2,4,5)->7], [(1,2,4,6)->22], [(1,2,5,6)->-11], [(1,3,4,5)->5], [(1,3,4,6)->3], [(1,3,5,6)->-1], [(1,4,5,6)->9], [(2,3,4,5)->35], [(2,3,4,6)->4], [(2,3,5,6)->7], [(2,4,5,6)->-2], [(3,4,5,6)->6])

If my input for the above module is (2,3,5,6) I should be able to directly get the value (7).

Edit: 'n' and 'k' are always even.


Solution

  • My understanding of the problem

    So, as I understand your question, the possible "keys" used to retrieve your data are a choice of k values among n values.

    With :

    Simple proposition

    Let start by a simple proposition as a reference point.

    You can consider that the values present in your "key" are the bit that must be set to 1 in an 'n' bits address :

    Divide and conquer : n=16, k=2

    Lets take this particular case : n=16, k=2.

    With the preceding solution, we use 2^16 words of memory, whereas there is only 16*15/2 = 120 possible keys.

    For such a case, a divide and conquer strategy can be :

    1. either the two value are both in the first part of the possible values (0 up to 7)
    2. either they are both in the second part of the possible values (8 up to 15)
    3. either one value is in the first part, and the othr value in the second part.

    Using this preliminary test, you can in this case use :

    2^8 + 2^8 + 64 = 576 words

    Divide and conquer : n=16, k=3

    Lets try to do the same with a bigger value of k : k = 3

    The smallest value of the key is between 0 and 13 (because if this is 13, the 2 other values will be 14 and 15). This first set bit can be found quite easily.

    So we can reduce the problem to 14 sub problems (all with k=2, so we can use the previously studied case to optimise memory usage for each of them) :

    I have not done the math, but this probably gives a better memory usage than the initial simple solution.

    "Symmetry" : n=6, k=4

    This si choosing 4 values among 6, so it is equivalent to decide what are the 2 values not choosen, so we are in a case similar to "n=6, k=2" as the memory optimisation is concerned.

    Hope this helps.