Aufgabe 5.5: Fehlerfolge und Fehlerabstandsfolge

From LNTwww

Fehlerfolge (oben, blau) und Fehlerabstandsfolge (unten, rot)

Eine jede Fehlerfolge  $〈e_{\nu}〉$  kann man auch als die Folge  $〈a_n〉$  der Fehlerabstände angeben. Ist die mittlere Fehlerwahrscheinlichkeit nicht zu groß, dann ergibt sich so ein geringerer Speicherbedarf als bei Speicherung der Fehlerfolge. Für den Vergleich in dieser Aufgabe soll von den folgenden Voraussetzungen ausgegangen werden:

  • Abgespeichert werden soll jeweils eine Fehlerfolge der Länge  $N = 10^6$  Elementen.
  • Für die Speicherung von  $〈e_{\nu}〉$  soll die speichereffizienteste Methode (ein Bit pro Fehler) verwendet werden.
  • Jeder Fehlerabstand wird durch 4 Byte (32 Bit) dargestellt.


Ist das zugrundeliegende Kanalmodell erneuernd wie zum Beispiel das BSC–Modell, so können zur Generierung der Fehlerfolge  $〈e_{\nu}〉$  auf einem Digitalrechner zwei unterschiedliche Methoden angewandt werden:

  • die symbolweise Erzeugung der Fehler, beim BSC–Modell gemäß den Wahrscheinlichkeiten  $p$  (Fehler) und  $1-p$  (kein Fehler),
  • die Erzeugung der Fehlerabstände, beim BSC–Modell entsprechend der  Binomialverteilung.




Hinweise:

  • Die Aufgabe gehört zum Themengebiet des Kapitels  Binary Symmetric Channel (BSC).
  • Bei den folgenden Fragen gibt  $G_e$  die erforderliche Dateigröße (in Byte) zur Abspeicherung der Fehlerfolge  $〈e_{\nu}〉$  und  $G_a$  (ebenfalls in Byte) die Dateigröße bei Abspeicherung der Fehlerabstandsfolge  $〈a_n〉$ an.



Fragebogen

1

Wieviel Speicherplatz (in Byte) wird benötigt, wenn man eine Fehlerfolge der Länge  $N = 10^6$  direkt abspeichert?

$G_e \ = \ $

$\ \rm kByte$

2

Wie groß wird die Dateigröße in etwa bei Speicherung der Fehlerabstände? Es gelte  $p_{\rm M} = 10^{-3}$.

$G_a \ = \ $

$\ \rm kByte$

3

Wie groß wird die Datei bei Speicherung der Fehlerabstände mit  $p_{\rm M} = 0.5$?

$G_a \ = \ $

$\ \rm kByte$

4

Geben Sie die Grenze  $p_{\rm M, \ max}$  der BSC–Fehlerwahrscheinlichkeit an, bei der die Speicherung als Fehlerabstandsfolge sinnvoll ist.

$p_{\rm M, \ max} \ = \ $

$\ \% $


Musterlösung

(1)  Pro Element $e_{\nu}$ der Fehlerfolge benötigt man genau ein $\rm Bit$.

  • Die Multiplikation mit $N$ ergibt $10^6 \ \rm Bit$ entsprechend $G_e \ \underline {= 125 \ \rm kByte}$.


(2)  Mit $N = 10^6$ und $p_{\rm M} = 10^{–3}$ sind ca. $1000$ Fehlerabstände abzuspeichern, jeder einzelne mit $4 \ \rm Byte$   ⇒   $G_a \ \underline {= 4 \rm kByte}$.

  • Im Gegensatz zur Speicherung der Fehlerfolge wird dieser Wert leicht variieren, da in einer Fehlerfolge der (begrenzten) Länge $N = 10^6$ nicht immer exakt $1000$ Fehler auftreten werden.


(3)  Nun werden im Mittel $0.5 \cdot 10^6$ Fehler auftreten   ⇒   $G_a \ \underline {= 2000 \ \rm KByte}$.

  • Daraus ist ersichtlich, dass die Speicherung der Fehlerabstände nur sinnvoll ist, wenn die (mittlere) Fehlerwahrscheinlichkeit nicht zu groß ist.


(4)  Aus den Erklärungen zu den oberen Teilaufgaben folgt:

$$N \cdot p_{\rm M} \cdot 4 < {N}/{8} \Rightarrow \hspace{0.3cm}p_{\rm M, \hspace{0.05cm}max} = {1}/{32} \hspace{0.15cm}\underline {= 3.125\%}\hspace{0.05cm}.$$
  • Dieses Ergebnis ist unabhängig von der Folgenlänge $N$.