# Story:

I have an input bus of 17b = 131 072 values. An output bus of 10b = 1024 values.

Among all the 131 072, only 20 000 values are used and known in advance.

I'd like to map all those 20 000 values to 1024 with the best distribution and the same probability of collisions.

From these 20 000 values, I know which input bits change the least and which ones change the most.

• From Karnaugh, I can get an equation to detect if the input is part of these 20 000 values.
• Knowing the probability of some bits, I can create custom hash with XOR on the least used bits.

I feel like it's reinventing the wheel.

# Questions:

• Is there any known way/algorithm/project?
• Is truncating a known hash (hash-256? or other common hashes) still valid and give the same probability?

The hash must use add, sub, mult, logic gates and shifts only. To be synthesized in RTL.

# Extra question (perfect hash)

Let's say my output is now 15b (32 768 values), all the 20k input values can fit inside. I believe that represents a perfect hash. Is there a simple way of defining the function? Known algorithm? As said, Karnaugh's table can help defining the exact equation but it will greatly depends on the association between input and output values.

### Example:

Let's say I have 4 values coded on 5bits: 2,7,12,28.

My output is 2bits (4 values, enough to map the 4 input values)

Mapping:

0:2
1:7
2:12
3:28


and

0:28
1:2
2:7
3:12


results in a different equation.

Do I need to bruteforce to find the minimal hash?

• Since they are known in advance you could simply precompute a LUT any way you like. I'd start by binning them according to the N (N >=5) LSBs, or fastest moving bits, for the smallest N with <= 1023 values in each bin, reserving the last bin to indicate unused values. That way, bin addr + N LSBs gives you a collision free hash should you want one. May 29 at 13:03