Aufgabe 1.5Z: SPC (5, 4) vs. RC (5, 1)

From LNTwww

Single Parity–check Code und Wiederholungscode mit  $n = 5$

Zwischen dem  Single Parity–check Code  und dem  Repetition Code  gleicher Codelänge  $n$  besteht eine gewisse Verwandtschaft. Wie im Kapitel  Allgemeine Beschreibung linearer Blockcodes  noch gezeigt wird, handelt es sich um so genannte  duale Codes.

  • Der  Single Parity–check Code mit den Parametern  $k = 4$  und  $n = 5$   ⇒   $\rm SPC \ (5, 4)$  fügt zu den vier Informationsbits  $u_{1}$, ... ,  $u_{4}$  ein Prüfbit  $p$  hinzu, so dass in jedem Codewort  $\underline{x}$  eine gerade Anzahl von Einsen vorkommt:
$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$
  • Ein jeder  Wiederholungscode  (englisch:   Repetition Code) ist durch den Codeparameter  $k = 1$  charakterisiert. Beim  $\rm RC \ (5, \ 1)$  lauten die beiden Codeworte  $(0, 0, 0, 0, 0)$  und  $(1, 1, 1, 1, 1)$.


Die Grafik zeigt die Grundstruktur dieser beiden Codes, die in dieser Aufgabe miteinander verglichen werden sollen.




Hinweise:



Fragebogen

1

Wie unterscheiden sich der  $\text{SPC (5, 4)}$  und der  $\text{RC (5, 1)}$  hinsichtlich des Codeumfangs?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $

$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $

2

Welche der folgenden Codeworte sind beim  $\text{SPC (5, 4)}$  möglich?

$(0, 0, 0, 0, 0)$,
$(0, 0, 1, 0, 0)$,
$(1, 1, 0, 1, 1)$,
$(1, 1, 1, 1, 1)$.

3

Welche der folgenden Codeworte sind beim  $\text{RC (5, 1)}$  möglich?

$(0, 0, 0, 0, 0)$,
$(0, 0, 1, 0, 0)$,
$(1, 1, 0, 1, 1)$,
$(1, 1, 1, 1, 1)$.

4

Wieviele Codefolgen  $(N)$  müssen in die Maximum–Likelihood–Entscheidung einbezogen werden?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}N \ = \ $

$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}N \ = \ $

5

Wie groß ist die minimale Distanz beider Codes?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}d_{\rm min} \ = \ $

6

Bis zu wievielen Bitfehlern  $(e)$  funktioniert die Fehlererkennung?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}e \ = \ $

$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}e \ = \ $

7

Bis zu wievielen Bitfehlern  $(t)$  funktioniert die Fehlerkorrektur?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}t \ = \ $

$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}t \ = \ $


Musterlösung

(1)  Der Codeumfang gibt die Anzahl der möglichen Codeworte an. Es gilt $|\mathcal{C}| = 2^k$, so dass es

  • beim hier betrachteten Single Parity–check Code 16 Codeworte gibt ($k = 4$), und
  • beim Wiederholungscode nur zwei Codeworte ($k = 1$).


(2)  Bei jedem Single Parity–check Code ist die Anzahl der Einsen geradzahlig   ⇒   Antwort 1 und 3.


(3)  Bei einem jeden Wiederholungscode gibt es (unabhängig von $n$) nur zwei Codeworte, die beide hier angegeben sind   ⇒   Antwort 1 und 4.


(4)  Aufgrund von Bitfehlern kann es für den Empfangsvektor $\underline{y}$ stets $N = 2^n \hspace{0.15cm}\underline{= 32}$ unterschiedliche Bitkombinationen geben, die alle in die Maximum–Likelihood–Entscheidung einbezogen werden müssen.

  • Dies gilt sowohl für den SPC (5, 4) als auch für den RC (5, 1).


(5)  Beim SPC (5, 4) beträgt die Hamming–Distanz zwischen zwei beliebigen Codeworten mindestens $d_{\rm min} \hspace{0.15cm}\underline{= 2}$. Dagegen sind beim RC (5, 1) alle Bit der beiden Codeworte unterschiedlich   ⇒   $d_{\rm min} \hspace{0.15cm}\underline{= 5}$.


(6)  Eine Fehlererkennung ist möglich, so lange nicht mehr als $e = d_{\rm min} – 1$ Bitfehler in einem Codewort auftreten.

  • Mit dem Ergebnis aus (5) erhält man $\underline{e = 1}$ (SPC) bzw. $\underline{e = 4}$ (RC).


(7)  Allgemein gilt für die Anzahl der korrigierbaren Fehler:

$$t = \left\lfloor \frac{d_{\rm min}-1}{2} \right\rfloor \hspace{0.05cm}.$$
  • Bei jedem Single Parity–check Code ist ($d_{\rm min} – 1)/2 = 0.5$   ⇒   $\underline{t = 0}$.
  • Dagegen können mit dem RC (5, 1) wegen $d_{\rm min} = 5$ bis zu $\underline{t = 2}$ Fehler korrigiert werden.