メインコンテンツまでスキップ

4.2. Using Transition Mappings to De-Skew (遷移マッピングを使用したスキュー除去)

4.2. Using Transition Mappings to De-Skew (遷移マッピングを使用したスキュー除去)​

もう 1 つの技術は, 元々 von Neumann [VON_NEUMANN] によるもので, ビットストリームを重複しないペアのシーケンスとして調べることです。次に, 見つかった 00 または 11 のペアを破棄し, 01 を 0 として解釈し, 10 を 1 として解釈できます。1 の確率が 0.5+E で, 0 の確率が 0.5-E であると仮定します。ここで, E は前のセクションで説明したソースの偏心率です。次に, 各ペアの確率は次の表に示されています:

        +------+-----------------------------------------+
        | pair |            probability                  |
        +------+-----------------------------------------+
        |  00  | (0.5 - E)^2          =  0.25 - E + E^2  |
        |  01  | (0.5 - E)*(0.5 + E)  =  0.25     - E^2  |
        |  10  | (0.5 + E)*(0.5 - E)  =  0.25     - E^2  |
        |  11  | (0.5 + E)^2          =  0.25 + E + E^2  |
        +------+-----------------------------------------+

この技術はバイアスを完全に排除しますが, 特定の望ましい出力ビット数に対して不確定な数の入力ビットを必要とします。特定のペアが破棄される確率は 0.5 + 2E^2 であるため, X 出力ビットを生成するために予想される入力ビット数は X/(0.25 - E^2) です。

この技術は, ビットがストリームからのものであり, 各ビットがストリーム内の他のビットと同じ 0 または 1 である確率を持ち, ビットが相関していない, つまり, ビットが同一の独立分布から来ることを前提としています。たとえば, 交互のビットが 2 つの相関したソースからのものである場合, 上記の分析は崩壊します。

上記の技術は, 敵が悪用できるパターンを常に警戒していない場合, 単純な統計分析がどのように誤解を招く可能性があるかの別の例も提供します。アルゴリズムが, 重複しないペアの代わりに重複する連続ビットペアが使用されるように少し誤読された場合, 与えられた統計分析は同じです。しかし, 偏りのない, 相関のない一連のランダムな 1 と 0 を提供する代わりに, ランダムな半分ではありますが, 完全に予測可能な正確に交互する 1 と 0 のシーケンスを生成します。

に最終更新