4.1. Using Stream Parity to De-Skew (Utilisation de la parité de flux pour corriger le biais)

4.1. Using Stream Parity to De-Skew (Utilisation de la parité de flux pour corriger le biais)

Comme exemple simple mais pas particulièrement pratique, considérons la prise d'une chaîne suffisamment longue de bits et le mappage de la chaîne vers "zéro" ou "un". Le mappage ne produira pas une distribution parfaitement uniforme, mais il peut être aussi proche que souhaité. Un mappage qui sert l'objectif est de prendre la parité de la chaîne. Cela a les avantages d'être robuste à travers tous les degrés de biais jusqu'au biais maximum estimé et d'être trivial à implémenter en matériel.

L'analyse suivante donne le nombre de bits qui doivent être échantillonnés:

Supposons que le rapport des uns aux zéros soit ( 0.5 + E ) à ( 0.5 - E ), où E est entre 0 et 0.5 et est une mesure de "l'excentricité" de la distribution. Considérons la distribution de la fonction de parité d'échantillons de N bits. Les probabilités respectives que la parité soit un ou zéro seront la somme des termes impairs ou pairs dans l'expansion binomiale de (p + q)^N, où p = 0.5 + E, la probabilité d'un un, et q = 0.5 - E, la probabilité d'un zéro.

Ces sommes peuvent être calculées facilement comme

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

et

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

(Quelle formule correspond à la probabilité que la parité soit 1 dépend de si N est impair ou pair.)

Puisque p + q = 1 et p - q = 2E, ces expressions se réduisent à

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

et

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

Aucune de celles-ci ne sera jamais exactement 0.5 à moins que E soit zéro, mais nous pouvons les rapprocher arbitrairement de 0.5. Si nous voulons que les probabilités soient à un certain delta d de 0.5, par exemple, alors

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

Résoudre pour N donne N > log(2d)/log(2E). (Notez que 2E est inférieur à 1, donc son log est négatif. La division par un nombre négatif inverse le sens d'une inégalité.)

Le tableau suivant donne la longueur N de la chaîne qui doit être échantillonnée pour divers degrés de biais afin d'arriver à 0.001 d'une distribution 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  |
            +---------+--------+-------+

La dernière entrée montre que même si la distribution est biaisée à 99% en faveur des uns, la parité d'une chaîne de 308 échantillons sera à 0.001 d'une distribution 50/50. Mais, comme nous le verrons dans la section 5.2, il existe des techniques beaucoup plus fortes qui extraient davantage de l'entropie disponible.