1
\$\begingroup\$

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?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ May 29 at 13:03
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks, also using XOR on bits should keep the probability too. That's good to know for generic data. I believe we can optimize more with my restrictions. \$\endgroup\$
    – Alexis
    May 28 at 23:24
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Very true. The only reason you might need a cryptographic hash would be if you might have an opponent selecting those 20k inputs explicitly to maximize collisions, and collisions could be sufficiently damaging to the algorithm. \$\endgroup\$
    – Cort Ammon
    May 30 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.