How to hash map known values to smaller data width?

Question

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?

Answer 1

You can truncate any "good" hash. Generally speaking, a property of a good hash is that each bit has a random likelihood of being a 1 or a 0. The first few bits of a good hash have this property, so the first few bits of a good hash should also be a good hash.

Answer 2

A cryptographic hash would be overkill. I would just use XORs. Make an equation for each of the 10 bits of the output bin number out of randomly selected bits of the input.

I.E. For each of the input bits give it a 50% chance of being included in the xor equation for a particular output bit.

Test with the 20k inputs, and repeat until you get a nearly even distribution. On average each output bit will use 17/2 input bits, so it will be very efficient.