Hauptmenü öffnen
Systematischer Blockcode aus voneinander getrennten Informations- und Prüfsymbolen

Blockcodes sind eine Art der Kanalkodierung der Familie der (fehlererkennenden und) fehlerkorrigierenden Codes. Sie zeichnen sich durch eine feste Blockgröße aus Symbolen eines festen Alphabets (bei Binärcodes ) aus. Einzelne Blocks werden im Gegensatz zu Faltungscodes unabhängig voneinander kodiert und dekodiert.

Wichtige Eigenschaften eines Blockcodes sind die Informationsrate (das Verhältnis aus enthaltener Informationsmenge zur Gesamt-Datenmenge ) sowie seine Korrekturrate (d. h. die Fähigkeit Fehler zu erkennen und/oder zu korrigieren). Beide Eigenschaften beeinflussen sich gegenseitig und spannen eine gemeinsame, unüberwindbare Schranke auf. Durch Optimierung kann man sich der Schranke nähern, erhält aber lange und aufwändig zu dekodierende Codes. Hier hat sich das Kaskadieren von Codes als praktikablere Lösung erwiesen.

Obwohl Blockcodes häufig nicht optimal im Sinne einer minimalen mittleren Codewortlänge sind, schränkt man sich oft auf Blockcodes ein. Eine weitere Spezialisierung stellen lineare Codes und systematische Codes dar.

Inhaltsverzeichnis

AufbauBearbeiten

Aus dem Alphabet   und der Blockgröße   ergeben sich   mögliche Worte, von denen ein Subset   die gültigen Codeworte darstellt. Die Mächtigkeit des Alphabets   wird mit   bezeichnet, sie beträgt im Falle von Binärcodes  . Die Mächtigkeit des Codes   kann bei vielen Codes (bei linearen Codes immer) als   mit   geschrieben werden. Diese Codes können bei einer Blockgröße von   Symbolen eine Nutzlast   tragen.

Die Informationrate beträgt  , die Korrekturrate wird durch den (minimalen) Hamming-Abstand des Codes   limitiert. Der Hamming-Abstand zweier Codeworte   und   ist hierbei die Anzahl unterschiedlicher Symbole dieser Codeworte  , der (minimale) Hamming-Abstand   eines (ganzen) Codes   ist der minimale Hamming-Abstand aller (disjunkten) Codewort-Paare, d. h.  . Letztere beschränkt die maximale (zuverlässige) Korrekturleistung auf   Symbolfehlern mit   ein. Bei kaskadierten Korrekturverfahren spielt neben der Fehlerkorrektur auch die Fehlererkennung eine Rolle. Zum einen erkennen Nicht-perfekte Codes eine gewisse Menge an Mehrbit-Fehler mit  , die sie selbst nicht mehr korrigieren können, zum anderen kann man Fehlerkorrektur-Fähigkeiten gegen weitere (garantierte) Fehlererkennungs-Fähigkeiten   eintauschen und damit folgende Korrektur-Stufen unterstützen:  .

Für Codes haben sich (leider) etliche Notationen eingebürgert:

  •   oder  , häufig wird das Semikolon durch ein Komma ersetzt, die eckigen Klammern durch runde Klammern.   wird häufig weggelassen, gleiches gilt für das   der klassischen Hamming-Codes.
  • häufig wird statt   (der Anzahl der Nutzsymbole) die Mächtigkeit des Codes  , d. h.   oder der Code selbst angegeben   angegeben, zum Teil wird diese Information in der Art der verwendeten Klammern versteckt.

Im weiteren wird versucht, dies wie auch die Nutzung von Variablennamen sowohl in diesem Artikel wie auch in verwandten Artikeln konsistent zu halten.

Man bezeichnet allgemein   als einen  -Code, falls

  •   ein Alphabet mit   ist,
  • der Code   ist und
  • der (minimalen) Hamming-Abstand   ist.

Betrachtet man lineare Codes, so spricht man von  -Codes bzw.  -Codes, wobei   hier die Dimension von   über dem Körper   ist.   und   haben dabei die gleiche Bedeutung wie bei den allgemeinen Blockcodes.

 
There theoretical limits (such as the hamming limit), but another question is which codes can actually constructed. It is like putting spheres in a box … This diagram shows the constructable codes, which are linear and binary. The x-axis shows the number of protected symbols k, the y-axis the number of needed check symbols n-k. Plotted are the limits for different Hamming distances from 1 (unprotected) to 34.
Marked with dots are perfect codes:
  • hellorange auf der x-Achse: trivial unproteced codes
  • orange, auf der y-Achse: trivial repeat codes
  • dunkelorange, auf der Linie für d=3: classic perfect hamming codes
  • dunkelrot und groß: the only perfect binary Golay code

Man interessiert sich bei gegebenem  ,   und   für eine Maximierung der Mächtigkeit des Codes, d. h. für  , da hierbei eine optimale Informationsrate für diese Parameter erzielt wird. Allerdings gibt es günstige Parameter, die zu effizienteren Codes als ihre Nachbarparameter führen. So fordert ein  -Code 11 Schutzbits, ein  -Code allerdings schon 14. Ein  - kommt wie ein  -Code mit 17 Schutzbits aus.

Es gibt Abschätzungen, ob Codes möglich sein könnten oder gegen gewisse Prinzipien verstoßen:

Schranken weisen darauf hin, ob Codes existieren können, nicht ob sie konstruierbar sind und wirklich existieren.

Typen von BlockcodesBearbeiten

Formal heißt der Code   Blockcode, wobei   als Alphabet bezeichnet wird und   die Länge jedes Codewortes   ist.

Triviale Blockcodes sind Codes

  • die nur ein Wort als Code umfassen:  . Es lassen sich alle Übertragungsfehler erkennen, aber keine Information übertragen oder
  • die alle möglichen Worte als Code umfassen:  . Es lassen sich keine Übertragungsfehler erkennen, die übertragene Information ist aber maximal.
Bemerkungen:
  • Der erste Code lässt sich als  -Code schreiben. Er hat im klassischen Sinne keine Hamming-Distanz, da es keine Codepaare gibt. Es lassen sich bis zu maximal   Symbolfehler im übertragenen Wort   korrigieren (das übertragene Codewort ist bekannt), was eine typische Eigenschaft für Codes mit   ist. Das gleiche gilt für die Anzahl von Codes, die sich eindeutig dekodieren lassen. Die Gleichung   liefert für   das richtige Ergebnis.
  • Der zweite Code lässt sich als  -Code schreiben. Er hat eine Hamming-Distanz von 1.

Lineare Blockcodes sind Codes,
wenn   ein  -dimensionaler Untervektorraum von   ist. Es existiert dann eine Basis   von  . Fasst man diese Basis zu einer Matrix

 

zusammen, erhält man eine Generatormatrix dieses linearen Blockcodes. Die Codeworte erhält man durch Multiplizieren des Eingangssignals   mit der Generatormatrix

 

Der Hauptvorteil linearer Code ist die einfache Codierbarkeit und die einfache Decodierbarkeit.

Bemerkungen:
Zur Kodierung eines Codes mit   Codeworten muss man nur noch   Codeworte vorrätig halten. Gleiches gilt für die Dekodierung mit   vs.  .

Paritätscodes sind
lineare, systematische und binäre Codes mit der Prüfsymbol-Generatormatrix

  und der Gesamt-Generatormatrix  

Sie haben eine Hamming-Distanz von 2 und stellen  -Blockcodes dar. Sie können einen Fehler erkennen, aber keine Fehler korrigieren. Lineare binäre Blockcodes mit ungeradem Hamming-Abstand   lassen sich mit einem zusätzlichen Paritätscode zu einem  -Code erweitern.

Systematische Blockcodes sind Codes,
die aus   Informationssymbolen am Blockanfang und   Prüfsymbolen am Blockende bestehen (siehe Abbildung am Anfang des Artikels). Sie können gleichzeitig lineare Blockcodes sein, müssen es aber nicht. Sie sind lineare Blockcodes, wenn neben den Informationssymbolen (die immer linear sind) auch die Prüfsymbole linear sind.

Perfekte Blockcodes sind Codes,
in denen jedes Wort   nur zu genau einem Codewort   (und nicht zu mehreren) einen geringsten Hamming-Abstand   hat. Jedes Wort läßt sich damit eindeutig decodieren.

Hadamard-Codes
sind lineare nicht-systematische Blockcodes  . Die Generatormatrix hat eine sehr auffällige Form

 

Sie haben eine geringe Informationsrate, können aber noch Daten aus sehr fehlerbehafteten Signal dekodieren.

Informationsrate für BlockcodesBearbeiten

Sei   ein Blockcode und es gelte  , das Alphabet habe also   verschiedene Elemente. Dann lautet für   die Definition der Informationsrate:

 .

Ist z. B.   ein binärer Code mit   verschiedenen Elementen, dann benötigt man   Bits, um   verschiedene Codewörter zu unterscheiden. Die Informationsrate setzt die geringstmöglichen Anzahl an Symbolen ins Verhältnis zur tatsächlich übertragenen Anzahl an Symbolen.

Wenn die ersten   Bits eines binären  -Bit-Codeworts Informationsbits sind, die in allen möglichen Codeworten existieren, dann ist die Informationsrate:

 .

Beispiele für BlockcodesBearbeiten

Beispiel 1Bearbeiten

 

Die   Codeworte   lauten in der Binärdarstellung:

.........
....#####
.###...##
#.##.##..
##.##.#.#
###.##.#.

Es existiert kein linearer Code dieser Mächtigkeit. Zum einen ist  , zum anderen sind die größten lineare Code dieser Art ein  - und ein  -Code. Der Code lässt sich nicht in einen linearen Code umwandeln.

Beispiel 2Bearbeiten

 

Die   Codeworte   lauten in der Binärdarstellung (MSB links):

...........
...#...####
..#..##..##
..##.####..
.#..#.#.#.#
.#.##.##.#.
.##.##..##.
.#####.#..#
#...##.#.#.
#..###..#.#
#.#.#.##..#
#.###.#.##.
##...######
##.#.##....
###....##..
####.....##

Es handelt sich um einen linearen systematischen Code mit der Basis

...#...####
..#..##..##
.#..#.#.#.#
#...##.#.#.

Die 16 Codeworte lassen sich durch eine XOR-Verknüpfung der Basisvektoren erzeugen, deren Informationsbits gesetzt sind (daher linearer Code). Die Informationsbits stellen die linken 4 Bit dar (Bit 10 bis 7), die Schutzbits die rechten 7 Bit (Bit 6 bis 0) (daher systematischer Code).

Beispiel 3Bearbeiten

 

Die   Codeworte   lauten in der Binärdarstellung:

........
.....###
...##..#
...####.
..#.#.#.
..##.#.#
.#..#.##
.#.#.#..
.##....#
.##.##..
.###..#.
.#######
#...##..
#..#..##
#.#..##.
#.#.#..#
#.##....
##....#.
##...#.#
##.##...

Es existiert kein linearer Code dieser Mächtigkeit. Auch hier ist zum einen  , zum anderen sind die größten lineare Code dieser Art ein  - und ein  -Code. Der Code lässt sich nicht in einen linearen Code umwandeln.

FehlerkorrekturBearbeiten

Blockcodes können zur Fehlererkennung und Fehlerkorrektur bei der Übertragung von Daten über fehlerbehaftete Kanäle verwendet werden. Dabei ordnet der Sender dem zu übertragenen Informationswort der Länge   ein Codewort der Länge   zu, wobei  . Durch das Hinzufügen der   zusätzlichen Symbole entsteht Redundanz und die Informationsrate sinkt; jedoch kann der Empfänger die redundante Information nun dazu nutzen Übertragungsfehler zu erkennen und zu korrigieren.

Verwendet man beispielsweise, im Fall der Binärkodierung, die Zuordnung

Informationswort Codewort
0 000
1 111

so können empfangene Codewörter mit genau einem Bitfehler korrigiert werden, indem man mit Hilfe einer Mehrheitsfunktion das abweichende Bit umkehrt:

Fehlerhaftes
Codewort
Korrigiertes
Codewort
Zugeordnetes
Informationswort
001 000 0
010 000 0
011 111 1
100 000 0
101 111 1
110 111 1

Sind in diesem Falle jedoch zwei Bits falsch, so wird zwar ein Fehler erkannt, aber fehlerhaft korrigiert. Sind gar drei Bits falsch, so kann nicht einmal mehr ein Fehler erkannt werden.

LiteraturBearbeiten

  • Rudolf Nocker: Digitale Kommunikationssysteme 1. Grundlagen der Basisbandübertragung, 1. Auflage, Friedrich Vieweg & Sohn Verlag, Wiesbaden 2004, ISBN 978-3-528-03976-9.
  • Markus Hufschmid: Information und Kommunikation. Grundlagen der Informationsübertragung, Vieweg und Teubner, Wiesbaden 2006, ISBN 3-8351-0122-6.
  • Bernd Friedrichs: Kanalcodierung. Grundlagen und Anwendungen in modernen Kommunikationssystemen. Springer Verlag, Berlin/ Heidelberg 1995, ISBN 3-540-59353-5.

WeblinksBearbeiten