4.1. Using Stream Parity to De-Skew (Utilizzo della Parità di Flusso per De-skewing)

4.1. Using Stream Parity to De-Skew (Utilizzo della Parità di Flusso per De-skewing)

Come esempio semplice ma non particolarmente pratico, si consideri di prendere una stringa di bit sufficientemente lunga e mappare la stringa a "zero" o "uno". La mappatura non produrrà una distribuzione perfettamente uniforme, ma può essere vicina quanto desiderato. Una mappatura che serve allo scopo è prendere la parità della stringa. Questo ha i vantaggi che è robusta attraverso tutti i gradi di skew fino allo skew massimo stimato e che è banale da implementare in hardware.

L'analisi seguente fornisce il numero di bit che devono essere campionati:

Si supponga che il rapporto di uno a zero sia ( 0.5 + E ) a ( 0.5 - E ), dove E è tra 0 e 0.5 ed è una misura dell'"eccentricità" della distribuzione. Si consideri la distribuzione della funzione di parità di campioni di N bit. Le rispettive probabilità che la parità sarà uno o zero saranno la somma dei termini dispari o pari nell'espansione binomiale di (p + q)^N, dove p = 0.5 + E, la probabilità di un uno, e q = 0.5 - E, la probabilità di uno zero.

Queste somme possono essere calcolate facilmente come

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

e

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

(Quale formula corrisponde alla probabilità che la parità sarà 1 dipende dal fatto che N sia dispari o pari.)

Poiché p + q = 1 e p - q = 2E, queste espressioni si riducono a

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

e

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

Nessuna di queste sarà mai esattamente 0.5 a meno che E sia zero, ma possiamo avvicinarle arbitrariamente a 0.5. Se vogliamo che le probabilità siano entro un certo delta d di 0.5, ad esempio, allora

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

Risolvendo per N si ottiene N > log(2d)/log(2E). (Si noti che 2E è inferiore a 1, quindi il suo logaritmo è negativo. La divisione per un numero negativo inverte il senso di una disuguaglianza.)

La seguente tabella fornisce la lunghezza N della stringa che deve essere campionata per vari gradi di skew per arrivare entro 0.001 di una distribuzione 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  |
            +---------+--------+-------+

L'ultima voce mostra che anche se la distribuzione è skewed al 99% a favore degli uni, la parità di una stringa di 308 campioni sarà entro 0.001 di una distribuzione 50/50. Ma, come vedremo nella sezione 5.2, ci sono tecniche molto più forti che estraggono più dell'entropia disponibile.