4.2. Using Transition Mappings to De-Skew (Verwendung von Übergangszuordnungen zur Entzerrung)
4.2. Using Transition Mappings to De-Skew (Verwendung von Übergangszuordnungen zur Entzerrung)
Eine andere Technik, ursprünglich von von Neumann [VON_NEUMANN], besteht darin, einen Bitstrom als Sequenz nicht-überlappender Paare zu untersuchen. Man könnte dann alle gefundenen 00- oder 11-Paare verwerfen, 01 als 0 interpretieren und 10 als 1. Nehmen Sie an, dass die Wahrscheinlichkeit einer 1 0.5+E ist und dass die Wahrscheinlichkeit einer 0 0.5-E ist, wobei E die Exzentrizität der Quelle ist, wie im vorherigen Abschnitt beschrieben. Dann ist die Wahrscheinlichkeit jedes Paares in der folgenden Tabelle gezeigt:
| 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 |
Diese Technik wird jegliche Verzerrung vollständig eliminieren, erfordert jedoch eine unbestimmte Anzahl von Eingangsbits für eine bestimmte gewünschte Anzahl von Ausgangsbits. Die Wahrscheinlichkeit, dass ein bestimmtes Paar verworfen wird, beträgt 0.5 + 2E^2, sodass die erwartete Anzahl von Eingangsbits zur Erzeugung von X Ausgangsbits X/(0.25 - E^2) beträgt.
Diese Technik nimmt an, dass die Bits aus einem Strom stammen, bei dem jedes Bit die gleiche Wahrscheinlichkeit hat, eine 0 oder 1 zu sein wie jedes andere Bit im Strom, und dass Bits unkorreliert sind, d.h., dass die Bits aus identischen unabhängigen Verteilungen stammen. Wenn abwechselnde Bits aus zwei korrelierten Quellen stammen, bricht die obige Analyse beispielsweise zusammen.
Die obige Technik bietet auch eine weitere Illustration dafür, wie eine einfache statistische Analyse irreführend sein kann, wenn man nicht immer auf der Suche nach Mustern ist, die von einem Gegner ausgenutzt werden könnten. Wenn der Algorithmus leicht falsch gelesen würde, sodass überlappende aufeinanderfolgende Bitpaare anstelle von nicht-überlappenden Paaren verwendet würden, wäre die gegebene statistische Analyse dieselbe. Anstatt jedoch eine unverzerrte, unkorrelierte Serie von zufälligen 1en und 0en bereitzustellen, würde sie eine völlig vorhersagbare Sequenz von genau alternierenden 1en und 0en erzeugen.