imported>Itti: Änderungen von Putzezumerbrechenbringer (Diskussion) auf die letzte Version von Valeee04 zurückgesetzt

2026-02-03T22:43:18Z

Änderungen von Putzezumerbrechenbringer (Diskussion) auf die letzte Version von Valeee04 zurückgesetzt

Neue Seite

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 (Mathematik)|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>).

Zur Kodierung verwendet man als Alphabet eine beliebige [[abelsche Gruppe]] <math>(A,\mathord+)</math>, meist <math>(\{0,1\},\mathord+)</math>, die [[zyklische Gruppe]] der [[Gruppenordnung|Ordnung]] zwei, da man deren beiden Elemente mit den [[Bit]]s 0 und 1 identifizieren kann.

Die [[Quellenkodierung|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 einen [[Injektivität|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]]
{| class="wikitable"
|- class="hintergrundfarbe5"
! + || 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 ==
* Ein [[linearer Code]] ist eine Codierung, bei der statt einer Gruppe ein [[endlicher Körper]] verwendet wird.

[[Kategorie:Kodierungstheorie]]

Gruppencode - Versionsgeschichte

imported>Itti: Änderungen von Putzezumerbrechenbringer (Diskussion) auf die letzte Version von Valeee04 zurückgesetzt