---
# System prepended metadata

title: VL 4 Codierungstheorie
tags: [Vorlesung, Codierungstheorie]

---

# 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:
![](https://i.imgur.com/cgxBzFQ.png)

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

Beispiel:
![](https://i.imgur.com/fxT9qPC.png)

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**:
![](https://i.imgur.com/7C5E5Qi.png)

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
![](https://i.imgur.com/q5OC4HX.png)
(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`











