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 Bearbeiten
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 ).
Zur Kodierung verwendet man als Alphabet eine beliebige abelsche Gruppe , meist , 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 . (Alle Wörter mit Symbolen aus der Länge )
Um die Gruppe zu Codieren wählt man einem injektiven Homomorphismus . Das Bild von ist eine Untergruppe von .
ist der Gruppencode. die zugehörige Kodierungsfunktion.
Im Gegensatz zu „willkürlichen“ Codierungen muss nicht für jedes Codewort extra angegeben (gespeichert) werden, sondern es reicht für ein erzeugendes System der Gruppe zu definieren. Die Codierung der restlichen Elemente kann dann mittels deren Darstellung als Summe von erzeugenden Elementen berechnet werden.
Beispiele Bearbeiten
Beispiel 1 Bearbeiten
Gruppe
Quellcodierung:
erzeugendes System: , ,
Codierung: , ,
Sei nun ein Wort in Quellcodierung. Um die Codierung zu berechnen geht man wie folgt vor:
Man stellt als Summe von erzeugenden Elementen dar:
und berechnet dann die Summe der Codierungen der selbigen
Beispiel 2 Bearbeiten
Gruppe , 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:
erzeugendes System: , , ,
Codierung: , , ,
Sei nun ein Wort in Quellcodierung. ,,
Eigenschaften Bearbeiten
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 Bearbeiten
- Ein linearer Code ist eine Codierung, bei der statt einer Gruppe ein endlicher Körper verwendet wird.