Zum Inhalt springen

Blockcode

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 23. Juli 2016 um 21:38 Uhr durch Frank Klemm (Diskussion | Beiträge) (Verwendete (einheitliche) Notation in der Diskussion. Etliches ist noch mehrfach im Artikel.). Sie kann sich erheblich von der aktuellen Version unterscheiden.
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 von einander 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 die linearen Codes dar und davon wiederrum die systematischen Codes.

Aufbau

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.

Die Spannung zwischen Effizienz (große Informationsrate) und Korrekturfähigkeit lässt sich auch durch den Versuch erkennen, bei einer bestimmten Anzahl Bits pro Codewort und einer bestimmten Korrekturrate (dargestellt durch den Hamming-Abstand ) die gesamte Anzahl der Codewörter zu maximieren.

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 [n, k; d, q]-Codes bzw. [n, k; d]q-Codes, wobei hier die Dimension von über dem Körper ist. und haben dabei die gleiche Bedeutung wie bei den allgemeinen Blockcodes.

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:

Die Existenz ist aber erst mit der Konstruktion bewiesen. Codes sind komplexe Puzzleaufgaben.

Definition

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

Blockcodes, die aus Informationssymbolen am Blockanfang und Prüfsymbolen am Blockende bestehen, werden Systematische Blockcodes genannt (siehe Abbildung).

Informationsrate für Blockcodes

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:

.

Fehlerkorrektur

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 oder gar drei Bits falsch, so wird zwar ein Fehler erkannt, aber fehlerhaft korrigiert.