跳到主要内容

4.1. Using Stream Parity to De-Skew (使用流奇偶校验去偏斜)

4.1. Using Stream Parity to De-Skew (使用流奇偶校验去偏斜)​

作为一个简单但不太实用的例子, 考虑取一个足够长的比特字符串并将该字符串映射到"零"或"一"。映射不会产生完全均匀的分布, 但可以达到所需的接近程度。一个达到目的的映射是取字符串的奇偶校验。这具有以下优点: 它对所有偏斜程度都是鲁棒的直到估计的最大偏斜, 并且在硬件中实现起来微不足道。

以下分析给出了必须采样的比特数:

假设1和0的比例为 (0.5 + E) 比 (0.5 - E), 其中E在0和0.5之间, 是分布"偏心度"的度量。考虑N个比特样本的奇偶校验函数的分布。奇偶校验为1或0的各自概率将是 (p + q)^N 的二项展开式中奇数或偶数项的和, 其中p = 0.5 + E, 即1的概率, q = 0.5 - E, 即0的概率。

这些和可以很容易地计算为

                     N            N
    1/2 * ( ( p + q )  + ( p - q )  )

和

                     N            N
    1/2 * ( ( p + q )  - ( p - q )  ).

(哪个公式对应于奇偶校验为1的概率取决于N是奇数还是偶数。)

由于p + q = 1且p - q = 2E, 这些表达式简化为

                   N
    1/2 * [1 + (2E)  ]

和

                   N
    1/2 * [1 - (2E)  ].

除非E为零, 否则这些都不会恰好是0.5, 但我们可以使它们任意接近0.5。例如, 如果我们希望概率在0.5的某个delta d范围内, 那么

                        N
    ( 0.5 + ( 0.5 * (2E)  ) )  < 0.5 + d.

求解N得到 N > log(2d)/log(2E)。(注意2E小于1, 所以其对数是负数。除以负数会反转不等式的方向。)

下表给出了对于各种偏斜程度必须采样的字符串长度N, 以便达到在0.001范围内的50/50分布。

            +---------+--------+-------+
            | Prob(1) |    E   |    N  |
            +---------+--------+-------+
            |   0.5   |  0.00  |    1  |
            |   0.6   |  0.10  |    4  |
            |   0.7   |  0.20  |    7  |
            |   0.8   |  0.30  |   13  |
            |   0.9   |  0.40  |   28  |
            |   0.95  |  0.45  |   59  |
            |   0.99  |  0.49  |  308  |
            +---------+--------+-------+

最后一项表明, 即使分布偏向1达到99%, 308个样本的字符串的奇偶校验也将在0.001范围内达到50/50分布。但是, 正如我们将在第5.2节中看到的, 有更强的技术可以提取更多可用的熵。

最后于 更新