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

Aus LNTwww
Wechseln zu:Navigation, Suche

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:


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

(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.