5.1. A Trivial Mixing Function (Une fonction de mélange triviale)

5.1. A Trivial Mixing Function (Une fonction de mélange triviale)

À des fins d'exposition, nous décrivons un exemple trivial pour les entrées de bits uniques utilisant la fonction Ou Exclusif (XOR). Cette fonction est équivalente à l'addition sans retenue, comme le montre le tableau ci-dessous. C'est un cas dégénéré dans lequel le bit de sortie unique change toujours pour un changement dans l'un ou l'autre bit d'entrée. Mais, malgré sa simplicité, elle fournit une illustration utile.

            +-----------+-----------+----------+
            |  input 1  |  input 2  |  output  |
            +-----------+-----------+----------+
            |     0     |     0     |     0    |
            |     0     |     1     |     1    |
            |     1     |     0     |     1    |
            |     1     |     1     |     0    |
            +-----------+-----------+----------+

Si les entrées 1 et 2 sont non corrélées et combinées de cette façon, alors la sortie sera un bit aléatoire encore meilleur (moins biaisé) que ne le sont les entrées. Si nous supposons une "excentricité" E comme définie dans la Section 4.1 ci-dessus, alors l'excentricité de sortie se rapporte à l'excentricité d'entrée comme suit:

    E       = 2 * E        * E
     output        input 1    input 2

Puisque E n'est jamais supérieur à 1/2, l'excentricité est toujours améliorée, sauf dans le cas où au moins une entrée est une constante totalement biaisée. Ceci est illustré dans le tableau suivant, où les valeurs du haut et du côté gauche sont les deux excentricités d'entrée et les entrées sont l'excentricité de sortie:

 +--------+--------+--------+--------+--------+--------+--------+
 |    E   |  0.00  |  0.10  |  0.20  |  0.30  |  0.40  |  0.50  |
 +--------+--------+--------+--------+--------+--------+--------+
 |  0.00  |  0.00  |  0.00  |  0.00  |  0.00  |  0.00  |  0.00  |
 |  0.10  |  0.00  |  0.02  |  0.04  |  0.06  |  0.08  |  0.10  |
 |  0.20  |  0.00  |  0.04  |  0.08  |  0.12  |  0.16  |  0.20  |
 |  0.30  |  0.00  |  0.06  |  0.12  |  0.18  |  0.24  |  0.30  |
 |  0.40  |  0.00  |  0.08  |  0.16  |  0.24  |  0.32  |  0.40  |
 |  0.50  |  0.00  |  0.10  |  0.20  |  0.30  |  0.40  |  0.50  |
 +--------+--------+--------+--------+--------+--------+--------+

Cependant, notez que les calculs ci-dessus supposent que les entrées ne sont pas corrélées. Si les entrées étaient, disons, la parité du nombre de minutes depuis minuit sur deux horloges précises à quelques secondes près, alors chacune pourrait sembler aléatoire si échantillonnée à des intervalles aléatoires beaucoup plus longs qu'une minute. Pourtant, si elles étaient toutes deux échantillonnées et combinées avec XOR, le résultat serait zéro la plupart du temps.