Surjective mapping constraint

SystemVerilog
,
1

Hi,

I have two groups of items A and B such that the size of group A is greater or equal to the size of group B.
How can I create a mapping array that maps items from group A to items in group B, such that all items in group B are mapped.

for instance, if A={0,1,2,3,4,5} and B={0,1,2} so
'{0,1,1,0,2,1} is a valid mapping
but '{0,1,1,0,0,1} is not a valid mapping since ‘2’ of group B is not mapped

2

Your question is missing some details. Are there three groups of items: A, B, and the mapping array? Or is A the mapping array? How do the initial values 0-5 of group A work in the mapping algorithm?

From the example you gave, it appears that every value in group B must appear at least once in the mapping array,

3

Groups A and B are given, I want to create a random array which it’s indices represent elements from group A and the values represents element from group B - in that way I map each index to value.

In mathematical form, I want to randomize a function f:A->B, so that for every value b in group B there is a value a in group A such that f(a)=b.

Maybe the structure of array is confusing, here is how I thought to do it using an associative array:

int A[6] = '{0,1,2,3,4,5};
int B[3] = '{0,1,2};

rand int mapping_array[int];

constraint surjective_mapping_c {
    foreach (A[i]) {
        mapping_array[A[i]] inside {B};
    }
}

but I’m missing the constraint to ensure all B’s values are used in the mapping array

4

More details needed:

  1. Could the mapping_array have more elements than the number in A? (i.e. could there be a mapping_array[7]) If so, are there any constraints on those element’s values?
  2. Are the values in A and B guaranteed to be unique?

Realize that a constraint cannot construct elements of an associative array. You have to allocate elements before calling randomize.

5

Sure,

  1. There is no meaning for key which is not in A, so I would say that mapping_array must be as the size of A.
  2. Yes, the values in A and B guaranteed to be unique

Is there a better data structure to implement this other than associative array?

6

Now there is enough information to suggest a solution.

class example;
  int A[6] = '{10,1,2,3,4,5};
  int B[3] = '{0,1,2};
  rand int mapping_array[int];
  
  function void pre_randomize();
    // construct associative array before randomization
    mapping_array = '{};
    foreach (A[i]) mapping_array[A[i]] = 0;
  endfunction
  
  constraint surjective_mapping_c {
    // each element of m_a must be in B
    foreach (mapping_array[i]) 
        mapping_array[i] inside {B};
    //B’s values are used at least once in the mapping array
      foreach (B[i]) 
        mapping_array.or() with (item == B[i]);
    }
endclass

module top;
  example h = new;
  initial repeat(5) begin
    assert( h.randomize() );
    $display("%p",h.mapping_array);
  end
endmodule

Cannot suggest a better structure to implement without knowing how you plan to use the results.