1

我对多级数据完整性检查和更正感兴趣。使用多个纠错码的地方（它们可以是 2 个相同类型的代码）。我的印象是，如果使用的 2 个哈希码彼此正交，则使用 2 个代码的系统将实现最大效率。

是否有哪些代码与哪些代码正交的列表？或者您是否需要使用相同的散列函数但具有不同的参数或用法？

我希望第一级 ecc 将是一个 reed-solomon 代码，尽管我实际上无法控制第一个函数，因此我不能使用具有改进功能的单个代码。

请注意，我不关心加密安全性。

编辑：这不是

4

1 回答 1

1

我不确定是否可以枚举所有正交散列函数。但是，您只要求提供一些示例，因此我将努力提供一些关于哪些属性似乎导致正交散列函数的一些直觉。

从一个相关的问题来看，这两个函数是相互正交的：

Domain: Reals --> Codomain: Reals
f(x) = x + 1
g(x) = x + 2

这是一个非常明显的案例。如果散列函数（两者）都是完美的散列函数，则更容易确定正交性。请注意，术语“完美”是指数学意义上的，而不是指这些应该用作散列函数的意义上。

完美的散列函数满足正交性要求或多或少是微不足道的。只要函数是单射的，它们就是完美的散列函数，因此是正交的。类似的例子：

Domain: Integers --> Codomain: Integers
f(x) = 2x
g(x) = 3x

在前一种情况下，这是一个单射函数，但不是双射的，因为域中的每个元素都映射到了域中的一个元素，但是域中的许多元素根本没有映射到。这些对于完美的散列和正交性仍然是足够的。（请注意，如果域/共域是实数，这将是双射。）

非单射函数更难分析。但是，如果一个函数是单射的而另一个不是，则它们总是不正交的：

Domain: Reals --> Codomain: Reals
f(x) = e^x // Injective -- every x produces a unique value
g(x) = x^2 // Not injective -- every number other than 0 can be produced by two different x's

因此，一个技巧就是知道一个函数是单射的，而另一个不是。但是，如果两者都不是单射的呢？除了蛮力之外，我目前不知道用于一般情况的算法来确定这一点。

Domain: Naturals --> Codomain: Naturals
j(x) = ceil(sqrt(x))
k(x) = ceil(x / 2)

这两个函数都不是单射的，在这种情况下，因为存在两个明显的非单射函数：ceil并且abs与受限域相结合。（在实践中，大多数散列函数不会有一个比整数更宽松的域。）测试值将显示j当不会时会产生非唯一的结果，k反之亦然：

j(1) = ceil(sqrt(1)) = ceil(1) = 1
j(2) = ceil(sqrt(2)) = ceil(~1.41) = 2
k(1) = ceil(x / 2) = ceil(0.5) = 1
k(2) = ceil(x / 2) = ceil(1) = 1

但是这些功能呢？

Domain: Integers --> Codomain: Reals
m(x) = cos(x^3) % 117
n(x) = ceil(e^x)

在这些情况下，这两个函数都不是单射的（由于模数和 ceil），但是它们何时发生碰撞？更重要的是，对于 x 的哪些值的元组，它们都发生了冲突？这些问题很难回答。我怀疑它们不是正交的，但是如果没有具体的反例，我不确定我能否证明这一点。

当然，这些不是您可能遇到的唯一哈希函数。所以确定正交性的诀窍是首先看看它们是否都是单射的。如果是这样，它们是正交的。其次，看看是否恰好一个是单射的。如果是这样，它们不是正交的。第三，看看你是否能看到导致它们不是单射的函数片段，看看你是否能确定它的周期或特殊情况（例如 x=0）并尝试提出反例。第四，访问math-stack-exchange并希望有人能告诉你他们在哪里破坏了正交性，或者证明他们没有。

于 2014-02-13T16:11:36.643 回答