Information und Kommunikation Hartmut Klauck Universität Frankfurt SS 07 25.5

Information und Kommunikation

Hartmut KlauckUniversität Frankfurt

SS 0725.5.

Information & Kommunikation 12

2

Dekodierung

• Wir wollen nun untersuchen, wie RS Codes dekodiert werden können (die Kodierung ist trivial)

• Gegeben sind n verschiedene Elemente a1,…,an von Zq, y1,…,yn2 Zq, und Parameter k,t mit t· (n-k)/2

• Gesucht ist ein Polynom P mit Grad <k und P(ai)yi für höchstens t Werte von i


3

Dekodierung

• Es gibt einen Polynomialzeitalgorithmus

• Der erste entworfene Algorithmus für das Problem hat Laufzeit O(n3), bester Algorithmus heute O(n polylog n)

• Wir betrachten einen einfachen Algorithmus mit O(n3) Laufzeit


4

Dekodierung

• Definition 12.1– Gegeben a1,…,an und einen erhaltenen

Vektor y1,…,yn nennen wir ein Polynom E(x) fehlerlokalisierend für P, wenn es Grad t hat und E(ai)=0 gdw P(ai)yi

• So ein Polynom existiert:T sei die Menge der Fehlerpositionen in y,

|T|=t, setze E(x)=i2T (x-ai)


5

Dekodierung

• Wir setzen N(x)=P(x)E(x)• N hat Grad höchstens k-1+t

• Es gilt für alle i: N(ai)=yiE(ai)

– Denn: wenn E(ai)=0, dann gilt P(ai)E(ai)=0=yi E(ai)

– Wenn E(ai)0, dann gilt P(ai)=yi


6

Welch-Berlekamp Algorithmus

• Gegeben n,k,t· (n-k)/2 sowie n Paare (ai,yi) mit verschiedenen ai

• Schritt 1:– Finde Polynome N,E wie folgt, wenn

diese existieren• deg(E)=t• deg(N)<k+t

• Für alle i: N(ai)=yiE(ai)

• Schritt 2: Ausgabe von N(x)/E(x)


7

Laufzeit• Die Laufzeit ist O(n3)

– Für Schritt 2 ist dies leicht zu sehen– Der erste Schritt ist die Lösung eines linearen

Gleichungssystems– Wir suchen Koeffizienten N0,…,Nk+t-1 und E0,…,Et so dass für alle

i gilt:

– Weiterhin muss gelten Et 0– Wir dürfen aber Et=1 festlegen (es gibt ein

fehlerlokalisierendes Polynom mit Et=1, denn wir können sonst alle Koeffizienten durch Et teilen ohne die Nullstellen zu ändern)

– Das lineare Gleichungssystem kann in Zeit O(n3) gelöst werden


8

Korrektheit

• Angenommen P hat Grad <k und stimmt mit n-t Paaren überein (d.h. P(ai)=yi)

• Wir zeigen, dass ein Paar von Polynomen N,E wie gefordert existiert– E sei das fehlerlokalisierende Polynom;

N=PE. Dann erfüllen N und E alle Eigenschaften.

• Allerdings sind N,E nicht unbedingt eindeutig


9

Korrektheit• Lemma 12.2

Alle Lösungen N,E und N‘,E‘ erfüllenN(x)/E(x)=N‘(x)/E‘(x)

• Damit gilt, dass N‘(x)/E‘(x)=N(x)/E(x)=P(x).• Beweis:

– Der Grad von N(x)E‘(x) und N‘(x)E(x) ist \leq k-1+2t– Für alle i gilt:

• yiE(ai)=N(ai) und N‘(ai)=yiE‘(ai)• yiE(ai)N‘(ai)=yiE‘(ai)N(ai)• Wir behaupten dass sogar E(ai)N‘(ai)=E‘(ai)N(ai)

– Klar wenn yi0– Sonst: N(ai)=N‘(ai)=0 und Beh. gilt ebenfalls

– Wenn nun n¸ k+2t, so stimmen E(x)N‘(x) und E‘(x)N(x) auf mehr Punkten überein als ihr Grad, und sind daher identisch


10

Codes

• Wir haben verschiedene fehlerkorrigierende Codes kennengelernt– Reed-Solomon, Hamming, Hadamard

• Diese Codes können ¼ doppelt so viele Erasures korrigieren wie Fehler

• Es gibt aber auch spezielle Erasure Codes


11

Codes

• Welche guten Codes gibt es noch?– BCH-Codes: algebraische Codes (Reed-Solomon

Spezialfall) mit teilweise besseren Eigenschaften– Low Density Parity Check Codes:

• können in Linearzeit dekodiert werden– durch graphtheoretische Ideen

• können konstanten Bruchteil von Fehlern korrigieren• Konstante Rate• Variante davon kann auch in Linearzeit kodiert werden

– Tornado Codes• Erasure Codes, welche Kapazität fast erreichen

– Linearzeit kodierbar und dekodierbar


12

Dynamische Codes

• Es gibt weitere Variante von Codes– Fountain Codes:

• Sender schickt eine Folge von Paketen. Jede Teilmenge von k Paketen reicht aus, um die Nachricht zu dekodieren

• Also für Erasure Kanäle mit beliebiger Verlustrate geeignet

• Sender schickt eine unendliche Folge von Paketen, stoppt erst, wenn Empfänger dies signalisiert


13

Datenkompression

• Wir kommen jetzt kurz zur Kompression zurück

• Praktisch relevantes Verfahren:Lempel-Ziv

• (Z.B. in zip-Programmen, oder dem GIF Standard)

• Dynamisches Verfahren• Verlustfrei


14

Lempel Ziv

• Universelles Verfahren zur Kompression von Daten aus einer Quelle

• Passt sich der Quelle an• Die Rate geht gegen die Entropie der

Quelle• Auch praktisch relativ effizient


15

Lempel Ziv

• Eine Quelle produziert einen Bitstring– (Verfahren kann einfach auf andere

Alphabete verallgemeinert werden)

• Der Algorithmus konstruiert eine Tabelle von Worten, die bereits vorkamen

• Worte, die noch nicht vorkamen, werden in die Tabelle aufgenommen


16

Lempel Ziv

• Beispiel:– 010010010110101010101– wird zu 0,1,00,10,01,011, 010,101,0101

• D.h. nach jedem Komma suchen wir das kürzeste neue Wort

• Alle Präfixe eines neuen Teilstrings xi,…,xi+t sind bereits in unserer Tabelle, insbesondere der String xi,…,xi+t-1

• Wir kodieren den neuen String als die Position des Präfixes in der Tabelle + das neue Bit


17

Lempel Ziv

• c(x) sei die Anzahl der Worte in der Tabelle zu einem n-Bit String x

• Jeder Tabellenindex braucht daherlog c(x) Bits, dazu 1 Bit für das letzte Zeichen

• Beispiel:– 0,1,00,10,01,011,010,101,0101– Wird zu (0000,0), (0000,1), (0001,0), (0010,0),

(0001,1), (0101,1), (0101,0), (0100,1), (0111,1)– Erst bei langen Strings erhalten wir tatsächlich

eine Kompression!


18

Lempel Ziv

• Der Algorithmus läuft also zweimal über de String, zuerst wird die Tabelle erzeugt, c(x) berechnet

• Dann wird kodiert• Varianten möglich, wo die Pointer

nicht alle die gleiche Länge haben, und wo nur ein Durchlauf nötig


19

Lempel Ziv

• Wir erhalten eine Kodierung mit Längec(x)(log(c(x))+1)

• Unser Ziel ist es zu zeigen, dassc(x)(log(c(x))+1)/n gegen die Entropie der Quelle geht

• Dies gilt für Stationäre Ergodische Quellen• Wir betrachten der Einfachheit halber nur

Quellen, die unabhängig zufällig Bits ausgeben


20

Lempel Ziv

• Theorem 12.3– Die Anzahl c(x) der Worte in die ein n-Bit String

x zerlegt wird, erfüllt c(x)· n/((1-n) log n),

wobei n gegen 0 geht

• Beweis:– Sei

– Dies ist die Summe der Längen aller Strings der Länge ·k


21

Lempel Ziv

• Die Anzahl der erzeugten Teilworte in unserem String x1,…,xn ist maximal, wenn diese möglichst kurz sind

• Wenn n=nk, dann geschieht dies wenn alle erzeugten Teilworte · k lang sind, daher gilt:

• Wenn nk· n < nk+1, gilt n=nk+ und · (k+1)2k+1

• Es gibt dann /(k+1) Worte der Länge k+1


22

Lempel Ziv

• Daher:

• Wir müssen noch die Größe von k für gegebenes n bestimmen.

• nk· n < nk+1,

• Dann:


23

Lempel Ziv


24

Lempel Ziv• Sei nun y1,…yc(x) eine Zerlegung von x in Teilworte• cl(x) sei die Anzahl der yi mit Länge l• Klar:

• Lemma 12.4– Für jede Verteilung p auf {0,1} (und deren Erweiterung auf {0,1}n )

und die Zerlegung y1,…yc(x) von x gilt:

log p(x)· -l=1....ncl(x) log cl(x)


25

Beweis 12.4

• Es gilt:

log p(x)=log i=1…n p(xi)

=log i=1…c(x) p(yi)

=i=1…c(x) log p(yi)

=l=1....n i:|yi|=l log p(yi)

=l=1....ncl(x)i:|yi|=l (1/cl(x)) log p(yi)

· l=1....ncl(x) log(i:|yi|=l (1/cl(x)) p(yi) )

mit Jensen und i:|yi|=l 1/cl(x)=1


26

Beweis 12.4

• Daher:

• log p(x)

· l=1....ncl(x) log(i:|yi|=l (1/cl(x)) p(yi))

= l=1....ncl(x) log((1/cl(x)) i:|yi|=l p(yi))

· l=1....ncl(x) log(1/cl(x))

=-l=1....ncl(x) log cl(x)

Documents

Information und Kommunikation Hartmut Klauck Universität Frankfurt SS 07 25.5