Difference between revisions of "Aufgaben:Exercise 1.5Z: SPC (5, 4) vs. RC (5, 1)"
m (Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “) |
|||
Line 3: | Line 3: | ||
}} | }} | ||
− | [[File:P_ID2386__KC_Z_1_5.png|right|frame|Single Parity–check Code und Wiederholungscode mit $n = 5$]] | + | [[File: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}.$$ | ||
− | *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)$. | + | *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. | ||
+ | |||
+ | |||
+ | |||
Line 20: | Line 23: | ||
''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–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]]. |
Line 30: | Line 33: | ||
<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)$, | ||
Line 43: | Line 46: | ||
- $(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)$, | ||
Line 51: | Line 54: | ||
− | {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 } | ||
Line 61: | Line 64: | ||
$\ {\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. } |
Revision as of 18:13, 7 May 2019
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}.$$
- Ein jeder 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.
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.