Blockcode
Systematischer Blockcode

Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet, z. B. Bits haben.

Obwohl Blockcodes häufig nicht optimal im Sinne einer minimalen mittleren Codewortlänge sind, schränkt man sich oft auf Blockcodes ein, da die Erforschung von Codes mit beliebiger Länge weitaus schwieriger ist. Eine weitere Spezialisierung stellen die linearen Codes dar.

Wichtige Parameter eines Blockcodes sind die Informationsrate (eine Kenngröße für die in einer festen Datenmenge enthaltenen Informationsmenge) sowie die Korrekturrate (Hamming-Abstand - eine Kenngröße für die Fehlerresistenz bei einer festen Datenmenge). Es ist im Allgemeinen nicht möglich, diese Eigenschaften gleichzeitig zu optimieren. Deshalb muss in der Praxis stets neu entschieden werden, welcher Blockcode den besten Kompromiss für eine bestimmte Anwendung bietet.

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 d) die gesamte Anzahl der Codewörter zu maximieren.

Man bezeichnet allgemein \mathcal C als einen (n,d,q)-Code ,falls

  • A ein Alphabet mit | A | = q ist,
  • für den Code  \mathcal C \subseteq A^n ,
  • für den Minimalabstand  d(\mathcal C) \geq d gilt.

Betrachtet man lineare Codes, so spricht man von (n,k,d,q)-Codes, wobei k hier die Dimension von \mathcal C über dem Körper \mathbb F_q ist. n und d haben dabei die gleiche Bedeutung wie bei Blockcodes.

Man interessiert sich also nun für Max(n,d,q):=max{ |\mathcal C| : \mathcal C ist (n,d,q)-Code }, da hierbei eine bei gegebenem n,d,q optimale Informationsrate erzielt wird. Siehe hierzu Singleton-Schranke (MDS-Code), Hamming-Schranke (Perfekter Code), Plotkin-Schranke, Optimaler Code.

Definition

Formal heißt der Code  \mathcal C \subseteq A^n Blockcode, wobei A als Alphabet bezeichnet wird und n die Länge eines Codewortes w \in \mathcal C ist.

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

Informationsrate für Blockcodes

Sei \mathcal C \subseteq A^n ein Blockcode und es gelte | A | = q, das Alphabet habe also q verschiedene Elemente. Dann lautet für \mathcal C die Definition der Informationsrate:

\frac{\log_q(|\mathcal C|)}{\log_q(A^n)}=\frac{\log_q(|\mathcal C|)}{n}.

Wenn z. B. \mathcal C ein binärer Code ist mit s verschiedenen Elementen, dann benötigt man höchstens log 2(s)+1 Bits, um s verschiedene Codewörter zu erhalten. Die Informationsrate setzt daher die tatsächlich benötigte Anzahl an Zeichen mit der geringstmöglichen Anzahl an Zeichen ins Verhältnis.

Wenn beispielsweise die ersten k Bits eines binären Codeworts Informationsbits sind, die in alle theoretisch möglichen Kombinationen existieren, dann ist die Informationsrate:

\frac{log_2(2^k)}{n}=\frac{k}{n}.

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 m ein Codewort der Länge n zu, wobei n > m. Durch das Hinzufügen der nm 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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Block-Code — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

  • Block-Codes — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

  • Blockkode — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

  • Hamming-Kode — Der Hamming Code ist ein von Richard Hamming entwickelter linearer fehlerkorrigierender Blockcode, der in der digitalen Signalverarbeitung und der Nachrichtentechnik zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird. Beim… …   Deutsch Wikipedia

  • Hamming-Schranke — Ein perfekter Code, oder auch dicht gepackter Code, bezeichnet in der Codierungstheorie einen Blockcode , bei dem jedes Wort nur zu genau einem Codewort eine minimale Hamming Distanz hat. Bei der für gewöhnlich verwendeten Maximum Likehood… …   Deutsch Wikipedia

  • Hammingcode — Der Hamming Code ist ein von Richard Hamming entwickelter linearer fehlerkorrigierender Blockcode, der in der digitalen Signalverarbeitung und der Nachrichtentechnik zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird. Beim… …   Deutsch Wikipedia

  • Hammingkode — Der Hamming Code ist ein von Richard Hamming entwickelter linearer fehlerkorrigierender Blockcode, der in der digitalen Signalverarbeitung und der Nachrichtentechnik zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird. Beim… …   Deutsch Wikipedia

  • Turbo-Convolutional-Code — Turbo Codes sind eine Gruppe von fehlerkorrigierenden Block oder Faltungs Codes, welche in der digitalen Signalverarbeitung zur gesicherten Datenübertragung, beispielsweise auf Satelliten Übertragungsstrecken, verwendet werden. Sie wurden 1993… …   Deutsch Wikipedia

  • Turbocode — Turbo Codes sind eine Gruppe von fehlerkorrigierenden Block oder Faltungs Codes, welche in der digitalen Signalverarbeitung zur gesicherten Datenübertragung, beispielsweise auf Satelliten Übertragungsstrecken, verwendet werden. Sie wurden 1993… …   Deutsch Wikipedia

  • Hamming-Code — Der Hamming Code ist ein von Richard Hamming entwickelter linearer fehlerkorrigierender Blockcode, der in der digitalen Signalverarbeitung und der Nachrichtentechnik zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird. Beim… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”