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 einander 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 Bearbeiten
Aus dem Alphabet und der Blockgröße ergeben sich mögliche Worte, von denen eine Teilmenge 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 in der Literatur unterschiedliche Notationen etabliert:
- 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.
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 , 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:
- 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 Bearbeiten
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: |
|---|
|
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. . |
Systematische Blockcodes sind Codes,
bei denen die 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 nur zu genau einem Codewort (und nicht zu mehreren) einen geringsten Hamming-Abstand 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 Bearbeiten
Die Informationsrate (auch Coderate) 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 .
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 Codeworten, dann benötigt man Bits, um diese eindeutig zu unterscheiden.
Handelt es sich um einen linearen Code, so ist die Informationsrate:
Beispiele für Blockcodes Bearbeiten
Wiederholungscode Bearbeiten
Wiederholungscodes sind lineare, systematische -Blockcodes über einem beliebigen Alphabet, bei denen jedes Nachrichtensymbol n-mal wiederholt wird. Damit hat ein Wiederholungscode die Generatormatrix
und eine Informationsrate von .
Paritätscode Bearbeiten
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:
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.
Hadamard-Code Bearbeiten
Hadamard Codes sind lineare nicht-systematische Blockcodes . Die Generatormatrix hat eine sehr auffällige Form
Sie haben eine geringe Coderate von , 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 Bearbeiten
Beispiel 1 Bearbeiten
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 2 Bearbeiten
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 3 Bearbeiten
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.
Fehlerkorrektur Bearbeiten
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.
Schranken Bearbeiten
Singleton-Schranke Bearbeiten
Die Singleton-Schranke bezeichnet eine obere Schranke für die Mindestdistanz eines Blockcodes der Länge bei Informationswörtern der Länge über einem einheitlichen Alphabet .
Sie lautet:
Die Schranke kann auf folgende Art intuitiv klargemacht werden:
- Annahme: Alphabet
- Anzahl der möglichen Informationswörter:
- Anzahl der Codewörter:
- Mindestdistanz:
Streicht man nun in den Codewörtern jeweils die letzten () der Stellen, so haben die übrigen Codewörter zueinander immer noch mindestens den Hamming-Abstand 1. Bei Streichungen wäre dies nicht mehr gewährleistet. Damit sind immer noch alle Codewörter unterschiedlich, also
Deswegen muss auch die Anzahl der durch die Länge erzeugbaren Wörter sein. Stellt man diese Gleichung um, ergibt sich daraus die Singleton-Schranke
Für nicht-lineare Codes gilt entsprechend
wobei .
Codes, die die Singleton-Schranke mit Gleichheit erfüllen, nennt man auch MDS-Codes.
Im Falle der Hamming-Schranke ist die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Hamming-Distanz .
Die Hamming-Schranke sagt aus, dass
beziehungsweise
erfüllt sein muss für einen Code, der mittels Symbolen eines Alphabets der Größe eine Nachricht mit der Länge transportiert.
Die Singleton-Schranke ist eine ungenauere Abschätzung als die Hamming-Schranke, die die Größe des Alphabets nicht berücksichtigt. Weiterhin gibt es Unterschiede in der Beziehung zwischen und .
Plotkin-Grenze Bearbeiten
In der Kanalcodierung verwendet man Blockcodes, um Fehler in Datenströmen erkennen und korrigieren zu können. Ein Blockcode der Länge über einem -nären Alphabet mit einem Minimalabstand erfüllt die Plotkin-Grenze, auch als Plotkin-Schranke bezeichnet,
dann, wenn der Nenner positiv ist. Somit liefert die Plotkin-Grenze nur dann ein Resultat, wenn hinreichend nahe bei liegt.
Nimmt ein Code die Plotkin-Schranke an, so gilt insbesondere, dass der Abstand zweier beliebiger Codewörter genau ist.
Ist und mit , so gilt sogar die schärfere Beziehung:
Beispielsweise liefert die Plotkin-Grenze für , und nur , die Verschärfung jedoch , da sich für und ein Widerspruch ergibt.
Sie wurde 1960 von Morris Plotkin veröffentlicht.
Literatur Bearbeiten
- 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 Bearbeiten
- 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)
Einzelnachweise Bearbeiten
- M. Plotkin: Binary codes with specified minimum distance, IRE Transactions on Information Theory, 6:445-450, 1960 (engl.).
- W.C. Huffman, V. Pless: Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003 (engl.).
- Die Plotkin-Grenze und ihre Verschärfung (englisch).