[[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}$ .
''Hinweis'':
*The code rate is $R = k/n$.
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|eispiele_binärer_Blockcodes]] vorweg genommen.
===Fragebogen===
*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>
{Welche Aussagen gelten, wenn alle Punkte in GF(23) belegt sind?
{Which statements hold if all points in $\rm GF(2^3)$ are occupied?
|type="[]"}
|type="[]"}
+ Es gilt die Zuordnung <u>u</u> = $ (u_{1}, u_{2}, u_{3})$) → <u>x</u>=$(x_{1}, x_{2},x_{3})$.
{Welche Eigenschaften zeigt der in Teilaufgabe 2) definierte Code $C_{1}$?
{What properties does the code $\mathcal{C}_{1}$ defined in subtask '''(2)''' show?
|type="[]"}
|type="[]"}
+ Ein Bitfehler lässt sich erkennen.
+ A bit error can be detected.
- Ein Bitfehler kann korrigiert werden.
- A bit error can be corrected.
{Welche Eigenschaften zeigt der Code $C_{4}$= {(0, 0, 0), (1, 1, 1)}?
{What properties does the code $\mathcal{C}_{4}= \{(0, 0, 0),\ (1, 1, 1)\}$ show?
|type="[]"}
|type="[]"}
- Die Coderate beträgt R = 1/4.
- The code rate is $R = 1/4$.
+ Die Coderate beträgt R = 1/3.
+ The code rate is $R = 1/3$.
+ Ein Bitfehler lässt sich erkennen.
+ A bit error can be detected.
Ein Bitfehler lässt sich erkennen.
+ A bit error can be corrected.
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{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)''' Correct <u>statements 1 and 3</u>:
*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$.
'''(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)$.
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).
'''(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).
