Codierungstheorie

Codes

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 Element A⁺ ein Wort c(x) Element B⁺ zuordnet.

Die Menge aller Codewörter, d.h. das Bild c(A⁺) enthalten 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(x₀) ... c(x_n-1) für alle x Element A⁺ mit x = x₀ ... x_n-1, x_i Element A, n Element natürliche Zahlen

Entsprechend wird das Bild des Alphabets c(A) enthalten 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⁺) enthalten 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.

Definition: Sei n Element natürliche Zahlen , boolesche Menge = {0, 1}. Ein n-Bit-Blockcode oder kurz n-Bit-Code ist eine Teilmenge C enthalten ⁿ.

Wir schreiben die Elemente von boolesche Menge ⁿ nicht als n-Tupel (x₀, ..., x_n-1), sondern als Wörter x₀ ... x_n-1.

Beispiel: 3-Bit-Binärcode C3 = boolesche Menge ³

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 Exklusiv-Oder und · in boolesche Menge

	0	1
0	0	1
1	1	0

·	0	1
0	0	0
1	0	1

Satz: Die Menge boolesche Menge bildet mit den Verknüpfungen Exklusiv-Oder und · einen Körper.

Ein Körper ist eine algebraische Struktur, in der mit den gewohnten Rechenregeln gerechnet werden kann.

Definition: Verknüpfungen Exklusiv-Oder in boolesche Menge ⁿ und · zwischen und ⁿ

Wörter aus boolesche Menge ⁿ werden komponentenweise addiert, d.h. für alle x, y Element ⁿ ist

x Exklusiv-Oder y = (x₀ ... x_n-1) (y₀ ... y_n-1) = x₀y₀ ... x_n-1y_n-1

Die Multiplikation eines Körperelements k Element boolesche Menge mit einem Wort x Element ⁿ geschieht ebenfalls komponentenweise:

k · x = k · (x₀ ... x_n-1) = k · x₀ ... k · x_n-1

Beispiel: 1 0 0 1 Exklusiv-Oder 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: boolesche Menge ⁿ bildet mit diesen Verknüpfungen einen Vektorraum über .

Definition: Unter dem Hamming-Abstand d(x, y) zweier Wörter x, y Element boolesche Menge ⁿ 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 enthalten boolesche Menge ⁿ versteht man das Minimum aller Hamming-Abstände zwischen je zwei verschiedenen Codewörtern:

d(C) = min{ d(x, y) | x, y Element C, x ungleich 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 = x₀ ... x_n-1 Element boolesche Menge ⁿ ist die Summe aller x_i, d.h. die Anzahl der Einsen in x:

w(x) = Summe _{i = 0, ..., n-1} x_i

Beispiel: w(0 1 1 0 1) = 3, w(1 0 1 1 1) = 4

Satz: Für alle x, y Element boolesche Menge ⁿ gilt: d(x, y) = w(x Exklusiv-Oder y)

Definition: Die Parität p(x) eines Wortes x = x₀ ... x_n-1 Element boolesche Menge ⁿ ist die Summe (modulo 2) aller x_i :

p(x) = Exklusiv-Oder _{i = 0, ..., n-1} x_i

Beispiel: p(0 1 1 0 1) = 1, p(1 0 1 1 1) = 0

Definition: Sei C ein n-Bit-Code. Ein Fehler ist ein Wort e Element boolesche Menge ⁿ mit e ungleich 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 Element C gilt:

x Exklusiv-Oder e nicht Element 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 Element C. Dann gilt:

d(x, x Exklusiv-Oder e) = w(x x e) = w(e) = 1

Somit kann x Exklusiv-Oder 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 enthalten boolesche Menge ⁴

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, so dass 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 enthalten boolesche Menge ⁿ 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 Exklusiv-Oder y wird nicht erkannt, denn es ist

x Exklusiv-Oder e = x x y = y Element 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.

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 Element natürliche Zahlen gibt, so dass es zu jedem Wort x Element boolesche Menge ^k genau ein Codewort xv Element 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 enthalten boolesche Menge ⁴ ist systematisch mit k = 3.

Systematische Codes lassen sich auffassen als Ergebnis einer Codierung c : boolesche Menge ^k ⁿ, 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: [Lineare Codes] oder