4.1. Using Stream Parity to De-Skew (ストリームパリティを使用したスキュー除去)

4.1. Using Stream Parity to De-Skew (ストリームパリティを使用したスキュー除去)

簡単ですが特に実用的ではない例として, 十分に長いビット文字列を取り, 文字列を "ゼロ" または "1" にマッピングすることを考えます。マッピングは完全に均一な分布を生成しませんが, 望むほど近づけることができます。目的に役立つ 1 つのマッピングは, 文字列のパリティを取ることです。これには, 推定最大スキューまでのすべてのスキューの程度にわたって堅牢であり, ハードウェアで実装するのが些細であるという利点があります。

以下の分析は, サンプリングする必要があるビット数を示します:

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 のあるデルタ d 以内にしたい場合, 次のようになります:

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

N を解くと, N > log(2d)/log(2E) になります。(2E は 1 未満であるため, その log は負であることに注意してください。負の数で除算すると, 不等式の意味が逆になります。)

次の表は, 50/50 の分布の 0.001 以内に収まるために, さまざまなスキューの程度に対してサンプリングする必要がある文字列の長さ N を示します。

            +---------+--------+-------+
            | 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 サンプルの文字列のパリティは 50/50 の分布の 0.001 以内になることを示しています。しかし, セクション 5.2 で見るように, 利用可能なエントロピーのより多くを抽出するはるかに強力な技術があります。