(9 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 2:
Zeile 2:
}}
}}
[[Datei:P_ID2400__KC_Z_1_2.png|right|]]
[[Datei:P_ID2400__KC_Z_1_2.png|right|frame|Raum $\rm GF(2^3)$ und <br>Code der Länge $n = 3$]]
Codes zur Fehlererkennung bzw. Fehlererkorrektur lassen sich sehr anschaulich im ''n''–dimensionalen Raum darstellen. Wir beschränken uns hier auf binäre Codes der Länge ''n'' = 3:
Codes zur Fehlererkennung bzw. Fehlererkorrektur lassen sich sehr anschaulich im $n$–dimensionalen Raum darstellen. Wir beschränken uns hier auf binäre Codes der Länge $n = 3$:
*Das Informationswort <u>u</u> = $(u_{1}, u_{2}, ... , u_{k})$ wird eindeutig in das Codewort <u>x</u> = $(x_{1}, x_{2}, ... , x_{n})$ überführt.
*Das Informationswort $\underline{u} = (u_{1}, u_{2}, \ \text{...} , \ u_{k})$ wird eindeutig in das Codewort $\underline{x} =(x_{1}, x_{2}, \ \text{...} , \ , x_{n})$ überführt.
*Die Coderate beträgt R = k/n.
*Die Hamming–Distanz $d_{\rm H}$(<u>x</u>,<u> x'</u>) zwischen zwei Codeworten <u>x</u> ∈ C und <u>x'</u> ∈ C gibt die Anzahl der Bitpositionen an, in denen sich x und x' unterscheiden.
*Die Coderate beträgt $R = k/n$.
*Die Minimaldistanz $d_{\rm min}$ = min [$d_{\rm H}$(<u>x</u>,<u> x'</u>)] ist ein Maß für die Korrekturfähigkeit eines Codes.
*Es können ''e'' =$d_{\rm min}$ – 1 Fehler erkannt und ''t'' = ($d_{\rm min}$ – 1)/2 korrigiert werden. Die letzte Aussage gilt allerdings nur für ungerades $d_{\rm min}$ .
*Die Hamming–Distanz $d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')$ zwischen zwei Codeworten $x ∈ \mathcal{C}$ und $x\hspace{0.05cm}' ∈ \mathcal{C}$ gibt die Anzahl der Bitpositionen an, in denen sich $x$ und $x\hspace{0.05cm}'$ unterscheiden.
*Die Minimaldistanz $d_{\rm min} = {\rm min}\big[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')\big]$ ist ein Maß für die Korrekturfähigkeit eines Codes.
*Die letzte Aussage gilt allerdings nur für ungerades $d_{\rm min}$.
Hinweise:
*Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Zielsetzung_der_Kanalcodierung|"Zielsetzung der Kanalcodierung"]].
*Zusätzlich werden einige einfache Fragen zum Kapitel [[Kanalcodierung/Beispiele_binärer_Blockcodes|"Beispiele binärer Blockcodes"]] vorweg genommen.
''Hinweis'':
Die Aufgabe gehört zum Themengebiet von [[Kanalcodierung/Zielsetzung_der_Kanalcodierung|Zielsetzung_der_Kanalcodierung]]. Zusätzlich werden einige einfache Fragen zu [[Kanalcodierung/Beispiele_binärer_Blockcodes|Beispiele_binärer_Blockcodes]] vorweg genommen.
===Fragebogen===
===Fragebogen===
Zeile 20:
Zeile 34:
<quiz display=simple>
<quiz display=simple>
{Welche Aussagen gelten, wenn alle Punkte in GF(23) belegt sind?
{Welche Aussagen gelten, wenn alle Punkte in $\rm GF(2^3)$ belegt sind?
|type="[]"}
|type="[]"}
+ Es gilt die Zuordnung <u>u</u> = $ (u_{1}, u_{2}, u_{3})$) → <u>x</u>=$(x_{1}, x_{2},x_{3})$.
+ Es gilt die Zuordnung $\underline{u} = (u_{1}, u_{2}, u_{3})$ → $\underline{x} = (x_{1}, x_{2},x_{3})$.
- Es gilt die Identität <u>x</u> = <u>u</u>.
- Es gilt die Identität $\underline{x} = \underline{u}$.
+ Die Coderate ist R = 1.
+ Die Coderate ist $R = 1$.
-Die Minimaldistanz zwischen zwei Codeworten ist $d_{\rm min}$ = 2.
-Die Minimaldistanz zwischen zwei Codeworten ist $d_{\rm min} = 2$.
{Welche Aussagen gelten für einen (3, 2, 2)–Blockcode?
{Welche Aussagen gelten für einen $(3, 2, 2)$–Blockcode?
{Welche Eigenschaften zeigt der in Teilaufgabe 2) definierte Code $C_{1}$?
{Welche Eigenschaften zeigt der in Teilaufgabe '''(2)''' definierte Code $\mathcal{C}_{1}$?
|type="[]"}
|type="[]"}
+ Ein Bitfehler lässt sich erkennen.
+ Ein Bitfehler lässt sich erkennen.
- Ein Bitfehler kann korrigiert werden.
- Ein Bitfehler kann korrigiert werden.
{Welche Eigenschaften zeigt der Code $C_{4}$= {(0, 0, 0), (1, 1, 1)}?
{Welche Eigenschaften zeigt der Code $\mathcal{C}_{4}= \{(0, 0, 0), (1, 1, 1)\}$?
|type="[]"}
|type="[]"}
- Die Coderate beträgt R = 1/4.
- Die Coderate beträgt $R = 1/4$.
+ Die Coderate beträgt R = 1/3.
+ Die Coderate beträgt $R = 1/3$.
+ Ein Bitfehler lässt sich erkennen.
+ Ein Bitfehler lässt sich erkennen.
Ein Bitfehler lässt sich erkennen.
+ Ein Bitfehler kann korrigiert werden.
Zeile 54:
Zeile 64:
===Musterlösung===
===Musterlösung===
{{ML-Kopf}}
{{ML-Kopf}}
'''(1)''' Richtig sind die <u>Aussagen 1 und 3</u>: k = 3 Informationsbits werden bei dieser Belegung auf n = 3 Codebits abgebildet ⇒ R = k/n = 1. Die Aussage <>x</u> = <>u</u> würde nur bei systematischer Codierung gelten. Prinzipiell möglich wäre zum Beispiel auch (0, 0, 0) → (0, 1, 1). Die letzte Aussage ist mit Sicherheit falsch: Aus der Grafik erkennt man die Minimaldistanz $d_{\rm min}$ = 1.
'''(1)''' Richtig sind die <u>Aussagen 1 und 3</u>:
*Die Aussage $\underline{x} = \underline{u} $ würde nur bei systematischer Codierung gelten.
$C_{1}$ und $C_{2}$ beschreiben tatsächlich Codes mit der Rate R = 2/3 und der Minimaldistanz $d_{\rm min}$ = 2 ⇒ <u>Antwort 1 und 2.</u>
*Prinzipiell möglich wäre zum Beispiel auch $(0, 0, 0)$ → $(0, 1, 1)$.
*Die letzte Aussage ist mit Sicherheit falsch: Aus der Grafik erkennt man die Minimaldistanz $d_{\rm min} = 1$.
In nebenstehender Grafik markieren die grünen Punkte den Code $C_{1}$ und die blauen Punkte den Code $C_{2}$. Beim angegebenen Code $C_{3}$ – ebenfalls mit Rate R = 2/3 – ist die minimale Distanz zwischen zwei Codeworten $d_{\rm min}$ = 1, zum Beispiel zwischen (0, 0, 0) und (1, 0, 0) oder auch zwischen (0, 1, 1) und (1, 1, 1).
'''(2)''' Richtig sind die <u>Aussagen 1 und 3</u>:
*$\mathcal{C}_{1}$ und $\mathcal{C}_{2}$ beschreiben tatsächlich Codes mit der Rate $R = 2/3$ und der Minimaldistanz $d_{\rm min} = 2$.
*In der Grafik markieren die grünen Punkte den Code $\mathcal{C}_{1}$ und die blauen Punkte den Code $\mathcal{C}_{2}$.
*Beim Code $\mathcal{C}_{3}$ – ebenfalls mit Rate $R = 2/3$ – ist die minimale Distanz zwischen zwei Codeworten $d_{\rm min} = 1$, zum Beispiel zwischen $(0, 0, 0)$ und $(1, 0, 0)$ oder zwischen $(0, 1, 1)$ und $(1, 1, 1)$.
'''(3)''' Mit der Minimaldistanz $d_{\rm min}$ = 2 kann lediglich ein Bitfehler erkannt werden. In der oberen Grafik kennzeichnen die grünen Punkte zulässige Codeworte von $C_{1}$. Wird ein blauer Punkt empfangen, so weist dies auf einen Übertragungsfehler hin. Eine Fehlerkorrektur ist mit $d_{\rm min}$ = 2 dagegen nicht möglich ⇒ <u>Antwort 1</u>. Hinweis: Der Code $C_{1}$ entspricht dem [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single Parity–check Code]] (3, 2, 2).
'''(3)''' Richtig ist nur die <u>Aussage 1</u>:
*Mit der Minimaldistanz $d_{\rm min} = 2$ kann lediglich ein Bitfehler erkannt werden.
*In der oberen Grafik kennzeichnen die grünen Punkte zulässige Codeworte von $\mathcal{C}_{1}$. Wird ein blauer Punkt empfangen, so weist dies auf einen Übertragungsfehler hin.
*Eine Fehlerkorrektur ist mit $d_{\rm min} = 2$ dagegen nicht möglich.
$C_{4}$ beschreibt den [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|(3, 1, 3)–Wiederholungscode]]. Bei diesem Code sind zwar zwei der insgesamt acht möglichen Punkte belegt, woraus man fälschlicherweise auf die Coderate R = 1/4 schließen könnte. Die Coderate berechnet sich aber gemäß R = k/n = 1/3.
Aus der unteren Grafik erkennt man, dass wegen dmin = 3 nun auch ein Bitfehler korrigiert werden kann. Bei der Decodierung werden alle hellgrünen Punkte (mit schwarzer Umrahmung) in den grünen Punkt (0, 0, 0) überführt und alle hellblauen in den blauen Punkt (1, 1, 1). Gleichzeitig können bis zu zwei Bitfehler erkannt werden (einer natürlich auch) ⇒ Richtig sind die <u>Antworten 2, 3 und 4</u>.
*Bei diesem Code sind zwar zwei der insgesamt acht möglichen Punkte belegt, woraus man fälschlicherweise auf die Coderate $R = 1/4$ schließen könnte. Die Coderate berechnet sich aber gemäß $R = k/n = 1/3$.
*Aus der unteren Grafik erkennt man, dass wegen $d_{\rm min} = 3$ nun auch ein Bitfehler korrigiert werden kann.
*Bei der Decodierung werden alle hellgrünen Punkte (mit schwarzer Umrahmung) in den grünen Punkt $(0, 0, 0)$ überführt und alle hellblauen in den blauen Punkt $(1, 1, 1)$.
*Gleichzeitig können bis zu zwei Bitfehler erkannt werden (einer natürlich auch).
{{ML-Fuß}}
{{ML-Fuß}}
Zeile 76:
Zeile 98:
[[Category:Aufgaben zu Kanalcodierung|^1.1 Zielsetzung der Kanalcodierung^]]
[[Category:Aufgaben zu Kanalcodierung|^1.1 Zielsetzung der Kanalcodierung^]]
Codes zur Fehlererkennung bzw. Fehlererkorrektur lassen sich sehr anschaulich im $n$–dimensionalen Raum darstellen. Wir beschränken uns hier auf binäre Codes der Länge $n = 3$:
Das Informationswort $\underline{u} = (u_{1}, u_{2}, \ \text{...} , \ u_{k})$ wird eindeutig in das Codewort $\underline{x} =(x_{1}, x_{2}, \ \text{...} , \ , x_{n})$ überführt.
Die Coderate beträgt $R = k/n$.
Die Hamming–Distanz $d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')$ zwischen zwei Codeworten $x ∈ \mathcal{C}$ und $x\hspace{0.05cm}' ∈ \mathcal{C}$ gibt die Anzahl der Bitpositionen an, in denen sich $x$ und $x\hspace{0.05cm}'$ unterscheiden.
Die Minimaldistanz $d_{\rm min} = {\rm min}\big[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')\big]$ ist ein Maß für die Korrekturfähigkeit eines Codes.
Es können $e =d_{\rm min} – 1$ Fehler erkannt und $t =(d_{\rm min} – 1)/2$ Fehler korrigiert werden.
Die letzte Aussage gilt allerdings nur für ungerades $d_{\rm min}$.
Bei dieser Belegung werden $k = 3$ Informationsbits auf $n = 3$ Codebits abgebildet ⇒ $R = k/n = 1$.
Die Aussage $\underline{x} = \underline{u} $ würde nur bei systematischer Codierung gelten.
Prinzipiell möglich wäre zum Beispiel auch $(0, 0, 0)$ → $(0, 1, 1)$.
Die letzte Aussage ist mit Sicherheit falsch: Aus der Grafik erkennt man die Minimaldistanz $d_{\rm min} = 1$.
Zwei $(3, 2, 2)$–Blockcodes
(2) Richtig sind die Aussagen 1 und 3:
$\mathcal{C}_{1}$ und $\mathcal{C}_{2}$ beschreiben tatsächlich Codes mit der Rate $R = 2/3$ und der Minimaldistanz $d_{\rm min} = 2$.
In der Grafik markieren die grünen Punkte den Code $\mathcal{C}_{1}$ und die blauen Punkte den Code $\mathcal{C}_{2}$.
Beim Code $\mathcal{C}_{3}$ – ebenfalls mit Rate $R = 2/3$ – ist die minimale Distanz zwischen zwei Codeworten $d_{\rm min} = 1$, zum Beispiel zwischen $(0, 0, 0)$ und $(1, 0, 0)$ oder zwischen $(0, 1, 1)$ und $(1, 1, 1)$.
(3) Richtig ist nur die Aussage 1:
Mit der Minimaldistanz $d_{\rm min} = 2$ kann lediglich ein Bitfehler erkannt werden.
In der oberen Grafik kennzeichnen die grünen Punkte zulässige Codeworte von $\mathcal{C}_{1}$. Wird ein blauer Punkt empfangen, so weist dies auf einen Übertragungsfehler hin.
Eine Fehlerkorrektur ist mit $d_{\rm min} = 2$ dagegen nicht möglich.
Bei diesem Code sind zwar zwei der insgesamt acht möglichen Punkte belegt, woraus man fälschlicherweise auf die Coderate $R = 1/4$ schließen könnte. Die Coderate berechnet sich aber gemäß $R = k/n = 1/3$.
Aus der unteren Grafik erkennt man, dass wegen $d_{\rm min} = 3$ nun auch ein Bitfehler korrigiert werden kann.
Bei der Decodierung werden alle hellgrünen Punkte (mit schwarzer Umrahmung) in den grünen Punkt $(0, 0, 0)$ überführt und alle hellblauen in den blauen Punkt $(1, 1, 1)$.
Gleichzeitig können bis zu zwei Bitfehler erkannt werden (einer natürlich auch).
