Codierungstheorie
Codes
Codierung
Definition: Seien A+ und B+ die Wortmengen über den Alphabeten A und B. Eine Codierung (der Wortmenge A+) ist eine injektive Abbildung
c : A+ → B+
die jedem Wort x ∈ A+ ein Wort c(x) ∈ B+ zuordnet.
Die Menge aller Codewörter, d.h. das Bild c(A+) ⊆ B+ nennt man den Code.
Unter der Dekodierung versteht man die Umkehrabbildung c -1 : c(A+) → A+.
Definition: Eine Codierung c : A+ → B+ heißt homomorphe Codierung, wenn c bereits durch die Codierung des Alphabets A festliegt, d.h. wenn gilt:
c(x) = c(x0) ... c(xn-1) für alle x ∈ A+ mit x = x0 ... xn-1, xi ∈ A, n ∈ ℕ
Entsprechend wird das Bild des Alphabets c(A) ⊆ B+ in diesem Fall als der Code bezeichnet.
Beispiel: (Morse-Code) A = { a , b, c, ..., z } , B = { ·, – }
| a | · – | ||
| b | – · · · | ||
| c | – · – · | ||
 | |||
| i | · · | ||
| s | · · · | ||
| u | · · – | ||
| usw. |
Auch wenn die Codierung c des Alphabets A injektiv ist und damit die Umkehrabbildung eindeutig ist, muss dies für die Dekodierung von Wörtern aus c(A+) nicht gelten:
Beispiel: Morse-Code
Es ist c(usa) = · · – · · · · – = c(idea)
Abhilfe: Einführung eines weiteren Zeichens '
' (kurze Pause) am Ende jedes Codewortes, d.h. B = {·, –, }; damit genügt der Code der folgenden Bedingung für homomorphe Codierungen:
Satz: (Fano
-Bedingung)
Wenn kein Codewort Anfangswort eines anderen Codewortes ist, dann ist jede Zeichenreihe aus c(A+) ⊆ B+ eindeutig dekodierbar.
Die Fano-Bedingung spielt eine Rolle bei Codes mit variabler Codewortlänge, z.B. beim Huffman-Code. Im Folgenden sollen jedoch zunächst Codes mit konstanter Codewortlänge, die Blockcodes, betrachtet werden. Bei Blockcodes ist die Fano-Bedingung immer erfüllt.
Blockcodes
Definition: Sei n ∈ ℕ, 𝔹 = {0, 1}. Ein n-Bit-Blockcode oder kurz n-Bit-Code ist eine Teilmenge C ⊆ 𝔹n.
Wir schreiben die Elemente von 𝔹n nicht als n-Tupel (x0, ..., xn-1), sondern als Wörter x0 ... xn-1.
Beispiel: 3-Bit-Binärcode C3 = 𝔹3
| 0 0 0 |
| 0 0 1 |
| 0 1 0 |
| 0 1 1 |
| 1 0 0 |
| 1 0 1 |
| 1 1 0 |
| 1 1 1 |
Mit diesen Codewörtern lassen sich z.B. die Zahlen von 0 bis 7 codieren, etwa in der Weise, dass jeder dieser Zahlen ihre Binärdarstellung zugeordnet wird, also z.B. c(5) = 1 0 1. Es ist jedoch auch möglich, die Zuordnung in anderer Reihenfolge zu machen, so wie z.B. beim Gray-Code. Statt der Zahlen von 0 bis 7 lassen sich mit dem Code C3 natürlich auch die Zahlen von -4 bis +3 codieren; bei der Zweierkomplement-Darstellung von ganzen Zahlen wird dies so gemacht. Oder man kann mit C3 jede beliebige andere Menge von 8 Elementen codieren.
Im Folgenden abstrahieren wir von der Codierungsabbildung c, wir betrachten nur noch das Bild von c, den Code.
Durch Ausnutzung der algebraischen Eigenschaften von Blockcodes lassen sich fehlererkennende und fehlerkorrigierende Codes konstruieren.
Definition: Verknüpfungen ⊕ und · in 𝔹
|
|
Satz: Die Menge 𝔹 bildet mit den Verknüpfungen ⊕ und · einen Körper.
Ein Körper ist eine algebraische Struktur, in der mit den gewohnten Rechenregeln gerechnet werden kann.
Definition: Verknüpfungen ⊕ in 𝔹n und · zwischen 𝔹 und 𝔹n
Wörter aus 𝔹n werden komponentenweise addiert, d.h. für alle x, y ∈ 𝔹n ist
x⊕y = (x0 ... xn-1) ⊕ (y0 ... yn-1) = x0⊕y0 ... xn-1⊕yn-1
Die Multiplikation eines Körperelements k ∈ 𝔹 mit einem Wort x ∈ 𝔹n geschieht ebenfalls komponentenweise:
k · x = k · (x0 ... xn-1) = k · x0 ... k · xn-1
Beispiel: 1 0 0 1 ⊕ 0 1 0 1 = 1 1 0 0 , 1 · 0 1 1 0 = 0 1 1 0 , 0 · 0 1 1 0 = 0 0 0 0
Satz: 𝔹n bildet mit diesen Verknüpfungen einen Vektorraum über 𝔹.
Hamming-Abstand
Ein wichtiger Begriff in der Codierungstheorie ist der Hamming-Abstand (nach R.W. Hamming).
Definition: Unter dem Hamming-Abstand d(x, y) zweier Wörter x, y ∈ 𝔹n versteht man die Anzahl der Stellen, an denen x und y bitweise verschieden sind.
Beispiel:
| x | = | 0 1 1 0 1 |
| y | = | 0 0 1 1 1 |
Es ist d(x, y) = 2, denn x und y sind an zwei Bitpositionen verschieden (an der 2. und 4. Position).
Satz: Der Hamming-Abstand ist eine Metrik.
Definition: Unter dem Hamming-Abstand eines Codes C ⊆ 𝔹n versteht man das Minimum aller Hamming-Abstände zwischen je zwei verschiedenen Codewörtern:
d(C) = min{ d(x, y) | x, y ∈ C, x ≠ y }
Beispiel: Der Hamming-Abstand des 3-Bit-Binärcodes C3 beträgt d(C3) = 1.
Definition: Das Hamming-Gewicht w(x) eines Wortes x = x0 ... xn-1 ∈ 𝔹n ist die Summe aller xi, d.h. die Anzahl der Einsen in x:
w(x) = 
i = 0, ..., n-1 xi
Beispiel: w(0 1 1 0 1) = 3, w(1 0 1 1 1) = 4
Satz: Für alle x, y ∈ 𝔹n gilt: d(x, y) = w(x ⊕ y)
Definition: Die Parität p(x) eines Wortes x = x0 ... xn-1 ∈ 𝔹n ist die Summe (modulo 2) aller xi :
p(x) = 
i = 0, ..., n-1 xi
Beispiel: p(0 1 1 0 1) = 1, p(1 0 1 1 1) = 0
Fehlererkennung
Definition: Sei C ein n-Bit-Code. Ein Fehler ist ein Wort e ∈ 𝔹n mit e ≠ 0.
Ist w(e) = 1, so heißt e Einfachfehler, ist w(e) = 2, so heißt e Doppelfehler usw.
C erkennt einen Fehler e, wenn für alle x ∈ C gilt:
x ⊕ e ∉ C
Das Prinzip eines fehlererkennenden Codes beruht darauf, dass alle Codewörter zu Nicht-Codewörtern werden, wenn sie durch bestimmte Arten von Fehlern verfälscht werden. Wenn der Empfänger ein Nicht-Codewort empfängt, weiß er, dass ein Fehler aufgetreten sein muss.
Satz: Sei C ein n-Bit-Code mit Hamming-Abstand 2. Dann erkennt C alle Einfachfehler.
Beweis: Sei e ein Einfachfehler und x ∈ C. Dann gilt:
d(x, x ⊕ e) = w(x ⊕ x ⊕ e) = w(e) = 1
Somit kann x ⊕ e kein Codewort sein, denn dann müsste der Hamming-Abstand d(x, x ⊕ e) mindestens 2 sein. Also wird e erkannt.
Beispiel: Binärcode mit Paritätsbit C4,3 ⊆ 𝔹4
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
An den 3-Bit Binärcode wird ein viertes Bit angehängt, sodass p(x) = 0 für alle Codewörter x gilt. Dieser Code hat den Hamming-Abstand 2. Dadurch erkennt C4,3 alle Einfachfehler.
Wenn allerdings ein Doppelfehler auftritt, erkennt C4,3 ihn nicht. Denn das verfälschte Codewort hat auch die Parität 0 und ist damit ebenfalls ein Codewort.
Satz: Sei C ⊆ 𝔹n ein n-Bit-Code mit mindestens zwei verschiedenen Codewörtern x und y. Dann gibt es einen Fehler e, den C nicht erkennt.
Beweis: Der Fehler e = x ⊕ y wird nicht erkannt, denn es ist
x ⊕ e = x ⊕ x ⊕ y = y ∈ C
Der Empfänger kann sich also nie sicher sein, dass kein Fehler aufgetreten ist. Nur wenn er ein Nicht-Codewort empfängt, kann er sich sicher sein, dass ein Fehler aufgetreten ist.
(n,k)-Codes
Definition: Zwei n-Bit-Codes heißen äquivalent, wenn sie durch Vertauschung der Bitpositionen auseinander hervorgehen.
Beispiel: Wenn in C4,3 das Paritätsbit nicht hinten, sondern vorne oder in der Mitte einfügt wird, entsteht ein zu C4,3 äquivalenter Code.
Definition: Ein n-Bit-Code C heißt systematisch, wenn es ein k ∈ ℕ gibt, sodass es zu jedem Wort x ∈ 𝔹k genau ein Codewort xv ∈ C gibt.
Die ersten k Bits der Codewörter von C heißen Informationsbits, die restlichen n – k Bits heißen Prüfbits.
Beispiel: C4,3 ⊆ 𝔹4 ist systematisch mit k = 3.
Systematische Codes lassen sich auffassen als Ergebnis einer Codierung c : 𝔹k → 𝔹n, wobei die Codierung im Hinzufügen der Prüfbits besteht und die Dekodierung im Weglassen der Prüfbits.
Definition: Ein Code C heißt (n, k)-Code, wenn er zu einem systematischen n-Bit-Code mit k Informationsbits äquivalent ist.
Beispiel: C4,3 ist ein (4, 3)-Code.
Weiter: [Gray-Code] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 12.09.1997 Updated: 08.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden