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.

Siehe auch

• Ein linearer Code ist eine Codierung, bei der statt einer Gruppe ein endlicher Körper verwendet wird.