Algorithmik Formate, Codes & Algorithmen. (Datei-) Formate
Preview:
Citation preview
- Folie 1
- Algorithmik Formate, Codes & Algorithmen
- Folie 2
- (Datei-) Formate
- Folie 3
- 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
- Folie 22
- Folie 23
- Folie 24
- Folie 25
- Folie 26
- Konzepte Beispiele Vektor- vs. Raster Farbtiefe indizierte
Farben Farbraum RGB(A), CMYK, LAB Pixel zusammenfassen Farbverlauf
Lauflnge.svg.bmp.jpg.gif.png,.tiff, RAW,.psd, eps
- Folie 27
- 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
- Folie 30
- JPG & GIF Pixel zusammenfassen Farben reprsentieren
Besonderheiten Anwendungsgebiet
- Folie 31
- JPG in Bildern
- Folie 32
- GIF in Bildern
- Folie 33
- Probleme & Spezialitten
- Folie 34
- 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?
- Folie 42
- Konzepte Beispiele Block-Codierung Frequenz-Codierung
Prfixfreier Code Telefonnummern Morse-Code Huffman Codierung
Arithmetische Codierung
- Folie 43
- Frequenzcodierung
- Folie 44
- 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?
- Folie 48
- DezimalHexBinrZeichen 96600110 0000` 97610110 0001a 98620110
0010b 99630110 0011c 100640110 0100d 101650110 0101e 102660110 f
103670110 0111g 104680110 1000h 105690110 1001i 1066A0110 1010j
1076B0110 1011k 1086C0110 1100l 1096D0110 1101m 1106E0110 1110n
1116F0110 1111o 112700111 0000p 113710111 0001q 114720111 0010r
115730111 0011s 116740111 0100t 117750111 0101u 118760111 0110v
119770111 w 120780111 1000x 121790111 1001y 1227A0111 1010z
1237B0111 1011{ 1247C0111 1100| 1257D0111 1101} 1267E0111 1110~
1277F0111 1111DEL ASCII (American Standard Code for Information
Interchange) Kleinbuchstaben:
- Folie 49
- Huffman Komprimierung
- Folie 50
- 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
- Folie 59
- Enthropie
- Folie 60
- Konzepte Beispiele (Informations) Entropie Entropieschtzung
Huffman in.zip
- Folie 61
- 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)
- Folie 64
- 1. 0101010101010101... 2. 2. 1111111111111111... 1. (= 1 Bit)
3. 0110001101100101... 4c 4. 0010111001100101... 4b (ASCII = ce) 5.
0000000011111111... 4a 6. 0011001100110011... 3.
- Folie 65
- 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.)
- Folie 92
- Ein bisschen Magie!
- Folie 93
- Fehlerkorrigierende Codes
- Folie 94
- Folie 95
- Konzepte Beispiele Fehlererkennung Prfsumme Parittsbit
Fehlerkorrektur Hamming-Distanz Binrmagie Hamming-Code CRSC
- Folie 96
- x 000 100 000
- Folie 97
- Folie 98
- 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