Digitale Information = Bitsequenzen Ein Bit ist eine atomare
Information Einen Informationsgehalt bekommt ein Bit, wenn es etwas
reprsentiert z. B. schwanger / nicht schwanger Mehrere Bits knnen
komplexere Informationen reprsentieren z.B. Zahlen, Farben,... (oft
Datentypen) Dazu muss man wissen, wofr eine bestimmte Bitsequenz
(=Zeichen) steht... und das wird komplizierter, wenn es nicht nur
um eine Farbe, einen Buchstaben geht, sondern bspw. um ein ganzes
Dokument Information existiert nicht in reiner Form eine
Formulierung von Information kann fr vieles stehen (reprsentieren)
1 oder 0 Sein oder nicht Sein true oder false
Folie 4
Definition (Daten-/Datei-) Format: Ein Format ist eine
spezifische Anordnung von Daten (Bits) fr Speicherung,
Weiterverarbeitung, Ausgabe, etc. Ein Format definiert so etwas wie
eine Erwartungshaltung, in welcher Form (digitale) Information
vorliegt. Das betrifft 1. die Anordnung (wie teilt man die Sequenz
in Zeichen auf?) 2. die Codierung (fr was steht ein
Zeichen/Bitsequenz?) Diese grsstenteils impliziten (also nicht in
der Sequenz enthaltenen) Informationen mssen allen Beteiligten
bekannt sein nur so kann man herausfinden, wofr die expliziten
Informationen (Bitsequenz) stehen
Folie 5
Universalitt vs. Speicherplatzbedarf Ein Format macht nur Sinn,
wenn es (fr einen gewissen Bereich) universell ist, also bspw. alle
Fotos speichern kann, nicht nur die grnen Andererseits bentigt
diese Universalitt Speicherplatz und ist nicht immer einfach
festzulegen: macht es beispielsweise Sinn, in.DOC Unicode zu
benutzen, nur damit die Chinesen dasselbe Format haben?... oder
sollte man Meta-Informationen einbauen, so dass z.B. die Codierung
ausgetauscht oder explizit mitgeschickt werden kann?
Folie 6
Digitale Reprsentation von Schach Was ist wichtig? nur die
Information, die einen Spielstande eindeutig definiert Was ist
mglich? alle Spielstnde mssen reprsentiert werden knnen Welche
Informationen codiert man (explizit) als Zeichen, welche (implizit)
in der Anordnung? es geht nicht um maximale Effizienz, man muss
aber trotzdem keinen Speicherplatz verschwenden Vorschlge? Wie
viele Bits brauchen Sie? oder: ein universeller digitale Koffer fr
Schach
Folie 7
Ein Schach Format (.sch), 257 BIT Das erste Bit gibt an, wer am
Zug ist (1=schwarz, 0=weiss) Die folgenden 256 Bit reprsentieren
die Belegung der 64 Felder, mit jeweils 4 Bit pro Feld (nummeriert
zeilenweise von links nach rechts, dann spaltenweise von oben nach
unten). Das erste Bit pro Feld steht fr die Farbe der Figur: Die
letzten 3 Bit pro Feld stehen fr die Figur, die hier steht: 1 =
schwarz 000 = leer 001 = Bauer 010 = Turm 011 = Springer 0 = weiss
100 = Pferd 101 = Dame 110 = Knig 111 = steht fr nichts
Folie 8
Ein Format fr Schieber-Jass Das Spiel: 4 Spieler haben zu
Beginn je 9 Karten, spielen sie reihum aus, und nach jeder Runde
wandern 4 Karten auf den einen oder anderen Stapel von gespielten
Karten. Aufgabe: erfinden Sie ein Format, mit dem jeder mgliche
Zustand des Spiels binr reprsentiert werden kann. Formulieren Sie
die von Ihnen erfundene Codierung so, dass ein anderer Schler eine
entsprechende Bitsequenz in den Spielzustand zurckbersetzen knnte
Geben Sie an, wie viele Bits fr die Speicherung eines Spielzustands
bentigt werden
Folie 9
Und woher weiss der Computer, welches Format eine Datei hat?
Die meisten Datei-Formate haben einen header, in dem 1. sie sich
vorstellen und 2. zustzliche Angaben zur Formatierung machen, z.B.
Version/Variation des Formats Parameter allgemeine
Zusatzinformationen 1. Endung 2. Header Diese Informationen sagen
dem Computer, welche Brille er anziehen muss
Folie 10
Beispiel.rtf {
\rtf1\ansi\ansicpg1252\cocoartf1038\cocoasubrtf250
{\fonttbl\f0\fnil\fcharset0 GoudyOldStyleT-Regular;}
{\colortbl;\red255\green255\blue255;\red6\green10\blue58;}
\paperw11900\paperh16840\margl1440\margr1440\vieww9000\viewh8
400\viewkind0
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\t
x5669\tx6236\tx6803\ql\qnatural\pardirnatural \f0\fs36 \cf2 Lirum
\b larum \b0 L\ f6ffelstiel } ffnen mit Hex-Editor, z.B.
http://www.onlinehexeditor.com/ ffnen mit Hex-Editor, z.B.
http://www.onlinehexeditor.com/
Folie 11
RTF (Rich Text Format) Entwickelt von Microsoft, aber frei
verfgbar Basierend auf Standard-Codetabellen (ASCII, UNICODE)
Lesbar von allen gngigen Texteditoren, wobei u.U. Teile der
Layout-Information ignoriert werden
Folie 12
RTF Spezifikationen Syntax: { } Der header beinhalten
Kontrollwrter, die mit Backslash anfangen und mit Leerzeichen
getrennt werden Im header wird zustzliche Layoutinformation
reprsentiert, z.B. Schriftfarbe oder Schrifttyp RTF kann mit
verschiedenen Versionen von ASCII oder UNICODE Zeichen umgehen
(Meta-Information im header) Bei RTF wird implizit angenommen, dass
die entsprechenden Codetabellen verfgbar sind, und dass die Blcke
innerhalb der Bitsequenz in der richtigen Reihenfolge
vorliegen
Folie 13
Zusammenfassung RTF kann mehr als TXT und weniger als DOC, das
ist seine digitale Nische RTF ermglicht die Reprsentation von
allgemeinen Layoutinformation durch standardisierte Kontrollwrter
im header Das Layout fr Textteile geschieht durch Auszeichnung des
Dokuments mit Kontrollwrtern im Text (wie HTML)
Folie 14
Bildinformation in einem etwas speziellen Format Die Brille
implementiert die Decodierung Das Format gibt an, welche Brille man
braucht Eine Analogie zur Zusammenfassung
Folie 15
Konzepte Beispiele Format Header Endung Zeichen explizite &
implizite Bestandteile Universalitt Eigene Formate fr
Spiele.rtf
Folie 16 ffnen mit Hex-Editor, z.B.
http://www.onlinehexeditor.com/ ffnen mit Hex-Editor, z.B.
http://www.onlinehexeditor.com/">
Datei: Raetsel ffnen mit Hex-Editor, z.B.
http://www.onlinehexeditor.com/ ffnen mit Hex-Editor, z.B.
http://www.onlinehexeditor.com/
Folie 17
Grafikformate und verlustbehaftete Komprimierung
Folie 18
Wie viel Information ist ntig? Anfangs- und Endpunkt definieren
die Linie eindeutig Mittelpunkt und Radius definieren den Kreis
eindeutig Die Eckpunkte definieren das Polygon eindeutig
Folie 19
Vektorgrafik Mit allgemeinen Kurven (z.B. Bezier Kurven) und
noch mehr Parametern kann man jede beliebige Form berechen kann zu
extrem geringen Dateigrssen fhren Vektorgrafiken sind beliebig
skalierbar 26 Kb
Folie 20
Folie 21
Reine Vektorgrafikformate Sind nicht weit verbreitet, meist
proprietr, in Verbindung mit einem Editor z.B. Adobe Illustrator
(.ai) Ausnahme: SVG (scalable vector graphics) Benutzt werden
Vektorgrafiken aber oft in Kombination, z.B. einzelne Ebenen in
Photoshop Vektor-Fonts Zeichnungen in Word oder Powerpoint in
Druckformaten (PDF, EPS) Interessant:.pptx hacken
Reine Rastergrafikformate Produzieren sehr grosse Dateien (aber
verlustfrei) Beispiele.bmp nur Windows, veraltet.pict nur MAC,
veraltet.tiff (wenn ohne Komprimierung) Bestes Format fr sehr hohe
Qualitt, blich beim Drucken RAW reine Sensordaten, fr jede Kamera
anders
Folie 28
RAW ist abhngig von Kamerasensor bzw. Hersteller DNG ist Adobes
Versuch fr ein herstellerbergreifendes Standard- RAW-Format
RAW-Dateien haben eine hhere Farbtiefe (10 16 Bit) RAW-Dateien
richten sich nach dem geomet- rischen Layout des Sensors, meist
Bayer-Matrix Arbeitsschritte wie Demosaicing, Rauschunterdrckung,
Weissabgleich, oder Tonwertkorrekturen knnen mit RAW- Daten in der
Nachbearbeitung festgelegt werdenDemosaicing Verschieden
Algorithmen fhren zu leicht unterschiedlichen Ergebnissen Bei
starken Manipulationen verhilft die Farbtiefe zu besseren
Ergebnissen
Folie 29
Die blichsten Grafikformate (.jpg &.gif) Komprimieren die
Information reiner Rastergrafiken Nehmen ggf. Informationsverlust
in Kauf (meist variabel) Anstze zum (verlustbehafteten)
Komprimieren: 1. mehrere Pixel zusammenfassen 2. Speicherplatz
sparen bei der Reprsentation von Farben Dabei geht es immer darum,
mglichst die Informationen zu verlieren, die (optisch) keinen
grossen Unterschied machen
Formatentscheidungen Sie wollen mit ihrer Digitalkamera ein
Photo aufnehmen, um dann Sie dann im Internet einen Abzug in
Postergrsse zu bestellen. Wie gehen Sie optimalerweise vor? Ein
Freund von ihnen hat gehrt, dass Vektorgraphiken wenig
Speicherplatz brauchen und trotzdem skalierbar sind. Er hat ein
Logo fr seine Webseite gezeichnet (von Hand) und fragt Sie, wie er
es in ein Vektorformat umwandelt. Was raten Sie ihm? Sie wollen
ihren Freunden ein paar Urlaubsbilder per E-Mail schicken. Wie
gehen Sie vor? Fr die Maturazeitung verfassen Sie einen Artikel, in
dem sie auch einige statistische Grafiken zeigen wollen. Worauf
achten Sie?
Folie 35
Zusammenfassung 1. Ein Bild besteht aus Pixeln (Rastergrafik)
Auflsung, Farbraum, Farbtiefe, Transparenz? (ggf.) verlustbehaftete
Komprimierung: 1. Farben indizieren (.gif) 2. Farbtiefe (in
LAB-Farbraum) reduzieren (.jpg) 3. Blcke gleicher Pixel
zusammenfassen (.gif) 4. Farbverlufe zusammenfassen (.jpg) 2. Ein
Bild besteht aus geometrischen Objekten, bzw. Kurven (Vektorgrafik)
Wie beschreibt man die Formen, welche Parameter gibt es?
Folie 36
(Grafik-) Formate, berblick BMP (Rastergrafik, Farbrume
erwhnen) JPEG(Grafik mit Kompression) GIF (Grafik mit Kompression)
PNG (Grafik mit Kompression, inkl. Alphakanal) TIFF (Grafik mit
optionaler Kompression) SVG(Vektorgrafik) EPS (Druckerformat,
Rastergrafik + Vektorgrafik) PDF (Grafik + Text) ZIP*
(Komprimierung) RAR (Archivierung) MIDI (Musik) MP3(Musik)
AVI(Video) MOV (Video) MPEG (Video) Warum gibt es dieses Format?
Wie funktioniert dieses Format?
Folie 37
Digitales Koffer packen bzw. verlustfreie Komprimierung
Folie 38
Aufgabenstellung: Sie wollen ihrem Freund eine Text-Botschaft
bermitteln, knnen dazu aber nur Zahlen verwenden (entscheiden Sie
selbst ob sie Dezimal- oder Binrzahlen benutzen). berlegen Sie sich
eine Methode, wie die gegebene Botschaft mglichst genau und
mglichst kompakt in Zahlen bersetzt werden kann. Dann erstellen Sie
zwei Textdokumente: 1. Ein Dokument soll nur die Zahlenfolge
enthalten 2. Im anderen Dokument formulieren Sie eine Anleitung,
mit deren Hilfe ihr Freund die ursprngliche Botschaft aus der
Zahlenfolge rekonstruieren kann
Folie 39
Auswertung Hat es geklappt? Was war schwierig? Welche
Informationen wurden bermittelt? (genau?) Wie viele Zahlen waren
ntig? (kompakt?) Welche anderen Botschaften knnten so verschickt
werden? Welche grundstzliche Idee steckt hinter dieser
Methode?
Folie 40
Arbeitsauftrag Ihr Ziel ist herauszufinden, wie die Huffman
Codierung funktioniert und sie selbst anwenden zu knnen Benutzen
Sie dazu das Applet HuffmanApplet.jarHuffmanApplet.jar
Experimentieren Sie mit dem Applet (nur Huffman Code) und versuchen
Sie, die Fragen im Arbeitsblatt AB Huffman Komprimierung.doc zu
beantwortenAB Huffman Komprimierung.doc
Folie 41
Besprechung Suchen Sie sich einen Partner und tauschen Sie ihre
Ergebnisse aus Notieren Sie alles, was ihnen beiden noch unklar ist
Knnen Sie die grundstzliche Idee formulieren?
Prfixfreie Telefonnummern WasTelefonnummer Allgemeiner
Notruf112 Feuerwehrnotruf118 Polizeinotruf117 Sanittsnotruf144 Rega
(Rettungshelikopter)1414 Pannenhilfe140 Toxikologisches Institut
(bei Vergiftungen)145 Auch normale Telefonnummern erfllen die
Fano-Bedingung, z.B. 0789218418 wenn das eine gltige Nummer ist
078921841 dann kann es diese 07892184182 oder diese nicht
geben
Folie 45
Information Genau & Kompakt Codieren Komprimieren Koffer (~
Format) so whlen, dass alles eingepackt werden kann, was man im
Urlaub vielleicht brauchen knnte Ziel: Der Koffer soll fr alle
Urlaube geeignet sein! Effizient packen, so dass mglichst wenig
Luft im Koffer bleibt kann davon abhngen, was genau eingepackt
wurde! Ziel: Der Koffer fr diesen Urlaub soll mglichst klein
werden! Koffer packen (Komprimieren von Information)
Folie 46
Effizientes Packen von Buchstaben 1. Codieren von Buchstaben
als binre Codewrter ASCII Code 2. Komprimieren der Bitsequenz z.B.
Huffman Codierung krzere Sequenz + neue Codewrter 3. Speichern oder
bermitteln 4. Dekomprimieren 5. Decodieren -> Darstellen
Folie 47
Komprimierung von Buchstaben originale Nachricht (z.B. ASCII)
codierte Nachricht + Liste (z.B. Huffman) codierte Nachricht +
Liste (z.B. Huffman) originale Nachricht (z.B. ASCII) Komprimieren,
z.B. mit Huffman Codierung Dekomprimieren, z.B. mit Huffman
Decodierung speichern /verschicken Welche Informationen braucht es
hier?
Huffman Decodierung Die binre Nachricht:
0100111101001110010100111110 Die Codewrter: e=110 d=111 o=00 p=010
s=011 u=100 c=101
Folie 51
Und was daran war jetzt prfixfrei ? o=00 p=010 s=011 u=100
c=101 e=110 d=111
Folie 52
Komprimierung allgemein originale Nachricht (z.B. ASCII)
codierte Nachricht + Liste (z.B. Huffman) codierte Nachricht +
Liste (z.B. Huffman) originale Nachricht (z.B. ASCII) Komprimieren,
z.B. mit Huffman Codierung Dekomprimieren, z.B. mit Huffman
Decodierung speichern /verschicken Welche Informationen braucht es
hier?
Folie 53
Grundstzliche Idee bei Huffman Hufige Zeichen (Buchstaben)
werden in kurze Codewrter bersetzt (Frequenzcodierung) Im
Binrsystem funktioniert das nur, wenn der entstehende Code (die
Codewrter) prfixfrei ist! Die Bumchen-Taktik (eigentlich ein
Algorithmus) produziert eine Codierung, die diese beiden Prinzipien
optimal verbindet. (allerdings ist der resultierende
Komprimierungsgrad nur annhernd optimal, noch effizienter ist die
Arithmetische Codierung)
Folie 54
Pseudocode... ist eine sprachliche Mischung aus natrlicher
Sprache, mathematischer Notation und einer hheren Programmier-
sprache arrayMax(A, n) // Input: Ein Array A, der n Integer Werte
enthlt // Output: Das maximale Element in A currentMax = A[0] for i
= 1 to n - 1 if currentMax < A[i] currentMax = A[i] end return
currentMax
Folie 55
decodieren(nachricht_bin, codewortliste) // Input: die
Bitsequenz nachricht_bin und // eine Liste, die binren Codeworten
Zeichen zuordnet // Output: nachricht_txt; die decodierte
Nachricht, eine Sequenz von Zeichen nachricht_txt = leer; lnge = 1;
while (nachricht_bin != leer) zeichen_bin =
get_first_n_bits(nachricht_bin, lnge); if found_in(zeichen_bin,
codewortliste) zeichen_txt = get_letter(zeichen_bin, codewortliste)
nachricht_txt = attach_letter(zeichen_txt); nachricht_bin =
delete_first_n_bits(lnge); lnge = 1; else lnge ++; end return
nachricht_txt;
Folie 56
Pseudocode fr Huffman Codierung codieren(nachricht_ascii) //
Input: die Bitsequenz nachricht_ascii, bestend aus einer Sequenz
von ASCII Zeichen (jeweils ein Byte) // Output: nachricht_bin; die
codierte Nachricht, eine Bitsequenz // codewortliste; eine Liste,
die binren Codeworten ASCII Zeichen zuordnet
Folie 57
Huffman Komprimierung 1. ASCII Nachricht in 8-er Blcke
aufteilen, zhlen wie oft jeder Block vorkommt 2. Blcke nach
Hufigkeit ordnen 3. Mit Huffman Baum prfixfreie Codewortliste
erstellen 4. ASCII Nachricht nach Huffman bersetzen, siehe Liste 5.
Bitsequenz & Liste in File speichern, evtl. verschicken 6. Auch
transportiert werden muss die Information, dass dieses File
Huffman-codiert ist
Folie 58
Fragen zu Huffman & Komprimierung 1. Was ist die
grundlegende Idee hinter Huffman Komprimierung? 2. Wann ist Huffman
am effizientesten? 3. Wann lohnt sich Huffman sicher nicht? 4.
Warum benutzt z.B. Word kein Huffman Komprimierung? 5. Was wren
andere grundlegende Ideen zu Komprimierung von Daten? (Erklren Sie
anhand eines Beispiels) 6. Was sind allgemeine Vorteile von
Datenkomprimierung? 7. Was sind allgemeine Nachteile der
Datenkomprimierung? originale Nachricht codierte Nachricht
originale Nachricht
Was ist eigentlich Information? Was ist das kleinstmgliche
Bisschen an Information? Sein oder nicht Sein, das ist hier die
Frage.
Folie 62
Ein BIT ist: eine Bezeichnung fr eine Binrziffer (blicherweise
0 und 1). eine Maeinheit fr die Datenmenge bei digitaler
Speicherung von Daten. Die Datenmenge entspricht in diesem Fall der
verwendeten Anzahl von binren Variablen zur Abbildung der
Information. eine Maeinheit fr den Informationsgehalt (siehe
Shannon). Dabei ist 1 Bit der Informationsgehalt, der in einer
Auswahl aus zwei gleich wahrscheinlichen Mglichkeiten enthalten
ist. There are 10 sorts of people: o those who unterstand binary
and o those who do not.
Folie 63
1. 0101010101010101... 2. 1111111111111111... 3.
0110001101100101... 4. 0010111001100101... 5. 0000000011111111...
6. 0011001100110011... Ordnen Sie diese Bitsequenzen nach
Informationsgehalt (aufsteigend)
Entropie ist eine physikalische Zustandsgre in der
Thermodynamik ein Ma fr den mittleren Informationsgehalt oder auch
Informationsdichte eines Zeichensystems Warum sollte uns das
interessieren? Huffman Komprimierung ist das Paradebeispiel fr eine
Entropiecodierung
Folie 66
Entropie & Wahrscheinlichkeit Der Normalzustand (= maximale
Entropie) ist die Gleichverteilung Abweichungen von der
Gleichverteilung bedeuten: es gibt eine gewisse Ordnung, Struktur
man kann es kompakter beschreiben 0100011110101010100101010101
0000000000000011111111111111 was ist wahrscheinlicher? was trgt
mehr Information?
Folie 67
Berechnen der Informationsdichte H = Entropie Z = endliches
Alphabet von Zeichen z = ein einzelnes Zeichen p =
Auftretenswahrscheinlichkeit (=Hufigkeit z/Gesamthufigkeit) Fr das
deutsche Alphabet: Eine perfekte Komprimierung wrde genau diesen
Entropiewert erreichen
Folie 68
Wozu brauchen wir das? 1. ASCII Nachricht in 8-er Blcke
aufteilen, zhlen wie oft jeder Block vorkommt 2. Blcke nach
Hufigkeit ordnen 3. Mit Huffman Baum prfixfreie Codewortliste
erstellen 4. ASCII Nachricht nach Huffman bersetzen, siehe Liste 5.
Bitsequenz & Liste in File speichern, evtl. verschicken 6. Auch
transportiert werden muss die Information, dass dieses File
Huffman-codiert ist 1. 0101010101010101... 2. 1111111111111111...
3. 0110001101100101... 4. 0010111001100101... 5.
0000000011111111... 6. 0011001100110011... Was, wenn wir nicht
wissen ob es ASCII Zeichen sind? (z.B. beim zippen)
Folie 69
Wozu brauchen wir das? Entropie wird pro Zeichen berechnet -
aber was ist ein Zeichen? 8er: 01100011 01100101 4er: 0110 0011
0110 0101 1. 0101010101010101... 2. 1111111111111111... 3.
0110001101100101... 4. 0010111001100101... 5. 0000000011111111...
6. 0011001100110011... Normierung fr unterschiedliche Block-, bzw.
Zeichenlngen noch allgemeiner: konditionelle Entropie
Folie 70
Huffman generalisiert 1. Binre Nachricht durch
Entropietests/Schtzung darauf analysieren, welche Bits ein Zeichen
bilden sollten, so dass sich die niedrigste Entropie ergibt 2.
Binre Nachricht in Zeichen aufteilen, zhlen wie oft jedes Zeichen
vorkommt 3. Blcke nach Hufigkeit ordnen 4. Mit Huffman Baum
prfixfreie Codewortliste erstellen 5. Binre Nachricht nach Huffman
bersetzen, s. Liste 6. Bitsequenz & Liste in File speichern,
evtl. verschicken 7. Auch transportiert werden muss die
Information, dass dieses File Huffman-codiert ist
Folie 71
Entropiecodierung bedeutet mit einer Entropieschtzung
herausfinden, welche Abschnitte der originalen Bitsequenz man als
Zeichen ansehen sollte diese Zeichen dann so in prfixfreie
Codewrter bersetzen, dass den hufigsten Zeichen die krzesten
Codewrter zugeordnet werden ACHTUNG: trade-off der Listengrsse
bercksichtigen!
Folie 72
Entropiecodierung ist eine allgemeine Methode um zu bestimmen,
wie viel Luft im Koffer ist, und den Koffer dann so umzupacken,
dass mglicht wenig Luft verbleibt wie Legomodell verpacken. Zuerst
muss man herausfinden, in wie kleine Teile man es zerlegen soll,
und dann braucht man eine Methode, um diese Teile effizient
ineinander zu stapeln
Folie 73
Optimalitt der Huffman Codierung ist die wohl am weitesten
verbreitete Art der Entropiecodierung wird oft als letzter Schritt
auf beliebige Bitsequenzen angewandt ist nur annhernd optimal. Bsp:
vllig zufllige Sequenz mit drei mal mehr Nullen als Einsen -
(1/4*lg(1/4)+3/4*lg(3/4)) = 0.811278 Bit/Zeichen(=Bit) weniger als
ein Bit geht aber nicht, die beiden krzest mglichen Codewrter haben
jeweils ein Bit Noch bessere Lsung: Arithmetische Codierung
Folie 74
Arithmetische Codierung Die gesamte Nachricht in einer einzigen
Zahl...... ausserdem braucht es die Zeichen und ihre Frequenz......
und einen schnellen Computer A = 0.6 B = 0.2 C = 0.1 D = 0.1 Zahl =
0.536 Nachricht = ACD
Folie 75
Lernziele - erreicht?? Sie verstehen, was Hamlet mit dem
zersplitternden Weinglas zu tun hat, und wie beide mit der Huffman
Kodierung zusammenhngen Sie kennen die allgemeine Form der Huffman
Kodierung Zusatz: Sie knnen erklren a) warum die Block-Entropie
einer Bitsequenz am kleinsten ist, wenn man die gesamte Sequenz als
einen einzigen Block (= ein Zeichen) ansieht b) warum es trotzdem
keinen Sinn macht, die ganze Sequenz als eine einziges Zeichen zu
kodieren
Folie 76
Hausaufgaben Prfziffern (jede(r) eine andere) Mglichkeiten s.
Wiki Eine bersichtliche Seite zusammenstellen mit Kurzbeschreibung:
Berechnung dieser Prfziffer Beispiel Versuch einer allgemeinen
Definition von Prfziffer
Folie 77
Formate, Codes & Algorithmen Definitionen und
Zusammenhnge
Folie 78
Lernziele Sie kennen die allgemeine Definition von Codierung
Sie wissen, was ein (Datei-) Format ist und warum die meisten
Formate einen header haben Sie knnen eine Binre Reprsentation fr
das Speichern eines Spielzustands entwickeln Sie verstehen, wie die
Begriffe Information, Code und Format zusammenhngen
Folie 79
Komprimierung allgemein originale Nachricht (Bitsequenz)
codierte Nachricht + Liste (Bitsequenz) codierte Nachricht + Liste
(Bitsequenz) originale Nachricht (Bitsequenz) Komprimieren, z.B.
mit Huffman Codierung Dekomprimieren, z.B. mit Huffman Decodierung
speichern /verschicken Welche Informationen braucht es hier?
Folie 80
Information Genau & Kompakt Codieren Komprimieren Koffer (~
Format) so whlen, dass alles eingepackt werden kann, was man im
Urlaub vielleicht brauchen knnte Ziel: Der Koffer soll fr alle
Urlaube geeignet sein! Effizient packen, so dass mglichst wenig
Luft im Koffer bleibt kann davon abhngen, was genau eingepackt
wurde! Ziel: Der Koffer fr diesen Urlaub soll mglichst klein
werden! Koffer packen (Komprimieren von Information)
Folie 81
Codieren Welche Informationen braucht es hier? Nicht-digitale
Information Digitale Information Nicht-digitale Information
Digitale Information Komprimieren Komprimierte digitale Information
Entkomprimieren Digitalisieren Entdigitalisieren?! Darstellen Wie
geht das? Beispiel :Fisch ers Fritz fischt frische...
Folie 82
Und wie passt das jetzt alles zusammen? Information Codierung
Format
Folie 83
Definition Code:
Folie 84
Definition von Code, lang Im Allgemeinen ist ein Code eine
Vereinbarung ber einen Satz (eine Menge) von Symbolen
(Bedeutungstrgern, oder Verweisen) zum Zweck des
Informationsaustauschs. Information existiert nicht in reiner Form;
sie ist immer in irgendeiner Weise formuliert. Ein Code ist
allgemein ausgedrckt eine Formulierung von Information. Das setzt
folgende Elemente voraus: 1. mindestens eine
informationsformulierende Instanz (Aufzeichner/Sender) 2.
mindestens eine informationsempfangende Instanz (Lesender/Empfnger)
kann unter Umstnden auch identisch mit (1) sein 3. ein zu
bermittelnder, abstrakter Inhalt, die Information 4. eine
Vereinbarung zum Zweck der Informationsformulierung und
gegebenenfalls Informationsbermittlung. Diese enthlt einen Satz von
Bedeutungstrgern oder Symbolen, der beiden Instanzen (1) und (2)
bekannt ist, und gegebenenfalls Regeln zur Verwendung der
Symbole
Folie 85
Codieren allgemein Nicht-digitale Information Digitale
Information Nicht-digitale Information Digitale Information
Komprimieren Komprimierte digitale Information Entkomprimieren
Digitalisieren Entdigitalisieren?! Darstellen
Folie 86
Codieren allgemein Nicht-digitale Information Digitale
Information Nicht-digitale Information Digitale Information
Verschlsseln Verschlsselte digitale Information Entschlsseln
Digitalisieren Entdigitalisieren?! Darstellen
Folie 87
Codieren allgemein Nicht-digitale Information Digitale
Information Nicht-digitale Information Digitale Information
Verschlsseln Verschlsselte Information Entschlsseln Digitalisieren
Entdigitalisieren?! Darstellen Komprimieren Kompr. Information
Entkomprimieren Format
Folie 88
Definition von Code, kurz Beispiele fr Codes: Ein Code ist eine
Anleitung, um Zeichen eines Zeichensystems in die eines anderen zu
bertragen. Ein Code definiert eine Umformulierung von Information
Morse Code ASCII Code Huffman Codierung Hamming Code Binrcode
Quellcode Genetischer Code Neuronaler Code Schrift Sprache...
Folie 89
Wozu Information umformulieren? Damit ein spezieller Empfnger
sie verstehen kann, z.B. bersetzung in andere Sprache,
Digitalisieren, Drucken... Um bestimmte bertragungswege oder
Speichermedien zu nutzen, z.B. Morsen, Telefonieren, Bcher, Fotos,
E-Mail... Um Platz zu sparen, z.B. DNA, Komprimierung,
Datenbertragung... Um Fehler bei der bertragung zu vermeiden, z.B.
DNA RNA, Hamming Code... Um Inhalte vor Unbefugten zu verstecken,
z.B. Geheimsprachen, Verschlsselung...
Folie 90
Codieren Welche Informationen braucht es hier? Nicht-digitale
Information Digitale Information Nicht-digitale Information
Digitale Information Komprimieren Komprimierte digitale Information
Entkomprimieren Digitalisieren Entdigitalisieren?! Darstellen Wie
geht das? Beispiel : NachrichtB.rtf Format? Wie gross sollte
NachrichtB sein? Inhalt: Fischers Fritz... (36 Zeichen)
Folie 91
Computer machen eigentlich nichts anderes als Information
mithilfe von Codes von einem Format in das andere umzuwandeln damit
diese Information gespeichert, transportiert, verschlsselt,
dargestellt, extrahiert, verglichen, zusammengefhrt oder sonst wie
verarbeitet werden kann I NFORMATIK = Automatische
Informationsverarbeitung Achtung! Gerade haben wir uns Codes OHNE I
NFORMATIONSVERLUST angeschaut. Es kann aber auch sein, dass
unwichtige Information verloren geht, z.B. weil man den Unterschied
sowieso kaum bemerkt (.jpg) oder weil man nur an bestimmten
Aspekten der Daten interessiert ist (der grsste Wert, die
Richtigkeit einer Antwort, etc.)
Lohnt sich das? P fr ein Bit, geflippt zu werden Anzahl Bits
Eines von 4 Bit ist geflippt P fr genau einen Flip P fr keinen Flip
P fr einen oder keinen Flip P fr mehr als einen Flip P fr einen
oder mehr Flips http://stattrek.com/online-calculator/binomial.aspx
Resultat fr 1% Flip-Wahrscheinlichkeit pro Bit: In ~96% der 4-Bit
Sequenzen gibt es sowieso keinen Fehler In ~3.9% gibt es einen
Fehler kann korrigiert werden In ~0.06% gibt es mehr als einen
Fehler keine Korrektur mglich
Folie 99
Lohnt sich das? P fr ein Bit, geflippt zu werden Anzahl Bits
Eines von 4 Bit ist geflippt P fr genau einen Flip P fr keinen Flip
P fr einen oder keinen Flip P fr mehr als einen Flip P fr einen
oder mehr Flips http://stattrek.com/online-calculator/binomial.aspx
Resultat fr 0.01% Flip-Wahrscheinlichkeit pro Bit: In ~99.96% der
4-Bit Sequenzen gibt es sowieso keinen Fehler In ~0.039% gibt es
einen Fehler kann korrigiert werden In ~0.00000006% gibt es mehr
als einen Fehler keine Korrektur