# VL 4 Codierungstheorie

## AN-Code
$(u_1,\ \ldots,\ u_k) \cdot c = v_1,\ \ldots,\ v_n$
$c$ := Wert zum Mulitplizieren, z.B.:
$3 = 11_2$
$7 = 111_2$
$(15 = 1111_2)$
$31 = 11111_2$
$\vdots$

Berechnen von $c$ wie folgt:

Codewörter: Vielfachen von Datenwörter
Konstante ist so gewählt, dass Multiplikation leicht ist

Beispiel:

Code ist nicht seperierbar in Datenbits und Prüfbits
seperierbare Codes $\Rightarrow$ Kann schon bits nutzen und dann prüfen, ob diese richtig sind. Bei nicht seperierbaren muss zuerst die Transformation angewandt werden.

Ist Code linear? GF(2) wenn ein Codewort + ein Codewort = ein anderes Codewort
& Codewort + 0000 = Codewort
Also nein ist nicht linear, da nicht für jedes Codewort Codewort + Codewort = Codewort.
Man muss drauf achten in welchem Köper man rechnet

## M-aus-N Code
nicht seperierbarer Code
### 1-aus-3-Code
Code / Menge der Codewörter = $\{001,\ 010,\ 100\}$
Menge der NICHT-Codewörter = $\{000,\ 011,\ 101,\ 110,\ 111\}$
#### Mengentheoretische Darstellung
000 :negative_squared_cross_mark:
001 :heavy_check_mark:
010 :heavy_check_mark:
011 :heavy_check_mark:
100 :negative_squared_cross_mark:
101 :negative_squared_cross_mark:
110 :negative_squared_cross_mark:
111 :negative_squared_cross_mark:

### 1-aus-4-Code
Code / Menge der Codewörter = $\{0001,\ 0010,\ 0100,\ 1000\}$
Menge der NICHT-Codewörter = $\{0000,\ 0011,\ 0101,\ 0110,\ 0111,\ \ldots\}$

| $u_1$ | $u_2$ | | $v_1$ | $v_2$ | $v_3$ | $v_4$ |
| ----- | ----- | --- | ----- | ----- | ----- | ----- |
| 0 | 0 | | 1 | 0 | 0 | 0 |
| 0 | 1 | | 0 | 1 | 0 | 0 |
| 1 | 0 | | 0 | 0 | 1 | 0 |
| 1 | 1 | | 0 | 0 | 0 | 1 |

$\quad\Rightarrow$
$v_1 = \overline{u_1 u_2}$
$v_2 = \overline{u_1} u_2$
$v_3 = u_1 \overline{u_2}$
$v_4 = u_1 u_2$

**Encoder**:

alternativ kann man auch eine andere Tabelle verwenden, z.B.:
| $u_1$ | $u_2$ | | $v_1$ | $v_2$ | $v_3$ | $v_4$ |
| ----- | ----- | --- | ----- | ----- | ----- | ----- |
| 0 | 0 | | 0 | 0 | 1 | 0 |
| 0 | 1 | | 1 | 0 | 0 | 0 |
| 1 | 0 | | 0 | 0 | 0 | 1 |
| 1 | 1 | | 0 | 1 | 0 | 0 |

$\quad\Rightarrow$
$v_1 = u_1 \overline{u_2}$
$v_2 = \overline{u_1 u_2}$
$v_3 = u_1 u_2$
$v_4 = \overline{u_1} u_2$

**Prüfer / Decoder** mit Fehlererkennung:
prüft, ob wir ein Codewort haben - ist es ein 1-aus-4-Codewort
(ein AND-Gate für jedes mögliche Codewort, kann aber vereinfacht werden, siehe | und Kreis bei AND_Gate-Inputs)
wenn Fehlermodell unidirektional (nur $0 \leadsto 1$ Fehler), dann reicht es Bits zu zählen, z.b. Berger-Code

### 2-aus-4-Code
Codewörteranzahl = $\binom{4}{2}$ = 6
Code / Menge der Codewörter = {0011, 0101, 0110, 1001, 1010, 1100}

## Parity Code
$u_1,\ \ldots,\ u_5,\ c$
$c = u_1 \oplus \ldots \oplus u_5$
### Group-Parity Code
z.B.:
$c_1 = u_1 \oplus u_2 \oplus c_4$
$c_2 = u_1 \oplus u_3 \oplus c_5$
$c_3 = u_2 \oplus u_4 \oplus c_5$

dadurch lassen sich alle linearen Codes abbilden

# Definition eines Codes

1) Wie betrachten eine Menge $X$, bspw. n-stellige Binärwörter

3) Wir wählen eine Teilmnge $\mathfrak{X} \subset X$
$\mathfrak{X}$ ==hilft==(?) Code
Ein Code ist eine Teilmenge $\mathfrak{X}$ von $X$

3) Wir codieren eine Menge von Daten
Wir ordnen jedem $d\in D$ ein Element aus $\mathfrak{X}$ zu
$C(d)\in\mathfrak{X}$, jedem Element $d$ der Daten wird ein Codewort zugeordnet.
Forderung für sinvolle Coderiung:
für $d\neq d' \rightarrow C(d) \neq C(d')$
Unterschiedlichen Daten d und d' werden unterschiedlche Codewörter zugeordnet.

4) **Kanal**
Wir übertragen ein codiertes Element $x = C(d)$ über einen (gestörten) Kanal $K$.
$x = C(d)$ wird in den Kanal eingegeben
$f = K(x) = K(C(d))$ wird aus dem Kanal ausgelesen

Zwei Möglichkeiten:
**a)** $f\in\mathfrak{X} \Rightarrow f$ ist Codewort:

Ist $f \in \mathfrak{X}$ Codewort: Ees wird kein Fehler erkannt
Vermutung: es ist kein fehler aufgetreten
Es ist "möglich", dass kein Fehler vorliegt oder, dass ein Codewort in ein anderes Codewort gestört wurde.

**b)** $f\notin\mathfrak{X} \Rightarrow f$ ist ++kein++ Codewort:

Wir **wissen**, dass ein Fehler aufgetreten ist.
$f\notin\mathfrak{X}$, dann erkennne wir sicher, dass ein Fehler vorliegt.

$f$ ist Codewort dadurch kein Fehler, keine Korrektur nötig.

$f$ ist kein Codewort, $f$ wird durch $f^{Corrected}$ vertauscht
$f$ wird dann ein Codewort ver, welches sich möglich wenig von $f$ unterscheidet
$f^{Corrected}$ sollte sich wenig von $f$ unterschieden
Praktik: $f^{Corrected}$ unterschiedet $f$ in mäglichst wenig Bits
Wähle $f^{Corrected}$ so, dass der Abstand $\delta(f, f^{Corrected})$ minimal ist

## Logische Definition
### seperierbare Codes
Datenbits $u_1,\ \ldots,\ u_k$
Prüfbits $c_1,\ \ldots,\ c_m$
$c_1 = f_1(u_1,\ \ldots,\ u_k)$
$c_2 = f_2(u_1,\ \ldots,\ u_k)$
$\vdots$
$c_m = f_m(u_1,\ \ldots,\ u_k)$
$f$ = $k$ stellige boolesche Funktion

### nicht seperierbare Codes:
$u_1,\ \ldots,\ u_k \rightarrow v_1,\ \ldots,\ v_m$
$v_1 = g_1(u_1,\ \ldots,\ u_k)$
$v_2 = g_2(u_1,\ \ldots,\ u_k)$
$\vdots$
$v_m = g_m(u_1,\ \ldots,\ u_k)$

:::info
**HA**: wie viele boolesche Funktionen es von k Variablen gibt
$2^{2^k}$
:::

<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`