[[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|Beispiele_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.
$C_{1}$ und $C_{2}$ beschreiben tatsächlich Codes mit der Rate R = 2/3 und der Minimaldistanz $d_{\rm min}$ = 2 ⇒ <u>Antwort 1 und 2.</u>
*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$.
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)''' 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)''' 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 Single Parity–check Code (3, 2, 2).
'''(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$.
$C_{4}$ beschreibt den (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)''' 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).
