[[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 <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.
*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}$(<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 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}$ .
===Fragebogen===
*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}$.
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.
===Questions===
<quiz display=simple>
<quiz display=simple>
{Multiple-Choice Frage
{Which statements hold if all points in $\rm GF(2^3)$ are occupied?
'''(2)''' Correct <u>statements 1 and 2</u>:
*$\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$, <br>for example between $(0, 0, 0)$ and $(1, 0, 0)$ or between $(0, 1, 1)$ and $(1, 1, 1)$.
'''(3)''' Correct is only <u>statement 1</u>:
*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}$. <br>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$.
'''(4)''' Correct <u>answers 2, 3, and 4</u>:
*$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$.
*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).
{{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).
