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