Blockcode

Aus dem Alphabet ${\displaystyle \Sigma }$ und der Blockgröße ${\displaystyle n}$ ergibt sich ${\displaystyle \Sigma ^{n}}$ als Menge der möglichen Worte, von denen eine Teilmenge ${\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}$ die gültigen Codeworte darstellt. Die Mächtigkeit des Alphabets ${\displaystyle \Sigma }$ wird mit ${\displaystyle q=|\Sigma |}$ bezeichnet, sie beträgt im Falle von Binärcodes ${\displaystyle q=|\Sigma |=2}$. Die Mächtigkeit des Codes ${\displaystyle |{\mathcal {C}}|}$ kann bei vielen Codes (bei linearen Codes immer) als ${\displaystyle |{\mathcal {C}}|=q^{k}}$ mit ${\displaystyle k\in \mathbb {N} ^{+}}$ geschrieben werden. Diese Codes können bei einer Blockgröße von ${\displaystyle n}$ Symbolen eine Nutzlast ${\displaystyle k\leq n}$ tragen.

Die Informationrate beträgt ${\displaystyle k/n\leq 1}$, die Korrekturrate wird durch den (minimalen) Hamming-Abstand des Codes ${\displaystyle {\mathcal {C}}}$ limitiert. Der Hamming-Abstand zweier Codeworte ${\displaystyle c_{i}}$ und ${\displaystyle c_{j}}$ ist hierbei die Anzahl unterschiedlicher Symbole dieser Codeworte ${\displaystyle \Delta (c_{i},c_{j})}$, der (minimale) Hamming-Abstand ${\displaystyle d}$ eines (ganzen) Codes ${\displaystyle {\mathcal {C}}}$ ist der minimale Hamming-Abstand aller (disjunkten) Codewort-Paare, d. h. ${\displaystyle d=\Delta ({\mathcal {C}})\,\,{\overset {\underset {\mathrm {def} }{}}{=}}\,\min _{i\neq j}\,\Delta (c_{i},c_{j})}$. Letztere beschränkt die maximale (zuverlässige) Korrekturleistung auf ${\displaystyle t}$ Symbolfehlern mit ${\displaystyle t=\left\lfloor (d-1)/2\right\rfloor }$ 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 ${\displaystyle t_{\mathrm {Mehrbit} }>t}$, die sie selbst nicht mehr korrigieren können, zum anderen kann man Fehlerkorrektur-Fähigkeiten gegen weitere (garantierte) Fehlererkennungs-Fähigkeiten ${\displaystyle r}$ eintauschen und damit folgende Korrektur-Stufen unterstützen: ${\displaystyle r=d-1-t_{\mathrm {benutzt} }}$.

Für Codes haben sich in der Literatur unterschiedliche Notationen etabliert:

• ${\displaystyle [n,k;d,q]}$ oder ${\displaystyle [n,k;d]_{q}}$, häufig wird das Semikolon durch ein Komma ersetzt, die eckigen Klammern durch runde Klammern. ${\displaystyle q=2}$ wird häufig weggelassen, gleiches gilt für das ${\displaystyle d=3}$ der klassischen Hamming-Codes.
• Häufig wird statt ${\displaystyle k}$ (der Anzahl der Nutzsymbole) die Mächtigkeit des Codes ${\displaystyle q^{k}=|{\mathcal {C}}|}$, d. h. ${\displaystyle (n,q^{k},d)_{q}}$ oder der Code selbst angegeben ${\displaystyle (n,{\mathcal {C}},d)_{q}}$ 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 ${\displaystyle {\mathcal {C}}}$ als einen ${\displaystyle (n,{\mathcal {C}};d,q)}$-Code, falls

• ${\displaystyle \Sigma }$ ein Alphabet mit ${\displaystyle |\Sigma |=q}$ ist,
• der Code ${\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}$ ist und
• der (minimalen) Hamming-Abstand ${\displaystyle d=\Delta ({\mathcal {C}})}$ ist.

Betrachtet man lineare Codes, so spricht man von ${\displaystyle [n,k;d,q]}$-Codes bzw. ${\displaystyle [n,k;d]_{q}}$-Codes, wobei ${\displaystyle k}$ hier die Dimension von ${\displaystyle {\mathcal {C}}}$ über dem Körper ${\displaystyle \mathbb {F} _{q}}$ ist. ${\displaystyle n}$ und ${\displaystyle d}$ haben dabei die gleiche Bedeutung wie bei den allgemeinen Blockcodes.

Es gibt zwar theoretische Grenzen (wie die Hamming-Grenze), aber eine andere Frage ist, welche Codes tatsächlich konstruiert werden können. Es ist, als würde man Kugeln in einem eckigen Karton verpacken … Dieses Diagramm zeigt die konstruierbaren Codes die linear und binär sind. Die x-Achse zeigt die Anzahl der geschützten Symbole k und die y-Achse die Anzahl der benötigten Prüfsymbole n-k. Es sind die Grenzen für verschiedene Hamming-Distanzen dargestellt: Von 1 (ungeschützt) bis 34.
Mit Punkten markiert sind perfekte Codes:

• hellorange auf der x-Achse: trivial ungeschützte Codes
• orange, auf der y-Achse: trivial Wiederholungs-Codes
• dunkelorange, auf der Linie für d=3: klassische, perfekte Hamming-Codes
• dunkelrot und groß: der einzige perfekte binäre Golay-Code

Man interessiert sich bei gegebenem ${\displaystyle n}$, ${\displaystyle d}$ und ${\displaystyle q}$ für eine Maximierung der Mächtigkeit des Codes, d. h. für ${\displaystyle \max\{|{\mathcal {C}}|:{\mathcal {C}}\,\,{\mathrm {mit} }\,\,\Delta ({\mathcal {C}})\geq d\}}$, 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 ${\displaystyle [23,12;7,2]}$-Code 11 Schutzbits, ein ${\displaystyle [27,13;7,2]}$-Code allerdings schon 14. Ein ${\displaystyle [41,24;7,2]}$- kommt wie ein ${\displaystyle [55,38;7,2]}$-Code mit 17 Schutzbits aus.

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

• Singleton-Schranke (MDS-Code)
• Hamming-Schranke (Perfekter Code)
• Plotkin-Schranke
• Gilbert-Varshamov-Schranke, Johnson-Schranke, Griesmer-Schranke, Bassalygo-Elias-Schranke
• Optimaler Code

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

Formal heißt der Code ${\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}$ Blockcode, wobei ${\displaystyle \Sigma }$ als Alphabet bezeichnet wird und ${\displaystyle n}$ die Länge jedes Codewortes ${\displaystyle c\in {\mathcal {C}}}$ ist.

Triviale Blockcodes sind Codes

• die nur ein Wort als Code umfassen: ${\displaystyle |{\mathcal {C}}|=1}$. Es lassen sich alle Übertragungsfehler erkennen, aber keine Information übertragen oder
• die alle möglichen Worte als Code umfassen: ${\displaystyle |{\mathcal {C}}|=|\Sigma |^{n}}$. Es lassen sich keine Übertragungsfehler erkennen, die übertragene Information ist aber maximal.

Lineare Blockcodes sind Codes,
wenn ${\displaystyle {\mathcal {C}}}$ ein ${\displaystyle k}$-dimensionaler Untervektorraum von ${\displaystyle \Sigma ^{n}}$ ist. Es existiert dann eine Basis ${\displaystyle g_{1},\dots ,g_{k}}$ von ${\displaystyle {\mathcal {C}}}$. Fasst man diese Basis zu einer Matrix

${\displaystyle G={\begin{pmatrix}g_{1}\\g_{2}\\\vdots \\g_{k-1}\\g_{k}\end{pmatrix}}}$

zusammen, erhält man eine Generatormatrix dieses linearen Blockcodes. Die Codeworte erhält man durch Multiplizieren des Eingangssignals ${\displaystyle x}$ mit der Generatormatrix

${\displaystyle c(x)=x\cdot G}$

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

Bemerkungen:
Zur Kodierung eines Codes mit ${\displaystyle q^{k}}$ Codeworten muss man nur noch ${\displaystyle k}$ Codeworte vorrätig halten. Gleiches gilt für die Dekodierung mit ${\displaystyle q^{n}}$ vs. ${\displaystyle n}$.

Systematische Blockcodes sind Codes,
bei denen die ${\displaystyle k}$ Informationssymbole direkt im Block ablesbar sind (meist am Blockanfang, 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 ${\displaystyle w\in \Sigma ^{n}}$ nur zu genau einem Codewort ${\displaystyle c\in {\mathcal {C}}}$ (und nicht zu mehreren) einen geringsten Hamming-Abstand ${\displaystyle d_{w}}$ hat. Jedes Wort lässt sich damit eindeutig decodieren. Der Hamming-Code ist ein Beispiel für einen perfekten Code.

Maximum-Distanz-Codes (MDS Codes) sind Blockcodes,

deren Codeworte den größtmöglichen Hamming-Abstand voneinander haben. Beispiele für MDS Codes sind Wiederholungscodes, Paritätscodes und Reed-Solomon-Codes.

Die Informationsrate (auch Coderate) ${\displaystyle R}$ gibt an, wie viel Information pro Codewortsymbol im Mittel übertragen wird, sie ist also das Verhältnis von Nachrichtensymbolen zu Codewortsymbolen. Da ein Code Redundanz hinzufügt, gilt allgemein ${\displaystyle 0\leq R\leq 1}$.

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

${\displaystyle R={\frac {\log _{q}(|{\mathcal {C}}|)}{\log _{q}(|\Sigma |^{n})}}={\frac {\log _{q}(|{\mathcal {C}}|)}{n}}}$.

Ist z. B. ${\displaystyle {\mathcal {C}}}$ ein binärer Code mit ${\displaystyle s}$ verschiedenen Codeworten, dann benötigt man ${\displaystyle \lceil \log _{2}s\rceil }$ Bits, um diese eindeutig zu unterscheiden.

Handelt es sich um einen linearen Code, so ist die Informationsrate:

${\displaystyle R={\frac {\log _{q}(q^{k})}{n}}={\frac {k}{n}}}$.

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 ${\displaystyle k}$ ein Codewort der Länge ${\displaystyle n}$ zu, wobei ${\displaystyle n>k}$. Durch das Hinzufügen der ${\displaystyle n-k}$ 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

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

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.

• 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.

• Kanalcodierung und Blockcodes (abgerufen am 6. April 2018)
• Lineare Fehlerkorrigierende Codes (abgerufen am 6. April 2018)
• Proinformatik - Funktionale Programmierung (abgerufen am 6. April 2018)
• Formelsammlung Kanalcodierung (abgerufen am 6. April 2018)
• Theory and Practice of Error Control Codes Block Code Performance (abgerufen am 6. April 2018)

1. M. Plotkin: Binary codes with specified minimum distance, IRE Transactions on Information Theory, 6:445-450, 1960 (engl.).
2. W.C. Huffman, V. Pless: Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003 (engl.).
3. Die Plotkin-Grenze und ihre Verschärfung (englisch).