5.1. A Trivial Mixing Function (一个简单的混合函数)

5.1. A Trivial Mixing Function (一个简单的混合函数)

出于说明目的, 我们使用异或 (XOR) 函数描述一个单比特输入的简单示例。该函数等同于无进位加法, 如下表所示。这是一个退化的情况, 其中一个输出比特总是因任一输入比特的改变而改变。但是, 尽管它很简单, 它提供了一个有用的说明。

        +---+---+-----+
        | I | J | XOR |
        +---+---+-----+
        | 0 | 0 |  0  |
        | 0 | 1 |  1  |
        | 1 | 0 |  1  |
        | 1 | 1 |  0  |
        +---+---+-----+

假设输入I和J是两个独立的随机比特, 其中1的概率分别为P sub I和P sub J。假设它们被组合在一起以产生输出, 如上表所示。然后, 输出为1的概率为

P sub I * ( 1 - P sub J ) + ( 1 - P sub I ) * P sub J

它始终位于P sub I和P sub J之间。因此, 如果以任何合理的方式组合任意数量的不相关输入, 输出不会比最好的输入更偏斜, 并且可能更好 (更接近0.5)。如果两个输入都是0.5, 则输出也是0.5。

然而, 如果两个输入是相关的, 特别是如果它们是相同的, 则输出可以更偏斜。例如, 如果这两个输入是相同的, P sub I = P sub J, 并且上式简化为

2 * P sub I * ( 1 - P sub I )

在P sub I为0或1时, 该表达式为零。因此, 如果输入始终为零 (或始终为一), 则输出也将始终为零。这对于任何合理的函数都是如此, 包括更强大的函数, 并且强调了混合相关源的无效性。