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

Aus LNTwww
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Beispiele binärer Blockcodes }} [[Datei:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-Choice Frage |t…“)
 
 
(14 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:|right|]]
+
[[Datei:P_ID2386__KC_Z_1_5.png|right|frame|Single Parity–check Code und Wiederholungscode mit&nbsp; $n = 5$]]
 +
 
 +
Zwischen dem&nbsp; ''Single Parity–check Code''&nbsp; und dem&nbsp; ''Repetition Code''&nbsp; gleicher Codelänge&nbsp; $n$&nbsp; besteht eine gewisse Verwandtschaft. Wie im Kapitel&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer
 +
Blockcodes]]&nbsp; noch gezeigt wird, handelt es sich um so genannte&nbsp; ''duale  Codes''.
 +
 
 +
*Der&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single Parity–check Code]] mit den Parametern&nbsp; $k = 4$&nbsp; und&nbsp; $n = 5$ &nbsp; &rArr; &nbsp; $\rm SPC \ (5, 4)$&nbsp; fügt zu den vier Informationsbits&nbsp; $u_{1}$, ... , &nbsp;$u_{4}$&nbsp; ein Prüfbit &nbsp;$p$&nbsp; hinzu, so dass in jedem Codewort&nbsp; $\underline{x}$&nbsp; 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,&nbsp; die in dieser Aufgabe miteinander verglichen werden sollen.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
''Hinweise:'' 
 +
*Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes|Beispiele binärer Blockcodes]].
 +
*Bezug genommen wird insbesondere auf die Seiten&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single Parity.E2.80.93check_Codes|Single Parity&ndash;check Codes]]&nbsp; sowie&nbsp;  [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscodes]].
 +
 +
 
  
  
Zeile 9: Zeile 31:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice Frage
+
 
 +
{Wie unterscheiden sich der&nbsp; $\text{SPC (5, 4)}$&nbsp; und der&nbsp; $\text{RC (5, 1)}$&nbsp; hinsichtlich des Codeumfangs?
 +
|type="{}"}
 +
$\ {\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}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 2 3% }
 +
 
 +
 
 +
{Welche der folgenden Codeworte sind beim&nbsp; $\text{SPC (5, 4)}$&nbsp; möglich?
 
|type="[]"}
 
|type="[]"}
- Falsch
+
+ $(0, 0, 0, 0, 0)$,
+ Richtig
+
- $(0, 0, 1, 0, 0)$,
 +
+ $(1, 1, 0, 1, 1)$,
 +
- $(1, 1, 1, 1, 1)$.
  
 +
{Welche der folgenden Codeworte sind beim&nbsp; $\text{RC (5, 1)}$&nbsp; möglich?
 +
|type="[]"}
 +
+ $(0, 0, 0, 0, 0)$,
 +
- $(0, 0, 1, 0, 0)$,
 +
- $(1, 1, 0, 1, 1)$,
 +
+$(1, 1, 1, 1, 1)$.
 +
 +
 +
{Wieviele Codefolgen&nbsp; $(N)$&nbsp; müssen in die Maximum&ndash;Likelihood–Entscheidung einbezogen werden?
 +
|type="{}"}
 +
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}N \ = \ $ { 32 }
 +
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}N \ = \ $ { 32 }
  
{Input-Box Frage
+
{Wie groß ist die minimale Distanz beider Codes?
 
|type="{}"}
 
|type="{}"}
$\alpha$ = { 0.3 }
+
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $ { 2 }
 +
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}d_{\rm min} \ = \ $ { 5 }
  
 +
{Bis zu wievielen Bitfehlern&nbsp; $(e)$&nbsp; funktioniert die Fehlererkennung?
 +
|type="{}"}
 +
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}e \ = \ $  { 1 }
 +
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}e \ = \ $ { 4 }
  
 +
{Bis zu wievielen Bitfehlern&nbsp; $(t)$&nbsp; funktioniert die Fehlerkorrektur?
 +
|type="{}"}
 +
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}t \ = \ $ { 0. }
 +
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}t \ = \ $ { 2 }
  
 
</quiz>
 
</quiz>
Zeile 25: Zeile 77:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.'''
+
'''(1)'''&nbsp; Der Codeumfang gibt die Anzahl der möglichen Codeworte an. Es gilt $|\mathcal{C}| = 2^k$, so dass es
'''2.'''
+
*beim hier betrachteten ''Single Parity–check'' Code <u>16 Codeworte gibt</u> ($k = 4$), und
'''3.'''
+
*beim Wiederholungscode nur <u>zwei Codeworte</u> ($k = 1$).
'''4.'''
+
 
'''5.'''
+
 
'''6.'''
+
 
'''7.'''
+
'''(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).
 +
 
 +
 
 +
 
 +
'''(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}$.
 +
 
 +
 
 +
 
 +
'''(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:
 +
:$$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$  &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.