Gruppencode - LinkFang.de





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 [math]n[/math]).

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

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

[math]C[/math] ist der Gruppencode. [math]f[/math] die zugehörige Kodierungsfunktion.

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

Beispiele

Beispiel 1

Gruppe [math](\{0,1\},\mathord +)[/math]

Quellcodierung: [math](\{0,1\},\mathord +)^3[/math]

erzeugendes System: [math]e_1 = (1,0,0)[/math], [math]e_2 = (0,1,0)[/math], [math]e_3 = (0,0,1)[/math]

Codierung: [math]f(e_1) = (1,1,0,0,0)[/math], [math]f(e_2) = (0,0,1,1,0)[/math], [math]f(e_3) = (1,0,1,0,1)[/math]

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

Man stellt [math]c[/math] als Summe von erzeugenden Elementen dar: [math]c=(1,0,1)=e_1+e_3[/math]

und berechnet dann die Summe der Codierungen der selbigen [math]f(c)=f(e_1)+f(e_3)=(1,1,0,0,0)+(1,0,1,0,1)=(0,1,1,0,1)[/math]

Beispiel 2

Gruppe [math](\{0,1,x,x+1\},\mathord+)[/math], 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: [math](\{0,1,x,x+1\},\mathord+)^2[/math]

erzeugendes System: [math]e_1 = (1,0)[/math], [math]e_2 = (x,0)[/math], [math]e_3 = (0,1)[/math], [math]e_4 = (0,x)[/math]

Codierung: [math]f(e_1) = (1,0,0)[/math], [math]f(e_2) = (1,1,0)[/math], [math]f(e_3) = (x,1,1)[/math], [math]f(e_4) = (0,0,x)[/math]

Sei nun [math]c=(1,x+1)[/math] ein Wort in Quellcodierung. [math]c=e_1+e_3+e_4[/math],[math]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) [/math],

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


Kategorien: Kodierungstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Gruppencode (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.