Aufgaben:Aufgabe 1.5Z: SPC (5, 4) vs. RC (5, 1): Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(6 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2386__KC_Z_1_5.png|right|frame|Single Parity–check Code und Wiederholungscode mit $n = 5$]]
+
[[Datei:P_ID2386__KC_Z_1_5.png|right|frame|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 [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer
+
Zwischen dem  ''Single Parity–check Code''  und dem  ''Repetition Code''  gleicher Codelänge  $n$  besteht eine gewisse Verwandtschaft. Wie im Kapitel  [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer
  Blockcodes]] noch gezeigt werden wird, handelt es sich um so genannte ''duale  Codes''.  
+
  Blockcodes]]  noch gezeigt wird, handelt es sich um so genannte  ''duale  Codes''.  
  
*Der [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|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:
+
*Der  [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|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}.$$
 
:$$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 [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|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.
+
Die Grafik zeigt die Grundstruktur dieser beiden Codes,  die in dieser Aufgabe miteinander verglichen werden sollen.
 +
 
 +
 
 +
 
  
  
Zeile 20: Zeile 22:
  
 
''Hinweise:''   
 
''Hinweise:''   
*Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Beispiele_binärer_Blockcodes|Beispiele binärer Blockcodes]].
+
*Die Aufgabe gehört zum Kapitel  [[Kanalcodierung/Beispiele_binärer_Blockcodes|Beispiele binärer Blockcodes]].
*Bezug genommen wird insbesondere auf die Seiten [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single Parity.E2.80.93check_Codes|Single Parity&nash;check Codes]] sowie  [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscodes]].
+
*Bezug genommen wird insbesondere auf die Seiten  [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single Parity.E2.80.93check_Codes|Single Parity–check Codes]]  sowie  [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscodes]].
*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
+
  
  
Zeile 30: Zeile 32:
 
<quiz display=simple>
 
<quiz display=simple>
  
{Wie unterscheiden sich der SPC (5, 4) und der RC (5, 1) hinsichtlich des Codeumfangs?
+
{Wie unterscheiden sich der&nbsp; $\text{SPC (5, 4)}$&nbsp; und der&nbsp; $\text{RC (5, 1)}$&nbsp; hinsichtlich des Codeumfangs?
 
|type="{}"}
 
|type="{}"}
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}|\mathcal{C}| \ = \ $ { 16 3% }
+
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 16 3% }
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}|\mathcal{C}| \ = \ $ { 2 3% }
+
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 2 3% }
  
  
{Welche der folgenden Codeworte sind beim SPC (5, 4) möglich?
+
{Welche der folgenden Codeworte sind beim&nbsp; $\text{SPC (5, 4)}$&nbsp; möglich?
 
|type="[]"}
 
|type="[]"}
 
+ $(0, 0, 0, 0, 0)$,
 
+ $(0, 0, 0, 0, 0)$,
Zeile 43: Zeile 45:
 
- $(1, 1, 1, 1, 1)$.
 
- $(1, 1, 1, 1, 1)$.
  
{Welche der folgenden Codeworte sind beim RC (5, 1) möglich?
+
{Welche der folgenden Codeworte sind beim&nbsp; $\text{RC (5, 1)}$&nbsp; möglich?
 
|type="[]"}
 
|type="[]"}
 
+ $(0, 0, 0, 0, 0)$,
 
+ $(0, 0, 0, 0, 0)$,
Zeile 51: Zeile 53:
  
  
{Wieviele Codefolgen $(N)$ müssen in die Maximum&ndash;Likelihood–Entscheidung einbezogen werden?
+
{Wieviele Codefolgen&nbsp; $(N)$&nbsp; müssen in die Maximum&ndash;Likelihood–Entscheidung einbezogen werden?
 
|type="{}"}
 
|type="{}"}
 
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}N \ = \ $ { 32 }
 
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}N \ = \ $ { 32 }
Zeile 61: Zeile 63:
 
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}d_{\rm min} \ = \ $ { 5 }
 
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}d_{\rm min} \ = \ $ { 5 }
  
{Bis zu wievielen Bitfehlern $(e)$ funktioniert die Fehlererkennung?
+
{Bis zu wievielen Bitfehlern&nbsp; $(e)$&nbsp; funktioniert die Fehlererkennung?
 
|type="{}"}
 
|type="{}"}
 
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}e \ = \ $  { 1 }
 
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}e \ = \ $  { 1 }
 
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}e \ = \ $ { 4 }
 
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}e \ = \ $ { 4 }
  
{Bis zu wievielen Bitfehlern $(t)$ funktioniert die Fehlerkorrektur?
+
{Bis zu wievielen Bitfehlern&nbsp; $(t)$&nbsp; funktioniert die Fehlerkorrektur?
 
|type="{}"}
 
|type="{}"}
 
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}t \ = \ $ { 0. }
 
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}t \ = \ $ { 0. }
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}t \ = \ ${ 2 }
+
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}t \ = \ $ { 2 }
  
 
</quiz>
 
</quiz>
Zeile 75: Zeile 77:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; 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 <u>16 Codeworte gibt</u> ($k = 4$) und beim Wiederholungscode nur <u>zwei Codeworte</u> ($k = 1$).
+
'''(1)'''&nbsp; 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 <u>16 Codeworte gibt</u> ($k = 4$), und  
 +
*beim Wiederholungscode nur <u>zwei Codeworte</u> ($k = 1$).
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp;  Bei jedem ''Single Parity–check Code'' ist die Anzahl der Einsen geradzahlig  &nbsp; ⇒  &nbsp; <u>Antwort 1 und 3</u>.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Bei einem jeden Wiederholungscode gibt es (unabhängig von $n$) nur zwei Codeworte, die beide hier angegeben sind  &nbsp; ⇒  &nbsp; <u>Antwort 1 und 4</u>.
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; 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&ndash;Likelihood–Entscheidung einbezogen werden müssen.
 +
*Dies gilt sowohl für den SPC (5, 4) als auch für den RC (5, 1).
 +
 
 +
 
  
'''(2)'''&nbsp; Bei jedem ''Single Parity–check Code'' ist die Anzahl der Einsen geradzahlig  <u>Antwort 1 und 3</u>.
+
'''(5)'''&nbsp; 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 &nbsp; &nbsp; $d_{\rm min} \hspace{0.15cm}\underline{= 5}$.
  
'''(3)'''&nbsp; Bei einem jeden Wiederholungscode gibt es (unabhängig von ''n'') nur zwei Codeworte, die beide hier angegeben sind  ⇒  <u>Antwort 1 und 4</u>.
 
  
'''(4)'''&nbsp; Aufgrund von Bitfehlern kann es für den Empfangsvektor <u>''y''</u> stets $N = 2^n \underline{= 32}$ unterschiedliche Bitkombinationen geben, die alle in die ML–Entscheidung einbezogen werden müssen. Dies gilt sowohl für den SPC (5, 4) als auch für den RC (5, 1).
 
  
 +
'''(6)'''&nbsp; 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).
  
'''(5)'''&nbsp; Beim SPC (5, 4) beträgt die Hamming–Distanz zwischen zwei beliebigen Codeworten mindestens $d_{\rm min} \underline{= 2}$. Dagegen sind beim RC (5, 1) alle Bit der beiden Codeworte unterschiedlich ⇒ $d_{\rm min} \underline{= 5}$.
 
  
'''(6)'''&nbsp; 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)'''&nbsp;  Allgemein gilt für die Anzahl der korrigierbaren Fehler:
 
'''(7)'''&nbsp;  Allgemein gilt für die Anzahl der korrigierbaren Fehler:
 
:$$t = \left\lfloor \frac{d_{\rm min}-1}{2} \right\rfloor \hspace{0.05cm}.$$
 
:$$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)  ⇒  $d_{\rm min}  = 5$ bis zu $\underline{t = 2}$ Fehler korrigiert werden.
+
*Bei jedem ''Single Parity–check Code'' ist ($d_{\rm min} – 1)/2 = 0.5$ &nbsp; &nbsp; $\underline{t = 0}$.  
 +
*Dagegen können mit dem RC (5, 1)  wegen $d_{\rm min}  = 5$ bis zu $\underline{t = 2}$ Fehler korrigiert werden.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Aktuelle Version vom 14. Juni 2022, 13:14 Uhr

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}.$$


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.