4.2. Using Transition Mappings to De-Skew (Utilizzo delle Mappature di Transizione per De-skewing)

4.2. Using Transition Mappings to De-Skew (Utilizzo delle Mappature di Transizione per De-skewing)

Un'altra tecnica, originariamente dovuta a von Neumann [VON_NEUMANN], è di esaminare un flusso di bit come una sequenza di coppie non sovrapposte. Si potrebbero quindi scartare qualsiasi coppia 00 o 11 trovata, interpretare 01 come 0 e 10 come 1. Si assuma che la probabilità di un 1 sia 0.5+E e che la probabilità di uno 0 sia 0.5-E, dove E è l'eccentricità della fonte come descritto nella sezione precedente. Allora la probabilità di ogni coppia è mostrata nella seguente tabella:

        +------+-----------------------------------------+
        | 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  |
        +------+-----------------------------------------+

Questa tecnica eliminerà completamente qualsiasi bias ma richiede un numero indeterminato di bit di input per qualsiasi particolare numero desiderato di bit di output. La probabilità che qualsiasi particolare coppia sia scartata è 0.5 + 2E^2, quindi il numero atteso di bit di input per produrre X bit di output è X/(0.25 - E^2).

Questa tecnica presuppone che i bit provengano da un flusso dove ogni bit ha la stessa probabilità di essere uno 0 o 1 come qualsiasi altro bit nel flusso e che i bit non siano correlati, cioè, che i bit provengano da distribuzioni indipendenti identiche. Se i bit alternati provengono da due fonti correlate, ad esempio, l'analisi sopra si rompe.

La tecnica sopra fornisce anche un'altra illustrazione di come un'analisi statistica semplice possa fuorviare se non si è sempre alla ricerca di pattern che potrebbero essere sfruttati da un avversario. Se l'algoritmo fosse letto leggermente male in modo che le coppie di bit successivi sovrapposti fossero utilizzati invece di coppie non sovrapposte, l'analisi statistica data sarebbe la stessa. Tuttavia, invece di fornire una serie non biased e non correlata di 1 e 0 casuali, produrrebbe una sequenza totalmente prevedibile di 1 e 0 esattamente alternati.