# VL 2 Codierungstheorie

## Einfache Codes

### Paritätscode
$k$ Informationsbits $u_1,\ ...,\ u_k$
ein Prüfbit $c_1$
$$
\begin{align}
c_1 & = f_1(u_1,\ \ldots,\ u_k)&\\
& = u_1 \oplus u_2 \oplus \ldots \oplus u_k&
\end{align}
$$

mit $k=3$:
| $u_1$ | $u_2$ | $u_3$ | | $c_1$ | Fehler erkannt? |
|:-----:|:-----:|:-----:| --- |:-----:|:----------------------------- |
| 0 | 0 | 0 | | 0 | :negative_squared_cross_mark: |
| 0 | 0 | **1** | | **1** | :heavy_check_mark: |
| 0 | **1** | 0 | | **1** | :heavy_check_mark: |
| 0 | **1** | **1** | | 0 | :negative_squared_cross_mark: |
| **1** | 0 | 0 | | **1** | :heavy_check_mark: |
| **1** | 0 | **1** | | 0 | :negative_squared_cross_mark: |
| **1** | **1** | 0 | | 0 | :negative_squared_cross_mark: |
| **1** | **1** | **1** | | **1** | :heavy_check_mark: |

:::info
Paritätscode kann nur ungerade Anzahl an Fehlern erkennen
:::

bei $k=4$:
Wörter $X = \{0,1\}^4 = \{0000,\ 0001,\ \ldots,\ 1111\}$
Codewörter $X_P =$ "alle mit einem :heavy_check_mark: in der Tabelle"
$X_P = \{0000,\ 0011,\ 0101,\ 0110,\ 1001,\ 1010,\ 1100,\ 1111\}$
$X_P \subset X$

Fehler durch Fehlerursache $E = e_1,\ \ldots,\ e_k$
Das i-te Bit ist fehlerhaft genau dann wenn $e_i = 1$
Übertragende Daten mit auftretenden Fehlern: $u_i' = u_i \oplus e_i$

Paritätscode erkennt ein Fehler wenn folgendes gilt:

> die Summe der Elemente ist $1$ oder Summe der Elemente modulo 2 gleich $1$ ist
> [name=Til]

> genau dann wenn Summe e_i gleich 1 (modulo 2)
> [name=Prof. Dr. Gössel] [color=#0e8cd0]

> alle ungerade Bitfehler
> [name=ich] [color=#245f56]


## Verdoppelung und Vergleich
bei $k=3$:
$u_1,\ u_2,\ u_3,\ c_1=u_1,\ c_2=u_2,\ c_3=u_3$

Wir verdoppeln somit die Daten zu
$u_1,\ u_2,\ u_3,\ u_1,\ u_2,\ u_3$

| $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | |
|:--------:|:-----:|:-----:|:-----:|:-----:|:-----:|:----------------------------- |
| 0 | 0 | 0 | 0 | 0 | 0 | :heavy_check_mark: |
| 0 | 0 | 0 | 0 | 0 | 1 | :negative_squared_cross_mark: |
| 0 | 0 | 0 | 0 | 1 | 0 | :negative_squared_cross_mark: |
| 0 | 0 | 0 | 0 | 1 | 1 | :negative_squared_cross_mark: |
| $\ldots$ | | | | | | |
| 0 | 0 | **1** | 0 | 0 | **1** | :heavy_check_mark: |
| $\ldots$ | | | | | | |
| 0 | **1** | 0 | 0 | **1** | 0 | :heavy_check_mark: |
| $\ldots$ | | | | | | |
| 0 | **1** | **1** | 0 | **1** | **1** | :negative_squared_cross_mark: |
| $\ldots$ | | | | | | |
| **1** | **1** | **1** | **1** | **1** | 0 | :negative_squared_cross_mark: |
| **1** | **1** | **1** | **1** | **1** | **1** | :heavy_check_mark: |

:::info
Bei **Verdoppelung und Vergleich**
8 von 64 Wörtern sind Codewörter $\Rightarrow \frac{1}{8}$
Für allgemeine Wortbreite $= \frac{2^n}{2^{2n}} = \frac{1}{2^{n}}$
$\Rightarrow$ unwahrscheinlich auf ein anderes Codewort zu stoßen bei einem Bitfehler

Bei **Paritätscode**
$\frac{8}{16} = \frac{1}{2}$
Für allgemeine Wortbreite $= \frac{2^n}{0.5\cdot 2^n} = \frac{1}{2}$
$\Rightarrow$ bleibt konstant unabhängig von $k$
:::

### Fehleranalyse
#### 1-Bit-Fehler
$\binom{6}{1} = \frac{6}{1} = 6$
:::spoiler Liste aller 1-Bit-Fehler
$E_1 =$ **1**00000
$E_2 =$ 0**1**0000
$E_3 =$ 00**1**000
$E_4 =$ 000**1**00
$E_5 =$ 0000**1**0
$E_6 =$ 00000**1**
:::

**Alle Fehler werden erkannt**

#### 2-Bit-Fehler
$\binom{6}{2} = \frac{6 \cdot 5}{2} = 15$

:::spoiler Liste aller 2-Bit-Fehler
$E_{12} =$ **11**0000
$E_{13} =$ **1**0**1**000
$E_{14} =$ **1**00**1**00 :negative_squared_cross_mark:
$E_{15} =$ **1**000**1**0
$E_{16} =$ **1**0000**1**
$E_{23} =$ 0**11**000
$E_{24} =$ 0**1**0**1**00
$E_{25} =$ 0**1**00**1**0 :negative_squared_cross_mark:
$E_{26} =$ 0**1**000**1**
$E_{34} =$ 00**11**00
$E_{35} =$ 00**1**0**1**0
$E_{36} =$ 00**1**00**1** :negative_squared_cross_mark:
$E_{45} =$ 000**11**0
$E_{46} =$ 000**1**0**1**
$E_{56} =$ 0000**11**
:::

**3 Fälle werden nicht erkannt, 12 werden als Fehler erkannt**
:::spoiler Fälle die nicht erkannt werden
$E_{14} =$ 100100
$E_{25} =$ 010010
$E_{36} =$ 001001
:::

#### 3-Bit-Fehler
$\binom{6}{3} = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2} = 20$

:::spoiler Liste aller 3-Bit-Fehler
use your imagination :stuck_out_tongue_winking_eye:
:::

**Alle Fehler werden erkannt**

#### 4-Bit-Fehler
$\binom{6}{4} = \frac{6 \cdot 5 \cdot 4 \cdot 3}{4 \cdot 3 \cdot 2} = 15$

:::spoiler Liste aller 4-Bit-Fehler
use your imagination :stuck_out_tongue_winking_eye:
:::

**3 Fälle werden nicht erkannt, 12 werden als Fehler erkannt**
:::spoiler Fälle die nicht erkannt werden
$E_{1245} =$ 110110
$E_{2356} =$ 011011
$E_{1346} =$ 101101
:::

#### 5-Bit-Fehler
$\binom{6}{5} = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2}{5 \cdot 4 \cdot 3 \cdot 2} = 6$
:::spoiler Liste aller 1-Bit-Fehler
use your imagination :stuck_out_tongue_winking_eye:
:::

**Alle Fehler werden erkannt**

#### 6-Bit-Fehler
$\binom{6}{6} = 1$

**Fehler wird nicht erkannt**

### Feheranalyse
| Anzahl Bit Fehler | erkannt | nicht erkannt |
| -----------------:|:-------:|:------------- |
| 1 | 6 | 0 |
| 2 | 12 | 3 |
| 3 | 20 | 0 |
| 4 | 12 | 3 |
| 5 | 6 | 0 |
| 6 | 0 | 1 |
| $\Rightarrow$ | **56** | **7** |

7 von 63 Fehler erkannt = 11% nicht erkannt

:::spoiler *Hausaufgabe* Tabelle für n=4:
| Anzahl Bit Fehler | erkannt | nicht erkannt |
| -----------------:|:-------:|:------------- |
| 1 | 8 | 0 |
| 2 | 24 | 4 |
| 3 | 56 | 0 |
| 4 | 64 | 6 |
| 5 | 56 | 0 |
| 6 | 25 | 4 |
| 7 | 8 | 0 |
| 8 | 0 | 1 |
| $\Rightarrow$ | **240** | **15** |
:::
*Hausaufgabe* allgemeine Formel
nicht erkannt = sum x=1 to 2n of (Piecewise[{{binomial(n,x/2), x modulo 2 = 0}},0]) where n=4
[erkannt](https://www.wolframalpha.com/input?i=sum+x%3D1+to+2n+of+(binomial(2n%2Cx)+-+Piecewise[{{binomial(n%2Cx%2F2)%2C+x+modulo+2+%3D+0}}%2C0])+where+n%3D4) = $\displaystyle\sum_{x=1}^{2n} \left(\binom{2n}{x}-\left(\begin{cases}\binom{n}{x / 2} & x\%2=0\\0 & \text{sonst}\end{cases}\right)\right)$

[nicht erkannt](https://www.wolframalpha.com/input?i=sum+x%3D1+to+2n+of+(Piecewise[{{binomial(n%2Cx%2F2)%2C+x+modulo+2+%3D+0}}%2C0])+where+n%3D4) = $\displaystyle\sum_{x=1}^{2n} \left(\begin{cases}\binom{n}{x / 2} & x\%2=0\\0 & \text{sonst}\end{cases}\right)$

### Häufige Anforderungen
Typischerweise Erkennen von allen 1- und 2- (manchmal auch 3-) Bit-Fehlern.
Andere Anforderungen treten nur sehr selten auf.

> Üblicherweise wird die Fehlererkennung einer bestimmten! Menge von Fehler gefordert und garantiert.
[name=Prof. Dr. Gössel] [color=#0e8cd0]

Marketing bei Verdoppelung und Vergleich:
Vermarkten von 1- und 2-Bit-Fehlern = 3/21 = 14% Nicht-Erkennungsrate
Vermarkten von 1-, 2- u. 3-Bit-Fehlern = 3/41 = 7.3% Nicht-Erkennungsrate

## Neues Modell
1-Bit-Fehler mit Wahrscheinlichkeit $p$
:warning: Fehlerauftreten stochastitsch unabhängig voneinander

### Multibitfehler
alle Fehler gleichberechtigt, haben wir beim Paritätscode verwendet
kein Fehlermodell verwendet

### Kausalketten
> "[Ich habe Frau kennengelernt, weil ich bei X arbeite, ich arbeite bei Y weil da beworben, weil ich nicht mehr an der Uni arbeiten wollte, weil ich nicht Entwicklungsmöglichkeiten mehr gab, weil keine angeboten, weil Chef nicht wollte, weil Stelle nur befristet, weil anderweilige Pläne, weil er anders beschäftigt, weil er es so wollte, weil er es so wollte, weil er nach Indien wollte.]"
> [name=someone]

> "[Prof geworden, weil dazu an FU beworben, da Akzeinkurs unter X, weil Akzienkrieg, weil Halbleiter alle zu decken, weil Automatisierung wurde perfekt eingefühhrt, weil kluge Köpfe im Management, weil Technik zur Verfügung stand, weil Simens investiert, weil Simens hatte großen plan, weil hatte zu Wissen Zugang, weil Simens zu den gruppen gehört, weil Kriterien, erfüllte, weil es sie die erfüllte.]"
[name=someone]

*Hausaufgabe*

> Ich mache diesen Kurs, da ich für dieses Semester Kurse machen muss.
> Ich muss dieses Semester Kurse machen, da ich im UP Master bin.
> Ich bin im UP Master, da ich meinen UP Bachelor abgeschlossen habe.
> Ich habe meinen UP Bachelor abgeschlossen, da ich ihn in Potsdam angefangen habe.
> Ich habe meinen Bachelor in Potsdam angefangen, da es sich angeboten hat.
> Angeboten hat es sich, da ich mich beworben hab.
> Beworben hab ich mich, da ich den Wohnheimsplatz sicher hatte.
> Den Wohnheimsplatz hatte ich sicher, da ich mich frühzeitig beworben habe.
> Frühzeitig beworben habe ich mich, da mir Leute am HPI dies geraten haben.
> Sie haben es mir geraten, da ich bei ihnen Veranstaltungen besucht habe.
> Ich habe diese Veranstaltungen besucht, da ich Interese am Thema habe.
> Interesse am Thema habe ich, da es mir Spaß macht.
> Spaß macht mir das Thema, da ich als Kind viel damit zu tun hatte.
> Als Kind hatte ich viel damit zu tun, da mein Vater es mir viel gezeigt hat.
> Mein Vater hat mir viel davon gezeigt, weil er ihm auch Spaß macht.
> Es macht ihm Spaß, weil ...
> [name=ich] [color=#245f56]

<br>

(c) *Sven Koch, 791664, WS22/23*
:::spoiler *`overscroll`*
<br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/>
:::
###### tags: `Codierungstheorie` `Vorlesung`