獨立於訂單的三個輸入的廉價散列

我有一個需要三個輸入的模塊，每個輸入都是三位寬。獨立於訂單的三個輸入的廉價散列

output = f(inputA, inputB, inputC)

輸出取決於三個輸入的值，但不取決於它們的順序。

即f(inputA, inputB, inputC) = f(inputB, inputC, inputA)

該解決方案應該兩個FPGA和ASIC工作良好。目前我正在實施它，但沒有利用對稱性，但我認爲明確強制合成器考慮對稱性會導致更好的實現。

我正在計劃使用不依賴於它們順序的三個輸入的散列h來執行此操作。我可以這樣做：

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

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

我的問題是我應該用什麼散列函數？

我的想法至今：

如果每個輸入爲3個位寬，有512級的可能性，但只有120當你考慮對稱性，所以理論上我應該能夠使用哈希是7位寬。實際上它可能需要更長一些。

散列的每一位都是輸入位的函數，並且必須尊重三個輸入的對稱性。散列的位應該彼此獨立。但我不確定如何生成這些功能。

來源

2014-11-14 Ben Reynwar

此外，我已經嘗試使用一個排序函數作爲散列，它返回按升序排序的輸入並連接，但是這個操作太昂貴，幾乎否定了能夠使用較小查找表的優點。 – 2014-11-14 18:38:33

一個直接的建議是使用'hash = xor b xor c'，但這當然只有3位寬 - 我不知道這是否足夠滿足您的目的。 – 2014-11-14 18:59:43

我需要獨特的哈希表示哈希必須至少有7位長。但是，是的，對於那些成爲三位的人來說，這肯定是有意義的。 – 2014-11-14 19:07:31

正如您的問題所述，你可以排序和連接你的輸入。

在僞碼：

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

如框圖：

enter image description here

的6英寸/所需的「條件交換」塊6輸出功能：

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 ;

我不得不承認，這個解決方案並不完全「便宜」，並導致9位散列而不是7位散列。因此，查找表實際上可能是最好的解決方案。

來源

2014-11-15 11:00:44

獨立於訂單的三個輸入的廉價散列

回答

相關問題