[[File:P_ID2400__KC_Z_1_2.png|right|frame|Raum $\rm GF(2^3)$ und Code der Länge $n = 3$]]
[[File:P_ID2400__KC_Z_1_2.png|right|frame|Space $\rm GF(2^3)$ and <br>code of length $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 for error detection or error correction can be represented very clearly in an $n$-dimensional space. We restrict ourselves here to binary codes of length $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.
*The information word $\underline{u} = (u_{1},\ u_{2}, \ \text{...} , \ u_{k})$ is uniquely transformed into the code word $\underline{x} =(x_{1},\ x_{2}, \ \text{...} , \ , x_{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 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}$.
*The code rate is $R = k/n$.
*The Hamming distance $d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')$ between two code words $x ∈ \mathcal{C}$ and $x\hspace{0.05cm}' ∈ \mathcal{C}$ indicates the number of bit positions in which $x$ and $x\hspace{0.05cm}'$ differ.
''Hinweise'':
*The minimum distance $d_{\rm min} = {\rm min}\big[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')\big]$ is a measure of the correctability of a code.
*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.
*It can detect $e =d_{\rm min} - 1$ errors and can correct $t =(d_{\rm min} - 1)/2$ errors.
*The last statement, however, is valid only for odd $d_{\rm min}$.
Hints:
*This exercise belongs to the chapter [[Channel_Coding/Objective_of_Channel_Coding|"Objective of Channel Coding"]]
*In addition, some simple questions about the chapter [[Channel_Coding/Examples_of_Binary_Block_Codes|"Examples of binary block codes"]] are anticipated.
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Welche Aussagen gelten, wenn alle Punkte in $\rm GF(2^3)$ belegt sind?
{Which statements hold if all points in $\rm GF(2^3)$ are occupied?
|type="[]"}
|type="[]"}
+ Es gilt die Zuordnung $\underline{u} = (u_{1}, u_{2}, u_{3})$ → $\underline{u} = (x_{1}, x_{2},x_{3})$.
'''(2)''' Richtig sind die <u>Aussagen 1 und 3</u>:
'''(2)''' Correct <u>statements 1 and 2</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$.
*$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ actually describe codes with rate $R = 2/3$ and minimum distance $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}$.
*In the graph, the green dots mark the code $\mathcal{C}_{1}$ and the blue dots mark the 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)$.
*For the code $\mathcal{C}_{3}$ – also with rate $R = 2/3$ – the minimum distance between two code words is $d_{\rm min} = 1$, <br>for example between $(0, 0, 0)$ and $(1, 0, 0)$ or between $(0, 1, 1)$ and $(1, 1, 1)$.
'''(3)''' Richtig ist nur die <u>Aussage 1</u>:
'''(3)''' Correct is only <u>statement 1</u>:
*Mit der Minimaldistanz $d_{\rm min} = 2$ kann lediglich ein Bitfehler erkannt werden.
*Only a bit error can be detected with the minimum distance $d_{\rm min} = 2$.
*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.
*In the upper graph, the green dots indicate allowed code words of $\mathcal{C}_{1}$. <br>If a blue dot is received, this indicates a transmission error.
*Eine Fehlerkorrektur ist mit $d_{\rm min} = 2$ dagegen nicht möglich.
*On the other hand, error correction is not possible with $d_{\rm min} = 2$.
'''(4)''' Richtig sind die <u>Antworten 2, 3 und 4</u>:
'''(4)''' Correct <u>answers 2, 3, and 4</u>:
*$C_{4}$ beschreibt den [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|(3, 1, 3)–Wiederholungscode]].
*$C_{4}$ describes the [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|$(3, 1, 3)$ repetition code]]. In this code, two of the total eight possible points are occupied, from which one could incorrectly conclude the code rate $R = 1/4$.
*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$.
*However, the code rate is calculated according to $R = k/n = 1/3$.
*Aus der unteren Grafik erkennt man, dass wegen $d_{\rm min} = 3$ nun auch ein Bitfehler korrigiert werden kann.
*From the lower diagram one recognizes that because of $d_{\rm min} = 3$ now also one bit error can be corrected.
*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)$.
*During decoding, all light green points (with black outline) are transferred to the green point $(0, 0, 0)$ and all light blue points are transferred to the blue point $(1, 1, 1)$.
*Gleichzeitig können bis zu zwei Bitfehler erkannt werden (einer natürlich auch).
*Up to two bit errors can be detected at the same time (one of course).
{{ML-Fuß}}
{{ML-Fuß}}
[[Category:Aufgaben zu Kanalcodierung|^1.1 Zielsetzung der Kanalcodierung^]]
[[Category:Channel Coding: Exercises|^1.1 Objective of Channel Coding^]]
[[de:Aufgaben:Aufgabe 1.2Z: 3D–Darstellung von Codes]]
Codes for error detection or error correction can be represented very clearly in an $n$-dimensional space. We restrict ourselves here to binary codes of length $n = 3$:
The information word $\underline{u} = (u_{1},\ u_{2}, \ \text{...} , \ u_{k})$ is uniquely transformed into the code word $\underline{x} =(x_{1},\ x_{2}, \ \text{...} , \ , x_{n})$.
The code rate is $R = k/n$.
The Hamming distance $d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')$ between two code words $x ∈ \mathcal{C}$ and $x\hspace{0.05cm}' ∈ \mathcal{C}$ indicates the number of bit positions in which $x$ and $x\hspace{0.05cm}'$ differ.
The minimum distance $d_{\rm min} = {\rm min}\big[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')\big]$ is a measure of the correctability of a code.
It can detect $e =d_{\rm min} - 1$ errors and can correct $t =(d_{\rm min} - 1)/2$ errors.
The last statement, however, is valid only for odd $d_{\rm min}$.
In this assignment, $k = 3$ information bits are mapped to $n = 3$ code bits ⇒ $R = k/n = 1$.
The statement $\underline{x} = \underline{u} $ would only hold in the case of systematic coding.
For example, in principle. $(0, 0, 0)$ → $(0, 1, 1)$ would also be possible.
The last statement is certainly false: From the graph one can see the minimum distance $d_{\rm min} = 1$.
Two $(3, 2, 2)$ block codes
(2) Correct statements 1 and 2:
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ actually describe codes with rate $R = 2/3$ and minimum distance $d_{\rm min} = 2$.
In the graph, the green dots mark the code $\mathcal{C}_{1}$ and the blue dots mark the code $\mathcal{C}_{2}$.
For the code $\mathcal{C}_{3}$ – also with rate $R = 2/3$ – the minimum distance between two code words is $d_{\rm min} = 1$, for example between $(0, 0, 0)$ and $(1, 0, 0)$ or between $(0, 1, 1)$ and $(1, 1, 1)$.
(3) Correct is only statement 1:
Only a bit error can be detected with the minimum distance $d_{\rm min} = 2$.
In the upper graph, the green dots indicate allowed code words of $\mathcal{C}_{1}$. If a blue dot is received, this indicates a transmission error.
On the other hand, error correction is not possible with $d_{\rm min} = 2$.
$C_{4}$ describes the $(3, 1, 3)$ repetition code. In this code, two of the total eight possible points are occupied, from which one could incorrectly conclude the code rate $R = 1/4$.
However, the code rate is calculated according to $R = k/n = 1/3$.
From the lower diagram one recognizes that because of $d_{\rm min} = 3$ now also one bit error can be corrected.
During decoding, all light green points (with black outline) are transferred to the green point $(0, 0, 0)$ and all light blue points are transferred to the blue point $(1, 1, 1)$.
Up to two bit errors can be detected at the same time (one of course).
