4.1. Using Stream Parity to De-Skew (Verwendung von Stream-Parität zur Entzerrung)

4.1. Using Stream Parity to De-Skew (Verwendung von Stream-Parität zur Entzerrung)

Als einfaches, aber nicht besonders praktisches Beispiel betrachten Sie das Nehmen einer ausreichend langen Zeichenkette von Bits und die Zuordnung der Zeichenkette zu "null" oder "eins". Die Zuordnung wird keine perfekt gleichmäßige Verteilung ergeben, aber sie kann so nah wie gewünscht sein. Eine Zuordnung, die dem Zweck dient, ist die Parität der Zeichenkette zu nehmen. Dies hat die Vorteile, dass es über alle Grade der Schiefe bis zur geschätzten maximalen Schiefe robust ist und dass es trivial in Hardware zu implementieren ist.

Die folgende Analyse gibt die Anzahl der Bits an, die gesampelt werden müssen:

Angenommen, das Verhältnis von Einsen zu Nullen ist ( 0.5 + E ) zu ( 0.5 - E ), wobei E zwischen 0 und 0.5 liegt und ein Maß für die "Exzentrizität" der Verteilung ist. Betrachten Sie die Verteilung der Paritätsfunktion von N Bit-Samples. Die jeweiligen Wahrscheinlichkeiten, dass die Parität eins oder null sein wird, werden die Summe der ungeraden oder geraden Terme in der Binomialentwicklung von (p + q)^N sein, wobei p = 0.5 + E die Wahrscheinlichkeit einer Eins ist und q = 0.5 - E die Wahrscheinlichkeit einer Null ist.

Diese Summen können leicht berechnet werden als

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

und

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

(Welche Formel der Wahrscheinlichkeit entspricht, dass die Parität 1 sein wird, hängt davon ab, ob N ungerade oder gerade ist.)

Da p + q = 1 und p - q = 2E, reduzieren sich diese Ausdrücke auf

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

und

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

Keiner davon wird jemals genau 0.5 sein, es sei denn, E ist null, aber wir können sie beliebig nahe an 0.5 bringen. Wenn wir wollen, dass die Wahrscheinlichkeiten innerhalb eines Deltas d von 0.5 liegen, z.B., dann

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

Das Lösen nach N ergibt N > log(2d)/log(2E). (Beachten Sie, dass 2E kleiner als 1 ist, sodass sein Logarithmus negativ ist. Division durch eine negative Zahl kehrt den Sinn einer Ungleichung um.)

Die folgende Tabelle gibt die Länge N der Zeichenkette an, die für verschiedene Grade der Schiefe gesampelt werden muss, um innerhalb von 0.001 einer 50/50-Verteilung zu kommen.

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

Der letzte Eintrag zeigt, dass selbst wenn die Verteilung zu 99% zugunsten von Einsen verzerrt ist, die Parität einer Zeichenkette von 308 Samples innerhalb von 0.001 einer 50/50-Verteilung liegen wird. Aber, wie wir in Abschnitt 5.2 sehen werden, gibt es viel stärkere Techniken, die mehr der verfügbaren Entropie extrahieren.