17: Informationstheorie, Entropie, Codierung
KIT Lehre und Wissen
https://www.youtube.com/watch?v=6og0-AQ-KpA

Transkript (automatisch erstellt)

0:07 ja hallo zusammen heute ist die vorletzte Vorlesung und wir fangen noch mal ein neues Kapitel an
0:14 M das Kapitel Informationstheorie da sind die Verbindungen zu den anderen Kapitel nicht so eng wie das bei den vorherigen Kapiteln untereinander war
0:26 also bei den vorherigen Kapitel war es ja so dass man insgesamt eigentlich ein ganz rundes äh Themengebiet hat wo
0:37 durchgängig fragen wie wie schwierig ist ein Problem bzw in unserer Sprache wie schwierig ist das wortproblem für bestimmte Fragen was sind sozusagen die
0:50 Klassen in die sich Sprachen entsprechend ihrer ja Mächtigkeit Ausdrucksfähigkeit einerseits und scherigkeit
1:01 andererseits eingruppieren lassen was ist das zugehörige Maschinenmodell was ist das zugehörige Regelsystem zur Erzeugung dieser Sprachen also das war
1:11 insgesamt ganz rund und vor allem auch das letzte Kapitel mit den Grammatiken hatte dann direkten Bezug zu dem ersten Kapitel wo wir die endlichen Automaten
1:20 regulären Sprachen betrachtet haben und durchgängig haben wir sowas wie Maschinenmodelle endliche Automaten touringmaschinen kellerautomaten
1:28 betrachtet ähm das hier Informationstheorie fällt da sozusagen raus ne eigenes Thema was aber zu den theoretischen Grundlagen der
1:40 Informatik gehört und deshalb soll es hier auf jeden Fall angesprochen werden so worum geht's äh ja wir betrachten sowas wie Codierung von äh m Alphabet
1:51 oder von inf von von Worten oder Daten äh mit unterschiedlichen [Musik] ähm aus unterschiedlichen Gründen oder
2:01 mit unterschiedlichen Anwendungen äh im Hinterkopf ähm quellcodierung dass war also eine Quelle einer informations für Information eineer Informationsquelle
2:14 codieren wollen kanalkcodierung dass wir eben uns auf die Übertragung von äh Daten konzentrieren oder auch Kryptografie um sozusagen sicher
2:26 gegenüber Zugriff von außen zu kodieren also noch mal genauer quellcodierung wir wollen am Ausgang einer
2:40 Informationsquelle kodieren und zwar so dass Redundanz reduziert wird ist also was sie komprimieren ja also hier steht's
2:52 auch ganz genau als Hauptaufgabe Datenkompression ja ähm da kann man jetzt unterscheiden zwischen verlustfreier und verlustbhafteter
3:01 Kompression also wir wollen unsere Daten komprimieren um Redundanzen auszu schalten aber möglicherweise noch darüber hinaus eben
3:15 um möglichst kurze kodierungslänge möglichst hohe Kompression zu bekommen und da könnte man natürlich sagen na ja wir nehmen
3:23 vielleicht auch sogar in Kauf dass ein gewisser Verlust gewisse teil der Information verloren geht
3:32 dabei das hat natürlich Zeiten von Big Data hohe wirtschaftliche Bedeutung die nächste Art der Codierung also Art der Codierung mit was ist die Motivation
3:45 warum wir codieren ist kanalkodierung da schauen wir also auf die Übertragung von Daten digitalen Daten und auf den Sachverhalt dass die
3:57 Übertragung gestört sein könnte ja der Kanal ist äh gestört und wir eben schützen wollen durch die Codierung vor Übertragungsfehlern indem wir wieder
4:08 Redundanz zufügen ja das also sozusagen konträr zu dem was bei der quellcodierung so typischerweise passiert hier würde man also mehr
4:17 Redundanz reinbringen um eben im Fehlerfall die Fehler auch finden und korrigieren zu können äh wie es hier als letzten Punkt auch steht ja und äh ja
4:28 dritte Grund oder Anwendung warum man codieren will ist eben Informationssicherheit ähm also wir wollen ja sozusagen
4:40 widerstandsfähig sein Gegenüber unbefugten Lesen von äh übertragener Informationen bzw unbefugten verändern okay
4:52 äh sie werden feststellen dass dieses Kapitel nicht in meinem Skript behandelt wird mit den Folien zur Vorlesung haben sie aber alles vollständig abgedeckt was
5:04 wir hier besprechen sie können auch darüber hinaus mal in das Skript von hern Müller Quade aus dem Wintersemester 0809 schauen also das habe ich auch als
5:16 Quelle genommen mit für dieses Thema das ist auch auf unserer Homepage verlinkt und das wiederum basiert sehr stark auf dem Buch von Werner Information und
5:28 Kodierung Link dazu haben wir auch auf der Webseite okay ja Informationstheorie da ist jetzt mal die allererste Frage was
5:37 ist Information von formalen Definition für Information also was wir betrachten ist immer so ein Alphabet wie bisher auch ja
5:47 ein Alphabet von Zeichen oder Elementen und hier schauen wir immer gleichzeitig auf die Wahrscheinlichkeit dieser Zeichen ja also wenn hier das Alphabet
5:58 oder die Menge von Zeichen σma ist = 1 bis n dann ist mit 1 bis n eigentlich gemeint das sind also nzeichen und die sind durchnummeriert mit 1 dur n kann
6:08 also auch irgendwas anderes sein als eben die Zahlen 1 bis n und die haben jeweils eine Wahrscheinlichkeit das erste Wahrscheinlichkeit P1 zweite
6:17 Wahrscheinlichkeit P2 und so weiter bis n hat Wahrscheinlichkeit PN und wir betrachten jetzt also so eine Informationsquelle aus der deutsche
6:27 Zeichen heraus ja Zeichen i aus Sigma mit einer Wahrscheinlichkeit PI als im mathematischen Sinn ist das nichts anderes als eine diskrete endliche
6:40 Zufallsvariable diese Informationsquelle wir müssen ein klein bisschen mit Wahrscheinlichkeiten auch umgehen aber
6:48 nie nicht nicht über das ganz grundlegende hinaus so einfach als Beispiel was gemeint ist mit einer Informationsquelle wo solche Zeichen
6:59 auskommen die eine gewisse Wahrscheinlichkeit haben betrachten Sie einen Würfel mit sechs Seiten bei dem jede Seite mit gleicher
7:09 Wahrscheinlichkeit auftritt wenn Sie den Würfel werfen das heißt also sie haben also als die Menge σma 1 2 3 4 5 6 ja und die Wahrscheinlichkeiten sind
7:20 jeweils ein Sechstel ne Pi ist für ein bis se jeweils ein Sechstel bei einem idealen Würfel wo es so ist wie hier das also wirklich
7:29 alle sechs Seiten mit gleicher Wahrscheinlichkeit auftreten ist es schwer vorher zu sagen was eigentlich passiert das heißt also der
7:39 Erkenntnisgewinn durch einen eine Ausführung ist hoch ja also vorher nicht sousag sagen können na ja da wird wahrscheinlich das und das kommen ist
7:49 das was dann kommt bringt ihnen sozusagen viel Information ja gegenüber der Situation wir hätten also einen Würfel wo die
8:01 Wahrscheinlichkeiten ungleich verteilt sind vor allem die sechs besonders häufig ist also mit hohe Wahrscheinlichkeit kommt also hier
8:08 meintwegen mit Wahrscheinlichkeit ein halb kommt und die anderen kommen in der Summe nur mit Wahrscheinlichkeit ein halb also jedes weiter mit der
8:15 Wahrscheinlichkeit ein Zehntel da würden Sie vorab schon sagen na ja gut also jetzt bevor ich werfe da wird wohl die sechs kommen ja das heißt also
8:24 der informations od Erkenntnisgewinn ist kleiner für einen solchen Wurf das sozusagen die Idee die zur Definition von Information führt wir
8:39 suchen als also ein Maß für den Erkenntnisgewinn nach Ausgang K ja folgendes kommt raus bei einem Würfelwurf mit Wahrscheinlichkeit PK und
8:53 diesen Erkenntnisgewinn bezeichnen wir als Information abgekürzt als I undten p K denn das hängt ja ganz entscheidend ab von dem der Wahrscheinlichkeit wie hoch
9:05 der Erkenntnis hoch die Information also Information wird mit IPK
9:12 abgezeichnet abgekürzt oder geschrieben PK ist die Wahrscheinlichkeit dass der Ausgang einer Informationsquelle fürs nächst
9:22 nächst mal K ist und äh wir wollen jetzt definieren wie also dieses PK aussieht ähm dazu kann man mal überlegen ja was was ist denn unsere Intuition wie das
9:35 aussehen soll oder Forderungen oder Wünsche an Aussehen von dem IPK was ja irgendwie ein Wert sein muss ne wir wollen sozusagen Information als Wert
9:45 oder Erkenntnisgewinn als Wert darstellen also Wert Zahlenwert äh ja was haben wir da an Wünsche na ja gut die Informationen soll nicht negativ
9:54 sein also das wollen wir nicht dass nach so einem Ereignis wir will weniger wissen als vorher ja ähm das heißt also das i PI soll größer
10:05 gleich 0 sein und bei einem sicheren Ereignis also wenn man vorher schon weiß was rauskommt haben wir keinen informations oder Erkenntnisgewinn also
10:15 da soll die Information sozusagen Null sein ja ähm kleine Veränderungen in der Wahrscheinlichkeit haben also betrachten
10:24 zwei Ereignisse äh die nur sehr unterschiedlich Wahrscheinlichkeit haben dann soll entsprechend auch die
10:33 Information nur in der Größe sich unwesentlich unterscheiden also kleine Änderungen an der Wahrscheinlichkeit sollen nur kleine
10:41 Änderungen an der Information bewirken also wenn man das mathematisch ausdrücken soll Information als eine Funktion in der Wahrscheinlichkeit
10:52 stetig und dann haben wir natürlich auch so ein Wunsch wie ähm das eine doppelt so lange Zeichenkette auch doppelt so viel
11:02 Information enthalten können soll ähm da passt hervorragend jetzt mal Wahrscheinlichkeitsrechnung im Kopf hat wenn wir sagen okay mach also jetzt eine
11:15 doppelt so lange Zeichenkette also die Zeichenkette i gefolgt von Zeichenkette J deren Wahrscheinlichkeit die ist ja pi mal PJ und wenn wir dann fordern und für
11:27 die Information zuud dem der doppelt so langen Zeichenkette bestehend aus i und J soll gerade IPI + ipj sein das passt ja auch zu dem äh wie die
11:40 Wahrscheinlichkeiten sich verhalten ein Ereignis hat und folgeereignis und jetzt sagen diese beiden zusammen als Ereignis betrachtet
11:50 und schaut welche Wahrscheinlichkeit haben die also das ist im Prinzip das was hier in anderen Worten steht also damit soll wird sichergestellt dass die
12:01 Information einer unabhängigen Zeichenkette gleich der Summe der einzelinform okay und mit den Wünschen im Hinterkopf definieren wir Information
12:11 folgendermaßen sei P also Wahrscheinlichkeit und die Information zu P zu ein festgewählten Basis B ist P = Logarithmus 1 dur P zur Basis B
12:27 was ja man Logar Gesetze anwendet nichts anderes ist als US Logarithmus P zur Basis B und wir werden jetzt immer als Basis 2 betrachten auch weil wir immer
12:40 binärkodierung also hier im Logarithmus muss man hantieren hab nur zur Erinnerung coolwissen Logarithmus x mal y z
12:51 irgendeiner Basis a ist logaritmus X + logaritmus y jeweils zur Basis a passt hervorragend zu dem was wir äh haben wollen für die Information von einer
13:03 Zeichenkette die eben aus zweiinandergereihten Zeichenketten besteht das was wir gerade eben gesehen also angewendet haben Logarithmus 1 dur
13:12 x = logaritmus x Basiswechsel kann man auch durchführen und hier ist mal aufgezeichnet wie sich also äh sozusagen die Kurve zur Informationen Abhängigkeit
13:22 von der Wahrscheinlichkeit äh verhält hier unten steht P aber eigentlich ist das 1 durch P was hier eingetragen also das ganze wird also
13:31 Wahrscheinlichkeit ist ja immer kleiner gleich 1 und in der Information gucken wir also jetzt logarimus 1 durch
13:40 P oder Logarithmus 1 dur P = logarimus P und die Funktion verhält sich also dann so für 1 durch P okay also hier noch mal Definition für
13:55 Information also IP Information z Wahrscheinlichkeit P soll sein logarimus P Z Basis 2 typischerweise jetzt mal noch
14:06 mal im Beispiel macht das Sinn also wir betrachten eine Münze mit zwei Seiten Kopf oder Zahl und beide Seiten kommen mit gleicher Wahrscheinlichkeit ein halb
14:18 ist die Information eines münzwurfs gleich Logarithmus 1 durch 1 ein/ g= logaritmus 2 = 1 wunderbar wenn wir jetzt kam mal
14:30 werfen ist die Wahrscheinlichkeit für einen ganz bestimmten Ausgang ja also Kopf Kopf Zahl Kopf Kopf Zahl Kopf Kopf irgendwie äh ein/b mal ein/b mal ein/b
14:41 sozusagen kfach also 1 durch 2 hoch K die entsprechende Information logaritmus 1 dur 2 hoch K = logaritmus 2 h k = k so eng verbunden mit dem Begriff der
14:55 Information ist der Begriff der Entropie und was ist das anschaulich formuliert die Entropie ist ein Maß für den mittleren
15:04 Informationsgehalt pro Zeichen einer Quelle ja also es kommen jetzt aus der Quelle Zeichen aus unserem Sigma raus so eine ganze Folge an und was ist
15:16 der mittlere Informationsgehalt Folge oder eben wenn das Sigma angucken alle Zeichen in sigσma was der mittlere
15:24 Informationsgehalt für Sigma das hängt natürlich von den Wahrscheinlichkeiten ab auch den Streuungen der Wahrscheinlichkeit
15:33 m interessante Sichtweise oder andere Sichtweise auf die wir hier nicht weiter eingehen die ich nur zuur Information auf der Folie habe die Entropie so eines
15:42 Strings bezeichnet die Länge und unter der ein String nicht komprimiert werden kann volmogerov Komplexität das ein
15:50 komplexitäts Begriff eines Strings ist gerade die Länge des kürzesten Programms das diesen String ausgibt und die Entropie ist gerade dafür eine untere
16:00 Schranke war das wie gesagt da gehen wir nicht weiter auf Entropie ja also mittlerer
16:08 Informationsgehalt einer Quelle ähm irgendwie klar wie das dann definiert ist wenn die Information äh als Logarithmus 1 durch P von X
16:20 definiert ist für ein Zeichen oder ein Element x Entropie bben jetzt immer bei der Basis 2 einer diskreten Zufallsvariable mit
16:31 Ereignissen gr x ja und Wahrscheinlichkeiten P von X für jedes x aus Groß X ist definiert durch na ja gut wir Summen summieren auf über
16:43 die Ereignisse Wahrscheinlichkeit jedes einzelnen Ereignis mal Information des ere und den in mittleren Informationsgehalt ist ja nicht anderes
16:54 anders als aufsummiert alle Möglichkeiten wahrscheinlich jeder einzelnen mal dem Informationsgehalt so hier fällt jetzt
17:03 auf dass man da auch schon mal durch Null dividieren würde ja die Wahrscheinlichkeit von so einem X könnte ja null sein so und da nutzen wir
17:13 einfach die konvension das soll Null rauskommen wenn hier vorne dann eben dieser Vorfaktor dann auch null ist ne also das P von X ist n wenn das Null ist
17:21 dann ist der Vorfaktor auch ull also insofern ist das unkritisch irgendwie hier zu sagen na ja gut da soll also rauskommen während sonst wenn
17:32 hier der Vorfaktor nicht null wäre und hier oben was leich Null stünde bei Division von Null man per Konvention unendlich
17:41 definieren so eins ist schon mal klar dieses h von X die Entropie ist immer größer n0 ja größer gleich Null so also Entropie ist der mittlere
17:56 informations Gehalt so ein Sigma äh das hängt von den Wahrscheinlichkeiten der Elemente aus Sigma ab als Frage ist wann wird der
18:07 maximalere Information HT sich auch von der Streuung der Wahrscheinlichkeiten ab man kann leicht einsehen dass die entropi in einer diskreten endlichen
18:20 Zufallsvariable mit Z mit nzeichen maximal wird wenn die alle gleich wahrscheinlich sind also Entropie ist ja aufsummiert überall die Zeichen
18:31 Wahrscheinlichkeit das Zeichen mal Logarithmus 1 durch Wahrscheinlichkeit des Zeichens das wird am größten wenn die alle gleich wahrscheinlich und dann
18:41 kommt gerade Log n Anzahl der zeen bei der deutschen Sprache z.B ist es nicht so dass maximum angenommen wird
18:52 die Entropie der deutschen Sprache liegt bei 4,1 ausrechnen wenn man die
18:59 Wahrscheinlichkeiten der einzelnen Buchstaben anschaut ja in deutscher deutschem Text äh bei 26 Buchstaben
19:10 würde sich als maximale Entropie 4,7 ergeben 4,1 klein und hier auch noch mal für die Münze diese Funktion die die Entropie
19:25 äh angibt aufgetragen also bei einer Münze realen Münze ist für beide Seiten Wahrscheinlichkeit ein halb würde man
19:37 gerade hier landen ne Wahrscheinlichkeit halb also Zahl ist die Wahrscheinlichkeit ein halb und wenn die ideale Münze ideal ist
19:46 dann ist auch für Kopf Wappen die Wahrscheinlichkeit ein halb und die ist ja formal wenn die Wahrscheinlichkeit für P für Zahl P ist
19:57 1 P ja dann wä P und 1- P beides ein/b da kommt gerade das 1 raus aber wenn jetzt die Wahrscheinlichkeit für die Zahl irgendwo liegt zwischen
20:09 wegen bei 0,2 oder so da würde für die andere Kopf bei 0,8 liegen das heißt also die Formel für die Entropie bei der Münze ist jetzt bei beliebiger
20:22 Wahrscheinlichkeit zwischen 0 und 1 für Zahl eben dieses h von X gleich minus Wahrscheinlichkeit für Zahl Wahrscheinlichkeit für Zahlen
20:34 1-us Wahrscheinlichkeit für Zahl was Wappen Kopf ist mal logaritmus 1- P und hier okay so jetzt gucken wir mal konkrete Mechanismen oder Verfahren zum
20:50 kodieren an und wir wollen jetzt also Soz sagen dies Thema quellcodierung angucken also wir wollen platzparend kodieren oder komprimieren
21:00 ja betrachten wieder eine Informationsquelle alsorete wahrscheinlichkeits Zufallsvariable x die Zeichen i aus
21:11 unserem Sigma haben jeweils Wahscheinlichkeit PI und wir wollen nur mit 0 1 codieren ja also für die Zeichen aus Sigma haben wir nur Zeichen Ketten
21:22 über 01 zur Verfügung Frage ist wie können wir Sigma ohne informations kutieren so dass die erwartete Länge der Ausgabe
21:32 möglichst klein ist komprimiert formal also wir ordnen jedem Zeichen I a Sigma ein codwort Z zu und
21:44 das ist jetzt weil wir eben 01 bewegen wollen aus 01 Sternchen hat ni Zeichen und das soll jetzt also für Sigma so passieren dass diese mittlere
21:56 cotwortlänge möglich klein ist was die mittlere kotwortlänge Bezeichnung n wenn wir nzeichen haben das ist nichts anderes als Summe i aus Sigma
22:08 Wahrscheinlichkeit für i mal Länge von PI so wir schauen jetzt erstmal codierungsbäume an also wir codieren binär unser sigσma ist 1 bis n und wir
22:23 wollen präfixcods auf einer späteren Folie steht das auch noch mal genau was damit gemeint ist als sollen CoDs wo der Code von einem Element aus σma nicht als
22:33 Präfix des Codes eines anderen Element V σma ähm so ein codierungsbaum für σma und C ist ein gerichteter binärer Baum der folgendermaßen aussieht jede Kante
22:48 ist mit 0 oder 1 annotiert ausgehend von einem Knoten haben wir immer höchstens eine Kante mit ull und höchstens eine Kante mit ein annotiert und die Blätter
23:01 entsprechen gerade den Elementen aus σma und der CoD soll jetzt so bestimmt sein dass er gerade der 01 Folge entspricht die auf dem Weg von der Wurzel zu dem
23:16 platt entsprechenden platt steht also hier haben wir als Elemente von σma a c d e f g h und das hier ist jetzt so ein codierungsbau und das kann man so lesen
23:29 die Kodierung von C ist wir gehen von der Wurzel durch den Baum nach C und sammeln die Nullen und Einsen die da an den Kanten annotiert sind auf also 0 10
23:41 WD der Code für C ja das hier ist jetzt definitiv ein Baum der unsere Forderung erfüllt binärer Baum jede Kante hat ist mit 0 oder 1 codiert und für jeden
23:53 Knoten haben die maximal zwei ausführenden Kanten auch nicht beide Null oder nicht beide 1 und hier weiteres ja B hat den Code
24:07 001 e hat 1 A hat den C wenn wir das so definieren dann gibt's einen direkten Zusammenhang zwischen der Codierung und dem was hier
24:21 den Blättern gehört und dem zugehörigen wir bezeichnen die Tiefe eines Knotens in einem T mit DT von V das ist NS anderes als die Anzahl der Kanten auf
24:32 demem kürzesten Weg von der Wurzel zu dem Knoten okay und wir interessieren uns ja für die mittlere
24:41 codelänge und die soll möglichst kurz sein also jetzt für hier so einen codierungsbaum der eben zum Alphabet Sigma gehört wo die Elemente i
24:51 Wahrscheinlichkeit PI haben und codwortlänge ni gilt die mittlere codwort Länge n Dach Elemente ist nichts anderes als die Summe i aus σma
25:04 Wahrscheinlichkeit von i mal kurwort Länge von i also ni und das entspricht ja hier nichts anderem als
25:13 der Tiefe des Knotens zu i im Baum heißt ist nichts anderes als die Summe alsoagen die Elemente aus Sigma als Knoten im Baum aufgefasst das
25:26 sind ja gerade die plät ja Summe über die V aus σma Wahrscheinlichkeit von V Tiefe von V okay gucken wir uns das hier noch mal
25:37 für das Beispiel an also unser Sigma ist a b c d e FG a das sind acht Elemente die wscheinlichkeit eines jedens ist ein AEL haben wir mittlere codwort Länge 3
25:50 alle kurodz haben länge 3 also ist auch dielere das ist jetzt nicht selbstverständlich ja dass man wenn man so CoD aufstellt mit entsprechendem
26:00 codierungsbaum kodwortlänge für alle gleich ist bzw mitlere K genauicht m natürlich klar bei so einem Baum dass
26:12 ich mit jedem zusätzlichen bit dass wir zur Verfügung stellen die Größe des darstellbaren Sigma verdoppelt ja einfach ein Bit mehr heißt wir können im
26:23 Baum um eins tiefer gehen das heißt das kommt eine Schicht hinzu bei so ein binären Baum können da gerade noch mal so viele hinzukommen das heißt wie wir
26:35 hier plätter haben das heißt Größe verdoppelt sich und man braucht dann natürlich für ein Alphabet mit Wörtern gleicher Länge durch den gleicher Länge
26:44 zu codieren gerade Log größes Alphabet okay jetzt Präfix kurz das Wort habe ich eben schon in den Mund genommen bei kurodz mit variabler Länge erstmal
26:57 bei den kurods die wir gerade betrachtet haben ist klar dass das präfixcode sind sie können wenn die Kodierung von je zwei Elementen verschieden ist wir
27:07 können dann nicht die Situation haben dass der Code des einen Präfixes Code des anderen ist aber wie ich eben schon gesagt habe wäre auch denkbar dass man
27:16 auf so ein codierungsbaum kommt das wird auch gleich passieren äh wo die Blätter nicht alle in derselben Ebene hängen ja der also so ausgeglichen ist
27:25 äh weil die Länge des cotes eines plattes ja gerade dem Weg von der Wurzel zu dem platt entspricht heißt es also wenn Sie ein Baum haben wo die Blätter
27:38 auf unterschiedlichen Ebenen hängen dass sie auch unterschiedliche cotwortlängen haben bei unterschiedlichen codwortlängen wäre jetzt mal prinzipiell
27:47 ja möglich dass der Code so ein kürzerer Code eines Elementes Präfix von dem Code eines anderen Element sowas will man nicht haben ja denn wenn Sie das hätten
27:59 und würden dann sozusagen kurz aneinander also Zeichen als String übertragen eine Folge von Zeichen als dring übertragen und
28:09 einfach die kurods aneinander hängen dann könnten sie einfach nicht entscheiden wann ist der Code der Kodierung eines Zeichens ist zu zu Ende
28:19 und wann fängt der nächste dann bräuchten s so trendzeichen also kurz bei kurz mit variabler Länge muss man wissen wann neu
28:27 das codwort beginnt und bei einem präfixcode fordert man eben dass kein codwort Anfang eines anderen codworts ist also man benötigt keine trendzeichen
28:39 zwischen einzelnen Codes weil das kann einfach nicht sein also sie wissen einfach wenn wissen welche Codes vkommen wissen Sie wann zu Ende ist ja WN der
28:47 nächste weil das eine nicht Präfix von M anderen sein kann und man kann jetzt jeden präfixcode also so ein Baum darstellen das ist offensichtlich dass
28:56 auch wenn die Bäume nicht ausgeglichen sind also die [Musik] Blätter auf verschiedenen Ebenen hängen
29:04 die auf die Art nicht kurz kriegen können wo das einen Präfix okay schauen wir uns mal konkrete Beispiele an ein Beispiel für eine Codierung ist Morse
29:14 morse alphabet das hat variable Länge also die Buchstaben das unseres Alphabets die sind eben codiert es gibt erstmal zwei Zeichen
29:26 kurzes Signal langes Signal ja also a hat kurz lang die Signale kommen in gleichem Abstand dann würden sie also hier nicht unterscheiden können wenn
29:37 kurz lang kommt ist das jetzt die Codierung von A oder ist das die Codierung von E gefolgt von T B hat nur kurz t hat nur lang a hat kurz lang ja
29:48 können sie nicht unterscheiden das heißt also sie brauchen hier noch ein trendzeichen was beim Mors Alphabet dann einfach eine längere Pause ist
29:58 dritte Zeichen so also moruse Alphabet ist jetzt ein Zeichen für eines Kodierung die nicht präfriix ist nach ihrer Sprechweise und
30:13 sowas würde man aber ganz gerne so jetzt erstmal ist ohne das was beweisen in dem Zusammenhang auch das chche quellcodierungstheorem interessant also
30:26 kurzviabler schauen wir ab jetzt mal an ähm dann ist es natürlich nützlich häufige Zeichen mit kürzeren Codes zu codieren wir wollen ja die mittlere
30:38 codelänge äh klein halten das heißt also wenn die häufigen kurz sind und die nicht so häufigen dann lang sein dürfen dann
30:47 können wir erzwingen dass die mittlere kotwortlänge kürzer wird ja und Shanon quellcodierungstheorem sagt wenn Sie also eine diskrete endliche
30:57 Zufallsvariable x haben mit Entropie h von X wie wir es eben definiert haben und wir hätten also einen präfixcode für X
31:06 mit einem codalphabet das aus großd Zeichen besteht dann gilt dass die minimale mittlere kotwortlänge n ob Dach größer gleich Entropie von X durch
31:22 logaritmus D und kleiner gleich Entropie von X durch logarimus D + 1 mittlere cotwortlänge liegt zwischen h von X dur Log D und H von X dur Log D + 1 wie
31:35 gesagt beweisen okay so jetzt ein erster erstes Beispiel einer ganz meinen Augen ganz witzigen Kodierung mit variabler
31:46 codwortlänge die präfixcode ist und die so ist dass man diese Idee häufige häufig vorkommende Zeichen
31:58 sollen ähm kürzere Codes haben als selten vorkommen Zeichen halt umsetzt auf eine bestimmte Art Frage ist ob das so umgesetzt ist dass man wirklich
32:09 beweisen kann dass die mittlere kotwortlänge minimal ist das kann man das nehme ich jetzt schon vorweg hierfür nicht beweisen es ist nicht der Fall
32:16 aber trotzdem ist eine schöne Kodierung die war später noch mal aufgreifen also chenen fanokodierung wir haben hier unsere Elemente also das nullte das
32:25 erste und so weiter und die Wahrscheinlichkeiten der Elemente wir sind also jetzt hier durchnummeriert entsprechend iher
32:34 Wahrscheinlichkeit das erste ist das wahrscheinlichste zweite zweitwahrscheinlichste und so weiter ja also die Wahrscheinlichkeit so wie wir
32:42 hier durchnummeriert haben nimmt von oben nach unten ab und die Frage ist welche Codeworte über 01
32:50 ordnen wir hier den Elementen dem Null dem n0 ersten zweiten und so weiter zu sass eben das nach unten halt immer länger wird oder eben die sehr
32:58 wahrscheinlich in möglichst kurz kodiert ja ich gebe als erstes Zeichen den oberen vier eine Null und den
33:08 anderen alle eine ein und dann teile ich hier oben noch mal durch und gebe als zweites Zeichen den ersten beiden Null und den zweiten
33:19 zweiten ein und so geht das irgendwie weiter Frage ist was ist das jetzt hier für eine Vorgehensweise geh wir noch mal eins zurück evorgehensweise ist jetzt
33:28 folgendes ich gucke mir die Wahrscheinlichkeiten an und ich gucke mir von oben nach unten an wenn ich aufsummiere wann komme ich das erste Mal
33:36 auf oder über Wahrscheinlichkeit einhb da mache ich ein Strich also hier ist die oberen vier sind ungefähr gleich wahrscheinlich wie die unteren vier also
33:46 wenn ich die vier Wahrscheinlichkeiten aufsummiere komme ich hier gerade auf über etwas über einhb ein bisschen über einhalb das heißt also die oberen vier
33:57 sind ungefähr gleich wahrscheinlich wie die unteren vier oder anders ausgedrückt die oberen vier auf Wahrscheinlichkeiten aufsummiert minus die unteren vier
34:05 Wahrscheinlichkeiten aufsummiert ist am dem Betrage nach am kleinsten unter allen Möglichkeiten wie ich hier sozusagen Unterteile ne also
34:14 ich unterteile da wo die Wahrscheinlichkeit der ober der Unterteilung aufsummiert minus die Wahrscheinlichkeit der unter der
34:24 Unterteilung aufsummierten äh dem Betrage nach minimal ist und dann gebe ich einfach den oberen als erstes Zeichen des codeworts entsprechend
34:33 codwort ull und den anderen da ein und in genau der gleichen Weise mache ich weiter ja das heißt also ich gucke mir jetzt die oberen vier an wir haben
34:40 zusammen ungefähr Wahrscheinlichkeit ein halb guck nach wo muss ich unterteilen dass die Differenz der Wahrscheinlichkeiten von dem oberen und
34:47 dem unteren dem Betrage nach minimal wird also wann bin ich da so sag erstm von oben betrachtet über ein Viertel oder bei ein Viertel ist ja gerade nach
34:56 den ersten zwei Elementen und da gebe ich einfach als zweites Zeichen der Codierung eine Null und bei den weniger wahrscheinliches
35:06 zweites Zeichen der Codierung ein und so mache ich weiter was dann aut automatisch dazu führt dass das erste Krieg als drittes Zeichen Null kriegt
35:15 und das zweite als drittes Zeichen ein und damit bin ich auch schon bei den oberen fertig ja die codwörte werden nicht mehr länger in zweiten zwei muss
35:24 ich natürlich auch noch mal gucken noch mal unterteilen die kriegen auch codwort der Länge 3 ja das wahrscheinlichere als drittes Zeichen 0 das
35:31 unwahrscheinlichere als drittes Zeichen 1 jetzt bin ich da oben für die ersten vier fertig und bei den unteren mache ich halt weiter ja so also ich Teile
35:41 wieder auf gucke jetzt weiter wann bin ich hier erstmal über ein Viertel die kriegen entsprechend Elemente kriegen als
35:47 zweiten zweites Zeichen in der Kodierung der Null und die anderen ein und so geht das weiter ja und dann sehe ich hier schon bei den weniger wahrscheinlichen
35:58 würde ich also dann kodworte der länge 4 bekommen ja also wenn jetzt so immer weiter macht kriegt man also für die nächsten vier codworte der Länge vi und
36:09 dann gibt's Codeworte der länge 5 und so weiter also je unwahrscheinlicher die werden desto länger werden die hier ist das noch mal als Algorithmus
36:16 aufgeschrieben also den Fano Kodierung ich habe meine zeichenliste Z Zeichen Z1 bis ZK mit Wahrscheinlichkeiten ein bis PK und was
36:28 ich haben will wollen sind im codeewte C1 bis CK ähm wenn ich nur noch ein Zeichen habe gebe ich dem entsprechenden füge ich an die
36:40 entsprechende Codierung in an und dann geht's eben folgendermaßen ich habe also meine äh Element aus z immer vorliegen
36:50 sortiert nach Wahrscheinlichkeiten absteigender Richtung und ich trenne im immer auf in Z1 und Z2 so dass die Wahrscheinlichkeiten der Elemente aus Z1
37:05 aufsummiert minus Wahrscheinlichkeiten der Elemente aus Z2 aufsummiert den betrage nach minimal wird und ich füge also dann den ersten vorne eine Null an
37:15 und den zweiten vorne eine ein an und mach dann mit dem Rest weiter ja okay und hier kriege ich jetzt natürlich so einen Baum wo die Blätter
37:28 nicht alle auf derselben Ebene liegen das sieht zwar jetzt hier so aus weil der blöd hingemalt ist aber der ist natürlich stark unbalanciert da nach
37:36 rechts geht wird das immer schwerer also hier die Blätter die hängen natürlich tiefer als diese Blätter hier vorne also wir haben ja von der Wurzel zu dem
37:45 entsprechenden K platt gerade kriegen wir das CoD wenn wir den Weg entlang gehen das codwort hier 00 für das nullte Element und so weiter und hier für das
37:55 vierte für sechste Element 10 1 0 ne werden nach rechts immer länger okay wir haben das ganze ja gemacht weil wir eine Codierung haben
38:07 wollen wo die mittlere codwlänge möglichst kurz ist nach der Art und Weise wie das hier vorgenommen wird bei der shenonfan Codierung ist es natürlich
38:17 so dass die mittlere codwortlänge kurz wird weil die sehr wahrscheinlichen ähm Zeichen kurz zu kurz kriegen aber man kann eben nicht beweisen dass shenon
38:29 Fano Codierung bezüglich Minimierung der mittleren codewortlänge optimal ist weil das einfach nicht der Fall ist ist gut aber
38:38 es nicht tut das also geh optimiert mit dem Ziel die schenenfah Codierung aber wir nicht optimal es gibt aber Codierungen wo die mittlere codwortlänge
38:50 minimal wird hafmancodierung etwa die wir gleich betrachten das heißt also Kodierung ist schon aus dem Grund dann vielleicht nicht so populär wie hafman
39:00 okay hafman Codierung wie funktioniert die haben ja wieder Elemente eine Sigma mit
39:11 Wahrscheinlichkeiten ja sechs Stück sind jetzt wieder nach der Wahrscheinlichkeit sortiert wir wollen jetzt also Codierung von C Codierung von A Codierung von E
39:21 und so weiter und das soll jetzt wieder so sein dass die sehr wahrscheinlichen die scheinlicheren eher kürzere kurz hab als die unwahrscheinlichen so hier wird
39:30 jetzt folgendermaßen vorgegangen wir betrachten uns die zwei unwahrscheinlichsten und passen die jetzt wieder auf als Kinder eines Knoten
39:40 im kodierungsbaums wobei ja der untere unwahrscheinlichere wir haben die
39:48 gleiche Wahrscheinlichkeit da ist das dann beliebig aberb ich festgelegt dass man eins kriegt als letztes Zeichen und das da
39:57 drüber eine Null und dann fassen wir die beiden zusammen füren neuen Elternknoten ein den Wahrscheinlichkeit gerad Summe wo die zugehörige Wahrscheinlichkeit
40:08 gerade Summe dieser beiden Wahrscheinlichkeit ist so und dann vergessen wir die zwei und machen weiter mit den Knoten die wir jetzt haben und
40:17 den entsprechenden Wahrscheinlichkeiten jetzt gucken wir wieder was sind die zwei unwahrscheinlichsten das ist dieses und das sind
40:26 dieser neuentststandene Knoten und der Knoten zu e die fassen wir wieder zusammen geben den einen Elternknoten der
40:35 unwahrscheinlichere kriegt eine Eins davor gehängt der wahrscheinlichere eine Null wir führen neuen Elternknoten ein den Wahrscheinlichkeit Summe der
40:45 Wahrscheinlichkeiten der beiden gerade betrachteten Noten und so machen wir weiter dann wäre also jetzt die nächste Frage was sind die nächsten zwei
40:54 unwahrscheinlichsten was sind die be heißt also die beiden werden zusammengefasst Elternknoten kriegt als Wahrscheinlichkeit die Summe der beiden
41:04 einzelwahrscheinlichkeiten und auch wieder das unwahrscheinlichere kriegt eine ein das wahrscheinlichere ull dann wieder die zwei
41:12 unwahrscheinlichsten das ist jetzt der Knoten und der Knoten dann zusammengefasst die Summe der Wahrscheinlichkeiten ist 0,6 für den
41:22 unwahrscheinlicheren fügen wir eine ein davor für den wahrscheinlicheren null vor und jetzt das wieder dasselbe und dann werden wir fertig und hier wird
41:32 jetzt dem eine Null gegeben und dem eine ein weil der obere weniger wahrscheinlich ist als der untere hier haben wir jetzt ganz genauso
41:41 wieder einen codierungsbaum wo wenn man von der Wurzel zum platt geht dann die Annotation an den Kanten gerade die Kodierung ergibt ne also für C kriegen
41:51 wir 0 1 1 1 ja während wir für D einfach nur eins kriegen also das wahrscheinlichste hat hier ein deutlich kürzeres kwort als diese
42:04 unwahrscheinlichen noch mal B hat z.B das codwort 1 e hat das codwort 0 1 0 sehe das codwort 0 1 und der
42:17 Algorithmus dazu also wir haben unsere Zeichen unsere entzeichen mit Wahrscheinlichkeiten P1 bis PN und wir bauen also auf den Baum zum hfman Code
42:28 dafür betrachten wir so eine Menge Q die zu eben den Elementen oder Zeichen gehört das ist also wir fügen alle Zeichen aus Q als Blätter in den Baum
42:37 ein und dann für i = 1 bis n-1 erzeugen wir also in dem Knoten neue in dem Baum neue Elternknoten also wir erzeugen neuen Knoten Z im Baum indem wir
42:49 folgendermaßen borgehen von den noch verbleibenden Elementen aus Q extrahieren wir das un wahrscheinlichste Element x ja hat wahrscheinlich halt px
43:00 und äh sagen das soll linker Nachfolger von dem neu einzuführenden Knoten Z sein und dann extrahieren wir das nächste unwahrscheinlichste Element
43:11 äh und machen das zum rechten Nachfolger von dem neuen Knoten dem neuen Knoten geben wir als Wahrscheinlichkeit gerade Summe der Wahrscheinlichkeiten dieser
43:20 beiden Knoten die wir gerade ähm bestimmt haben äh fügen den neullen Knoten ein und
43:29 äh fertig und so geht das immer weiter und dann ist das einfach ein Baum der da draus entstanden ist mit linker Nachfolger rechter Nachfolger und der
43:39 linke kriegt immer eine Eins und der rechte kriegt immer eine Null ja das steht hier gar nicht dabei aber so wäre dann eben die Codierung
43:48 äh deshalb mal aufgepasst der Baum hier sieht jetzt nicht so aus wie wie der Baum bespinnt wird nach dem Algorithmus weil der da
44:02 oben der müsste eigentlich hier unten hin sagen als der wahrscheinlichere dann nicht rechter sondern linker Nachfolger von dem
44:14 als weniger wahrscheinliche nicht rechter sondern linkerg also nach rechts geht's immer mit null und nach links immer mit ein
44:22 okay so und für den Code kann man jetzt beweisen dass die mittlere cotwortlänge minimal ist und das machen wir jetzt also auch also der hafman Algorithmus
44:33 berechnet ein codierungsbaum wo rauskommt dass die mittlere kotwortlänge minimal ist und um das zu beweisen brauchen wir
44:44 so ein Lemmer das lautet folgendermaßen wir haben unsere Zeichen oder unser Alphabet Sigma mit n Elementen und Wahrscheinlichkeiten B1 bis PN und X und
44:56 Y aus σma sein jetzt die zwei unwahrscheinlichsten Zeichen oder wenn wir jetzt eben mehrere Zeichen haben die gleich unwahrscheinlich sind eben zwei
45:06 beliebige da draus ja X und Y X und Y eine beliebige Wahl für die zwei unwahrscheinlichsten Zeichen dann gilt es gibt einen codierungsbaum t für σma
45:17 und P mit minimaler mittlere kotwortlänge so dass X und Y denselben Elternknoten haben ja ähm das ist wie gesagt ein hilfslemmer und das weist
45:29 jetzt schon stark da drauf hin wie dann der Beweis ähm unseres Satzes dass der hafman Algorithmus minimale mittlere
45:40 kurutwortlänge erzeugt wie der Beweis geht nämlich das weiß natürlich auf einen induktionsbeweis hin ne wir gucken uns die Bäume an und gucken dann die
45:48 zwei unwahrscheinlichsten an und dann lassen wir die mal weg und Induktionsvoraussetzung gilt auf den Baum davor und dann müssen wir nur
45:55 gucken wie kriegen wir die zwei untersten da wieder rein ne also ähm also jetzt die Beweis zu diesem Lemmer dass diese beiden
46:04 ähm un oder zwei unwahrscheinlichste ähm in so einem dass es für die das es insgesamt einen einen kodierungsbaum mit minimaler
46:16 kutwortlänge gibt wo die zwei unwahrscheinlichsten denelbenen haben äh betrachten wir einfach mal einen beliebigen
46:24 kodierungsbaum mit minimaler mittlerer kurzwortlänge und da gucken wir also X und Y an so zwei unwahrscheinlichste und oBdA ist die Tiefe von X größer gleich
46:36 der Tiefe von Y die beiden haben entweder gleiche Tiefe oder wenn Sie verschiedene Tiefe haben dann soll eben x dasjenige sein was tiefer hängt und Z
46:46 sei jetzt mal der Elternknoten von X in T STR und wenn das noch nicht so ist in dem T STR wie wir es haben wollen dann hängt das Y also irgendwo hier
46:58 anders ne also nicht unter demselben direkt unter dem selben Knoten wie das X so jetzt erster Fall der vorgängerknoten
47:10 von X hat nur x als nach kommmen dann könnte man natürlich das Z auch vergessen und das X sozusagen direkt unter den vorgängerknoten von Z
47:23 hängen das wä dann Raum mit kleinerer mittlerer kotwortlänge weil wir für X automatisch eine kürzere kotwortlänge haben was ein wiederspr Widerspruch zur
47:34 Optimalität von T Strich ist Widerspruch zu der Annahme dass T Strich ein kodierungsbau mit minimaler mittlerer kodwandlänge ist das heißt eigentlich
47:43 kann das nicht sein ja der unmittelbare Vorgänger von Z nur ein nach von X nur ein nach hab also mehr als zwei Nachkommen
47:54 ähm und wir betrachten mal so ein nachffahren von dem Z der maximale Tiefe hat maximal tief hängt das W
48:05 ähm weil t Strich optimal ist müsste also dann die Wahrscheinlichkeit von dem auch kleiner gleich der Wahrscheinlichkeit von PX sein
48:16 ähm andererseits ist ja px1 mit minimaler Wahrscheinlichkeit das heißt also das PW muss g=ich PX sein
48:26 und dann kann ich ja auch das X mit dem W tauschen und kriegt dann einen anderen Fall den wir als nächstes machen nämlich
48:34 den Fall Z hat genau zwei Nachkommen bei der andere Nachfolge na andere Nachfahre des unmittelbaren Vorgängers von X dieses Q
48:47 hier so und was wir einfach wollen ist dass Y mit dem Q tauschen können ja denn wir wollen ja er ichen dass aus dem T Strich durch eine einfache Vertauschung
48:59 einen Baum bekommen der bezüglich mittlerer kotwortlänge genauso ist und wo X und Y unter genau demselben Knoten
49:08 hängen wollen Q mit Y tauschen wenn u und Y beide gleiche Höhe haben geht das ja auch
49:18 problemlos das einfach machen wenn jetzt das Q tiefer wäre als y müsste aber wegen der Optimalität PQ = PY sein und dann können
49:31 wir auch tauschen das auch okay das heißt also das können wir auf jeden Fall äh bewerkstelligen ähm dass
49:42 wir zu so einem alpab B Sigma mit Wahrscheinlichkeiten P1 bis PN und zwei unwahrscheinlichsten Zeichen X und Y einen optimalen codierungsbau also
49:55 codierungsbaum mit minimaler codwortlänge betrachten bei denen X und Y genau denselben Elternknoten das können wir immer voraussetzen also wir
50:04 können können sozusagen immer zu sowas kommen ne also zu einem beliebigen optimalen kodierungsbaum gibt's dann auch so ein und das von benutzen wir
50:12 jetzt um per Induktion über die Anzahl der Zeichen unseres Alphabets zu beweisen dass der haftmancode optimal ist
50:21 ja die mittlere kotwortlänge minimal ist also der entsprech codierungsbaum genauso ist wie die gerade betrachtet haben also Induktion über die Anzahl der
50:31 Zeichen in sigσma am Anfang WN man nur ein Zeichen haben ist das trivialerweise erfüllt mittlere kodwortlänge gerade dieortlänge die ein
50:41 Zeichens okay das heißt aber nehmen jetzt mal an dass der haffenalgorithmus ein kodierungsbaum zum kodierungsbaum gehört
50:51 wo gilt die mittlere codwortlänge ist min mal wenn immer σma kleiner gleich n ist ja für alle möglichen
51:04 Wahrscheinlichkeiten Elemente und jetzt gucken wir halt so ein sigσma mit n + 1 Zeichen Wahrscheinlichkeiten P1 bis PN + 1 diesen Term hier müssen wir betrachten
51:17 mittlere codwortlänge ist ja nichts anderes als Summe über die V aus Sigma Wahrscheinlichkeit von V mal von V ist das was wir minimieren wollen das nennen
51:28 wir mal F F von T wir machen einen widerspruchsbeweis wenn wir annehmen das wäre nicht so dass der
51:38 kodierungsbaum zum hafman Code hier für optimal ist dann führen wir das zum Widers also mit Th Huf bezeichnen wir den
51:48 hafmenbaum für unser Sigma mit den n + 1 Elementen und den Wahrscheinlichkeiten P und wir betrachten andererseits ein optimalen Baum ja
51:58 topt zu demselben σ P ein kodierungsbaum mit bessere mittlere kodierungslänge wir nehmen an dass F die mittlere
52:09 kodierungslänge für das topt ist echt kleiner als das F für das TUF und X und Y seien also jetzt diese zwei Zeichen die im hafmann Algorithmus zu zuerst
52:19 zusammengefasst werden das sind also zwei der unwahrscheinlichsten ja äh mit dem vorbereiteten lämer wissen wir wir können jetzt einfach annehmen dass unser
52:30 topt ja das ist ja ein kodierungsbaum mit minimaler mittlerer kotwurlänge gerade so aussieht dass diese X und Y den gleichen Elternknoten haben das
52:41 heißt also wenn wir die beiden Bäume topt und thuf nebeneinander tun dann gilt bei TH Huf das X und Y denselben Elternknoten haben weil X und Y gerade
52:51 die zwei ersten sind die zusammengefasst werden und bei opt aufgrund unseres lemmers ja dann können wir jetzt auch schon den entscheidenden Schritt machen
53:02 nämlich mal nehmen die zweimal weg und gucken dann mal nah an wie ist denn die mittlere codwortlänge der entsprechenden Bäume t opt und T Huf
53:13 und dann gucken wir und was passiert mit X und Y also Strich sei σma ohne X und Y zusammen mit äh dem Zeichen das sozusagen zu dem Elternknoten von x und
53:27 y gehört in in T STR Huf und das hat natürlich Wahrscheinlichkeit PX + PY so und T opt und T HU sind also die
53:41 entsprechenden Bäume die sich aus topt und T geben wenn ich X und Y weglasse m also in beiden nenne ich sozusagen den
53:53 gemeinsamen Elternknoten von x und Y Z ne also es ist wirklich bei beiden derselbe den nenne ich so ähm thuf ist dann aber auch wieder ein
54:05 Haman Baum für die Instanz Instanz y Strich ja wenn ich mir einfach angucke y STR das ist ja das Y ohne XY also ohne klein x und Klein y und zusätzlich kommt
54:17 das Z hinzu und wenn ich dazu den Baum aufbauen würde äh dann würde ich ich sag mal bei ähm gleicher Wahlen der
54:26 unwahrscheinlichsten Elemente wenn ich da eine Auswahl habe gerade wieder t strichhuf bekommen für Sie ich und genauso ist t STR opt ein
54:38 codierungsbaum für strich mit den neuen Wahrscheinlichkeiten ja okay und jetzt gucke ich mir da die mittlere
54:47 kodwortlänge an bei T Huf ist das die Mittler cowortlänge von t Huf min Tiefe von X in T Huf mal Wahrscheinlichkeit von x und
55:03 Tiefe von TH Huf von Y TH mal Wahrscheinlichkeit von Y ja also die zwei gehen raus und stattdessen kommt das Z dazu also die Tiefe von Z in T STR
55:18 Huf mal der Wahrscheinlichkeit von Z und in T ist das genauso jetzt ist dummerweise so dass die entscheidenden zwei Berechnungsschritte hier nicht auf
55:28 der Folie stehen die sind aber offensichtlich was ist denn mit dem T DT HU von Z mal PZ ja das äh Z hat in dem Baum gerade dieselbe
55:44 Tiefe wie X oder Y -1 ja also hier könnte ich reinschreiben stattdessen gleich dt H x - 1 mal PZ und das PZ ist gerade PX
56:01 + PY und wenn man also hier sozusagen DTX Huf DT Huf von X mal P von X + P von Y einsetzt und das ganze ausrechnet und
56:17 ausnutzt dass DTH von x= DTH von Y ist dann kommt gerade raus das ist die mittlere Länge von T Huf - P von X - P von
56:28 Y und bei T Strich ob geht das ganz genauso da kommt also dann genauso raus das ist die mittlere kotwortlänge von T - PX -
56:38 PY und damit haben wir unseren ähm ja Widerspruch das T STR opt wä also dann auch der besserer codierungsbaum für σ STR als T Huf aber nach t nach
56:55 Induktionsvoraussetzung ist thu optimal okay ja gut jetzt können wir auch noch ein bisschen über Nachteile von Hoffmann Codierung sprechen
57:06 haben unterschiedliche codwortlängen das führt natürlich zu unterschiedlichen Bitraten und eben bei der Dekodierung zu
57:16 Verzögerung das ist jetzt was was also generell gegen das spricht was man eigentlich erzielen will wenn man mittlere die mittlere kurwortlänge
57:27 minimieren will wenn man mittlere kurutwortlänge minimieren will und eine Situation hat wo die Wahrscheinlichkeiten der Zeichen stark
57:33 differgieren dann kommt man automatisch dazu dass man sehr unterschiedlich kotwen len hat also tut sich dann immer derselbe Nachteil auf
57:44 ähm und insgesamt ist natürlich auch Datenkompression etwas was auch wieder Nachteile mit sich bringt also Datenkompression heißt ja ich reduziere
57:55 wenn ich sozusagen verlustfrei kodieren will aber möglichst mit möglichst kurzer Länge dann reduziere ich die Redundanz das reduziert natürlich auf der anderen
58:06 Seite auch die Fehleranfälligkeit wenn wir später gucken wie kann man die fehleranfändlichkeit für die Übertragung
58:14 reduzieren da würde man wieder Redundanz einführen das ist sind einfach konträre Ziele möglichst kurz kodieren andererseits fehleranfällig
58:26 verringern und beim hafman Code wird natürlich vorausgesetzt dass ich weiß wie die Wahrscheinlichkeiten der einzelnen Zeichen sind gibt andere
58:35 Codierungsverfahren wo man so ein a priori wissen nicht voraussetzt etwa l okay so jetzt wollen wir lauflängenkodierung betrachten und dazu
58:49 folgendes Szenario wir betrachten die Übertragung von ähm dieser Folie übers Faxgerät ja ähm da werden einfach weiße Blätter mit
59:04 schwarzen Pixeln übertragen ne also einfach äh kann das als ein Bild auffassen mit weißen und schwarzen Bildelementen und natürlich ist
59:17 üblicherweise die Anzahl der weißen Pixel Ex deutlich größer als die Anzahl der schwarzen Pixel das ist im allgemeinen natürlich nicht
59:28 [Musik] voneinander unabhängig ja wo schwarze und wo weiße Pixel sind bei einem richtigen Bild sage ich mal wir nehmen
59:38 jetzt einfach der einfache teilber an das ist aber unwahrscheinlich unabhängig also das sind einfach was wir übertragen wollen
59:46 sind einfach weiße Blätter mit schwarzen Pixeln drauf wenn man z.B 15%zentigen schwerzungsgrad hat ergäbe sich als intropie
59:57 ähm Wahrscheinlichkeit für minus Wahrscheinlichkeit für Schwarz mal Logarithmus Wahrscheinlichkeit für Schwarz minus Wahrscheinlichkeit für nee
1:00:06 umgekehrt Wahrscheinlichkeit für weiß minus Wahrscheinlichkeit für weiß mal logarithmuswahrscheinlichkeit für weiß minus Wahrscheinlichkeit für Schwarz
1:00:13 minus Logarithmus für Wahrscheinlichkeit für Schwarz äh gleich ja da kommt hier ungefähr 0,61 raus und bei einer äh
1:00:25 Codierung würde man also so eine Art mittlere codwortlänge erwarten jetzt eben die Frage wie ist eine platzsparende
1:00:35 Codierung von dem Alphabet das nur zwei Zeichen hat überhaupt möglich ja wie kann man das machen und da gibt's jetzt folgende
1:00:45 Idee Idee sogenannte block codes zu verwenden also es werden immer kzeichen als Block zusammen befasst und dieser Block dann
1:00:56 codiert ja also Beispiel wir fassen äh immer zwei Zeichen zu eine Block zusammen da hätten wir jetzt hier bei es gibt nur weiß und schwarz weiß weiß weiß
1:01:09 schwarz Schwarzweiß und schwachz schwarz als die Möglichkeiten ja möglichen Zeichen sozusagen möglichen Blöcke also möglichen Zeichen bei dieser Block
1:01:19 Sichtweise und ähm ja das könnte man z.B jetzt mit hafman codieren ne also wenn man sagt na ja gut also weiß weiß hat Wahrscheinlichkeit ein halb
1:01:31 weiß schwachz schwarzweiß schwarz schwarz weiß schwarz schwarzweiß jeweils zwe schwarz schwarz einehel dann bekämen man
1:01:40 bei haftman diese codierungus mit codworten unterschiedlicher Länge und optimaler mittlerer
1:01:51 kotwort jetzt könnte man auch folgendes machen ähm man äh passt in Blöcke unterschiedlicher Länge zusammen und
1:02:05 codiert gar nicht die Blöcke sondern die Abstände oder man ja codiert die Blöcke aber man fasst sie auf als Abstände und zwar es ist ja weiß deutlich öfter als
1:02:18 schwachz das heißt also so ein so ein äh so eine Übertragung könnte so aussehen äh weiß weiß weiß schwarz weiß weiß weiß weiß weiß schwarz schwarz weiß weiß weiß
1:02:30 wei weiß also oft weiß wenig schwarz und das war einfach sagt na ja gut dann gucke ich mir einfach die Abstände zwischen schwarz zwei aufeinander
1:02:39 folgende schwarze an also hier wäre das erstmal kommen drei weiße bevor das erste schwarz kommt also das erste sozusagen
1:02:50 meines ja kurods hierzu ist eine dre dann zwischen dem ersten schwarzen im zweiten schwarz kommen zwei weiße Nexus kommt also zwei dann zwischen dem
1:03:02 zweiten und dritten schwachz kommt kein weißes nächste ist also null und so weiter ne also für diese Folge von weiß und schwachz hätte ich 320
1:03:13 416 einfach die Abstände zwischen den schwarzen hintereinander ge schrieben und das könnte ich jetzt binär codieren ja einfach ich nehme als
1:03:25 Codierung von dem hier eine geeignete binärcodierung der Abstände zwischen den schwarzen erfolgen ähm ja das die Abstände können im
1:03:40 Prinzip beliebige Zahlen aus n sein ja natürlich je länger wie größer das Element aus N ist desto weniger wahrscheinlich ist ab einer gewissen
1:03:49 Größe dass man den Abstand noch ja ja ne nee das macht wir genauso wie am Anfang ne also am Anfang fängt ja auch nicht mit dem schwarz an also man tut die
1:04:00 Anzahl der weißen da hinten dran ne wie am Anfang auch und dann eine Null ne und dann ach so
1:04:10 ähm wie macht man das äh nee ich mach dann eine Null dran genau wie am Anfang auch ne wenn es mit Schwarz anfängt dann wäd das erstes eine
1:04:21 Null und dann Abstand zwischen dem ersten und zweiten und so weiter und dann kommt noch mal der Abstand zwischen dem letzten schwachs
1:04:32 und dem Ende ja müsste ich dann hier noch eine Null dran hängen ja ja ja okay okay jetzt da haben sie
1:04:42 recht okay ja das ist dann einfach auf der Folie nicht korrekt so äh und dafür muss man jetzt für eine
1:04:53 Kodierung die in Abhängigkeiten der Wahrscheinlichkeiten eben quotwörter produziert die so sind dass die unwahrscheinlichen
1:05:03 lang und die wahrscheinlichen kurzen die Wahrscheinlichkeiten für die einzelnen Abstände wissen jetzt haben wir ja angenommen die
1:05:13 Bildpunkte sind voneinander unabhängig dann sei also PL die Wahrscheinlichkeit für einen Block aus l aufeinander folgende weiße Bildpunkte
1:05:22 wo dann am Schluss schwachzerbildpunkt kommt das heißt also das PL ist dann die Wahrscheinlichkeit für so einen String l mal W gefolgt von S und das ist
1:05:35 natürlich nichts anderes als die Wahrscheinlichkeit von W hoch l mal Wahrscheinlichkeit von S das heißt wir kriegen hier so eine
1:05:47 geometrische Verteilung wie hier und jetzt gucken wir uns das mal konkret an ja also hier haben wir die Abstände hier
1:06:00 die Wahrscheinlichkeiten und jetzt benutzen wir einfach shenon Fano um die Elemente entsprechend der Wahrscheinlichkeiten zu
1:06:10 codieren ja also für den äh gucken wier Wahrscheinlichkeiten an unterteilen wieder sozusagen die die obere äh oberen Wahrscheinlichkeiten bis
1:06:22 wir zur Wahrscheinlichkeit ein halb kommen untere Wahrscheinlichkeiten die oberen kriegen als erstes Null die unteren ein und so weiter
1:06:29 ähm und damit kann man dann verlustfrei kodieren über eben die Angabe der Längen äh Sonderbehandlung für den letzten Block erforderlich und Problem die
1:06:42 Lauflängen können beliebig lang werden wissen nicht also was der größte Abstand zwischen zwei schwachzen okay ähm jetzt mal gucken ob das sinnvoll ist
1:06:53 mit anzufangen ich hatte mir überlegt dass wir praktisch bis hierhin heute besprechen haben sie mal wieder ein bisschen
1:07:02 früher Schluss