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

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(11 dazwischenliegende Versionen von 3 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 <i>n</i> = 5]]
+
[[Datei:P_ID2386__KC_Z_1_5.png|right|frame|Single Parity–check Code und Wiederholungscode mit&nbsp; $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&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]] noch gezeigt werden wird, handelt es sich um so genannte '''duale Codes'''.
+
  Blockcodes]]&nbsp; noch gezeigt wird, handelt es sich um so genannte&nbsp; ''duale Codes''.  
  
*Der [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single Parity–check Code]] mit $k = 4$ und $n = 5$ SPC (5, 4) fügt zu den vier Informationsbits $u_{1}, ... , u_{4}$ ein Prüfbit ''p'' hinzu, so dass in jedem Codewort <u>''x''</u> eine gerade Anzahl von Einsen vorkommt:
+
*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}.$$
 
:$$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 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.
 
  
''Hinweis'' :  
+
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]].
 +
 +
 
  
Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Beispiele_binärer_Blockcodes|Beispiele binärer Blockcodes]]  des vorliegenden Buches.
 
  
 
===Fragebogen===
 
===Fragebogen===
Zeile 23: Zeile 32:
 
<quiz display=simple>
 
<quiz display=simple>
  
{Wie unterscheiden sich SPC (5, 4) und RC (5, 1) hinsichtlich Codeumfang?
+
{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):   |C|$ = { 16 3% }
+
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 16 3% }
$\ {\rm SPC} (5, 4):   |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)$,
- (0, 0, 1, 0, 0),
+
- $(0, 0, 1, 0, 0)$,
+ (1, 1, 0, 1, 1),
+
+ $(1, 1, 0, 1, 1)$,
- (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)$,
- (0, 0, 1, 0, 0),
+
- $(0, 0, 1, 0, 0)$,
- (1, 1, 0, 1, 1),
+
- $(1, 1, 0, 1, 1)$,
+(1, 1, 1, 1, 1).
+
+$(1, 1, 1, 1, 1)$.
  
  
{Wieviele Codefolgen (''N'') müssen in die ML–Entscheidung einbezogen werden?
+
{Wieviele Codefolgen&nbsp; $(N)$&nbsp; müssen in die Maximum&ndash;Likelihood–Entscheidung einbezogen werden?
 
|type="{}"}
 
|type="{}"}
$\ {\rm SPC} (5, 4):   N$ = { 32 3% }
+
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}N \ = \ $ { 32 }
$\ {\rm RC} (5, 1):   N$= { 32 3% }
+
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}N \ = \ $ { 32 }
  
 
{Wie groß ist die minimale Distanz beider Codes?
 
{Wie groß ist die minimale Distanz beider Codes?
 
|type="{}"}
 
|type="{}"}
$\ {\rm SPC} (5, 4):   d_{\rm min} $ = { 2 3% }
+
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $ { 2 }
$\ {\rm RC} (5, 1):   d_{\rm min} $ = { 5 3% }
+
$\ {\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):   e$ = { 1 3% }
+
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}e \ = \ $ { 1 }
$\ {\rm RC} (5, 1):   e$ = { 4 3% }
+
$\ {\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):   t$ = { 0.3 }
+
$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}t \ = \ $ { 0. }
$\ {\rm RC} (5, 1):   t$ = { 2 3% }
+
$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}t \ = \ $ { 2 }
  
 
</quiz>
 
</quiz>
Zeile 68: Zeile 77:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.''' Der Codeumfang gibt die Anzahl der möglichen Codeworte an. Es gilt $|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.'''  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.''' 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.''' 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.''' 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.''' 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:
+
'''(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.