*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.
*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 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 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}[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')]$ ist ein Maß für die Korrekturfähigkeit eines Codes.
*Die Minimaldistanz $d_{\rm min} = {\rm min}[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')]$ 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}$.
*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}$.
Line 56:
Line 56:
===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>:
*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$.
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>.
'''(4)''' Richtig sind die <u>Antworten 2, 3 und 4</u>:
*$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 $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).
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}[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')]$ 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).
