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

• Zurück zum Buch

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 werden 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:

• Die Aufgabe gehört zum Kapitel Beispiele binärer Blockcodes.
• Bezug genommen wird insbesondere auf die Seiten Single Parity&nash;check Codes sowie Wiederholungscodes.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

1

Wie unterscheiden sich der SPC (5, 4) und der RC (5, 1) hinsichtlich des Codeumfangs?

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

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

2

Welche der folgenden Codeworte sind beim 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 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

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.