Cheap hash of three inputs independent of their order

Question

I have a module that takes three inputs, each of which is three bits wide.

output = f(inputA, inputB, inputC)

The output depends on the values of the three inputs but does not depend on their order.

i.e. f(inputA, inputB, inputC) = f(inputB, inputC, inputA)

The solution should work well for both FPGAs and ASICs. Currently I am implementing it without taking advantage of the symmetry, but I assume that explicitly forcing the synthesizer to consider the symmetry will result in a better implementation.

I am planning on implementing this using a hash, h, of the three inputs that does not depend on their order. I can then do:

hash <= h(inputA, inputB, inputC);

output <= VALUE0 when hash = 0 else
          VALUE1 when hash = 1 else
          .....

My question is what should I use for the hash function?

My thoughts so far:

If each input is 3 bits wide there are 512 possibilities, but only 120 when you consider the symmetry, so theoretically I should be able to use a hash that is 7 bits wide. Practically it may need to be longer.

Each bit of the hash is a function of the input bits and must respect the symmetry of the three inputs. The bits of the hash should be independent from one another. But I'm not sure how to generate these functions.

Answer 1

As mentioned in your question, you could sort and concatenate your inputs.

In pseudo code:

if (A < B)
    swap(A, B);
if (B < C)
    swap(B, C);
if (A < B)
    swap(A, B);

As block diagram:

The 6-in/6-out function needed for a "conditional swap" block:

A3x = A3 B3 ;
A2x = A3 B3' B2  + A3' A2 B3  + A2 B2 ;
A1x = A2 B3' B2' B1 + A3' A2' A1 B2  + A3 A2 B2' B1 
    + A2' A1 B3 B2  + A3 B3' B1 + A3' A1 B3  + A1 B1;
B3x = B3  + A3 ;
B2x = A3' B2  + A2 B3'  + B3 B2  + A3 A2 ;
B1x = A3' A2' B1 + A1 B3' B2'  + A2' B3 B1 + A3 A1 B2'  
    + A3' B2 B1 + A2 A1 B3'  + A3' B3 B1 + A3 A1 B3'  
    + B3 B2 B1 + A3 A2 A1 ;

I have to admit that this solution is not exactly "cheap" and results in a 9-bit hash rather than in a 7-bit hash. Therefore, a look-up table might in fact be the best solution.