Aufgaben:Aufgabe 1.5Z: SPC (5, 4) vs. RC (5, 1): Unterschied zwischen den Versionen
(5 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 | + | 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 | + | *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}.$$ | ||
− | |||
− | 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& | + | *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 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 $\text{SPC (5, 4)}$ und der $\text{RC (5, 1)}$ 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 $\text{SPC (5, 4)}$ 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 $\text{RC (5, 1)}$ 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–Likelihood–Entscheidung einbezogen werden? | + | {Wieviele Codefolgen $(N)$ müssen in die Maximum–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 $(e)$ 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 $(t)$ 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 78: | Zeile 80: | ||
*beim hier betrachteten ''Single Parity–check'' Code <u>16 Codeworte gibt</u> ($k = 4$), und | *beim hier betrachteten ''Single Parity–check'' Code <u>16 Codeworte gibt</u> ($k = 4$), und | ||
*beim Wiederholungscode nur <u>zwei Codeworte</u> ($k = 1$). | *beim Wiederholungscode nur <u>zwei Codeworte</u> ($k = 1$). | ||
+ | |||
'''(2)''' Bei jedem ''Single Parity–check Code'' ist die Anzahl der Einsen geradzahlig ⇒ <u>Antwort 1 und 3</u>. | '''(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>. | '''(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. | '''(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). | *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}$. | '''(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. | '''(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). | *Mit dem Ergebnis aus (5) erhält man $\underline{e = 1}$ (SPC) bzw. $\underline{e = 4}$ (RC). | ||
+ | |||
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.