[[File:P_ID2400__KC_Z_1_2.png|right|frame|Raum $\rm GF(2^3)$ und <br>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 $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 codeword $\underline{x} =(x_{1}, x_{2}, \ \text{...} , \ , x_{n})$ .
*Die Coderate beträgt $R = k/n$.
*The code rate is $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.
*The Hamming distance $d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')$ between two codewords $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.
*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.
*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 letzte Aussage gilt allerdings nur für ungerades $d_{\rm min}$.
*The last statement, however, is valid only for odd $d_{\rm min}$.
Line 19:
Line 19:
''Hinweise'':
Hints:
*Die Aufgabe gehört zum Kapitel [[Channel_Coding/Zielsetzung_der_Kanalcodierung|Zielsetzung der Kanalcodierung]].
*This exercise belongs to the chapter [[Channel_Coding/Objective_of_Channel_Coding|Obective of Channel Coding]]
*Zusätzlich werden einige einfache Fragen zum Kapitel [[Channel_Coding/Beispiele_binärer_Blockcodes|Beispiele binärer Blockcodes]] vorweg genommen.
*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{x} = (x_{1}, x_{2},x_{3})$.
'''(2)''' Richtig sind die <u>Aussagen 1 und 3</u>:
'''(2)''' Correct <u>statements 1 and 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$.
*$\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 codewords 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)''' 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 codewords of $\mathcal{C}_{1}$. 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 [[Channel_Coding/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]].
*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$.
*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$.
*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 a 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).
Codes for error detection or error correction can be represented very clearly in $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 codeword $\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 codewords $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 $e =d_{\rm min} - 1$ detect errors and $t =(d_{\rm min} - 1)/2$ correct 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 3:
$\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 codewords 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 codewords 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$.
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 a 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).
