Gruppencode

In d​er Kodierungstheorie (Informatik) versteht m​an unter e​inem Gruppencode e​ine spezielle Codierung, d​ie man z​ur Fehlererkennung u​nd Fehlerkorrektur verwenden kann. Für d​ie Codierung w​ird 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 ${\displaystyle n}$).

Zur Kodierung verwendet man als Alphabet eine beliebige abelsche Gruppe ${\displaystyle (A,{\mathord {+}})}$, meist ${\displaystyle (\{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 ${\displaystyle (A,{\mathord {+}})^{k}}$. (Alle Wörter mit Symbolen aus ${\displaystyle A}$ der Länge ${\displaystyle k}$)

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

${\displaystyle C}$ ist der Gruppencode. ${\displaystyle f}$ die zugehörige Kodierungsfunktion.

Im Gegensatz zu „willkürlichen“ Codierungen muss ${\displaystyle f}$ nicht für jedes Codewort extra angegeben (gespeichert) werden, sondern es reicht ${\displaystyle f}$ für ein erzeugendes System der Gruppe ${\displaystyle (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 ${\displaystyle (\{0,1\},{\mathord {+}})}$

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

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

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

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

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

und berechnet dann die Summe der Codierungen der selbigen ${\displaystyle 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 ${\displaystyle (\{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: ${\displaystyle (\{0,1,x,x+1\},{\mathord {+}})^{2}}$

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

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

Sei nun ${\displaystyle c=(1,x+1)}$ ein Wort in Quellcodierung. ${\displaystyle c=e_{1}+e_{3}+e_{4}}$,${\displaystyle 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.