4.2. Using Transition Mappings to De-Skew (Utilisation de mappages de transition pour corriger le biais)

4.2. Using Transition Mappings to De-Skew (Utilisation de mappages de transition pour corriger le biais)

Une autre technique, originalement due à von Neumann [VON_NEUMANN], consiste à examiner un flux de bits comme une séquence de paires non chevauchantes. On pourrait alors rejeter toutes les paires 00 ou 11 trouvées, interpréter 01 comme un 0 et 10 comme un 1. Supposons que la probabilité d'un 1 soit 0.5+E et que la probabilité d'un 0 soit 0.5-E, où E est l'excentricité de la source comme décrit dans la section précédente. Alors la probabilité de chaque paire est montrée dans le tableau suivant:

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

Cette technique éliminera complètement tout biais mais nécessite un nombre indéterminé de bits d'entrée pour un nombre particulier désiré de bits de sortie. La probabilité qu'une paire particulière soit rejetée est 0.5 + 2E^2, donc le nombre attendu de bits d'entrée pour produire X bits de sortie est X/(0.25 - E^2).

Cette technique suppose que les bits proviennent d'un flux où chaque bit a la même probabilité d'être un 0 ou 1 que n'importe quel autre bit dans le flux et que les bits sont non corrélés, c'est-à-dire que les bits proviennent de distributions indépendantes identiques. Si les bits alternés proviennent de deux sources corrélées, par exemple, l'analyse ci-dessus échoue.

La technique ci-dessus fournit également une autre illustration de la façon dont une simple analyse statistique peut induire en erreur si on n'est pas toujours à l'affût de motifs qui pourraient être exploités par un adversaire. Si l'algorithme était légèrement mal lu de sorte que des paires de bits successives chevauchantes soient utilisées au lieu de paires non chevauchantes, l'analyse statistique donnée serait la même. Cependant, au lieu de fournir une série non biaisée et non corrélée de 1 et de 0 aléatoires, elle produirait une séquence totalement prévisible de 1 et de 0 exactement alternés.