Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

17: Informationstheorie, Entropie, Codierung

Name: 17: Informationstheorie, Entropie, Codierung
Uploaded: 2017-02-07T11:27:28+00:00
Duration: 1 h 7 min 17 s
Channel: KIT Lehre und Wissen
Description: Informationstheorie betrachtet Codierung von Daten je nach Ziel: Quellcodierung zur Kompression, Kanalkodierung zur robusteren Übertragung und …

KIT Lehre und Wissen1:07:17 2.136 Aufrufe veröffentlicht 7. Feb. 2017 Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 374 Zeilen

Herunterladen

ja hallo zusammen heute ist die vorletzte Vorlesung und wir fangen noch mal ein neues Kapitel an
M das Kapitel Informationstheorie da sind die Verbindungen zu den anderen Kapitel nicht so eng wie das bei den vorherigen Kapiteln untereinander war
also bei den vorherigen Kapitel war es ja so dass man insgesamt eigentlich ein ganz rundes äh Themengebiet hat wo
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
Klassen in die sich Sprachen entsprechend ihrer ja Mächtigkeit Ausdrucksfähigkeit einerseits und scherigkeit
andererseits eingruppieren lassen was ist das zugehörige Maschinenmodell was ist das zugehörige Regelsystem zur Erzeugung dieser Sprachen also das war
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
regulären Sprachen betrachtet haben und durchgängig haben wir sowas wie Maschinenmodelle endliche Automaten touringmaschinen kellerautomaten
betrachtet ähm das hier Informationstheorie fällt da sozusagen raus ne eigenes Thema was aber zu den theoretischen Grundlagen der
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
oder von inf von von Worten oder Daten äh mit unterschiedlichen [Musik] ähm aus unterschiedlichen Gründen oder
mit unterschiedlichen Anwendungen äh im Hinterkopf ähm quellcodierung dass war also eine Quelle einer informations für Information eineer Informationsquelle
codieren wollen kanalkcodierung dass wir eben uns auf die Übertragung von äh Daten konzentrieren oder auch Kryptografie um sozusagen sicher
gegenüber Zugriff von außen zu kodieren also noch mal genauer quellcodierung wir wollen am Ausgang einer
Informationsquelle kodieren und zwar so dass Redundanz reduziert wird ist also was sie komprimieren ja also hier steht's
auch ganz genau als Hauptaufgabe Datenkompression ja ähm da kann man jetzt unterscheiden zwischen verlustfreier und verlustbhafteter
Kompression also wir wollen unsere Daten komprimieren um Redundanzen auszu schalten aber möglicherweise noch darüber hinaus eben
um möglichst kurze kodierungslänge möglichst hohe Kompression zu bekommen und da könnte man natürlich sagen na ja wir nehmen
vielleicht auch sogar in Kauf dass ein gewisser Verlust gewisse teil der Information verloren geht
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
warum wir codieren ist kanalkodierung da schauen wir also auf die Übertragung von Daten digitalen Daten und auf den Sachverhalt dass die
Ü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
Redundanz zufügen ja das also sozusagen konträr zu dem was bei der quellcodierung so typischerweise passiert hier würde man also mehr
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
dritte Grund oder Anwendung warum man codieren will ist eben Informationssicherheit ähm also wir wollen ja sozusagen
widerstandsfähig sein Gegenüber unbefugten Lesen von äh übertragener Informationen bzw unbefugten verändern okay
ä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
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
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
Kodierung Link dazu haben wir auch auf der Webseite okay ja Informationstheorie da ist jetzt mal die allererste Frage was
ist Information von formalen Definition für Information also was wir betrachten ist immer so ein Alphabet wie bisher auch ja
ein Alphabet von Zeichen oder Elementen und hier schauen wir immer gleichzeitig auf die Wahrscheinlichkeit dieser Zeichen ja also wenn hier das Alphabet
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
also auch irgendwas anderes sein als eben die Zahlen 1 bis n und die haben jeweils eine Wahrscheinlichkeit das erste Wahrscheinlichkeit P1 zweite
Wahrscheinlichkeit P2 und so weiter bis n hat Wahrscheinlichkeit PN und wir betrachten jetzt also so eine Informationsquelle aus der deutsche
Zeichen heraus ja Zeichen i aus Sigma mit einer Wahrscheinlichkeit PI als im mathematischen Sinn ist das nichts anderes als eine diskrete endliche
Zufallsvariable diese Informationsquelle wir müssen ein klein bisschen mit Wahrscheinlichkeiten auch umgehen aber
nie nicht nicht über das ganz grundlegende hinaus so einfach als Beispiel was gemeint ist mit einer Informationsquelle wo solche Zeichen
auskommen die eine gewisse Wahrscheinlichkeit haben betrachten Sie einen Würfel mit sechs Seiten bei dem jede Seite mit gleicher
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
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
alle sechs Seiten mit gleicher Wahrscheinlichkeit auftreten ist es schwer vorher zu sagen was eigentlich passiert das heißt also der
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
das was dann kommt bringt ihnen sozusagen viel Information ja gegenüber der Situation wir hätten also einen Würfel wo die
Wahrscheinlichkeiten ungleich verteilt sind vor allem die sechs besonders häufig ist also mit hohe Wahrscheinlichkeit kommt also hier
meintwegen mit Wahrscheinlichkeit ein halb kommt und die anderen kommen in der Summe nur mit Wahrscheinlichkeit ein halb also jedes weiter mit der
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
der informations od Erkenntnisgewinn ist kleiner für einen solchen Wurf das sozusagen die Idee die zur Definition von Information führt wir
suchen als also ein Maß für den Erkenntnisgewinn nach Ausgang K ja folgendes kommt raus bei einem Würfelwurf mit Wahrscheinlichkeit PK und
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
der Erkenntnis hoch die Information also Information wird mit IPK
abgezeichnet abgekürzt oder geschrieben PK ist die Wahrscheinlichkeit dass der Ausgang einer Informationsquelle fürs nächst
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
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
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
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
gleich 0 sein und bei einem sicheren Ereignis also wenn man vorher schon weiß was rauskommt haben wir keinen informations oder Erkenntnisgewinn also
da soll die Information sozusagen Null sein ja ähm kleine Veränderungen in der Wahrscheinlichkeit haben also betrachten
zwei Ereignisse äh die nur sehr unterschiedlich Wahrscheinlichkeit haben dann soll entsprechend auch die
Information nur in der Größe sich unwesentlich unterscheiden also kleine Änderungen an der Wahrscheinlichkeit sollen nur kleine
Änderungen an der Information bewirken also wenn man das mathematisch ausdrücken soll Information als eine Funktion in der Wahrscheinlichkeit
stetig und dann haben wir natürlich auch so ein Wunsch wie ähm das eine doppelt so lange Zeichenkette auch doppelt so viel
Information enthalten können soll ähm da passt hervorragend jetzt mal Wahrscheinlichkeitsrechnung im Kopf hat wenn wir sagen okay mach also jetzt eine
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
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
Wahrscheinlichkeiten sich verhalten ein Ereignis hat und folgeereignis und jetzt sagen diese beiden zusammen als Ereignis betrachtet
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
Information einer unabhängigen Zeichenkette gleich der Summe der einzelinform okay und mit den Wünschen im Hinterkopf definieren wir Information
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
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
binärkodierung also hier im Logarithmus muss man hantieren hab nur zur Erinnerung coolwissen Logarithmus x mal y z
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
Zeichenkette die eben aus zweiinandergereihten Zeichenketten besteht das was wir gerade eben gesehen also angewendet haben Logarithmus 1 dur
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
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
Wahrscheinlichkeit ist ja immer kleiner gleich 1 und in der Information gucken wir also jetzt logarimus 1 durch
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
Information also IP Information z Wahrscheinlichkeit P soll sein logarimus P Z Basis 2 typischerweise jetzt mal noch
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
ist die Information eines münzwurfs gleich Logarithmus 1 durch 1 ein/ g= logaritmus 2 = 1 wunderbar wenn wir jetzt kam mal
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
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
Information ist der Begriff der Entropie und was ist das anschaulich formuliert die Entropie ist ein Maß für den mittleren
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
der mittlere Informationsgehalt Folge oder eben wenn das Sigma angucken alle Zeichen in sigσma was der mittlere
Informationsgehalt für Sigma das hängt natürlich von den Wahrscheinlichkeiten ab auch den Streuungen der Wahrscheinlichkeit
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
Strings bezeichnet die Länge und unter der ein String nicht komprimiert werden kann volmogerov Komplexität das ein
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
Schranke war das wie gesagt da gehen wir nicht weiter auf Entropie ja also mittlerer
Informationsgehalt einer Quelle ähm irgendwie klar wie das dann definiert ist wenn die Information äh als Logarithmus 1 durch P von X
definiert ist für ein Zeichen oder ein Element x Entropie bben jetzt immer bei der Basis 2 einer diskreten Zufallsvariable mit
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
die Ereignisse Wahrscheinlichkeit jedes einzelnen Ereignis mal Information des ere und den in mittleren Informationsgehalt ist ja nicht anderes
anders als aufsummiert alle Möglichkeiten wahrscheinlich jeder einzelnen mal dem Informationsgehalt so hier fällt jetzt
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
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
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
hier der Vorfaktor nicht null wäre und hier oben was leich Null stünde bei Division von Null man per Konvention unendlich
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
informations Gehalt so ein Sigma äh das hängt von den Wahrscheinlichkeiten der Elemente aus Sigma ab als Frage ist wann wird der
maximalere Information HT sich auch von der Streuung der Wahrscheinlichkeiten ab man kann leicht einsehen dass die entropi in einer diskreten endlichen
Zufallsvariable mit Z mit nzeichen maximal wird wenn die alle gleich wahrscheinlich sind also Entropie ist ja aufsummiert überall die Zeichen
Wahrscheinlichkeit das Zeichen mal Logarithmus 1 durch Wahrscheinlichkeit des Zeichens das wird am größten wenn die alle gleich wahrscheinlich und dann
kommt gerade Log n Anzahl der zeen bei der deutschen Sprache z.B ist es nicht so dass maximum angenommen wird
die Entropie der deutschen Sprache liegt bei 4,1 ausrechnen wenn man die
Wahrscheinlichkeiten der einzelnen Buchstaben anschaut ja in deutscher deutschem Text äh bei 26 Buchstaben
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
äh angibt aufgetragen also bei einer Münze realen Münze ist für beide Seiten Wahrscheinlichkeit ein halb würde man
gerade hier landen ne Wahrscheinlichkeit halb also Zahl ist die Wahrscheinlichkeit ein halb und wenn die ideale Münze ideal ist
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
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
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
Wahrscheinlichkeit zwischen 0 und 1 für Zahl eben dieses h von X gleich minus Wahrscheinlichkeit für Zahl Wahrscheinlichkeit für Zahlen
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
kodieren an und wir wollen jetzt also Soz sagen dies Thema quellcodierung angucken also wir wollen platzparend kodieren oder komprimieren
ja betrachten wieder eine Informationsquelle alsorete wahrscheinlichkeits Zufallsvariable x die Zeichen i aus
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
über 01 zur Verfügung Frage ist wie können wir Sigma ohne informations kutieren so dass die erwartete Länge der Ausgabe
möglichst klein ist komprimiert formal also wir ordnen jedem Zeichen I a Sigma ein codwort Z zu und
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
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
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
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
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
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
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
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
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
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
Knoten haben die maximal zwei ausführenden Kanten auch nicht beide Null oder nicht beide 1 und hier weiteres ja B hat den Code
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
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
demem kürzesten Weg von der Wurzel zu dem Knoten okay und wir interessieren uns ja für die mittlere
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
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
Wahrscheinlichkeit von i mal kurwort Länge von i also ni und das entspricht ja hier nichts anderem als
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
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
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
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
codierungsbaum kodwortlänge für alle gleich ist bzw mitlere K genauicht m natürlich klar bei so einem Baum dass
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
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
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
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
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
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
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
ä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
auf unterschiedlichen Ebenen hängen dass sie auch unterschiedliche cotwortlängen haben bei unterschiedlichen codwortlängen wäre jetzt mal prinzipiell
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
und würden dann sozusagen kurz aneinander also Zeichen als String übertragen eine Folge von Zeichen als dring übertragen und
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
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
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
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
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
auch wenn die Bäume nicht ausgeglichen sind also die [Musik] Blätter auf verschiedenen Ebenen hängen
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
morse alphabet das hat variable Länge also die Buchstaben das unseres Alphabets die sind eben codiert es gibt erstmal zwei Zeichen
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
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
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
dritte Zeichen so also moruse Alphabet ist jetzt ein Zeichen für eines Kodierung die nicht präfriix ist nach ihrer Sprechweise und
sowas würde man aber ganz gerne so jetzt erstmal ist ohne das was beweisen in dem Zusammenhang auch das chche quellcodierungstheorem interessant also
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
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
können wir erzwingen dass die mittlere kotwortlänge kürzer wird ja und Shanon quellcodierungstheorem sagt wenn Sie also eine diskrete endliche
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
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
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
gesagt beweisen okay so jetzt ein erster erstes Beispiel einer ganz meinen Augen ganz witzigen Kodierung mit variabler
codwortlänge die präfixcode ist und die so ist dass man diese Idee häufige häufig vorkommende Zeichen
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
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
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
erste und so weiter und die Wahrscheinlichkeiten der Elemente wir sind also jetzt hier durchnummeriert entsprechend iher
Wahrscheinlichkeit das erste ist das wahrscheinlichste zweite zweitwahrscheinlichste und so weiter ja also die Wahrscheinlichkeit so wie wir
hier durchnummeriert haben nimmt von oben nach unten ab und die Frage ist welche Codeworte über 01
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
wahrscheinlich in möglichst kurz kodiert ja ich gebe als erstes Zeichen den oberen vier eine Null und den
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
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
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
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
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
sind ungefähr gleich wahrscheinlich wie die unteren vier oder anders ausgedrückt die oberen vier auf Wahrscheinlichkeiten aufsummiert minus die unteren vier
Wahrscheinlichkeiten aufsummiert ist am dem Betrage nach am kleinsten unter allen Möglichkeiten wie ich hier sozusagen Unterteile ne also
ich unterteile da wo die Wahrscheinlichkeit der ober der Unterteilung aufsummiert minus die Wahrscheinlichkeit der unter der
Unterteilung aufsummierten äh dem Betrage nach minimal ist und dann gebe ich einfach den oberen als erstes Zeichen des codeworts entsprechend
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
zusammen ungefähr Wahrscheinlichkeit ein halb guck nach wo muss ich unterteilen dass die Differenz der Wahrscheinlichkeiten von dem oberen und
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
den ersten zwei Elementen und da gebe ich einfach als zweites Zeichen der Codierung eine Null und bei den weniger wahrscheinliches
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
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
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
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
wieder auf gucke jetzt weiter wann bin ich hier erstmal über ein Viertel die kriegen entsprechend Elemente kriegen als
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
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
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
aufgeschrieben also den Fano Kodierung ich habe meine zeichenliste Z Zeichen Z1 bis ZK mit Wahrscheinlichkeiten ein bis PK und was
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
entsprechende Codierung in an und dann geht's eben folgendermaßen ich habe also meine äh Element aus z immer vorliegen
sortiert nach Wahrscheinlichkeiten absteigender Richtung und ich trenne im immer auf in Z1 und Z2 so dass die Wahrscheinlichkeiten der Elemente aus Z1
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
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
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
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
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
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
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
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
Fano Codierung bezüglich Minimierung der mittleren codewortlänge optimal ist weil das einfach nicht der Fall ist ist gut aber
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
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
okay hafman Codierung wie funktioniert die haben ja wieder Elemente eine Sigma mit
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
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
jetzt folgendermaßen vorgegangen wir betrachten uns die zwei unwahrscheinlichsten und passen die jetzt wieder auf als Kinder eines Knoten
im kodierungsbaums wobei ja der untere unwahrscheinlichere wir haben die
gleiche Wahrscheinlichkeit da ist das dann beliebig aberb ich festgelegt dass man eins kriegt als letztes Zeichen und das da
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
gerade Summe dieser beiden Wahrscheinlichkeit ist so und dann vergessen wir die zwei und machen weiter mit den Knoten die wir jetzt haben und
den entsprechenden Wahrscheinlichkeiten jetzt gucken wir wieder was sind die zwei unwahrscheinlichsten das ist dieses und das sind
dieser neuentststandene Knoten und der Knoten zu e die fassen wir wieder zusammen geben den einen Elternknoten der
unwahrscheinlichere kriegt eine Eins davor gehängt der wahrscheinlichere eine Null wir führen neuen Elternknoten ein den Wahrscheinlichkeit Summe der
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
unwahrscheinlichsten was sind die be heißt also die beiden werden zusammengefasst Elternknoten kriegt als Wahrscheinlichkeit die Summe der beiden
einzelwahrscheinlichkeiten und auch wieder das unwahrscheinlichere kriegt eine ein das wahrscheinlichere ull dann wieder die zwei
unwahrscheinlichsten das ist jetzt der Knoten und der Knoten dann zusammengefasst die Summe der Wahrscheinlichkeiten ist 0,6 für den
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
jetzt dem eine Null gegeben und dem eine ein weil der obere weniger wahrscheinlich ist als der untere hier haben wir jetzt ganz genauso
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
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
unwahrscheinlichen noch mal B hat z.B das codwort 1 e hat das codwort 0 1 0 sehe das codwort 0 1 und der
Algorithmus dazu also wir haben unsere Zeichen unsere entzeichen mit Wahrscheinlichkeiten P1 bis PN und wir bauen also auf den Baum zum hfman Code
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
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
folgendermaßen borgehen von den noch verbleibenden Elementen aus Q extrahieren wir das un wahrscheinlichste Element x ja hat wahrscheinlich halt px
und äh sagen das soll linker Nachfolger von dem neu einzuführenden Knoten Z sein und dann extrahieren wir das nächste unwahrscheinlichste Element
äh und machen das zum rechten Nachfolger von dem neuen Knoten dem neuen Knoten geben wir als Wahrscheinlichkeit gerade Summe der Wahrscheinlichkeiten dieser
beiden Knoten die wir gerade ähm bestimmt haben äh fügen den neullen Knoten ein und
ä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
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
äh deshalb mal aufgepasst der Baum hier sieht jetzt nicht so aus wie wie der Baum bespinnt wird nach dem Algorithmus weil der da
oben der müsste eigentlich hier unten hin sagen als der wahrscheinlichere dann nicht rechter sondern linker Nachfolger von dem
als weniger wahrscheinliche nicht rechter sondern linkerg also nach rechts geht's immer mit null und nach links immer mit ein
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
berechnet ein codierungsbaum wo rauskommt dass die mittlere kotwortlänge minimal ist und um das zu beweisen brauchen wir
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
Y aus σma sein jetzt die zwei unwahrscheinlichsten Zeichen oder wenn wir jetzt eben mehrere Zeichen haben die gleich unwahrscheinlich sind eben zwei
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
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
jetzt schon stark da drauf hin wie dann der Beweis ähm unseres Satzes dass der hafman Algorithmus minimale mittlere
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
zwei unwahrscheinlichsten an und dann lassen wir die mal weg und Induktionsvoraussetzung gilt auf den Baum davor und dann müssen wir nur
gucken wie kriegen wir die zwei untersten da wieder rein ne also ähm also jetzt die Beweis zu diesem Lemmer dass diese beiden
ähm un oder zwei unwahrscheinlichste ähm in so einem dass es für die das es insgesamt einen einen kodierungsbaum mit minimaler
kutwortlänge gibt wo die zwei unwahrscheinlichsten denelbenen haben äh betrachten wir einfach mal einen beliebigen
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
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
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
anders ne also nicht unter demselben direkt unter dem selben Knoten wie das X so jetzt erster Fall der vorgängerknoten
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
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
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
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
ähm und wir betrachten mal so ein nachffahren von dem Z der maximale Tiefe hat maximal tief hängt das W
ähm weil t Strich optimal ist müsste also dann die Wahrscheinlichkeit von dem auch kleiner gleich der Wahrscheinlichkeit von PX sein
ähm andererseits ist ja px1 mit minimaler Wahrscheinlichkeit das heißt also das PW muss g=ich PX sein
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
den Fall Z hat genau zwei Nachkommen bei der andere Nachfolge na andere Nachfahre des unmittelbaren Vorgängers von X dieses Q
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
einen Baum bekommen der bezüglich mittlerer kotwortlänge genauso ist und wo X und Y unter genau demselben Knoten
hängen wollen Q mit Y tauschen wenn u und Y beide gleiche Höhe haben geht das ja auch
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
wir auch tauschen das auch okay das heißt also das können wir auf jeden Fall äh bewerkstelligen ähm dass
wir zu so einem alpab B Sigma mit Wahrscheinlichkeiten P1 bis PN und zwei unwahrscheinlichsten Zeichen X und Y einen optimalen codierungsbau also
codierungsbaum mit minimaler codwortlänge betrachten bei denen X und Y genau denselben Elternknoten das können wir immer voraussetzen also wir
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
jetzt um per Induktion über die Anzahl der Zeichen unseres Alphabets zu beweisen dass der haftmancode optimal ist
ja die mittlere kotwortlänge minimal ist also der entsprech codierungsbaum genauso ist wie die gerade betrachtet haben also Induktion über die Anzahl der
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
Zeichens okay das heißt aber nehmen jetzt mal an dass der haffenalgorithmus ein kodierungsbaum zum kodierungsbaum gehört
wo gilt die mittlere codwortlänge ist min mal wenn immer σma kleiner gleich n ist ja für alle möglichen
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
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
wir mal F F von T wir machen einen widerspruchsbeweis wenn wir annehmen das wäre nicht so dass der
kodierungsbaum zum hafman Code hier für optimal ist dann führen wir das zum Widers also mit Th Huf bezeichnen wir den
hafmenbaum für unser Sigma mit den n + 1 Elementen und den Wahrscheinlichkeiten P und wir betrachten andererseits ein optimalen Baum ja
topt zu demselben σ P ein kodierungsbaum mit bessere mittlere kodierungslänge wir nehmen an dass F die mittlere
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
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
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
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
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
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
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
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
entsprechenden Bäume die sich aus topt und T geben wenn ich X und Y weglasse m also in beiden nenne ich sozusagen den
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
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
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
unwahrscheinlichsten Elemente wenn ich da eine Auswahl habe gerade wieder t strichhuf bekommen für Sie ich und genauso ist t STR opt ein
codierungsbaum für strich mit den neuen Wahrscheinlichkeiten ja okay und jetzt gucke ich mir da die mittlere
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
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
Huf mal der Wahrscheinlichkeit von Z und in T ist das genauso jetzt ist dummerweise so dass die entscheidenden zwei Berechnungsschritte hier nicht auf
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
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
+ 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
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
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 -
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
Induktionsvoraussetzung ist thu optimal okay ja gut jetzt können wir auch noch ein bisschen über Nachteile von Hoffmann Codierung sprechen
haben unterschiedliche codwortlängen das führt natürlich zu unterschiedlichen Bitraten und eben bei der Dekodierung zu
Verzögerung das ist jetzt was was also generell gegen das spricht was man eigentlich erzielen will wenn man mittlere die mittlere kurwortlänge
minimieren will wenn man mittlere kurutwortlänge minimieren will und eine Situation hat wo die Wahrscheinlichkeiten der Zeichen stark
differgieren dann kommt man automatisch dazu dass man sehr unterschiedlich kotwen len hat also tut sich dann immer derselbe Nachteil auf
ähm und insgesamt ist natürlich auch Datenkompression etwas was auch wieder Nachteile mit sich bringt also Datenkompression heißt ja ich reduziere
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
Seite auch die Fehleranfälligkeit wenn wir später gucken wie kann man die fehleranfändlichkeit für die Übertragung
reduzieren da würde man wieder Redundanz einführen das ist sind einfach konträre Ziele möglichst kurz kodieren andererseits fehleranfällig
verringern und beim hafman Code wird natürlich vorausgesetzt dass ich weiß wie die Wahrscheinlichkeiten der einzelnen Zeichen sind gibt andere
Codierungsverfahren wo man so ein a priori wissen nicht voraussetzt etwa l okay so jetzt wollen wir lauflängenkodierung betrachten und dazu
folgendes Szenario wir betrachten die Übertragung von ähm dieser Folie übers Faxgerät ja ähm da werden einfach weiße Blätter mit
schwarzen Pixeln übertragen ne also einfach äh kann das als ein Bild auffassen mit weißen und schwarzen Bildelementen und natürlich ist
üblicherweise die Anzahl der weißen Pixel Ex deutlich größer als die Anzahl der schwarzen Pixel das ist im allgemeinen natürlich nicht
[Musik] voneinander unabhängig ja wo schwarze und wo weiße Pixel sind bei einem richtigen Bild sage ich mal wir nehmen
jetzt einfach der einfache teilber an das ist aber unwahrscheinlich unabhängig also das sind einfach was wir übertragen wollen
sind einfach weiße Blätter mit schwarzen Pixeln drauf wenn man z.B 15%zentigen schwerzungsgrad hat ergäbe sich als intropie
ähm Wahrscheinlichkeit für minus Wahrscheinlichkeit für Schwarz mal Logarithmus Wahrscheinlichkeit für Schwarz minus Wahrscheinlichkeit für nee
umgekehrt Wahrscheinlichkeit für weiß minus Wahrscheinlichkeit für weiß mal logarithmuswahrscheinlichkeit für weiß minus Wahrscheinlichkeit für Schwarz
minus Logarithmus für Wahrscheinlichkeit für Schwarz äh gleich ja da kommt hier ungefähr 0,61 raus und bei einer äh
Codierung würde man also so eine Art mittlere codwortlänge erwarten jetzt eben die Frage wie ist eine platzsparende
Codierung von dem Alphabet das nur zwei Zeichen hat überhaupt möglich ja wie kann man das machen und da gibt's jetzt folgende
Idee Idee sogenannte block codes zu verwenden also es werden immer kzeichen als Block zusammen befasst und dieser Block dann
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ß
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
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
weiß schwachz schwarzweiß schwarz schwarz weiß schwarz schwarzweiß jeweils zwe schwarz schwarz einehel dann bekämen man
bei haftman diese codierungus mit codworten unterschiedlicher Länge und optimaler mittlerer
kotwort jetzt könnte man auch folgendes machen ähm man äh passt in Blöcke unterschiedlicher Länge zusammen und
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
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ß
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
folgende schwarze an also hier wäre das erstmal kommen drei weiße bevor das erste schwarz kommt also das erste sozusagen
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
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
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
Codierung von dem hier eine geeignete binärcodierung der Abstände zwischen den schwarzen erfolgen ähm ja das die Abstände können im
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
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
Anzahl der weißen da hinten dran ne wie am Anfang auch und dann eine Null ne und dann ach so
ä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
Null und dann Abstand zwischen dem ersten und zweiten und so weiter und dann kommt noch mal der Abstand zwischen dem letzten schwachs
und dem Ende ja müsste ich dann hier noch eine Null dran hängen ja ja ja okay okay jetzt da haben sie
recht okay ja das ist dann einfach auf der Folie nicht korrekt so äh und dafür muss man jetzt für eine
Kodierung die in Abhängigkeiten der Wahrscheinlichkeiten eben quotwörter produziert die so sind dass die unwahrscheinlichen
lang und die wahrscheinlichen kurzen die Wahrscheinlichkeiten für die einzelnen Abstände wissen jetzt haben wir ja angenommen die
Bildpunkte sind voneinander unabhängig dann sei also PL die Wahrscheinlichkeit für einen Block aus l aufeinander folgende weiße Bildpunkte
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
natürlich nichts anderes als die Wahrscheinlichkeit von W hoch l mal Wahrscheinlichkeit von S das heißt wir kriegen hier so eine
geometrische Verteilung wie hier und jetzt gucken wir uns das mal konkret an ja also hier haben wir die Abstände hier
die Wahrscheinlichkeiten und jetzt benutzen wir einfach shenon Fano um die Elemente entsprechend der Wahrscheinlichkeiten zu
codieren ja also für den äh gucken wier Wahrscheinlichkeiten an unterteilen wieder sozusagen die die obere äh oberen Wahrscheinlichkeiten bis
wir zur Wahrscheinlichkeit ein halb kommen untere Wahrscheinlichkeiten die oberen kriegen als erstes Null die unteren ein und so weiter
ä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
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
mit anzufangen ich hatte mir überlegt dass wir praktisch bis hierhin heute besprechen haben sie mal wieder ein bisschen
früher Schluss

Zum Nachlesen

Entropie (Informationstheorie)Datenkompression und Entropie. Bearbeiten. Die Entropiekodierung ist ein Kompressionsalgorithmus, um Daten verlustfrei zu komprimieren. In diesem Zusammenhang … Huffman-KodierungDie Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of … InformationsgehaltDer Informationsgehalt (oder auch Überraschungswert) einer Nachricht ist eine logarithmische Größe, die angibt, wie viel Information in dieser Nachricht … InformationstheorieEs beschreibt die theoretische Obergrenze der Kanalkapazität, also die maximale Datenübertragungsrate, die ein Übertragungskanal in Abhängigkeit von Bandbreite …