Aufgaben:Aufgabe 1.5Z: SPC (5, 4) vs. RC (5, 1): Unterschied zwischen den Versionen
Wael (Diskussion | Beiträge) (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 $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 | ||
+ | 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: | ||
+ | :$$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:'' | ||
+ | *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–check Codes]] sowie [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscodes]]. | ||
+ | |||
+ | |||
Zeile 9: | Zeile 31: | ||
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | |
+ | {Wie unterscheiden sich der $\text{SPC (5, 4)}$ und der $\text{RC (5, 1)}$ 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 $\text{SPC (5, 4)}$ möglich? | ||
|type="[]"} | |type="[]"} | ||
− | - | + | + $(0, 0, 0, 0, 0)$, |
− | + | + | - $(0, 0, 1, 0, 0)$, |
+ | + $(1, 1, 0, 1, 1)$, | ||
+ | - $(1, 1, 1, 1, 1)$. | ||
+ | {Welche der folgenden Codeworte sind beim $\text{RC (5, 1)}$ 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 $(N)$ müssen in die Maximum–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 } | ||
− | { | + | {Wie groß ist die minimale Distanz beider Codes? |
|type="{}"} | |type="{}"} | ||
− | $\ | + | $\ {\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 $(e)$ 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 $(t)$ 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)''' 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)''' Bei jedem ''Single Parity–check Code'' ist die Anzahl der Einsen geradzahlig ⇒ <u>Antwort 1 und 3</u>. |
+ | |||
+ | |||
+ | |||
+ | '''(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 $\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. | ||
+ | |||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 14. Juni 2022, 14:14 Uhr
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:
- Die Aufgabe gehört zum Kapitel Beispiele binärer Blockcodes.
- Bezug genommen wird insbesondere auf die Seiten Single Parity–check Codes sowie Wiederholungscodes.
Fragebogen
Musterlösung
- 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.