Gruppencode
# Gruppencode

In der Kodierungstheorie (Informatik) versteht man unter einem Gruppencode eine spezielle Codierung, die man zur Fehlererkennung und Fehlerkorrektur verwenden kann. Für die Codierung wird eine Gruppe (algebraische Struktur) verwendet.

## Codierung

Ein Gruppencode ist ein Blockcode, das heißt alle Codewörter haben die gleiche Länge (Im weiteren bezeichnen wir die Länge der Codewörter mit $n$).

Zur Kodierung verwendet man als Alphabet eine beliebige abelsche Gruppe $(A,{\mathord {+}})$, meist $(\{0,1\},{\mathord {+}})$, die zyklische Gruppe der Ordnung zwei, da man deren beiden Elemente mit den Bits 0 und 1 identifizieren kann.

Die quellkodierten Wörter sind die Elemente der Gruppe $(A,{\mathord {+}})^{k}$. (Alle Wörter mit Symbolen aus $A$ der Länge $k$)

Um die Gruppe $(A,{\mathord {+}})^{k}$ zu Codieren wählt man einem injektiven Homomorphismus $f\colon (A,{\mathord {+}})^{k}\to (A,{\mathord {+}})^{n}$. Das Bild von $f$ ist eine Untergruppe $(C,{\mathord {+}})$ von $(A,{\mathord {+}})^{n}$.

$C$ ist der Gruppencode. $f$ die zugehörige Kodierungsfunktion.

Im Gegensatz zu „willkürlichen“ Codierungen muss $f$ nicht für jedes Codewort extra angegeben (gespeichert) werden, sondern es reicht $f$ für ein erzeugendes System der Gruppe $(A,{\mathord {+}})^{k}$ zu definieren. Die Codierung der restlichen Elemente kann dann mittels deren Darstellung als Summe von erzeugenden Elementen berechnet werden.

## Beispiele

### Beispiel 1

Gruppe $(\{0,1\},{\mathord {+}})$

Quellcodierung: $(\{0,1\},{\mathord {+}})^{3}$

erzeugendes System: $e_{1}=(1,0,0)$, $e_{2}=(0,1,0)$, $e_{3}=(0,0,1)$

Codierung: $f(e_{1})=(1,1,0,0,0)$, $f(e_{2})=(0,0,1,1,0)$, $f(e_{3})=(1,0,1,0,1)$

Sei nun $c=(1,0,1)$ ein Wort in Quellcodierung. Um die Codierung $f(c)$ zu berechnen geht man wie folgt vor:

Man stellt $c$ als Summe von erzeugenden Elementen dar: $c=(1,0,1)=e_{1}+e_{3}$

und berechnet dann die Summe der Codierungen der selbigen $f(c)=f(e_{1})+f(e_{3})=(1,1,0,0,0)+(1,0,1,0,1)=(0,1,1,0,1)$

### Beispiel 2

Gruppe $(\{0,1,x,x+1\},{\mathord {+}})$, die Kleinsche Vierergruppe

| + | 0 | 1 | x | x+1 |
| - | - | - | - | - |
| 0 | 0 | 1 | x | x+1 |
| 1 | 1 | 0 | x+1 | x |
| x | x | x+1 | 0 | 1 |
| x+1 | x+1 | x | 1 | 0 |

Quellcodierung: $(\{0,1,x,x+1\},{\mathord {+}})^{2}$

erzeugendes System: $e_{1}=(1,0)$, $e_{2}=(x,0)$, $e_{3}=(0,1)$, $e_{4}=(0,x)$

Codierung: $f(e_{1})=(1,0,0)$, $f(e_{2})=(1,1,0)$, $f(e_{3})=(x,1,1)$, $f(e_{4})=(0,0,x)$

Sei nun $c=(1,x+1)$ ein Wort in Quellcodierung. $c=e_{1}+e_{3}+e_{4}$,$f(c)=f(e_{1})+f(e_{3})+f(e_{4})=(1,0,0)+(x,1,1)+(0,0,x)=(x+1,1,x+1)$,

## Eigenschaften

Gruppencodes erfüllen folgende Eigenschaften:

* Die Codewörter bilden eine Gruppe
* Bei einem binären Gruppencode ist die Distanzverteilung jeweils gleich für alle Codewörter und auch gleich der Gewichtsverteilung.
* Jeder Gruppencode enthält den „Nullvektor“ als gültiges Codewort.
* Das Gewicht eines Gruppencodes ist definiert als das kleinste Codewortgewicht (Hamming-Gewicht) außer dem des Nullvektors.
* Bei binären Gruppencodes gilt, dass der Hamming-Abstand dem Gewicht des Codes entspricht.
