Codierungstheorie

Codes

 aufwärts

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+ Pfeil nach rechts B+

die jedem Wort x Element A+ ein Wort c(xElement B+ zuordnet.

Die Menge aller Codewörter, d.h. das Bild c(A+enthalten in B+ nennt man den Code.

Unter der Dekodierung versteht man die Umkehr­abbildung c -1 : c(A+Pfeil nach rechts A+.

Definition:  Eine Codierung c : A+ Pfeil nach rechts 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 Element A+ mit  x = x0 ... xn-1,   xi Element A,   n Element natürliche Zahlen

Entsprechend wird das Bild des Alphabets c(Aenthalten in B+ in diesem Fall als der Code bezeichnet.

Beispiel:  (Morse-Code)   A = { a , b, c, ..., z } ,   B = { ·, – }

a · –
b – · · ·
c – · – ·
 drei Punkte übereinander  
i · ·
s · · ·
u · · –
usw. 

Auch wenn die Codierung c des Alphabets A injektiv ist und damit die Umkehr­abbildung 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 'Leerzeichen' (kurze Pause) am Ende jedes Codewortes, d.h. B = {·, –, Leerzeichen}; damit genügt der Code der folgenden Bedingung für homomorphe Codierungen:

Satz:  (Fanozur Person-Bedingung)

Wenn kein Codewort Anfangswort eines anderen Codewortes ist, dann ist jede Zeichenreihe aus c(A+enthalten in B+ eindeutig dekodierbar.

Die Fano-Bedingung spielt eine Rolle bei Codes mit variabler Code­wort­länge, z.B. beim Huffman-Code. Im Folgenden sollen jedoch zunächst Codes mit konstanter Code­wort­länge, die Blockcodes, betrachtet werden. Bei Blockcodes ist die Fano-Bedingung immer erfüllt.

Blockcodes

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

Wir schreiben die Elemente von boolesche Werten nicht als n-Tupel (x0, ..., xn-1), sondern als Wörter x0 ... xn-1.

Beispiel:  3-Bit-Binärcode C3 = boolesche Werte3

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är­darstellung 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 Zweier­komplement-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 Codierungs­abbildung c, wir betrachten nur noch das Bild von c, den Code.

Durch Ausnutzung der algebraischen Eigen­schaften von Blockcodes lassen sich fehler­erkennende und fehler­korrigierende Codes konstruieren.

Definition:  Ver­knüpfungen  entweder oder  und  ·  in boolesche Werte

 

entweder oder01
001
110
 
 ·  01
000
101

Satz:  Die Menge boolesche Werte bildet mit den Ver­knüpfungen entweder oder und · einen Körper.

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

Definition:  Ver­knüpfungen entweder oder in boolesche Werten und · zwischen boolesche Werte und boolesche Werten

Wörter aus boolesche Werten werden komponenten­weise addiert, d.h. für alle x, y Element boolesche Werten ist

xentweder odery   =   (x0 ... xn-1entweder oder (y0 ... yn-1)   =   x0entweder odery0 ... xn-1entweder oderyn-1

Die Multi­plikation eines Körper­elements k Element boolesche Werte mit einem Wort x Element boolesche Werten geschieht ebenfalls komponenten­weise:

k · x   =   k · (x0 ... xn-1)   =   k · x0 ... k · xn-1

Beispiel:  1 0 0 1 entweder 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 Werten bildet mit diesen Ver­knüpfungen einen Vektorraum über boolesche Werte.

 

Hamming-Abstand

Ein wichtiger Begriff in der Codierungs­theorie ist der Hamming-Abstand (nach R.W. Hammingzur Person).

Definition:  Unter dem Hamming-Abstand d(x, y) zweier Wörter x, y Element boolesche Werten 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 Bit­positionen verschieden (an der 2. und 4. Position).

Satz:  Der Hamming-Abstand ist eine Metrik.

Definition:  Unter dem Hamming-Abstand eines Codes C enthalten in boolesche Werten versteht man das Minimum aller Hamming-Abstände zwischen je zwei ver­schiedenen Codewörtern:

d(C)   =   min{ d(x, y)  |  x, y Element 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 Element boolesche Werten ist die Summe aller xi, d.h. die Anzahl der Einsen in x:

w(x)   =    Summe 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 Element boolesche Werten gilt:   d(x, y)   =   w(x entweder oder y)

Definition:  Die Parität p(x) eines Wortes x = x0 ... xn-1 Element boolesche Werten ist die Summe (modulo 2) aller xi :

p(x)   =   Exklusiv-Oder 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 Element boolesche Werten mit e ≠ 0.

Ist w(e) = 1, so heißt e Einfach­fehler, ist w(e) = 2, so heißt e Doppelfehler usw.

C erkennt einen Fehler e, wenn für alle x Element C gilt:

x entweder oder e  nicht Element C

Das Prinzip eines fehler­erkennenden 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 Einfach­fehler.

Beweis:  Sei e ein Einfach­fehler und x Element C. Dann gilt:

d(x, x entweder oder e)   =   w(x entweder oder x entweder oder e)   =   w(e)   =   1

Somit kann x entweder oder e kein Codewort sein, denn dann müsste der Hamming-Abstand d(x, x entweder oder e) mindestens 2 sein. Also wird e erkannt.

Beispiel:  Binärcode mit Paritätsbit C4,3 enthalten in boolesche Werte4

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 Einfach­fehler.

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 in boolesche Werten ein n-Bit-Code mit mindestens zwei ver­schiedenen Codewörtern x und y. Dann gibt es einen Fehler e, den C nicht erkennt.

Beweis:  Der Fehler  e  =  x entweder oder y  wird nicht erkannt, denn es ist

x entweder oder e   =   x entweder oder x entweder oder 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.

(n,k)-Codes

Definition:  Zwei n-Bit-Codes heißen äquivalent, wenn sie durch Vertauschung der Bit­positionen 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 Wertek 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 in boolesche Werte4 ist systematisch mit k = 3.

Systematische Codes lassen sich auf­fassen als Ergebnis einer Codierung c : boolesche Wertek Pfeil nach rechts boolesche Werten, 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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.09.1997   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik