Blockcode

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 $n$ Symbolen eines festen Alphabets $\Sigma$ (bei Binärcodes $\Sigma =\{0,1\}$) 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 $k$ zur Gesamt-Datenmenge $n$) sowie seine Korrekturrate (d. h. die Fähigkeit Fehler zu erkennen und/oder zu korrigieren). Beide Eigenschaften beeinflussen einander 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.

Aufbau

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

Die Informationrate beträgt $k/n\leq 1$, die Korrekturrate wird durch den (minimalen) Hamming-Abstand des Codes ${\mathcal {C}}$ limitiert. Der Hamming-Abstand zweier Codeworte $c_{i}$ und $c_{j}$ ist hierbei die Anzahl unterschiedlicher Symbole dieser Codeworte $\Delta (c_{i},c_{j})$, der (minimale) Hamming-Abstand $d$ eines (ganzen) Codes ${\mathcal {C}}$ ist der minimale Hamming-Abstand aller (disjunkten) Codewort-Paare, d. h. $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 $t$ Symbolfehlern mit $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 $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 $r$ eintauschen und damit folgende Korrektur-Stufen unterstützen: $r=d-1-t_{\mathrm {benutzt} }$.

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

• $[n,k;d,q]$ oder $[n,k;d]_{q}$, häufig wird das Semikolon durch ein Komma ersetzt, die eckigen Klammern durch runde Klammern. $q=2$ wird häufig weggelassen, gleiches gilt für das $d=3$ der klassischen Hamming-Codes.
• Häufig wird statt $k$ (der Anzahl der Nutzsymbole) die Mächtigkeit des Codes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q^k = |\mathcal C|} , d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n, q^k, d)_q} oder der Code selbst angegeben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal C} als einen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (n,{\mathcal {C}};d,q)} -Code, falls

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

Betrachtet man lineare Codes, so spricht man von $[n,k;d,q]$-Codes bzw. $[n,k;d]_{q}$-Codes, wobei $k$ hier die Dimension von ${\mathcal {C}}$ über dem Körper $\mathbb {F} _{q}$ ist. $n$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} für eine Maximierung der Mächtigkeit des Codes, d. h. für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [23,12;7,2]} -Code 11 Schutzbits, ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [27,13;7,2]} -Code allerdings schon 14. Ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [41,24;7,2]} - kommt wie ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Typen von Blockcodes

Formal heißt der Code Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal C \subseteq \Sigma^n} Blockcode, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} als Alphabet bezeichnet wird und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} die Länge jedes Codewortes $c\in {\mathcal {C}}$ ist.

Triviale Blockcodes sind Codes

• die nur ein Wort als Code umfassen: $|{\mathcal {C}}|=1$. Es lassen sich alle Übertragungsfehler erkennen, aber keine Information übertragen oder
• die alle möglichen Worte als Code umfassen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\mathcal C| = |\Sigma|^n} . Es lassen sich keine Übertragungsfehler erkennen, die übertragene Information ist aber maximal.

Bemerkungen:

Der erste Code lässt sich als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [n,0;2n+1,q]} -Code schreiben. Er hat im klassischen Sinne keine Hamming-Distanz, da es keine Codepaare gibt. Es lassen sich bis zu maximal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t = n} Symbolfehler im übertragenen Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} korrigieren (das übertragene Codewort ist bekannt), was eine typische Eigenschaft für Codes mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d = 2 t + 1 = 2 n + 1} ist. Das gleiche gilt für die Anzahl von Codes, die sich eindeutig dekodieren lassen. Die Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q^n = {\sum_{i=0}^{\lfloor (d-1)/2 \rfloor}(q-1)^i \binom n i} } liefert für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d \geq 2 n + 1} das richtige Ergebnis. Der zweite Code lässt sich als $[n,n;1,2]$-Code schreiben. Er hat eine Hamming-Distanz von 1.

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} mit der Generatormatrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c(x) = x \cdot G}

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

Bemerkungen:

Zur Kodierung eines Codes mit $q^{k}$ Codeworten muss man nur noch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Codeworte vorrätig halten. Gleiches gilt für die Dekodierung mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q^n} vs. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} .

Systematische Blockcodes sind Codes,
bei denen die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w \in \Sigma^n} nur zu genau einem Codewort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c \in \mathcal C} (und nicht zu mehreren) einen geringsten Hamming-Abstand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Informationsrate von Blockcodes

Die Informationsrate (auch Coderate) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 \le R \le 1} .

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal C \subseteq \Sigma^n} ein Blockcode und es gelte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q =|\Sigma|} , das Alphabet habe also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} verschiedene Elemente. Dann lautet für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal C} die Definition der Informationsrate:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R = \frac{\log_q(|\mathcal C|)}{\log_q(|\Sigma|^n)} = \frac{\log_q(|\mathcal C|)}{n}} .

Ist z. B. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal C} ein binärer Code mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} verschiedenen Codeworten, dann benötigt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lceil \log_2 s \rceil} Bits, um diese eindeutig zu unterscheiden.

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R = \frac{\log_q(q^k)}{n}=\frac{k}{n}} .

Beispiele für Blockcodes

Wiederholungscode

Wiederholungscodes sind lineare, systematische Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [n,1;n]} -Blockcodes über einem beliebigen Alphabet, bei denen jedes Nachrichtensymbol n-mal wiederholt wird. Damit hat ein Wiederholungscode die Generatormatrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G = \begin{pmatrix} 1 \cdots 1 \end{pmatrix}}

und eine Informationsrate von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R = \frac{1}{n}} .

Paritätscode

Paritätscodes (engl. Single Parity Check (SPC) codes) sind lineare, systematische und binäre Codes, bei denen der Nachricht ein einziges Prüfbit angefügt wird, das sich als XOR-Verknüpfung aller Nachrichtenbits ergibt. Somit hat jedes Codewort eine gerade Anzahl an "1"-Bits. Die Generatormatrix hat folgende Form:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=\begin{pmatrix} 1 0 \dots 0 0 \,\, 1 \\ 0 1 \dots 0 0 \,\, 1 \\ \,\,\,\,\vdots\ddots \vdots \,\,\,\,\,\, \vdots \\ 0 0 \dots 1 0 \,\, 1 \\ 0 0 \dots 0 1 \,\, 1 \\ \end{pmatrix}}

Sie haben eine Hamming-Distanz von 2 und stellen -Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [n,n-1;2,2]} Blockcodes dar. Sie können einen Fehler erkennen, aber keine Fehler korrigieren. Lineare binäre Blockcodes mit ungeradem Hamming-Abstand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [n,k;2m+1,2]} lassen sich mit einem zusätzlichen Paritätscode zu einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [n+1,k;2m+2,2]} -Code erweitern.

Hadamard-Code

Hadamard Codes sind lineare nicht-systematische Blockcodes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [ 2^k, k+1; 2^{k-1} ]} . Die Generatormatrix hat eine sehr auffällige Form

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=\begin{pmatrix} 0 1 0 1 0 1 0 1 \cdots 1 0 \cdots 0 1 0 1 0 1 0 1 \\ 0 0 1 1 0 0 1 1 \cdots 1 0 \cdots 0 0 1 1 0 0 1 1 \\ 0 0 0 0 1 1 1 1 \cdots 1 0 \cdots 0 0 0 0 1 1 1 1 \\ \vdots \\ 0 0 0 0 0 0 0 0 \cdots 0 1 \cdots 1 1 1 1 1 1 1 1 \\ 1 1 1 1 1 1 1 1 \cdots 1 0 \cdots 0 0 0 0 0 0 0 0 \\ \end{pmatrix} }

Sie haben eine geringe Coderate von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R = \frac{k+1}{2^k}} , können aber noch Daten aus sehr fehlerbehafteten Signal dekodieren. Daher fanden sie unter anderem in der Mariner 9 Mission Anwendung.

Weitere Beispiele für Blockcodes

Beispiel 1

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (9, \{0, 31, 227, 364, 437, 474 \}; 5, 2)}

Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\mathcal C| = 6} Codeworte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} lauten in der Binärdarstellung:

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

Es existiert kein linearer Code dieser Mächtigkeit. Zum einen ist ${\text{log}}_{q}6\not \in \mathbb {N} ^{+}$, zum anderen sind die größten lineare Code dieser Art ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [8, 2; 5, 2]} - und ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [10, 3; 5, 2]} -Code. Der Code lässt sich nicht in einen linearen Code umwandeln.

Beispiel 2

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (11, \{0,143,307,444,597,730,870,1001,1130,1253,1369,1494,1599,1712,1804,1923\}; 5, 2)}

Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\mathcal C| = 16} Codeworte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} 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 3

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (8, \{ 0, 7, 25, 30, 42, 53, 75, 84, 97, 108, 114, 127, 140, 147, 166, 169, 176, 194, 197, 216 \}; 3, 2)}

Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\mathcal C| = 20} Codeworte $c$ lauten in der Binärdarstellung:

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

Es existiert kein linearer Code dieser Mächtigkeit. Auch hier ist zum einen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{log}_q 20 \not\in \mathbb{N}^+} , zum anderen sind die größten lineare Code dieser Art ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [7, 4; 3, 2]} - und ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [9, 5; 3, 2]} -Code. Der Code lässt sich nicht in einen linearen Code umwandeln.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} ein Codewort der Länge $n$ zu, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n > k} . Durch das Hinzufügen der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

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.

Literatur

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

Weblinks

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