17: Informationstheorie, Entropie, Kodierungsbäume, Lauflängenkodierung
KIT Lehre und Wissen
https://www.youtube.com/watch?v=7fh78aENNNU

Transkript (automatisch erstellt)

0:05 das neue kapitel informationstheorie das ist ein bisschen losgelöst von den übrigen kapiteln also wir werden keine referenzen auf juri maschinen oder
0:18 ähnliches haben trotzdem ist es auch ein gebiet der theoretischen informatik das wichtig ist und dass sie ansonsten nicht in ihrem
0:27 studium kennen lernen würden wenn wir das hier nicht machen würden und auch eigentlich ganz spannend fangen wir an informationstag beinhaltet oder
0:40 anwendungen in den kanal kodierung und kryptographie um die kelterung werden wir uns heute kümmern um die kanal kodierung und die
0:51 kryptografie werden sie sich der nächste woche kümmern ein bisschen zur erklärung dieser wörter quell codierung ist da um an einer
1:03 quelle die information aus sendet diese information codiert als code wörter auszusenden sodass redundanz oder irrelevanz in der informationsquelle
1:15 reduziert wird also die daten komprimiert werden oder und das ganze sollte entweder verlustfrei oder -verlust behaftet sein je nachdem was
1:28 das für eine anwendung ist wie wichtig das ist das keine kein verlust auftritt das hat eine hohe wirtschaftliche bedeutung wie sie sich das sicher denken
1:37 können also das ist sowohl für die datenübermittlung als auch die komprimierung von daten zum beispiel das mp3 datenformat ist quasi eine codierung
1:50 eine verlust- behaftet [Musik] dann gibt es die kanal codierung da geht es dann darum dass daten übertragen
1:58 werden über einen kanal und dieser kanal eventuell fehleranfällig ist ja also störungen aufweist dass die nicht wirklich 100 prozent die biz die sie
2:07 vornherein schicken in den kanal exakt so wie da hinten rauskommen aus dem kanal und dann geht es darum diese fehler zu erkennen oder gegebenenfalls
2:15 sogar zu korrigieren und das kann man machen indem man die code wörter die man da rein schickt speziell wählt zum beispiel redundanz da rein bringt ja
2:28 also statt jedes zeichen nun normal durch den kanal zu schicken könnten wir das zehnmal durch den kanal schicken und hoffen dass nicht alle zehn davon
2:35 den fehler darf der hinten rauskommen ok also da geht es um übertragung die der schutz vor übertragungsfehler durch einführen von redundanz und eventuell
2:47 auch die korrektur der fehler und das letzte ist kryptografie da geht es um sicherheit also dass diese kanäle die die informationen übertragen dass die
2:59 widerstandsfähig gemacht werden gegen unbefugtes lesen oder sogar verändern und da ist die kryptographie ist das codieren und dann gibt es noch die
3:09 krypto analyse oder die kryptologie zusammen ein eigenes themengebiet das wird hier aber in der vorlesung nicht behandelt werden da gibt es dann andere
3:21 vorlesung wie sich darum kümmern gut ich möchte darauf hinweisen dass es noch ein bisschen mehr material gibt zu der informationstheorie hier in zwei mal
3:30 90 minuten können wir wirklich los die oberfläche ankratzen wenn sie sich mehr dafür interessieren natürlich in die vorlesung folien die
3:38 sie hier sehen finden sie informationen oder auch in dem cgi skript was schon ein bisschen her ist von 2008/2009 von professor müller quade
3:49 oder als buch kann man informationen und kodierung von martin werner empfehlen fangen wir an ich rede die ganze zeit über informationsquellen
4:03 also sollten wir uns erst mal darum kümmern was überhaupt eine information ist also information für uns oder eine informationsquelle für uns hier ist das
4:17 folgende wir haben eine endliche menge von zeichen die wir wieder wie gewohnt mit sigma bezeichnet werden und einfach nur 1 bis ende zum beispiel also enden
4:28 verschiedene zeichen und die informationsquelle iks liefert jedes zeichen mit einer gewissen wahrscheinlichkeit okay also denken sie
4:38 zum beispiel daran die zeichen könnten die buchstaben unseres alphabets sein und die informationsquelle könnte einfachen instream von wörtern sein
4:47 die ganze zeit kommen da deutsche wörter oder was auch immer für eine sprache wird daraus okay und dann hat gibt es zeichen die jedes zeichen hat eine
4:56 gewisse wahrscheinlichkeit dass es übermittelt wird aus dieser informationsquelle im deutschen ist die wahrscheinlichkeit für eine sehr viel
5:04 höher als für den iks beispielsweise okay also wir gehen davon aus jetzt erst mal das wir wissen aus dieser informationsquelle kommen wie auch immer
5:12 gearteten und weichen ii hat die wahrscheinlichkeit p ok und diese wahrscheinlichkeiten p1 pm und positiv und summieren sich zu 1 ok
5:28 dann im stochastischen sinne nennt man nix auch einfach nur eine diskrete endliche zufalls variable und wir machen ein beispiel des standard beispiel ist
5:43 natürlich der würfel der würfel hat sechs zeichen die er über mitteln könnte das sind die sechs seiten des würfels und eine information wird übermittelt in
5:53 dem der würfel einmal geworfen wird und da hat natürlich jedes zeichen die gleiche wahrscheinlichkeit wenn der würfel ist er ist also ein 6 1 6 1 6 1 6
6:02 0 und so weiter sind diese entsprechenden wahrscheinlichkeiten ok
6:08 der würfel ist für uns die die wir jetzt kalkulieren machen wollen ein schwieriges beispiel also unsere idee oder unser vorhaben ist ja die
6:20 informationen die von der informationsquelle generiert wird zu kodieren und möglichst effizient dann rauszuschicken ja und effizient heißt zu
6:33 komprimieren die informationen soll möglichst in kurzen code werden komprimiert werden
6:41 [Musik] und man kann sich das so vorstellen dass das ergebnis also das nächste zeichen wie wahrscheinlich das ist dass das
6:55 zeichen kommt wenn er sehr wahrscheinlich ist dann haben wir keinen großen informationsgewinn durch dieses zeichen ja wir werden bestätigt in
7:03 dieser ohnehin wahrscheinlich eine annahme dass dieses zeichen kommen wird bei einem würfel jedoch wissen wir überhaupt nicht was als nächstes kommt
7:11 und unser informationsgewinn ist relativ hoch der erkenntnis gewinnen können sie sozusagen sagen wenn wir jetzt ein
7:19 zweites beispiel machen und der würfel sagen wir mal ganz arg gezinkt dass irgendeine seite die sechs kommt mit wahrscheinlichkeit ein halb und alle
7:27 anderen seiten mit wahrscheinlichkeit ein zehntel dann ist schon klarer was wir erwarten von dem nächsten zeichen es wird schon
7:35 mit hoher wahrscheinlichkeit mit sechs sein und dann ist es so dass wenn die sechs wirklich kommt dann ist unser
7:41 erkenntnisgewinn die mich niedrig ok und das wollen wir jetzt [Musik] näher betrachten also wir wollen wissen
7:53 was ist die informationen die in einem zeichen steckt okay also wir suchen ein maß dafür für den erkenntnisgewinn für nach dem ausgang
8:06 eines pärchens ja also der ausgang heißt dann kam wenn wir jetzt über zufalls experimente reden dann ist der ausgang des experiments und der hatte die
8:15 wahrscheinlichkeit pk das zeichen kamen mit wahrscheinlichkeit pk das ist ein ausgang eines zufalls experiment und der erkenntnisgewinn den wir jetzt kriegen
8:25 durch die information das war das zeichen den wollen wir pk da hängt nur von der wahrscheinlichkeit ab was wünschen wir
8:36 uns denn wir sollten dieses diese information dass so eine zahl sein wir wollen das irgendwie uhr informationen oder niedrige
8:44 informationen zu so einer wahrscheinlichkeit assoziieren und wir wünschen uns ein paar sachen also wir wünschen uns dass die informationen
8:52 nicht negativ sein soll ja wir wollen nicht irgendwie informationen bei mir ja wir wollen noch mal was dazu gewinnen wir wünschen uns
9:02 dass wenn das ereignis sicher ist also in wahrscheinlichkeit theorie wahrscheinlichkeit 1 hat ein sicheres ereignis was auf jeden fall eintritt
9:11 dann durch beobachten dieses zeichen sollen wir keine informationen kriegen ja also die informationen zu wahrscheinlichkeit 100 sein
9:23 okay wir uns wünschen uns auch dass wenn wir die informationen zu einer wahrscheinlichkeit haben und die wahrscheinlichkeit sich ein bisschen
9:33 ändert dann soll sich die informationen auch nur ein bisschen ändern ok oder mathematischen thermen die informationen als abbildung soll stetig
9:43 sein okay kleine änderungen der wahrscheinlichkeit so eine kleine änderung in der information mit sich bringen desweiteren
9:53 wünschen wir uns dass wir wollen dann die informationen nicht nur für ein zeichen machen sondern wir kriegen informationen aus dem ganzes string von
10:01 zeichen von der kette von zeichen und wünschen uns dass wenn wir wenn die kette doppelt so lang ist dann soll die informationen auch doppelt
10:10 so groß sein okay und wir gehen jetzt hier davon aus dass unsere informationsquelle unabhängig gleich also unabhängig diese diese zeichen
10:21 würfelt das heißt wenn zeichen und dann zeichen j kommt dann passiert es mit wahrscheinlichkeit x p j und dann soll die informationen die wir
10:33 dadurch kriegen genau die informationen von zeichen ii sein plus die information von zeichen j ok
10:43 gut und mit diesen anforderungen haben wir schon so mehr oder weniger unsere
10:52 funktion bestimmt die diese informationen darstellt ja also wie genau wir wahrscheinlich keiten auf informationen abbilden
11:02 nochmal zur erinnerung die soll niemals negativ sein wie soll an der stelle 1 uns interessiert nur die information
11:10 zwischen 0 und 11 wahrscheinlichkeit einer stelle 10 sein davor soll die positiv sein und multiplizieren von wahrscheinlichkeiten
11:20 soll zu agieren von informationen führen und hier kommt die definition die genau das tut logarithmisch ja sie haben vielleicht schon mal schon ein
11:31 logarithmen gedacht als sie gesehen haben dass multiplizieren so zu agieren werden das tun genau die logarithmen wir nehmen eine beliebige basis b
11:42 wir werden heute und im allgemeinen immer basis zwei nehmen also wenn ich es nicht hin schreibe des loga rhytmus 2 und definieren die informationen für
11:52 wahrscheinlichkeit p&i loga rhytmus von p negativ weil wir wollen dass der positive information und nach logarithmen gesetzen ist das das gleiche
12:05 wie der logos von 1 durch hier ist der graf für die normale logarithmisch funktion zur erinnerung ja die normale logarithmisch funktion ist nur auf
12:19 positiven werten definiert kommt aus - unendlich geht an der stelle 1 durch die 0 und steigt dann sehr schwach aber monoton
12:29 uns interessiert vor allen dingen der teil zwischen der 0 und der 1 also hier dieser bereich zwischen 0 und 1 und wir nehmen aber - senior it muss das
12:42 heißt das ganze ding wird nach oben gespiegelt ja und dann erinnern sie sich was wir sagen wollen wenn ein [Musik]
12:51 die inform die wahrscheinlichkeit eines zeichens spd von p die der erkenntnisgewinn sein den wir haben wenn dieses zeichen kommt ja also
13:04 je unwahrscheinlicher es war dass dieses zeichen kommt desto größer ist die erkenntnis dass dieses zeichen jetzt kam deswegen ist wenn wir das jetzt spiegeln
13:14 wenn es von oben kommt es ist sehr groß für wahrscheinlichkeit gegen null und dann geht es runter je wahrscheinlicher es war das ohnehin
13:22 dieses zeichen kommt desto geringer als unser erkenntnisgewinn bis zum sicheren ereignis an der stelle 1 da ist die information 0
13:33 warum da keine 1 oder irgendwas stehen sondern nur hinweise nicht okay so
13:42 genau welchen regeln zum logarithmisch sie wissen wenn sie die basis festhalten und das argument multiplizieren dann korrespondiert es zum addieren auf der
13:53 einzelteile des loga rhytmus das ist genau das was wir wollten wir wollten wenn wir wahrscheinlichkeiten multiplizieren
14:01 sollte es in der information addiert werden dann haben wir dieses logarithmisch von also - logarithmisch von phoenix das ist
14:09 ja das was sie nehmen ist das gleiche wie logo rhytmus von 1 durch iks das werden wir heute oft verwenden und ich erinnere sie auch noch kurz an
14:19 den basis wechsel also wenn sie den logarithmisch zur basis b schon kennen und sie wollen den umrechnen in loga rhytmus zur basis
14:27 wenn es ist einfach multipliziert mit einem faktor ja und der faktor ist eine konstante 1 durch logarithmisch zur basis b also
14:37 alle logarithmen funktionen bin quasi gleich sind unterscheiden sich nur durch stauchung dieser funktion dort durch den bestimmten faktor ok deswegen können wir
14:49 wir nehmen einfach basis zwei heute gut also hier oben ist noch mal die definition von der information
14:59 information so wahrscheinlichkeit p ist - logarithmisch von b oder äquivalent logos von 1 durch manchmal noch ein beispiel von so einer
15:10 informationsquelle wieder ein klassisches zufalls experiment eine münze ja er hat jetzt zwei mögliche zeichen diese übermitteln könnte nämlich
15:19 kopf oder zahl oder hier ist es mit null oder eins und wenn die münze fair ist dann um die auch bei der mit wahrscheinlichkeiten einhalb
15:28 und jetzt können wir uns einmal ausrechnen wie groß die information eines münzwurf sist dadurch dass die beiden
15:36 möglichkeiten die gleiche wahrscheinlichkeit haben haben wir also auch die gleiche information also ein münzwurf oder ein zeichen hat
15:45 wahrscheinlichkeit ein halb das heißt die information ist da oben eingesetzt für pelé als ein hype ist logarithmisch von 1 durch ein halb also logarithmisch
15:55 von 2 was da wir zur basis zwei rechnen genau einzeln okay das heißt in diesem experiment haben wir blieben münzwurf kriegen wir informationen 1 das sagt
16:11 natürlich jetzt nichts aber einfach um die dahin mal ein bisschen rum zu stellen wenn wir die münze jetzt kam mal hintereinander werfen
16:19 und die information kriegen von diesem jahr von von dieser folge von k ergebnissen des zufalls experiments ist die wahrscheinlichkeit für eine
16:30 bestimmte folge also die folge zum beispiel kopf kopfzahl kopfzahl so oder so genau eineinhalb mal eineinhalb mal eineinhalb mal ein halb mann halb der
16:40 einheit ja das ganze kam er weil die ereignisse unabhängigen einfach multiplizieren von wahrscheinlichkeiten das ist also 1 durch zwei
16:52 und die informationen jetzt für diesen landen string ist also eingesetzt die wahrscheinlichkeit 1 durch zwei hochkar open in die informations definition ist
17:05 also der warum da jetzt - geht weiß ich nicht logarithmisch von 1 durch zwei hoch
17:15 ka-news der logik muss von 12 k wir nehmen jetzt die rechte seite von der definition da oben - der logo rhythmus von der wahrscheinlichkeit das ist das
17:25 gleiche wie der logarithmisch von care wert also logarithmisch von zwei hoch und dadurch dass wir das zur basis zwei rechnern es ist genau wir kriegen also
17:36 carl informationen aus kamenz dürfen und mit formation 1 aus einem münzwurf das ist genau das was wir haben wollten
17:46 also als nächstes machen wir die entropie ja wir wissen jetzt zu jeder wahrscheinlichkeit gibt es eine assoziierte information und so eine
17:59 informationsquelle ist er für uns einfach nur eine menge von zeichen und jedes zeichen hat seine wahrscheinlichkeit
18:06 das heißt jedes zeichen hat quasi seine information und so können wir sagen was ist so die mittlere informationen die wir aus dieser informationsquelle
18:17 kriegen ja und das ist die entropie wie viel information übermittelt diese informationsquelle und die idee ist je
18:30 zufälliger die informationsquelle zeichen liefert desto höher ist die informationen die wir kriegen also ganz extrem wenn die informationsquelle immer
18:40 nur einzeln macht dann ist die informationen die wir von kriegen null damit können wir keine informationen übermitteln wir können nur einzelne
18:47 machen und wenn wir aber 90 irgendwie 90 prozent 1 1 und 10 nullen dann können wir schon ein bisschen informationen damit übermitteln aber nicht so viel am
18:57 meisten informationen können wir mit denen mit hilft die 50 das war die entropie sein also die entropie weil ein maß für den mittleren
19:08 informationsgehalt pro zeichen sei hier kurz erwähnt wird auch später nicht verwendet werden also von im string ist die entropie die länge unter der
19:25 einst bringen nicht komprimiert werden kann die idee ist wenn das dringen viele informationen viel informationen enthält
19:34 dann brauchen wir auch viele bits um den zu kodieren hier ist kurz erwähnt die commodores komplexität eines strings von dem die vielleicht schon mal gehört
19:47 haben das ist die länge eines kürzesten programms das den spring ausgibt also ist insbesondere die entropie eine untere schranke an die combo griff
19:59 komplexität weil das programm muss er den string einmal ausgeben das programm muss also mindestens so lang sein wie der string sei
20:09 so jetzt kommt die normale definition der entropie das ist einfach nur ein mittelwert nehmen über die informationen der einzelnen
20:18 zeichen ok also die entropie so basis 2 sowie immer einer diskreten zufalls variable iks oder informationsquelle mit
20:31 ergebnissen in sigma unseren zeichen und den wahrscheinlichkeiten positive wahrscheinlichkeiten für jedes symbol ist definiert als das da groß half onyx
20:45 so wird die bezeichnet die summe über alle zeichen wahrscheinlichkeit des zeichens mal informationen bis zeichen oder informationen der zugehörigen
20:56 wahrscheinlichkeit ja das ist es hinten dieses logo rhythmus 1 durch p das ist einfach die information über kriegen weil durch dieses zeichen mit
21:04 dieser wahrscheinlichkeit und wir nehmen jetzt diese informationen wir kriegen ja die zeichen nicht gleich häufig wir nehmen also nicht den mittelwert über
21:14 alle informationen sondern wir nehmen die information so häufig wie das zeichen auftritt ja also wahrscheinlichkeit mal information gut
21:25 gewichtetes mittel das ist die entropie bemerkung dadurch dass jeder teil in dieser formel da oben immer positiv ist
21:37 logarithmisch ist immer positiv die wahrscheinlichkeiten sind immer positiv das heißt die produkte sind immer positiv das heißt die summe davon
21:46 dass immer positiv also entropie ist immer irgend eine positive zahl eine positive reelles sal [Musik]
21:58 jetzt kurz also wie groß kann so eine entropie werden dies tendenziell nein sage ich mal ich weiß nicht was ihr gefühl von groß und klein ist
22:10 tendenziell klein ich hatte schon angedeutet die höchste die höchsten informationsgehalt würden wir kriegen wenn wir ein zeichen haben
22:21 und die mit gleicher jedes zeichen mit gleicher wahrscheinlichkeit kommen würde ok wie sähe das aus also von der diskreten zu variable mit allen
22:33 möglichen ausgängen und wahrscheinlichkeit 1 durch n für jedes zeichen wenn man jetzt einsetzen dann würden wir rauskriegen in die entropie
22:41 wir setzen ein die summe über die wahrscheinlichkeiten die wahrscheinlichkeiten sind alle 1 durch m
22:49 und logarithmisch zur basis 2 von 1 durch 1 durch und die summe alle so nannten sind jetzt gleich hier es hängt ja nur von n abkriegen also
23:02 enden mal die gleichen summen dann kürzlich dieses einmal 1 durch ein schön weg und wir kriegen nur noch den logarithmisch 2 von n
23:13 und das ist unsere entropie also locker ist die entropie die wir haben wenn die renn zeichen uniformen
23:24 gleich verteilt in der informationsquelle ein anderes beispiel wenn wir jetzt die deutsche sprache nehmen so wie ich
23:32 gerade vorhin angekündigt habe dann haben wir also 26 zeichen und wir nehmen als wahrscheinlichkeiten die relative häufigkeit in der deutschen sprache sony
23:44 hat ein ziemlich hoher wahrscheinlichkeit und eine ziemlich niedrige wahrscheinlichkeit und dann können wir das jetzt kann man sich diese
23:51 wahrscheinlichkeit mehr ausrechnen und diese entropie dazu ausrechnen und sozusagen gucken wie viel information weckt in der deutsche sprache drin oder
24:00 wie viel redundanz ist da drin und wenn man das macht dann kommt man ungefähr bei 4,1 aus wie die deutsche sprache als entropie und zum vergleich das maximal
24:13 mögliche bei 26 zeichen wenn die alle gleich wahrscheinlich wären wäre der logo rhythmus von 26 was 4,7 wäre ok das heißt wir haben eine gewisse
24:26 redundanz in der sprache im sinne von schriftsprache müsste man müsste man sagen ja ein sinne von der alb zeichen wie wir sie verwenden
24:37 das beste wäre war sie wenn jedes zeichen jeder buchstabe gleich häufig auftauchen wurde in der deutschen sprache gut auch nochmal grafisch diese
24:53 entropie wenn wir jetzt nur wieder eine münze haben wir haben eine münze zwei mögliche ausgänge und die ist vielleicht nicht fair sondern eine münze mit
25:06 wahrscheinlichkeit p bezahl unterhalt entsprechend wahrscheinlichkeit 1 - per kopf dann ist die entropie hier unten einfach eine summe von zwei möglichen
25:16 werten nämlich einmal p mal logarithmisch einzig p&i loga rhytmus man einst durch 1 - p und das ist der graf von dieser funktion
25:29 also wieder keine beschriftung in der mitte ist wahrscheinlichkeit ein halb da ist die entropie am höchsten nämlich genau 1 ich verrate ihnen die
25:42 beschriftung und wenn die wahrscheinlichkeit für zahl sinkt dann ist die information der informationsgehalt den wir kriegen durch
25:50 die münze bringt oder wenn die wahrscheinlichkeit für zahl steigt und gegen eins geht dann sinkt auch die der informationsgehalt wird dann quasi schon
26:00 vorher sehen können dass die einst kommt die zahl kommen gut jetzt haben wir informationen und entropie was hat das ganze mit codierung zu tun
26:12 also was wir wollen ist das folgende wir haben diese informationsquelle ix die zeichen aus sieht man mit bestimmten wahrscheinlichkeit von i liefert wir
26:23 kennen nur die wahrscheinlichkeiten wir wissen nicht genau apriori was für was für ein string der überliefert werden soll und werden nur wie häufig oder wie
26:32 wahrscheinlich ist es dass ein bestimmtes zeichen da ist und wir wollen wir wollen es jetzt kodieren das heißt wir wollen in zeichenketten aus 01
26:43 überführen mit strings und wir wollen das jetzt hier ohne informationsverlust machen
26:54 und wir wollen es so machen dass die länge der ausgabe also wir überführen diese beliebigen string aus sigmaringen string aus 0 1 und der soll möglichst
27:06 kurz sein wir wollen die daten komprimieren also normal ordnen wir jedem zeichen ein codewort zu ci das ist es dringend aus 0
27:19 1 und hängen dann statt die zeichen hintereinander zu hängen hängen wir die kurve da hintereinander und kriegen ein langes lang 01 string als beispiel
27:31 beispielsweise here are a und o sind meine vier zeichen und ich habe mich dazu entschieden zu kodieren als 00 und h als 11 0 und 11 0 1 0 1 und dann
27:46 würden würden wir zum beispiel das wort hallo oder den string hll kodieren als 11.000 10 10 01 okay wir machen keine trennzeichen
27:59 einfach nur ein stream von witz ok das klingt erst mal gefährlich keine trennzeichen zu machen
28:11 ja wir wollen natürlich nicht nur kopieren sondern wir wollen das natürlich so machen dass am ende das auch wieder decodiert werden kann dass
28:18 die informationen nicht verloren geht ja eine frage das macht können sie also erlauben es aber es wird nie sinnvoll sein außer die
28:36 irgendwelche komischen rand fälle ja gut ja warum wie kann es sein dass wir ohne trennzeichen trotzdem das ding dekodieren können also eine möglichkeit
28:52 wäre natürlich dass sie alle gleich lang sind unsere code wörter dann wissen wir einfach immer drei zeichen sind ein boot wort das ist ein sogenannter lockout
29:07 aber rockets brauchen eventuell dann müssen wir also auch denken sie an die deutsche sprache dann müssen wir für das e3 zeichen
29:14 machen aber auch für das x3 zeichen und für das e3 zeichen ist blöd weil das so häufig vorkommt würde mein lieber weniger zeichen für das e machen ok und
29:25 deswegen wollen wir mit codes variabler länge hantieren aber trotzdem ohne trennzeichen und damit es wieder auseinander klamme sabar ist muss man
29:36 einen so genannten präfix code machen also es muss klar sein dass man ein zeichen aufhört okay ich gehe noch einmal kurz zurück zu dem
29:48 beispielsweise gerade hatten wir kriegen jetzt einfach nur diesen 01 dringen 11.000 19 und so weiter und wir kennen natürlich diese übersetzungs tabelle und
29:59 fragen uns jetzt wo hört das erste zeichen auf ja und das können wir mal ganz kurz machen also wir lesen zuerst eine eins wir
30:06 gucken nach steht die 1 führung ein zeichen also kann es noch kein code wort gewesen sein
30:12 ok dann also muss die zweite 1 auch noch dazu gehören 11 steht die 1 1 führung ein zeichen nee also kann es kein ko ist kein code
30:21 wort also muss das codewort noch länger sein 110 und jetzt merken wir 110 taucht in der liste auf das muss ja heißen warum muss das haar heißen das einzige
30:31 problem wäre wenn es nicht heißt und es der präfix von einem anderen codewort wäre der noch nicht fertig ist ja das wollen wir
30:43 verhindern weil dann wissen wir nicht ist es jetzt schon das haar oder geht es noch weiter und das sind diese präfix codes wir verhindern dass ein codewort
30:53 ein präfix von einem anderen codewort ist also ein präfix kohtes und code bei dem kein codewort anfang eines anderen kurz ist und dann kann man die
31:06 dekodieren ohne trennzeichen ok präfix codes können als baum dargestellt werden wie folgt das sind die sogenannten codierung bäume
31:18 also das alphabet ist wieder sicher und die code wörter sind jetzt für cfc und und dann der codierung baum sieht so aus wir machen noch mal kurz über dem
31:34 alphabet 0 1 das ist ein gewitter baum gerichtet informatik bäume dass er die wurzeln oben und die blätter unten und jeder knoten hat bei kannten höchstens
31:50 denn die kannten haben entweder eine null oder eins da dran und jeder knoten hat höchstens einer mit ner 0 und höchstens eine mit einer eins nach unten
32:01 ausgehend von dem knoten und die blätter sind die zeichen des alphabets und das codewort für einen blatt ist der string den ich auf sammle wenn ich von
32:16 der wurzel zu diesem blatt gehe ja also dann sehe ich ein land bekannten nullen und einsen und das sind die code wörter für die blätter also als beispiel b hat
32:30 ihr den code 0 0 1 und er hat 100 und hat 1 1 1 ok das funktioniert für jeden präfix code jeder präfix code kann in so einem baum
32:47 überführt werden und jeder baum definiert uns ein präfix code das wichtige ist dass die code dass die zeichen an den blättern stehen das ist
32:59 genau die präfix eigenschaft nämlich dass von dort aus nicht ist noch weiter nach unten in den baum geht es ist keine code wird er gibt die dort noch weiter
33:07 nach unten ok der baum muss aber nicht immer so balanciert aussehen wie hier die blätter müssen nicht alle auf der gleichen höhe hängen denn welche geben
33:18 die weiter oben hängen mit kurzen kurz wörtern und andere die weiter unten hängen mit langen kutter
33:24 gut also es ist diese direkte zusammenhang zwischen codierungen und den zugehörigen bäumen und die tiefe eines knotens bau in den baum t
33:35 bezeichnen wir den dtv ist genau die anzeige kanten auf dem weg von der wurzel zu dem knoten und es entspricht dann also der länge des zugehörigen code
33:46 wurde wenn wir jetzt eine gegebene codierung haben für ein alphabet also wir haben uns geeinigt jedes zeichen hat ein
33:57 entsprechendes codewort und das ist ein präfix code dann gibt es dazu eine codierung baum und wir bezeichnen die mittlere codewort länger als die summe
34:11 über die wahrscheinlichkeit dass ein zeichen kommt mal die länge des zugehörigen kurz
34:19 ja und das ist das was wir letztendlich minimieren wollen wir wollen diese summe möglichst klein haben und deswegen kann
34:29 es sein dass für wenn dieses p ihr sehr kleines wenn die wahrscheinlichkeit sehr niedrig ist ein zeichen dass wir es uns leistungs leisten können da ein langes
34:39 codewort für zu machen okay das ist ein quer die mittlere codewort länge dass die können wir auch direkt in den baum ablesen als die summe über alle knoten
34:50 in also blätter in dem baum die wahrscheinlichkeit dieses zugehörigen zeichens mal die tiefe in dem baum es weil die tiefe sehr genau
35:00 die länge des courts das heißt hier sehe ich alle blätter haben tiefe 3 das heißt alle code wörter haben länge 3 also die mittlere codewort
35:12 länge ist 3 als informationsquelle gesehen wenn das jetzt hier die acht zeichen sind a bis h und die mit gleicher
35:24 wahrscheinlichkeit ein achtel kommen dann würde ich diesen diese codierung hier wählen und dann haben wie ich gerade gesagt
35:32 habe alle code wird die länge 3 und ist also auch die mittlere [Musik]
35:43 kann natürlich so nur mit mittlere codewort länge 3 oder mit codewort länge 3 kann ich höchstens acht weichen kodieren wenn ich jetzt
35:55 den balancierten baum der in der tiefe vier nehmen würde dann könnte ich das verdoppeln ja das ist wirklich 16 zeichen
36:02 das heißt also ich brauche mindestens wenn ich die alle gleich langen mache lockt von anzeichen viele bits oder codewort länger
36:18 noch ein beispiel das morse alphabet dass sie vielleicht schon kennen als codierung von dem alphabet oder von von einem sigma was relativ groß ist also 26
36:30 zeichen und codiert auf nur zwei zeichen ja kurz und lang alphabet das ist aber kein traffics code aber sie haben schon mal gesehen wie so etwas aussieht das
36:43 ist so normal tabelle zum beispiel das ist einfach nur kurz oder des t ist einfach nur lang aber es kein präfix code zum beispiel wenn ich kurz lang
36:53 übermittle dann weiß ich nicht genau ist es jetzt et oder ist das einfach nur nah ok und deswegen hat der morsecode tatsächlich drei zeichen nämlich
37:05 meistens das dritte zeichen pause ok aber es ist ein code mit variabler länge
37:14 der ist daraufhin optimiert dass man möglichst die häufigen buchstaben wie das ehe- und das t mit kurzen code wörter ausstattet und die seltenen
37:24 buchstaben sowie das ixs mit langen code wörter damit im durchschnitt im mittel die nachrichten möglichst kurz sind im morsecode
37:37 jetzt kommen wir zu dem ersten theorien shannons quellen codierung theorem an dass es das theorem das link jetzt was ich davor erzählt habe nämlich entropie
37:49 wie viel information steckt in der quelle zu wie gut können wir das eigentlich codieren ja und da gibt es die sind eigentlich
37:57 quasi das gleiche die entropie und die bestmögliche mittlere codewort länger in dem präfix bot also fix ist eine diskrete endliche
38:12 zu variable entropia von iks wir haben einen präfix code mit einem code aus dem zeichen wir werden hier immer zwei zeichen haben er also ds2 in
38:27 unserer anwendung und wir haben minimale mittlere codewort länge also unter allen präfix codes haben wir den genommen wo diese summe über wahrscheinlichkeit mal
38:39 längere skateboards minimal ist dann gilt denken sie sich wieder d12 dann ist nämlich ihr logarithmen basis 2 von 2 ist genau 1 dann fällt es einfach weg
38:52 dann ist diese mittlere codewort länge zwischen h von iks und habe von x1 also ich glaube wir hatten das beispiel das deutsche alphabet hatte entropie von
39:09 4,1 ja dann ist die bestmögliche minimale codewort länge zwischen 4,1 und 5,1
39:26 das werden wir nicht beweisen beweisen doch was anderes später und zwar beweisen wir wie man diese minimale codewort länge erreichen kann
39:36 und da gibt es ganz schöne verfahren das eine verfahren ist es denn bano verfahren erscheinen fahrrad codierung okay ich mache spiel das erst an einem
39:48 beispiel durch erklärt das so ein bisschen mündlich und danach sehen wir wie man das tatsächlich formal macht also angenommen unsere zeichen sind
39:56 jetzt hier null bis irgendwas das könnte hier weitergehen denken sie an die buchstaben und wir kennen wir kennen die wahrscheinlichkeit
40:06 für jedes zeichen ja denken sie wieder an die buchstaben in deutschland alphabet wie häufig ein ehe vorkommt und so weiter wir sortieren die zeichen
40:17 das häufigste zeichen ganz nach oben ja also ich habe jetzt so umbenannt dass die jetzt in der richtigen reihenfolge kommen also bis häufig die zeichen ganz
40:26 oben als zweithäufigste und so weiter und dann wird es immer unwahrscheinlicher
40:31 und wir wollen die code wörter finden das ist die dritte spalte in der tabelle so und was wir jetzt machen ist wir wollen erstmal die code wörter aufteilen
40:41 in die code wörter die mit einer null anfangen und die code wörter die mit einer 1 anfangen und wir sagen die mit einer null anfangen sollen so für die
40:48 erste hälfte verzeichnen sein und die mit der einst anfang für die zweite hälfte wir zeichnen wobei hälfte nicht wirklich
40:57 hälfte ist sondern gewichtete hälfte wie häufig die sachen auftauchen das heißt ich frag mich wo ist der cut so dass ungefähr 50 prozent der
41:10 wahrscheinlichkeit hier oben liegen und 50 prozent der wahrscheinlichkeiten hier unten liegen
41:16 da mache ich den cut und sage okay die alle oben fangen schon mal mit der null an und die unten fangen mit einer eins sein und dann mache ich das reh kursiv
41:25 weiter das heißt ich frage mich jetzt in dem oberen teil was ist denn das zweite zeichen und fragt mich wieder von den ganzen wahrscheinlichkeiten die hier
41:33 noch da sind wo ist denn der kattas ungefähr die obere hälfte davon so häufig auftaucht wie die untere hälfte davon
41:42 ja und dann sage ich okay diese die oberen die wahrscheinlich die mit 0 weitergehen und die unteren die mit 1 weitergehen und dann mache ich das
41:52 wieder rosig und hier drin muss ich natürlich noch rosig machen und auf diesem großen ding muss ich auch noch rosig machen da frage
42:00 ich mich jetzt wieder unter all denen die mit einer 1 anfangen weiß ich wie viel wie häufig die insgesamt auftauchende gesamt wahrscheinlichkeit
42:08 und ich frage mich ok wo ist der po ist ungefähr die mitte von wahrscheinlichkeiten gesehen und dann teile ich das so auf und so weiter und
42:17 dann kriege ich am ende diese code wörter zum beispiel raus und es wird sich so einstellen dass sachen die wahrscheinlich sind kriegen kurze kurz
42:27 roth wörter und sachen die unwahrscheinlich sind zeichen die unwahrscheinlich sind kriegen lange code wörter und das wird ein präfix code sein
42:37 das sehen sie vielleicht schon an dem verfahren warum das eintreffen gut das war informell formell als algorithmus sozusagen formuliert sieht
42:50 es wie folgt aus die eingabe ist die liste der zeichen mit ihren zugehörigen wahrscheinlichkeiten und die ausgabe ist
42:59 die codierung also ein codewort für jedes zeichen aus dem 0 1 stern und wir machen das so rosig wie ich das gerade schon angedeutet habe hier zuerst
43:13 den abbruch bedingungen wenn wir nur ein zeichen bekommen haben dann ist das codewort ist leere rot rot ist kommt ein bisschen auf die
43:22 frage von vorhin zurück dann müssen wir nicht studieren ja es gibt nur ein zeichen und wir müssen nichts passieren andernfalls wenn da nicht ein schuss
43:37 also es gibt mindestens zwei zeichen dann machen wir dieses aufteilen ja also wir sortieren die zeichen die wir da gekriegt haben nach ihrer
43:44 wahrscheinlichkeit nicht aufsteigen und nehmen uns die gruppen z1 und z2 so dass die ungefähr gleich wahrscheinlich sind das ist dieses ungefähr in der mitte
43:56 trennen also formal ist es dass die gesamt wahrscheinlichkeiten in der ersten hälfte möglichst nahe an den gesamt wahrscheinlichkeit einer zweiten
44:05 hälfte sind also der absolut wert der differenz ist minimal und dann sagen wir okay die erste hälfte trägt 0
44:19 und die zweite hälfte kriegt ne 1 und dann wird die erste hälfte in die region gegeben und was auch immer die kriegen wird einfach vorne die null dran gehängt
44:29 und die zweite hälfte wird auch in die region gegeben und was immer die kriegen kriegen formel 1 waren und dann habe ich die zusammen und krieg meine code wörter
44:42 das ist schon in planung als codierung baum könnte man das dann so auffassen
44:51 das ist glaube ich aus dem beispiel was wir vorne hatten das sieht jetzt so aus als ob die blätter alle auf der gleichen tiefe sind
44:57 aber ist natürlich nicht so weil es hier so lange kanten gibt ja also die null hat nun codewort der länge 3 und die elf hat schon codewort der länge 5
45:16 ein inferno codierung klassisch aber nicht optimal ja könnte eventuell es gibt fälle wo stellen fahrer nicht die bestmöglichen
45:28 die kleinstmögliche mittlere codewort länge kreiert deswegen nicht weit verbreitet als nächstes kommt die zweite codierung
45:36 die der klassiker ist und die auch optimal optimale mittlere codewort länger macht das ist die hafen codierung wieder zuerst am beispiel und dann
45:47 normal hier stellen wir uns das so vor wieder der gleiche trick wir haben diese zeichen mit ihren assoziierten
45:53 wahrscheinlichkeiten wir sortieren die häufigste es steht ganz oben seltensten es steht ganz unten und jetzt suchen wir uns die beiden
46:03 kleinsten wir machen das jetzt von hinten so investieren wir suchen uns die beiden kleinsten wahrscheinlichkeiten die in dem bild sind
46:12 und trennen die ja ich sagen da fängt bei dem einen fängt das codewort mit null an und bei dem anderen mit 1 und dann sagen wir
46:26 okay wir kreieren uns so neuen noten nennen diesmal und der kriegt als wahrscheinlichkeit die summe von den beiden ja das steht sozusagen welche
46:38 zwar steht und der für cnc entsteht dass hierfür zeichen a oder c und wir suchen uns wieder die beiden kleinsten wahrscheinlichkeiten die wir
46:47 hier im bild haben ja also a und c sind fertig aber dafür ist dieser oder zehn knoten da und das wäre jetzt also die 0,1 mit 0,15 und kombinieren die beiden
47:02 ja hat eine null und eins beliebig tatsächlich auf die beiden summieren die wahrscheinlichkeiten zu einem neuen
47:10 noten wenn wir uns wieder die beiden kleinsten das sind jetzt 10 501 502 und trennen die beiden nehmen uns die beiden kleinsten zahlen die wir haben und
47:21 nehmen uns dann die beiden kleinsten sein bis wir nur noch ein knoten haben der wahrscheinlichkeit 1 1 hat und jetzt das codewort entsprechend sowie das ding
47:33 jetzt aussieht schon als codierung baum also das zeichen de ist so häufig dass es verdienten codewort der länge 1 nur zu kriegen
47:42 das heißt alle anderen code wird dann müssen mit einer null anfangen damit wir nicht denken das ist ein de ist also alle anderen sind hier in dem brunch von
47:53 den bauern fangen mit einer null an und zb hat das codewort 0 1 0 formal sie die half men codierung so aus wie der eingabe die zeichen mit ihrem
48:07 wahrscheinlichkeiten ausgabe ist der baum der decodierung widerspiegelt die präfix codierung wir fangen an legen uns eine menge von blättern an u
48:18 wir sind die blätter des baumes und wir gehen jetzt durch den - einst schritten ergeben schritt wird die anzahl der aktiven knoten sozusagen eins verringert
48:29 also ein mit obst minus 1 schritte wir erzeugen uns neuen knoten fed und holen uns und v die beiden elemente mit den niedrigsten wahrscheinlichkeiten
48:44 wir verbinden set mit omv als linken und rechten nachbarn mit einer 0 respektive 1 kannte und sagen z ist ein neues element von q mit der wahrscheinlichkeit
48:58 der summe der beiden vorigen wahrscheinlichkeiten und repeat ja
49:06 ok jetzt schon angekündigt hat man codierung ist optimal bezüglich
49:15 mittlerer codewort länger das ist ein satz den wir tatsächlich beweisen können und werden die essenz des satzes liegt in diesem lämmer
49:26 nämlich angenommen wir haben einen codierung baum mit mittlerer minimaler minimaler mittlerer codewort
49:38 länger und wir haben zwei zeichen mit kleinster wahrscheinlichkeit dann kann dieser regierungsform auch geändert werden in
49:53 einen wo diese beiden unwahrscheinlichsten zeichen die kinder eines gemeinsamen eltern knoten sind das ist ja das was hart macht nimmt sich
50:05 die beiden unwahrscheinlichsten und gibt den eltern knoten und dann geht's weiter ja also es gibt immer einen optimalen also eine codierung baum minimaler
50:16 mittel codewort länge der die beiden unwahrscheinlichsten zeichen zu einem gemeinsamen eltern knoten verbindet das ist das beweisen wir dass angenommen
50:32 also wir fangen einfach an mit einem beliebigen optimalen baum t strich und dann schauen wir irgendwo in den baum sind ja unsere zeichen xy als
50:44 blätter unsere beiden unwahrscheinlichsten zeichen bda ist mindestens so tief wie y in den baum
50:56 der eltern knoten von iks ist also wenn wir so jetzt gibt es fälle drei fälle wenn das so aussieht wie hier das ist voll 1
51:08 also ist das einzige kind von z hat kein weiteres kein zweites kind nun das wird auf keinen fall passieren in der optimalen codierung weil ich dann
51:25 einfach zeit löschen könnte und xi oben schön schreiben könnte und das wäre kürzere minimale also eine kürzere mittlere codewort länger an also im
51:36 optimalfall nicht auftauen auftauchen ok also z hatten weiteren nachbarn hat ein weiteres kind weiter fall dieses kind ist noch kein blatt
51:47 wenn er sein ja also z hat zwei kinder einzufahren des iks und das andere ist aber noch kein blatt dhz hat mehr als zwei nachkommen wir nehmen wir uns
52:00 irgend einen nachfahren deren blatt ist hier unten muss irgendwann mal ein blatt auftauchen w okay in dem optimalen baum wer hat also
52:12 ein längeres codewort als fix das heißt ich könnte theoretisch wie gegen ex porsche näher ich konnte
52:25 einfach sagen okay pass auf weg kriegt das codewort von xx kriegt das codewort von w das darf meine code mittlere codewort länge nicht verkürzen weil der
52:34 baum mehr optimal war das heißt das einzige was sein könnte ist dass die beiden die gleiche wahrscheinlichkeit haben ja also
52:41 tendenziell ist er so lange code wörter sind zum unwahrscheinlichen zeichen nix ist aber unter den beiden unwahrscheinlichsten zeichen dhb muss
52:54 höchstens zur wahrscheinlichkeit sei so wahrscheinlich sein muss also genauso wahrscheinlich sein dann kann ich dir also trotzdem tauschen
53:03 und ich ändere gar nicht so an der mittleren codewort länger ja die haben ja die gleiche wahrscheinlichkeit gut dann habe ich es also nach unten
53:10 getauscht und ich konnte und ich mache weiter mit der fall unterscheidung guckt dann wir wieder den den vater von iks an cook ob der kindheit ob das schon platt
53:25 ist oder nicht irgendwann landet dann also in dem fall das axon vater hat der fahrer hat ein zweites kind und dieses kind ist auch
53:34 schon blatt ok und y liegt irgendwo anders in den baum mein ziel ist ja xy und hinten
53:45 gemeinsamen vater gibt zu geben also was passiert denn wenn ich kuh mit y tausche wenn die beiden die gleiche
53:54 tiefe hatten wenn ändert sich an der länge ihrer code wörter gar nichts und das ist okay weitere codewort länger bleibt weil ich
54:04 es nicht mindestens so tief liegt wie y ist also wenn die ungleiche tiefe haben dann muss also kuh echt tiefer liegen heitz oops i lon dann ist aber wiederum
54:17 weil y auch einer der unwahrscheinlichsten ist kann nicht häufiger sein das heißt die wahrscheinlichkeit von p&g
54:25 muss gleich sein und dann ist das tauschen wieder okay okay und dann habe ich also einen optimalen baum gefunden wo die beiden unwahrscheinlichsten
54:34 zeichen gemeinsamen vater haben sowie hafen anfängt ok so dass es dieses vorbereitende lämmer was wir jetzt benutzen um zu
54:46 beweisen dass die half men codierung optimales bezüglich mittlerer codewort längen wir beweisen dass nach induktion über
54:56 die anzahl der zeichen des alphabets wenn das alphabet nur ein zeichen hat was macht hoffmann hoffmann [Musik]
55:03 macht ein leeres codewort da muss auch nichts codiert werden induktions voraussetzung ist jetzt also der hafen algorithmus berechnet einen
55:14 optimalen codierung baum für alphabete der länge höchstens n wir haben jetzt ein alphabet der länge m + 1
55:28 mit zugehörigen wahrscheinlichkeiten p1 bis 1 wir kürzen diese mittlere codewort länger ab als oder die mittlere codewort länge 1 bezüglich eines baumes ab als es
55:41 von t das ist einfach die definition dieser mittleren codewort länger bezüglich dieser codierung der summe wahrscheinlichkeit x tiefe in dem baum
55:51 jetzt machen wir ein widerspruchs beweis wir nehmen also an der half men algorithmus liefert uns einen baum th der nicht optimal ist also es gibt
56:04 einen alternativen baum t en wo dieser fw recht kleiner ist wo die mittlere wort länge echt kleiner ist als die von dem hafen baum
56:20 das sieht jetzt so aus nach dem vorigen lämmer wissen können wir sagen okay wenn es einen optimalen baum gibt dann gibt es auch einen optimalen baum der xy
56:32 als die beiden kinder eines gemeinsamen eltern knotens hat also ceop können wir annehmen dass inter optics und y liegen direkt unterhalb des
56:42 gleichen eltern knotens in chf ist es auf jeden fall sowohl hoffmann codierung so funktioniert es fängt er an im ersten schritt nimmt ihr die beiden zeichen mit
56:54 kleinster wahrscheinlichkeit usw was machen ist wir tun das was der hafen ein algorithmus tut wir löschen exil on gucken uns neues zeichen z an mit der
57:06 wahrscheinlichkeit der summe der wahrscheinlichkeiten von xy ok dadurch kriegen wir unser alphabet um 1 kleiner ja wir nehmen zwar aus xy und fügen ein
57:18 neues hinzu wir können auch auf den bäumen diese operationen machen dass wir einfach
57:24 sagen okay bis hierhin ist das codewort für z das ist einfach jetzt wir kriegen jetzt chf strich und tee ob strich
57:35 das sind einfach legale codierung bäume für das neue bei für den neuen zeichensatz über optimal i tät oder so habe ich noch
57:45 nichts gesagt einfach nur legale bäume tatsächlich aber wissen wir dass chf strich wirklich das resultat des hafen
57:55 algorithmus ist für diese neue instanz nach walter hoffmann codierung so rief jetzt genau das tut und sie oft strich ist einfach nur irgendein codierung swan
58:10 wie die neue instanz vielleicht nicht optimal aber wir können uns ausrechnen die mittlere wort länge von diesen neuen baum bäumen mit den strichen in
58:22 abhängigkeit von dem alten bäumen also weil ja alle blätter quasi gleich bleiben und ihre wahrscheinlichkeiten gleich bleiben und ihre wort längen
58:35 gleich bleiben ändert sich nicht viel nur dort wo wir wirklich was geändert haben nämlich in dem großen baum rth hatten wir noch
58:45 fix und y drin als knoten die tauchten in der summe auf mit tiefe des knotens mal wahrscheinlichkeit des knotens das heißt die sind hier in diesem termin
58:53 drin die müssen wir wieder rausnehmen und dafür haben jetzt neue reihen diesen z er ist tiefe von dem zett mal die
59:01 wahrscheinlichkeit von dem zelt jetzt wissen wir aber die wahrscheinlichkeit von dem set ist genau die summe von diesen beiden wahrscheinlichkeit und die
59:10 tiefer vor dem zelt ist genau 1 weniger als diese beiden tiefen die sind irgendwelche zahlen hier a und a und dann ist es ja - 1 wenn man das einmal
59:18 hin schreibt dann sieht man dass genau das rauskommt also die mittlere wort länge des neuen des gestrichenen haft baumes ist genau
59:30 um pxp y kleiner als die mittleren wort länger des vorherigen worms aber die exakt gleiche argumentation funktioniert für diesen job strich
59:46 die oft strich hat auch als mittlere wort länge genau wie xy kleiner als vorher
59:55 dadurch dass wir vorher angenommen haben das recht kleiner ist als chf muss also jobs strich die sind gebäude jetzt um die gleiche zahl verkleidet worden dann
1:00:09 musste ob strich recht kleiner sein als chf strich das ist aber ein widerspruch dazu dass auf dem kleineren alphabet affen optimal
1:00:21 war okay also die ob strich ist jetzt echt ein besserer codierung baum als chf sprich widerspruch dazu dass auf dem alphabet 120 hartmann der haft einen
1:00:34 algorithmus aber optimal war okay also das beweist die optimal i tät des ok wird den diskussionen zur hafen codierung
1:00:47 wir haben natürlich jetzt unterschiedliche wort längen wenn dem präfix co das hat auch ein paar nachteile also vor
1:00:55 allen dingen bei der dekodierung kann es jetzt zu verzögerungen kommen ja also dass die die decodierung geht jetzt nicht mit uniformen geschwindigkeit weil
1:01:06 manchmal kommt auf einmal so ein super langes codewort für das obwohl es nur ein zeichen repräsentiert irgendwie unverhältnismäßig lange brauchen um das
1:01:14 zu dekodieren ist nicht so in uniform geschwindigkeit die decodierung das will man vielleicht nicht außerdem wir haben jetzt die daten
1:01:25 wirklich komprimiert auf das bestmögliche wir haben das so kurz wie nur irgendmöglich gekriegt mit dieser codierung so kurz dass kürzer ist nicht
1:01:36 geht weil einfach zu viel information in der informationsquelle steckt ja die entropie von der informationskette ist einfach so hoch dass wir nicht
1:01:44 spekulieren können das heißt anschaulich gesehen haben wir mit jedem biz in unserem chor den optimal ausgenutzt und so viel wie möglich informationen da
1:01:56 reingesteckt das heißt aber auch wiederum dass wir wirklich keinerlei redundanz in unserem code haben sobald man in unserem co
1:02:06 eine 0 in der 1 ändert ist die decodierung komplett kaputt das heißt sehr fehleranfällig ist der code außerdem haben wir die ganze zeit
1:02:21 vorausgesetzt dass wir die häufigkeiten der zeichen kennen die wahrscheinlichkeit für die zeichen was man eventuell manchmal nicht kennt aber
1:02:29 wir werden immer davon ausgehen dass wir es kennen es gibt andere codierung verfahren die die statistik also die diese
1:02:38 wahrscheinlichkeit nicht vorher kennen müssen so was wie lempertz die machen wir hier nicht aber ich will sie kurz erwähnt haben
1:02:49 ich möchte noch einmal eine andere codierung vorgehen vorschlagen die besonders effektiv ist wenn unser alphabet sowieso schon nur zwei zeichen
1:03:00 hatte ja wenn unser alphabet nur zwei zeichen hat null und eins oder schwarz und weiß dann können wir nicht mit präfix code nicht besser kodieren als
1:03:14 schwarze null zu geben und weiß nur eins wie sollen wir das anderes mal anders machen wir können ja nicht leere worte das könnten eigentlich dekodieren
1:03:23 trotzdem wollen wir eventuell 01 strings auch komprimieren und da gibt es die sogenannte lauflänge codierung also hier ist als beispiele angegeben wie fax
1:03:33 übertragung ich weiß nicht ob sie wissen was ein fax ist wachs gab es früher da wurde ein papier auf schwarz-weiß eingescannt und wirklich zeile für zeile
1:03:44 gelesen pixel für pixel und da so hat man einen langen string von nullen und einsen gekriegt weißes pixel weiße pixel weiße pixel schwarzes pixel und es wurde
1:03:56 sofort mutiert und rausgeschickt und bei dem anderen faxgerät beim empfänger gerät wieder decodiert und ausgedruckt und da hat man mit lauflänge codierung
1:04:09 arbeitet also üblicherweise wenn sie was einst kennen ist derweil oder faxen wollen ist der weiß anteil sehr viel höher als der schwarz anteil also die
1:04:20 wahrscheinlichkeit für weiß liegt hier sagen sie so was wie 85 ok warum nicht und wir nehmen immer noch an auch wenn es natürlich nicht stimmt das unabhängig
1:04:34 also für jeden folge pixel die wahrscheinlichkeit dass er weiß und schwarz ist unabhängig davon von beat pixel der fonds ja sowas ist jetzt
1:04:45 lauflänge codierung die frage ist wie kann ich platz sparen kodieren obwohl ich nur zwei zeichen habe wie kann ich was cleveres machen als
1:04:54 einfach nur für jedes weiße 0 senden und für ihre schwarzen 1 die idee ist wir könnten blog codes zum beispiel machen wir könnten sagen okay
1:05:07 wir warten k zeichen ab und sehen dann das als neue zeichen an zum beispiel könnten weiß weiß sehen weiß schwarz schwarz weiß schwarz schwarz und uns
1:05:20 dann ausrechnen wie ist die wahrscheinlichkeit dass weiß weiß kommt zum beispiel wenn weiß mit was wirklich gesagt 15 prozent mit 85 prozent
1:05:31 wahrscheinlichkeit ist werden vielleicht weiß mit ein halb oder so und dann könnte ich auf diese längeren blöcke könnte ich half men machen ja dann würde
1:05:41 es jetzt wieder sinn machen es ist eine möglichkeit das ist aber noch nicht die lauflänge codierung die lauflänge codierung sieht anders aus als
1:05:48 das was wirklich passiert auch für faxt aber auch für video codierung die idee ist wir codieren stadt jedes einzelne zeichen
1:06:02 kodieren wir den abstand zum nächsten schwarzen ja also wir gehen davon aus schwarzes sehr
1:06:11 selten weiß es sehr häufig und wenn das hier zum beispiel das ist was unser faxgerät hier ein liest dann würden wir diskutieren als 320 4166 weil
1:06:23 nach drei weisen kommt ein schwarzes werden wieder nach zwei weißen kommt ein schwarzes dann wieder nach null weisen kommt ein schwarzes nach vier weisen und
1:06:32 so weiter ja und dann müssen wir also unser alphabet ist leider nicht nur 0 bis 9 weil diese
1:06:45 abstände könnte natürlich auch 127 sein und wir müssen das unterscheiden von zwölf und sieben also leider ist unser alphabet nicht mehr endlich aber man
1:06:55 macht halt irgendeine obere schranken wie groß kann sein abstand sein [Musik] und das kann man dann wirklich
1:07:03 platzsparend modellen man benötigt aber die wahrscheinlichkeiten für diese ganzen einzelnen abstände so wie sieht es also
1:07:12 aus die wahrscheinlichkeiten für die einzelnen abständen die man erst mal ausrechnen um dann vielleicht hat man oder so zu machen wie gesagt wir gehen
1:07:20 davon aus dass die wahrscheinlichkeiten und also die ereignisse dass das nächste pixel schwarz ist es unabhängig von dem ausgang von dem vorigen pixel
1:07:30 ja da ist die wahrscheinlichkeit dass genau aufeinander folgende weise kommen und dann ein schwarzes nämlich die das produkt der einzel wahrscheinlichkeiten
1:07:39 also die wahrscheinlichkeit für ein wort das hochkar schwarz ist genau wahrscheinlichkeit von weiss mal wahrscheinlichkeit verweis mal
1:07:48 wahrscheinlichkeit von weiß paarmal wahrscheinlichkeit von schwarz das ist ja immer die gleiche wahrscheinlichkeit das ist die gegenwart
1:07:59 ein lichkeit und wenn man das dann ab trägt dann kriegt man eine geometrische verteilung das ist mir sieht so aus also wir können sich vorstellen hier die
1:08:09 wahrscheinlichkeit dass sofort 0 hieß das sofort wieder ein schwarzes kommt wenn zb die wahrscheinlichkeit dass sofort wieder ein schwarzes kommt 80
1:08:20 prozent ist also schwarzes tatsächlich sehr häufig dann ist die wahrscheinlichkeit dass erst ein weißes kommt und dann ein
1:08:29 schwarzes hier oder dass zwei weiße kommt man dann schwarz ist hier und drei weiße und schwarze das wird sehr schnell sehr
1:08:35 klein ja natürlich irgendwie ein bisschen sinnvoller denn wenn sie sich die blaue kurve hier angucken das heißt die
1:08:42 wahrscheinlichkeit dass schwarzes so 20 prozent dass die wahrscheinlichkeit dass erstmal ein weißes kommt und dann schwarz ein bisschen geringer aber es
1:08:50 geht trotzdem relativ schnell gegen null und sowie ruhe zahlen sowie 20 weiße und dann erst ein schwarzes relativ unwahrscheinlich
1:08:58 aber jedes mal in jedem schritt haben wir diese 20 das ein schwarzes kommen könnte und wir müssen jedes mal vorbei schießen
1:09:06 ja loifling codierung nochmal zusammengefasst man kann also ein
1:09:14 schwarz-weiß-bild durch angabe der lauflänge verlustfrei rekonstruieren man braucht ein bisschen sonder behandlung für den letzten blog okay die
1:09:26 lauflänge können aber beliebig groß werden das heißt streng genommen ist unser eingabe alphabet jetzt nicht mehr endlich
1:09:33 wir können aber trotzdem zum beispiel stefano machen werden förderung kommt sie war nicht optimal war aber relativ okay kommt aber mit unendlichen
1:09:44 alphabeten klar ja wenn wir diese abstände solisten können ja für abstand 0 ist zum beispiel die wahrscheinlichkeit für abstand 1 ist die
1:09:53 wahrscheinlichkeit automatisch kleiner wir sind jetzt schon vorsortiert für unsere wissen dass größere abstände immer unwahrscheinlicher werden
1:10:00 und erinnern sie sich anscheinend fahren und wir wollten nur den punkt finden dass bis hierhin ungefähr genauso wahrscheinlich ist wie ab dort
1:10:12 also im ersten schritt ist 50 50 also wann sich diese wahrscheinlichkeiten zuerst zu ungefähr 50 summieren und da können wir schon das den die erste
1:10:21 stelle des codes festsetzen das ist tatsächlich exakt das beispiel aus dem keller und was wir am anfang hatten und so kann man kann celentano auch
1:10:35 unendlich großes alphabet kodieren indem es das codewort erst auf stellt in dem moment wo das zeichen kommt ja gut das ist die lauflänge codierung
1:10:49 das ist die übersicht so ein bisschen aus der informationstheorie die hier in der tg behandelt wird also es geht um die übertragung von informationen von
1:11:01 einer quelle zu einer empfänger wir haben heute über die quellen codierung geredet das heißt in der quelle kommen irgendwelche zeichen mit irgendwelchen
1:11:10 wahrscheinlichkeiten und wir wollen das jetzt erstmal in mit strings übersetzen verlustfrei ja wir wollen bei der codierung keine informationen verlieren
1:11:18 oder es soll halt wieder dick und bierbar sein in dieser codierung wird es dann über irgendeinen kanal geschickt da kommt
1:11:28 dann die kanal kodierung und [Musik] da ist es dann so dass wir davon ausgehen müssen dass dieser kanal
1:11:35 eventuelle fehler behaftet ist dass da irgendwelche störungen drin sind dass die biz das da gibt es verschiedenste arten von fehlern
1:11:44 wir können bis geflickt werden wir können witz verschwinden wir können mit sowie neu eingefügt werden die eigentlich gar nicht da waren also so
1:11:53 eine art von fehler gibt es da ja damit muss man umgehen das heißt die frage ist nachdem wir in der quellen codierung alles schön klein komprimiert
1:12:05 haben dieses neue diesen neuen code wie wollen wir den jetzt nehmen wollen jetzt wieder auf dicken redundanz reinbringen um gegen fehler gewappnet zu sein
1:12:16 und das passiert in der kanal codierung was seine in der nächsten vorlesung gesprochen wird das muss natürlich so sein dass das dann
1:12:24 wieder decodiert werden kann und die fehler erkannt werden vielleicht sogar repariert werden vielleicht mit sicherheit vielleicht mit
1:12:32 einer gewissen wahrscheinlichkeit und so weiter und dann kriegen wir wieder unsere quellen
1:12:37 und den quellcode der muss natürlich wieder zurück decodiert werden beim empfänger so das ist das große bild wir haben heute davon den ersten teil
1:12:46 gemacht erste vorlesung sehen sie den zweiten teil und dann gibt es noch diesen quasi das dritte feld in der
1:12:56 informationstheorie die kryptographie die wir hier aber nicht behandelt werden okay das war's für heute danke