Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2014 / Codierungstheorie / Material / Skript Teil 1


Inhaltsbereich

Skript Teil 1

Skript Teil 1. Beweis der Kraft'schen Ungleichung aktualisiert.

Plain Text icon skript1.txt — Plain Text, 13 KB (13422 bytes)

Dateiinhalt

Codierungstheorie SS14 
======================



O. Einfuehrung
--------------
Codierungstheorie befasst sich mit der Uebertragung von Information
ueber fehlerbehaftete Kanaele (Draehte, Glasfaserkabel, Datentraeger,
...) 

Die zu sendende Information wird zunaechst in Woerter ueber einem
Alphabet Sigma verwandelt. Diesen Vorgang bezeichnet man als
Quellencodierung.

Beispiele fuer die Quellencodierung bilden verschiedene Audio- und
Videoformate, die ASCII Codierung etc. 

Um die Uebertragung der quellencodierten Information ueber einen
fehlerbehafteten Kanal moeglichst verlustarm zu gestalten, wird die
Information redundant codiert (Kanalcodierung), sodass die Erkennung
und auch die Korrektur von Uebertragungsfehlern ermoeglicht wird.

Fehlererkennung ist sinnvoll, wenn eine Wiederholung der gesendeten
Information moeglich ist:

ARQ (automatic repeat request): Wird ein Fehler erkannt, so wird die
Nachricht automatisch erneut angefordert.

In manchen Situationen ist ein erneutes Senden nicht oder nur schwer moeglich. 

Beispiele: Datentraeger (CD, Festplatte). Kommunikation mit langer
Uebrtragungszeit (Weltraumsonden).

Hier ist eine Fehlerkorrektur angebracht. 

FEC (forward error correction): Die Information wird so redundant
codiert, dass eine betimmte Maximalzahl von Uebertragungsfehlern
korrigiert werden kann.

Beispiele fuer fehlererkennende Codes: 

Paritaet: Nach sieben uebertragenen Bits wird ein achtes Bit so
angefuegt, dass die Zahl der 1en in dem entstehenden Achterblock
(Byte) gerade ist.

0010011 -> 00100111
1101010 -> 11010100

Wird nun ein Byte mit einer ungeraden Zahl gesetzter Bits empfangen,
so liegt ein Fehler vor und eine Sendewierholung kann angefordert
werden. Bemerkung: die Bedingung, dass die Zahl der gesetzten Bits
unter c_1, ..., c_8 gerade ist, kann auch als 

      c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7 + c_8 = 0 (mod 2)

geschrieben werden. 


ISBN-Code: Die Information besteht hier aus neun Ziffern z_1, ..., z_9
aus F={0..9}. Diesen wird eine Pruefziffer z_10 aus F u {X} angefuegt,
sodass gilt:

			sum_{i=1}^10 (11-i)z_i = 0    (mod 11)

wobei X=10 gesetzt wird. 

Zum Beispiel hat das Buch Codierungstheorie von Willems die ISBN Nummer 

3-11-015873-6

Es gilt 10*3 + 9*1 + 8*1 + 7*0 + 6*1 + 5*5 + 4*8 + 3*7 + 2*3 + 1*6 = 
30 + 9 + 8 + 6 + 25 +32 +21 + 6 + 6 = 
-3 - 2 + 8 + 6 + 3 - 1 - 1 +1 = 0 (mod 11) 

Da man eine beliebige Ziffer aus den neun anderen ausrechnen kann,
laesst sich eine verfaelschte Ziffer erkennen. Sind allerdings zwei
Ziffern verfaelscht, so erkennt man das im allgemeinen nicht mehr. 

Immerhin hat der ISBN Code die zusaetzliche Eigenschaft, dass eine
Vertauschung zweier benachbarter (verschiedener) Ziffern erkannt wird:
Fuer die Differenz der Pruefsummen gilt naemlich dann (falls i die
Position der Vertauschung und u,v die beiden vertauschten Ziffern
sind):

i * u + (i+1) * v - 
i * v - (i+1) * u = v-u =/= 0 

Aehnliche Codes werden fuer die Strichcodes fuer Produkte und auch
fuer Kontonummern eingesetzt.

Beispiele fuer fehlerkorrigierende Codes: 

Dreifache Wiederholung: Will man einen Block b von Bits uebermitteln,
so kann man stattdessen die dreifache Wiederholung des Blocks bbb
senden. Durch Mehrheitsentscheidung kann dann mindestens ein Fehler
korrigiert werden.

(7,16,3)-Hammingcode: vier Bit c_1, c_2, c_3, c_4 werden um drei
Pruefbits c_5, c_6, c_7 so erweitert, dass gilt: 

c_1 + c_4 + c_6 + c_7 = 0 (mod 2)
c_2 + c_4 + c_5 + c_7 = 0 (mod 2)
c_3 + c_5 + c_6 + c_7 = 0 (mod 2)

Wird ein Wort (c_1,...,c_7) uebertragen, so bildet man die drei linken
Seiten jeweils mod 2 und erhaelt so drei Pruefbits p_1,p_2,p_3. Aus
diesen kann der Fehler rekonstruiert werden. 

Beispiel: Es sei c_1=1, c_2=0, c_3=1, c_4=1. Wir fuegen hinzu: 
c_5 = 1, c_7 = 0, c_6 = 0 und senden also das Wort 1011100. Entsteht
nun ein Fehler an der dritten Position, so wird 1001100 empfangen. 

Wir bilden die Pruefbits p_1=1+1+0+0=0, p_2=0, p_3=1. Das einzige Bit,
welches nur in p_3 vorkommt, ist c_3, daher muss dieses verfaelscht
worden sein. Ebenso kommt c_4 genau in p_1 und p_2 vor. Liegt daher
das sog. "Syndrom" p_1=1, p_2=1, p_3=0 vor, so wurde c_4 verfaelscht. 

Grundaufgabe der Kanalcodierung: Moeglichst viele Fehler erkennen und
korrigieren bei gleichzeitig moeglichst geringer "Rate" (Verhaeltnis
Codewortlaenge / Nutzlaenge). Dabei algorithmisch moeglichst einfache
Codierung, Decodierung, und Korrektur. Unterschiedliche Loesung je
nach Art der zu erkennenden Fehler: Bitfehler, Transposition, Burst,
Verschiebung. 

Grundaufgabe der Quellencodierung: Laenge der Codierung in
vernuenftigem Verhaeltnis zur Auftretenswahrscheinlichkeit (des
kodierten Symbols).


1. Quellencodierung nach Shannon-Fano und Huffman
-------------------------------------------------

Wir betrachten hier die folgende Aufgabe, die bei der Quellencodierung
eine wichtige Rolle spielt: 

Gegeben sei eine Informationsquelle, die Zeichen aus einem
Zeichenvorrat S={s_1,...,s_n} generiert. Die
Auftretenswahrscheinlichkeit des Zeichens s_i sei p_i. Wir machen die
Annahme, dass die Informationsquelle gedaechtnislos sei, d.h. die
Wahrscheinlichkeit, dass Zeichen s_i generiert wird, ist unabhaengig
davon, welche Zeichen vorher generiert wurden. 

Ist die Annahme der Gedaechtnislosigkeit nicht gerechtfertigt, so kann
u.U. zu einem groesseren Zeichenvorrat uebergegangen werden. Beispiel:

Sei S={0,1} und x_1,x_2,... die Folge der gesendeten Zeichen. Es
gelte: 

Pr(x_{2i} = 0) = 0,4 
Pr(x_{2i} = 1) = 0,6
Pr(x_{2i+1}=0|x_{2i}=0) = 0,9  
Pr(x_{2i+1}=1|x_{2i}=0) = 0,1  
Pr(x_{2i+1}=0|x_{2i}=1) = 0,2  
Pr(x_{2i+1}=1|x_{2i}=1) = 0,8  

Wir fassen jeweils x_{2i} und x_{2i+1} zu einem Symbol aus dem Vorrat
S'={00,01,10,11} zusammen. Die entstehende Quelle ist gedaechtnislos
mit p_{00} = 0,36, p_{01}=0,04, p_{10}=0,12, p_{11}=0,48.

Sei also nunmehr wiederum eine gedaechtnislose Quelle
vorausgesetzt. In der Praxis werden die Auftretenswahrscheinlichkeiten
durch relative Haeufigkeiten ersetzt. 

Notation: Mit log(x) bezeichnen wir den Logarithmus von x zur 
Basis 2. Will man x Zustaende codieren, so benoetigt man ca. log(x) bits.

Definition (Informationsgehalt)
Der Informationsgehalt des Zeichens s_i ist gegeben durch 

                       I(s_i) = -log(p_i)

Seltene Zeichen haben also entsprechend grossen Informationsgehalt. 

Sind n Zeichen gleichwahrscheinlich, so hat jedes Zeichen
Informationsgehalt log(n) = -log(1/n), also gerade soviel, wie man
Bits benoetigt um es zu codieren. Tritt ein Zeichen a mit W. 1/2 auf
und zwei andere b,c mit W. jeweils 1/4, so bietet es sich an, a mit 0
zu kodieren und b,c, jeweils mit 10 und 11. Die Laenge der Kodierung
eines Symbols stimmt so genau mit seinem Informationsgehalt ueberein.

Definition (Entropie):
Die Entropie der Informationsquelle Q ist ihr mittlerer
Informationsgehalt: 
 
             H(Q) = sum_i.p_i * I(s_i) = -sum_i p_i*log(p_i)

Eine Quelle, die die zwei Zeichen gleichwahrscheinlich generiert, hat
die Entropie H = 0.5 * 1 + 0.5 * 1 = 1 

Eine Quelle, die n Zeichen gleichwahrscheinlich generiert, hat die
Entropie H = log(n). 

Definition (Entropiefunktion): 
Man definiert die Entropiefunktion auf Tupeln (p_1,...,p_n) mit 
p_i:[0,1] und sum_i p_i=1 durch 

        H(p_1,...,p_n) = - sum_i p_i * log(p_i)

Hierbei setzen wir 0*log(0) = 0, was durch lim_{x->0} x*log(x) = 0
gerechtfertigt ist. 

Die Entropie einer Quelle mit Wahrscheinlichkeiten p_1,..,p_n ist also
gerade durch die Entropiefunktion gegeben.

Definition (binaere Entropiefunktion): 
Man definiert h(p) = H(p,1-p). 

Notation: Statt p_1,...p_k schreiben wir auch ps (lies pehs,
an der Tafel auch als p-Vektor geschrieben).

Satz (Additivitaet): Es gilt: 
H(ps,p,q) = H(ps,p+q) + (p+q)*h(p/(p+q))

Beweis: H(ps,p+q) + (p+q)*h(p/(p+q)) = 
H(ps,p+q) - (p+q)*(p/(p+q)*log(p/(p+q)) + q/(p+q)*log(q/(p+q))) = 
H(ps,p+q) - p*log(p) - q*log(q) + (p+q)*log(p+q) = 
H(ps)- p*log(p) - q*log(q) = H(ps,p,q)       [] 

Wir moechten nun jedem Zeichen s_i eine Bitfolge b_i zuordnen, sodass
gilt: 

1) (Fano-Bedingung) Wenn i=/=j, so ist b_i nicht Praefix von b_j. 
2) Die mittlere Laenge sum_i p_i*|b_i| ist moeglichst klein. 

Die Fano Bedingung ist erfuellt fuer {0,10,110,111}, nicht aber fuer
{10,11,100}. Ist sie erfuellt, so koennen die Codierungen bi ohne
Trennsymbol aneinandergefuegt werden. 

01011010100101110101010011010111 ==
0 10 110 10 10 0 111 0 10 10 10 0 110 10 111

Beachte: Uebertragungsfehler werden hier ignoriert. Ihnen kann durch
nachfolgende Kanalcodierung begegnet werden. 

Die Fanobedingung ist gleichbedeutend damit, dass die Woerter b_i die
Adressen der Blaetter eines endlichen Baumes sind. 

                      / \ 
                      0  1
                        / \ 
                       10 11
                          / \
                        110  111

Ist nur die Fano-Bedingung erfuellt, so spricht man von einem
Praefixcode (vgl auch Telefonnummern).

Es gilt also, die Zeichen s_1...s_n so als Blaetter eines binaeren
Baumes zu arrangieren, dass die mittlere Tiefe des Baumes moeglichst
klein wird. (Tiefe eines Symbols = Laenge des zu ihm fuehrenden
Pfades). 

Shannon und Fano schlugen nun vor, die Symbolmenge S so in zwei
Haelften S = U u V aufzuteilen, dass die Wahrscheinlichkeiten Pr(U)
und Pr(V) moeglichst nahe beieinander liegen. Die Symbole aus U kommen
dann in den linken Teilbaum, die aus V in den rechten Teilbaum. Sodann
wird dieses Verfahren auf die Teilbaeume rekursiv angewendet. 

Beispiel: 5 Zeichen A,B,C,D,E mit Wahrscheinlichkeiten
(Haeufigkeiten): 15/39, 7/39, 6/39, 6/39, 5/39. 

Wir teilen auf in U={A,B} (W. 22/39) und V={C,D,E} (W. 17/39) (Beste
Aufteilung). U wird in {A}, {B} aufgeteilt. V in {C}, {D,E} und dann
{D,E}. Es ergibt sich die Codierung: 

A = 00
B = 01
C = 10
D = 110
E = 111

mit mittlerer Laenge 

1/39 * (28*2 + 3*11) = 1/39 * (56+33) = 1/39 * 89 = 2,282

Ueberraschenderweise ist die folgende Kodierung guenstiger: 

A = 0 
B = 100
C = 101
D = 110
E = 111

1/39 * (15 + 3*24) = 1/39 * 87 = 2,231
 
Ein Algorithmus, der immer die optimale Kodierung findet, wurde von
Huffman gefunden: 

1. Benutze einen Wald aus binaeren Baeumen deren Blaetter mit Symbolen
bechriftet sind. Die Beschriftungen der einzelnen Baeume sind
disjunkt. Zusammen ergeben die Beschriftungen gerade die Menge S aller
Symbole. Die Haeufigkeit eines Baumes ist die Summe der Haeufigkeiten
seiner Beschriftungen. Man kann die Haeufigkeit in der Wurzel des
Baumes speichern, um sie nicht immer neu berechnen zu muessen. 

2. Zu Beginn wird fuer jedes Symbol ein eigener Baum eingefuehrt. 

3. Solange noch mindestens zwei Baeume vorhanden sind, verbinde man
die beiden Baeume mit den niedrigsten Haeufigkeiten zu einem neuen
Baum.  

4. Ist nur noch ein Baum vorhanden, so liefert dieser die optimale
Kodierung. 

Im Beispiel beginnt man also mit dem Wald 

{(15,A), (7,B), (6,C), (6,D), (5,E)}

Danach ergeben sich die folgenden Arbeitsschritte: 

{(15,A), (7,B), (6,C), (6,D), (5,E)}
{(15,A), (7,B), (6,C), (11,(D,E))}
{(15,A), (13,(B,C)), (11,(D,E))}
{(15,A), (24,((B,C),(D,E)))}
{(39,(A,((B,C),(D,E))))}

aus dem die oben genannte Kodierung abgelesen werden kann. 

Satz: Huffmans Algorithmus liefert immer eine optimale Kodierung. 

Beweis: Man benutzt die Invariante, dass sich der Wald zu einem
optimalen Kodebaum erweitern laesst. Am Anfang ist dies sicher der
Fall, den es gibt ja nur endlich viele Kodebaeume, unter diesen also
einen besten und der ist trivialerweise eine Erweiterung des initialen
Waldes. Gelte die Invariante also zu einem bestimmten Zeitpunkt und
sei ein optimaler Kodebaum t, der den aktuellen Wald w erweitert,
fixiert. 

Wir betrachten die Entfernung der beiden seltensten Baeume von der
Wurzel in t. Wegen der Optimalitaet muessen die maximale Entfernung
haben, denn sonst koennte man die Haufigkeit von t durch
entsprechendes Vertauschen noch verbessern. 

Durch ggf weiteres Vertauschen kann man erreichen, dass die beiden
seltensten Baeume in w Geschwister in t werden und erhaelt so einen
den naechsten Wald erweiternden optimalen Kodebaum.  []

Die Huffman-Kodierung findet mit geringfuegigen weiteren
Verbesserungen in der jpeg-Bildcodierung eine Anwendung. Ganz grob
gesagt, entsprechen die Farbwerte den zu kodierenden Symbolen. Fuer
seltene Farben kann man dann laengere Kodierungen in Kauf
nehmen. "Ganz grob" bezieht sich auf die verlustbehaftete
Komprimierung, die bei jpeg noch vor der Huffman-Kodierung
stattfindet. 

Satz (Kraftsche Ungleichung): Es seien l1..ln Zahlen sodass sum_i
2^{-li} <= 1. Dann existiert eine Teilmenge {w1..wn}:{0,1}^* sodass
|wi|=li und ausserdem die Fano-Bedingung erfuellt ist, d.h. i=/=j =>
wi nicht Praefix von wj.

Beweis: Wir setzen voraus, dass l1 <= l2 <= ... <= ln =:max. Sind die Woerter w1..wi bereits gewaehlt, so waehlen wir w(i+1) so, dass w(i+1) keines der bereits gewaehlten Woerter zum Praefix hat. Dass dies immer moeglich ist, folgt aus der Annahme. Sei naemlich ri der Anteil derjenigen Woerter der Laenge max, die eines der
bereits gewaehlten Woerter w1..wi als Praefix haben, also nicht mehr in Frage kommen.  Zu Beginn ist r0=0. Die Wahl eines Wortes der Laenge i+1 erhoeht diesen Anteil gerade um 2^{-l(i+1)}, sodass nach Annahme ri stets kleiner als Eins ist und dementsprechend immer noch Platz fuer das naechste Wort verbleibt. 

Bemerkung: Die Umkehrung des Satzes gilt auch (jeder Praefixcode
erfuellt die Kraftsche Ungleichung).

Artikelaktionen


Funktionsleiste