40
1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes ASCII, Unicode, UTF Begriffe: Byte, KByte, KibiByte Ablage von Datenwörtern im Speicher: – „Big-Endian“ vs. „Little Endian“ Codierung / Komprimierung von Bildern – Lauflängen-Codierung Wörterbuch Bit-Plane

1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

Embed Size (px)

Citation preview

Page 1: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

1

Vertiefungsstoff zum Thema Code und Codierung

Themen

Codierung von Zeichen in gebräuchlichen n-Bit-Codes

– ASCII, Unicode, UTF

Begriffe: Byte, KByte, KibiByte

Ablage von Datenwörtern im Speicher:

– „Big-Endian“ vs. „Little Endian“

Codierung / Komprimierung von Bildern

– Lauflängen-Codierung

– Wörterbuch

– Bit-Plane

Page 2: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

2

Darstellung von Zeichen und Ziffern

Kriterien für geeignete Codierungen: Technische Realisierung einfach und billig (z.B. Binärcodierungen). Codierung / Decodierung soll schnell und einfach durchführbar sein. zu realisierende Operationen (auf codierten Wörtern) sollen schnell,

einfach und zuverlässig durchführbar sein.

Darstellung fester Zeichensätze

Darzustellen sind– Schriftzeichen: Buchstaben, Ziffern, Sonderzeichen– evtl. Steuerzeichen

Darstellung erfolgt meistens mit n-Bit-Codes

c: Zeichenvorrat Booln mit n Nat abhängig von der Größe des Zeichenvorrats: |Zeichenvorrat| 2n.

Page 3: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

3

Codierung von Text (Vertiefungsstoff)

Um Texte in einem Rechner darzustellen, codiert man Alphabet und Satzzeichen in Bitfolgen. Mit einem Alphabet von 26 Kleinbuchstaben, ebenso vielen Großbuchstaben, einigen Satzzeichen wie etwa Punkt, Komma und Semikolon und Spezialzeichen wie '+', '&', '%' hat eine normale Schreibmaschinentastatur eine Auswahl von knapp hundert Zeichen.Die Information, wo ein Zeilenumbruch stattfinden oder wo ein Text eingerückt werden soll, codiert man ebenfalls wie ein Zeichen.Beispiele: - CR-Zeichen (von englisch Carriage Return = Wagenrücklauf),- LF-Zeichen (von englisch Line Feed = Zeilenvorschub),- das Tabulatorzeichen Tab.

Solche Steuerzeichen haben bei der Darstellung von Text eine formatierende Wirkung. Sie werden nicht "wirklich gedruckt". Sie heißen daher auch nicht-druckbare Zeichen.

Page 4: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

4

ASCII (1)

Für die Darstellung aller Lateinischen Buchstaben und arabischen Ziffern reichen 7 Bits (128 verschiedene Möglichkeiten) aus. Es genügt eine Tabelle zu erstellen, mit der jedem Zeichen ein solcher Bitcode zugeordnet wird. Dazu numeriert man die 128 gewählten Zeichen einfach durch und stellt die Nummer eines Zeichens durch 7 Bit binär dar. Die heute fast ausschließlich gebräuchliche Numerierung ist die sogenannte ASCII-Numerierung. Sie berücksichtigt einige Systematiken, wie:- die Kleinbuchstaben sind in der alphabetischen Reihenfolge

durchnumeriert,- die Großbuchstaben sind in der alphabetischen Reihenfolge

durchnumeriert,- die Ziffern 0 bis 9 stehen in der natürlichen Reihenfolge.

ASCII steht für American Standard Code for Information Interchange.

Page 5: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

5

ASCII TabelleASCII 7-Bit-Code (+1 Prüfbit): genau 128 Zeichen darstellbar 8-Bit-ASCII auch üblich:dann 256 Zeichen darstellbar

4 bit + jeweils 3bit = 7

Page 6: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

6

ASCII (2)Da der ASCII-Code zur Datenübertragung (Information Interchange) konzipiert wurde, dienen die ersten Zeichen, ASCII 0 bis ASCII 31 und ASCII 127, verschiedenen Signalisierungs- und Steuerungszwecken.

Steuerzeichen können über Tastatur mit Steuerungsnmaske ("Ctrl" oder mit "Str" bezeichnet) eingegeben werden. Die ASCII-Codes von 1 bis 26 entsprechen dabei den Tastenkombinationen Ctrl-A bis Ctrl-Z. z.B. entspricht ASCII 7 (Bell - das Klingelzeichen) der Kombination Ctrl-G und ASCII 8 (Backspace) ist Ctrl-H.

Die gebräuchlichen Tastaturen spendieren den wichtigsten dieser ASCII-Codes eine eigene Taste. Dazu gehören u.a. Ctrl-I (Tabulator), Ctrl-H (Backspace), Ctrl-[ (Escape=ASCII 27) und Ctrl-M (Return).

Eine Datei, die nur ASCII-Zeichen enthält, nennt man ASCII-Datei. Oft versteht man unter einer ASCII-Datei auch einfach eine Textdatei, selbst wenn Codes aus einer ASCII-Erweiterung verwendet werden.

Page 7: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

7

ASCII - Erweiterungen (1)Bei der ASCII-Codierung werden nur die ersten 7 Bits eines Byte genutzt. Das letzte Bit verwendete man früher als Kontrollbit für die Datenübertragung. - Es wurde auf 0 oder 1 gesetzt, je nachdem ob die Anzahl der 1en an

den übrigen 7 Bitpositionen gerade (even) oder ungerade (odd) waren.

- Die Anzahl der 1-en in dem gesamten Byte wurde dadurch immer gerade (even parity). Wenn nun bei der Übertragung ein kleiner Fehler auftrat, d.h. wenn in dem übertragenen Byte nur ein Bit verfälscht wurde, so konnte der Empfänger dies erkennen, indem er einfach die Anzahl der 1-en zählte.

Bei der Verwendung des ASCII-Codes zur Speicherung von Texten und auch als Folge der verbesserten Qualität der Datenübertragung wurde dieses Kontrollbit überflüssig. Daher lag es nahe, nun alle 8 Bit zur Zeichenkodierung zu verwenden. Somit ergab sich ein weiterer verfügbarer Bereich von ASCII 128 bis ASCII 255.

Page 8: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

8

ASCII - Erweiterungen (2)PCs benutzen diese zusätzlichen Codes zur Darstellung von sprachspezifischen Zeichen wie z.B. "ä" (ASCII 132), "ö" (ASCII 148) "ü" (ASCII 129) und einigen Sonderzeichen anderer Sprachen.

Darüber hinaus auch für Zeichen, mit denen man einfache graphische Darstellungen wie Rahmen und Schraffuren zusammensetzen kann.

Leider ist auch die Auswahl der sprachspezifischen Sonderzeichen eher zufällig und bei weitem nicht ausreichend für die vielfältigen Symbole fremder Schriften. => Daher wurden von der „International Standardization Organization“

(ISO) verschiedene ASCII-Erweiterungen normiert. In Europa sind dazu die ASCII-Erweiterung Latin-x nützlich, die

durch die Normen ISO 8859-x (auch ISO/IEC 8859-x) beschrieben werden.

Derzeit aktuellste Version ist die Norm ISO-8859-16:2001 (Latin-16, erhältlich von ISO, www.iso.ch/ ).

Page 9: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

9

Unicode

Wegen der Problematik der ASCII-Erweiterungen bei der weltweiten Datenübertragung entstand in den letzten Jahren ein neuer Standard, der versucht, sämtliche relevanten Zeichen aus den unterschiedlichsten Kulturkreisen in einem universellen Code zusammenzufassen. Dieser neue Zeichensatz heißt Unicode und verwendet eine 16-Bit-Codierung (d.h. 2 Bytes), kennt also maximal 216 = 65536 Zeichen.

Page 10: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

10

Unicode Sprachspezifische Schriftzeichen, wie z.B. ö, ß, æ, ç oder Ã, griechische, kyrillische, arabische, japanische, tibetische, ...

Die ersten 128 Unicode-Zeichen sind identisch mit dem ASCII-Code, die nächsten 128 mit dem ISO-Latin 1 Code. => ASCII leicht einbettbar.Herkömmliche Programmiersprachen lassen meist keine Zeichen aus ASCII-Erweiterungen zu. Java erlaubt als erste der weit verbreiteten Sprachen die Verwendung beliebiger Unicode-Zeichen. Allerdings heißt dies noch lange nicht, dass jede Java-Implementierung einen Editor zur Eingabe von Unicode mitliefern würde.Unicode wurde vom Unicode-Consortium (www.unicode.org) definiert. Dieses arbeitet ständig an neuen Versionen und Erweiterungen dieses Zeichensatzes.

Page 11: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

11

UCS Universal Character Set

Die Arbeit des Unicode-Consortium wurde von der ISO (www.iso.ch) aufgegriffen. Unter der Norm ISO-10646 wurde Unicode als Universal Character Set (UCS) international standardisiert. Beide Gremien bemühen sich darum, ihre jeweiligen Definitionen zu synchronisieren, um unterschiedliche Codierungen zu vermeiden. ISO geht allerdings in der grundlegenden Definition von UCS noch einen Schritt weiter als Unicode. Es werden grundsätzlich sowohl eine 16-Bit-Codierung (UCS-2) als auch eine 31-Bit-Codierung (UCS-4) vorgesehen. - Die Codes von UCS-2 werden als Basic Multilingual Plane

(BMP) bezeichnet, beinhalten alle bisher definierten Codes und stimmen mit Unicode überein. - Codes, die UCS-4 ausnutzen sind für potenzielle zukünftige

Erweiterungen vorgesehen

Page 12: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

12

UTF-8 UCS Transformation Format

Die Einführung von Unicode bzw. UCS-2 und UCS-4 führt zu beträchtlichen Kompatibilitätsproblemen, und bläht derart codierte Textdateien auf. => Wunsch nach einer kompakteren Codierung, die kompatibel mit der historischen 7-Bit ASCII Codierung ist, und die den neueren Erweiterungen Rechnung trägt. Entwicklung von UTF-8, in den 90-er Jahren. - Teil der ISO-10646 Norm (Anhang R)- von den Internetgremien als RFC2279 (www.rfc-editor.org) standardisiert.

UTF steht für UCS Transformation Format. Name betont, dass es sich lediglich um eine andere Codierung von UCS bzw. Unicode handelt.

Neben UTF-8 gibt es noch andere Transformations-Codierungen wie UTF-2, UTF-7 und UTF-16, die allerdings nur geringe Bedeutung erlangt haben.

Page 13: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

13

UTF-8 (2)UTF-8 ist eine sog. Mehr-Byte-Codierung. 7-Bit ASCII-Zeichen werden mit einem Byte codiert, alle anderen verwenden zwischen 2 und 6 Bytes. Die Kodierung erfolgt nach den folgenden Prinzipien:i) Jedes mit 0 beginnende Byte ist ein Standard 7-Bit ASCII Zeichen.

Jedes mit 1 beginnende Byte gehört zu einem aus mehreren Bytes bestehenden UTF-8 Code. => garantiert, dass Teile eines Mehrbyte UTF-8 Zeichens

nicht als 7-Bit-ASCII Zeichen missdeutet werden können. ii) Besteht ein UTF-8 Code aus n 2 Bytes, so beginnt das erste Byte mit n 1-en, und jedes der n-1 Folgebytes mit der Bitfolge 10.

=> erlaubt Wortgrenzen in einer UTF-8 codierten Datei leicht zu erkennen, was ein einfaches Wideraufsetzen bei einem

Übertragungsfehler ermöglicht.

Auch einfache syntaktische Korrektheitstests sind möglich. Darüber hinaus ist es ziemlich unwahrscheinlich, dass eine (längere) korrekte UTF-8 Datei versehentlich anders interpretiert wird.

Page 14: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

14

UTF-8UTF-8 Codes können die verschiedenen UCS-Codes (und Teilmengen

davon) auf einfache Weise repräsentieren:1-Byte-Codes haben die Form 0xxx xxxx und ermöglichen die Verwendung von 7 (mit x gekennzeichneten) Bits und damit die Codierung von allen 7-Bit ASCII Codes. 2-Byte-Codes haben die Form: 110x xxxx 10xx xxxx und ermöglichen die Codierung aller 11-Bit UCS-2 Codes. 3-Byte-Codes haben die Form: 1110 xxxx 10xx xxxx 10xx xxxx. Mit den 16 noch verfügbaren Bits können alle 16-Bit UCS-2 Codes dargestellt werden. 4-Byte-Codes der Form: 1111 0xxx 10xx xxxx 10xx xxxx 10xx xxxx ermöglichen die Verwendung von 21 Bits zur Codierung aller 21-Bit UCS-4 Codes. 5-Byte-Codes können alle 26-Bit UCS-4 Codes darstellen. Sie haben die Form: 1111 10xx 10xx xxxx 10xx xxxx 10xx xxxx 10xx xxxx6-Byte-Codes ermöglichen die Codierung des kompletten 31-Bit UCS-4 Codes: 1111 110x 10xx xxxx 10xx xxxx 10xx xxxx 10xx xxxx 10xx xxxx

Page 15: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

15

UTF-8UTF-8 codierte Dateien sind also kompatibel zur 7-Bit ASCII Vergangenheit und verlängern den Umfang von Dateien aus dem amerikanischen und europäischen Bereich gar nicht oder nur unwesentlich. Diese Eigenschaften haben dazu geführt, dass diese Codierungsmethode der de facto Standard bei der Verwendung von Unicode geworden ist. Bei den Webseiten des Internets wird UTF-8 immer häufiger verwendet – alternativ dazu können in HTML-Dateien Sonderzeichen, also z.B. Umlaute wie „ä“ durch so genannte Entities als „ä“ umschrieben werden. Bei den Bytecode Dateien von Java ist die UTF-8 Codierung schon von Anfang an verwendet worden.

Page 16: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

16

Zeichenketten

Zur Codierung eines fortlaufenden Textes fügt man einfach die Codes der einzelnen Zeichen aneinander.

Eine Folge von Textzeichen heißt auch Zeichenkette (engl.: String). Der Text "Hallo Welt" wird also durch die Zeichenfolge H,  a,  l,  l,  o,   , W,  e,  l,  t  repräsentiert.

Jedes dieser Zeichen, einschließlich des Leerzeichens ’ ’ wird durch seine Nummer in der ASCII-Tabelle ersetzt:072 097 108 108 111 032 087 101 108 116.

Alternativ können wir die ASCII-Nummern auch hexadezimal schreiben, also als: 48 61 6C 6C 6F 20 57 65 6C 74.

Daraus lässt sich unmittelbar die Repräsentation durch eine Bitfolge entnehmen: 01001000 01100001 01101100 01101100 01101111

00100000 01010111 01100101 01101100 01110100.

Page 17: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

17

Anmerkungen zum Begriff Byte, KByte und KiBDas Wort "Byte" ist künstlich und stammt von "Bit" und "Bite" (Quelle: The New Shorter Oxford English Dictionary). Verwendet wurde es, um eine Speichermenge oder Datenmenge zu kennzeichnen, die ausreicht, um ein Zeichen darzustellen. Der Begriff wurde nach 1956 von Werner Buchholz geprägt in einer frühen Designphase eines IBM-Computers. Im Original beschrieb er eine Breite von 6 Bit und stellte die kleinste direkt adressierbare Speichereinheit eines Computers dar. Bereits 1956 erfolgte der Übergang zu 8 Bit. Die Schreibweise "Bite" wurde zu "Byte" geändert, um versehentliche Verwechslungen mit "Bit" zu vermeiden.Zur Unterscheidung der ursprünglichen Bedeutung als kleinste adressierbare Einheit und der Bedeutung als 8 Bit Tupel wird in der Fachliteratur korrekterweise der Begriff Oktett (engl. "octett") für letzteres benutzt, um eine klarere Trennung zu erzielen.Die Abkürzung KiB steht in der Informationstechnik für die Speichermengeneinheit KibiByte ("Kilobinary Byte") und bezeichnet das 1024-fache eines Bytes (= 1024 8 Bits = 214 Bits). Die Maßeinheit „Kilo-Byte“ (KByte) steht hingegen für das 1000-fache eines Bytes (= 1000 8 Bits)

Page 18: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

18

Ablage von mehr-bytigen Wörtern im Speicher:Big Endians vs. Little-Endians

Rechenanlagen unterscheiden sich zum Teil auch dadurch, wie sie längere Datenwörter, die aus mehreren Bytes bestehen, organisieren.

Beispiel: 32 Bit Datenwörter besten aus 4 Bytes. Darin kann man beispielsweise 8-stellige Hexadezimalzahlen ablegen, etwa:

( 4 3 F A 2 7 C 7 )16

Adresse Byte B Adresse B+1 Adresse B+2 Adresse B+3

Es sind zwei unterschiedliche Organisationsformen in Gebrauch:

1. Big Endians: der signifikanteste Teil eines Wortes (Most Significant Byte MSB) erhält die niedrigste Byteadresse.

( 4 3 F A 2 7 C 7 )16

Adresse Byte B Adresse B+1 Adresse B+2 Adresse B+3

0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 11 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1MSB

Page 19: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

19

Ablage von mehren Bytes breiten Wörter im Speicher:„Big Endians“ vs. „Little-Endians“

2. Little endians: der am wenigsten signifikante Teil (Lowest Significant Byte, LSB) eines Wortes erhält die niedrigste Byteadresse.Beispiel: Ablage von 0x43FA27C7 im 32 Bit (= 4 Bytes) Datenwort

( 4 3 F A 2 7 C 7 )16

C 7 2 7 F A 4 3

Adresse Byte B Adresse B+1 Adresse B+2 Adresse B+3

Intel (Windows PC) verwendet Little Endians IBM, HP, MAC, (JAVA) verwenden Big Endian POWER PC (Kooperation von IBM, Apple,

Motorola) „versteht“ beide Formate (Bi Endian)

1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 00 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1MSB LSB

Begriffe „Big Endians“ und „Little Endians“ aus Gulliver‘s Reisen entlehnt.

Page 20: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

20

BildkompressionInterpixelredundanz

Lauflängen-CodierungWörterbuch-Codierung Huffman-CodierungBit-Plane Codierung Kombination aus Bit-Plane & Lauflänge & Huffman

Page 21: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

21

Speicherbedarf für Bilder Der für die Speicherung eines nm Rasterbildes benötigte Speicheplatz in

Bits hängt neben der Anzahl der Bildpunkte (= n m) auch davon ab, welche Information man pro Bildpunkt ablegen möchte und wie diese Information codiert ist (z.B. in Codewörtern eines Blockcodes oder mit Codewörtern variabler Länge).

Bildtyp: mögliche Werte pro Pixel Speicherbedarf pro Pixel

Schwarz-Weiß-Bild 2 1 bit

Graustufenbild 256 8 bitbzw. 256 Farben

optimale Farbe 16,7 Mio. 24 bit (= 3 8)

Beispiel z1z2z3z4z5z6z7z8

Schwarz-Weißbild mit 8 8 Bildpunkten benötigt:8 8 1 = 64 Bit = 8 Byte

s1 s2 s3 s4 s5 s6 s7 s8

Page 22: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

22

BildkompressionIdee Bei der Bildkompression versucht man Speicherplatz einzusparen, durch:

- Weglassen nicht unbedingt benötigter Bildinformation - Wahl einer platzsparenden Codierung

Bewertungskriterien für die Auswahl von Kompressionsverfahren Wie viel Speicherplatz kann man einsparen?

Kompressionsrate = (Platzbedarf Originalbild) / (Platzbedarf komprimiertes Bild)

Lässt sich das Originalbild wieder vollständig aus den komprimierten Daten rekonstruieren oder tritt ein Informationsverlust auf?

Wie aufwändig (Rechenzeit, Speicherbedarf) ist die Durchführung der Kompression und der Dekompression?

Ist das Verfahren patentrechtlich geschützt, so dass ggf. Lizenzgebühren anfallen?

Page 23: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

23

BildkompressionInterpixel-Redundanz Haben die in einer kleinen Region benachbarten Pixel ähnliche Grauwerte,

so kann man vom Grauwert eines Pixels den Grauwert eines Nachbarpixels gut schätzen.

Anstatt gleiche (sich stark ähnelnde) Grauwerte aller in der Region enthaltenen Pixel zu betrachten, könnte man sich auf eine repräsentative Auswahl beschränken und so das Datenvolumen reduzieren.

Beispiel B1 und B2 besitzen jeweils 50% weiße und 50% schwarze Pixel, jedoch

weist B2 eine höhere Pixelredundanz auf und bietet somit vermeintlich mehr Potential zur Datenreduktion durch Kompression.

B1 B2

Page 24: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

24

InterpixelredundanzBeobachtung Viele Grauwertbilder weisen Interpixel-Redundanz in einem Maß

auf, das zur Datenreduktion genutzt werden kann.

Beispiel Ca. 75% der

Grauwertdifferenzen liegen unter 10.

Page 25: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

25

Lauflängen-CodierungIdee In Grafiken sowie in Binärbildern haben benachbarte Bildpunkte oftmals

identische Helligkeitswerte (oder Grauwerte / Farbwerte). Anstatt für jeden Bildpunkt die Helligkeitswerte zu speichern, merkt man sich nur die Position der Bildpunkte, an denen ein Wechsel des Helligkeitswerts auftritt und wie lange der neue Wert beibehalten wird.

Kodierungsmöglichkeit 1 Notiere Lauflängen pro Zeile durch eine Liste von Tripel:

(Spalte, Wert, Länge), ... # ;; # bedeutet ZeilenendeBeispiel Gegeben: 88 BinärbildLauflängenkodierung Kommentar

z1z2z3z4z5z6z7z8

#(3,s, 2), (6,s,1), (8,s,1) # (3,s, 2), (8,s,1) # (3,s, 2), (8,s,1) #(3,s, 3) #(3,s, 2) #(3,s, 2) # #

kein Wechsel in 1. Zeiledrei Wechsel von weiß nach schwarz in Zeile 2, (s bedeutet Wert = schwarz)....

kein Wechsel in 8. Zeile

s1 s2 s3 s4 s5 s6 s7 s8

Page 26: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

26

Lauflängen-CodierungAnmerkung zur Codierungsvarianten 1 Bringt nicht viel Ersparnis bei sehr häufigen Wechseln (z.B.

Schachbrett Musterung). Bei zeilenweiser Codierung „übersieht“ man vertikale und diagonale

Gruppen benachbarter Punkte gleicher Farbe.

Kodierungsmöglichkeit 2 Schreibe zunächst alle Bildzeilen hintereinander, wende dann darauf

Lauflängencodierung an. Beispiel Gegeben: 88 Binärbild Lauflängenkodierung

z1z2z3z4z5z6z7z8

(8+3,s, 2), (8+6,s,1), (16,s,1), (16+3,s, 2), (16 +8,s,1) ..... (48+3,s, 1)

s1 s2 s3 s4 s5 s6 s7 s8.....

= (11,s, 2), (14,s,1), (16,s,1), (19,s, 2), (24,s,1) ..... (51,s, 1)

Anmerkung: Man spart das Zeilenende-Zeichen #, andererseits benötigt man mehr Bits zur Darstellung der Positionen von Bildpunkten mit Wechsel.

Page 27: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

27

Lauflängen-Codierung

Kodierungsmöglichkeit 3 Wie Ansatz 2, jedoch nützt man zusätzlich aus, dass in einem

Schwarzweißbild zwei nacheinanderfolgende Wechsel w1, w2 folgende Form haben: falls w1 = s -> w, dann w2 = w -> s (oder s, w vertauscht)=> Es genügt also, sich auf eine Anfangsfarbe festzulegen und dann nur die Wechsel zu notieren.

Beispiel Gegeben: 88 Binärbild Lauflängenkodierung

z1z2z3z4z5z6z7z8

11, 13, 14, 15, 16 ..... 58, 59

s1 s2 s3 s4 s5 s6 s7 s8.....

erster Wechsel von w -> s an Position 11 (= 8+3),gefolgt von Wechsel s -> w an Position 13,gefolgt von Wechsel w -> s an Position 14,gefolgt von Wechsel s -> w an Position 15,....in Zeile 7 Wechsel von w -> s an Position 58gefolgt von Wechsel s -> w an Position 59, fertig!

Page 28: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

28

Vergleich der Varianten (Lauflängencodierung) Speicherbedarf Originalbild: 8 8 1 = 64 Bit = 8 Byte

Speicherbedarf nach Kompression

#(3,s, 2), (6,s,1), (8,s,1) # (3,s, 2), (8,s,1) # (3,s, 2), (8,s,1) #(3,s, 3) #(3,s, 2) #(3,s, 2) # #

zu codieren sind folgende 9 Zeichen:{1,2,3,4,6,8, s, w, #}.Das geht mit Codewörtern aus Blockcode B4 Die komprimierte Repräsentation des Bildes besteht aus insgesamt 18 Zeichen (ohne Klammern und Kommata!).

Speicherbedarf: 38 4 Bit = 144 Bit

Variante 1

Variante 2

(11,s, 2), (14,s,1), (16,s,1), (19,s, 2), (24,s,1) ..... (51,s, 1)

Zu codieren sind: 10 Positionen, drei Spannweiten 1, 2,3, sowie die beiden Farbwerte s, w: {11, 14, 16, 19, ... 51, 1,2,3, s, w} Diese 15 Angaben kann man wieder mit Codewörtern aus Blockcode B4 codieren.Die komprimierte Repräsentation des Bildes besteht aus insgesamt 18 Zeichen (ohne Klammern und Kommata!).

Speicherbedarf: 30 4 Bit = 120 BitVariante 3

11, 13, 14, 15, 16 ..... 58, 59Zu codieren sind insgesamt 16 Positionen für aufeinanderfolgende Wechsel von s->w bzw. w->s, das geht mit Codewörtern aus Blockcode B4 Die komprimierte Repräsentation des Bildes besteht dann aus insgesamt 16 Codewörtern.

Speicherbedarf: 16 4 Bit = 64 Bit

Page 29: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

29

WörterbuchcodierungIdee In Grafiken sowie in Binärbildern kommen oftmals sich wiederholende

Muster von Farbwerten (oder Grauwerten) vor - Beispiel: Schachbrett. Erkennt man solche Muster, so kann man diese nummerieren. Anstatt der Bildpunktinformation speichert man dann die Musternummer.

Kernidee des Verfahrens ist der Aufbau eines „Wörterbuchs“ in dem man die Muster in einer festgelegten Reihenfolge ablegt.

Beispiel Gegeben: 4x4 Binärbild:

w = weiss, s= schwarz Schritt 1

z1z2z3z4

s1 s2 s3 s4

Wörterbuch (Mustertabelle)

Index Muster0 „leeres Muster“1 w2 s

3 wsw s w s

initial

neue Muster

- lese w- im Wörterbuch ist noch kein längeres Muster, das mit w beginnt. => gib Index i von w aus (d.h. Ausgabe = 1)- trage neues Muster ws ins Wörterbuch ein Muster ws bekommt Index 3

w s s s w w w s.....

[ 1,

Page 30: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

30

Wörterbuchcodierung Beispiel (Fortsetzung) Gegeben: 8x8 Binärbild: Schritt 2 u. 3

- lese s- im Wörterbuch ist noch kein längeres Muster, das mit s beginnt.=> gib Index i von s aus (d.h. Ausgabe = 2)- trage neues Muster sw ins Wörterbuch ein Muster sw bekommt Index 4

- lese w- im WB gibt es bereits längeres Muster, das mit w beginnt => lies nächsten Wert und prüfe, ob Muster ws vorliegt. - Muster ws wird erkannt. Allerdings gibt es im WB kein längeres Muster, das mit ws beginnt: => gib Index i von ws aus (d.h. Ausgabe = 3)- trage neues Muster wsw ins Wörterbuch ein. Muster wsw bekommt Index 5

Bisher wurden also die ersten vier Bildpunkte bearbeitet und führten zur Ausgabe: 1,2,3Die komprimierte Form des gesamten Bilds besteht nachher aus der Folge der Ausgaben [ 1, 2, 3, .... ] sowie dem initialen Wörterbuch

z1z2z3z4

w s w s w s s s w w w s.....

Wörterbuch (Mustertabelle)

Index Muster0 „leeres Muster“1 w2 s

3 ws4 sw5 wsw

initial

neue Muster

w s w s w s s s

[ 1, 2,

[ 1, 2, 3,

Page 31: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

31

Wörterbuchcodierung Beispiel (Fortsetzung) Gegeben: 8x8 Binärbild: Schritt 4 usw.

- lese w- erkenne Muster ws=> gib Index i von ws aus (d.h. Ausgabe = 3)- trage neues Muster wss ins Wörterbuch ein

z1z2z3z4

w s w s w s s s w w w s.....

Wörterbuch (Mustertabelle)

Index Muster0 „leeres Muster“1 w2 s

3 ws4 sw5 wsw6 wss7 ss8 sww

initial

neue Muster

w s w s w s s s

- lese s=> gib Index i von s aus (d.h. Ausgabe = 2)- trage neues Muster ss ins Wörterbuch ein

w w w s

w s w s w s s s

- lese s-erkenne Muster sw=> gib Index i von sw aus (d.h. Ausgabe = 4)- trage neues Muster sww ins Wörterbuch ein

w w w s

w s w s w s s s w w w s

[ 1, 2, 3, 3,

[ 1, 2, 3, 3, 2,

[ 1, 2, 3, 3, 2, 4,

Page 32: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

32

Wörterbuchcodierung Decodierung Gegeben: komprimierte Darstellung des Bilds als

Folge von Indices von Wörterbucheinträgen [ 1, 2, 3, 3, 2, 4 .... ] sowie das initiale Wörterbuch.

Beispiel:

z1z2z3z4

w .....

Wörterbuch (Mustertabelle)

Index Muster0 „leeres Muster“1 w2 s

initial

- lese 1 => Index steht für Muster w, gib w aus[ 1,

2,

3,

3,

Index Muster0 „leeres Muster“1 w2 s

3 ws4 sw5 wsw

initial

neue Muster

- lese 2 => Index steht für s, gib s aus- ergänze Wörterbuch um Eintrag ws mit Index 3

w s .....

- lese 3 => Index steht für Muster ws , gib ws aus- ergänze Wörterbuch um Eintrag sw mit Index 4

w s w s .....

- lese 3 => Index steht für Muster ws , gib ws aus- ergänze Wörterbuch um Eintrag wsw mit Index 5

.....w s w s w s

....

Page 33: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

33

WörterbuchcodierungAnmerkung Als Ergebnis der Komprimierung entsteht eine Liste von Wörterbuch-

Indizes. Man muss nur diese Liste sowie das initiale Wörterbuch speichern (bzw. übertragen).

Bei der Decodierung kann man die komplexeren Muster aus dem initialen Wörterbuch sowie der Reihenfolge der Indizes wieder rekonstruieren.

Das Verfahren eignet sich gut, wenn ein Bild tatsächlich viele wiederkehrende Grauwertmuster enthält. Bei Fotos ist das allerdings meist nicht der Fall!

Wurde ursprünglich entwickelt von Lempel, Ziv und Welch und ist daher auch unter dem Namen „LZW-Kompression“ bekannt.

In der Praxis findet das Verfahren Anwendung in den Bildformaten GIF, TIFF sowie bei der Kompression von Textdaten .

Es gibt zahlreiche Verbesserungen, etwa das für ZIP-Archive verwendete Deflate-Verfahren, das LZW mit Huffman kombiniert.

Page 34: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

34

Bildkompression mit HuffmanIdee Ordne häufig vorkommenden Grauwerten kurze

Codewörter zu.

Page 35: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

35

Bit-Plane CodierungIdee Grauwerte eines Bildes werden als n-stellige Binärwerte dargestellt.

Jede i-te Stelle eines Binärwerts wird als „Bildebene“ (Bit-Plane) interpretiert.

Beispiel 4x4 Pixel-Bild B mit binären Grauwerten b = b3b2b1b0

(Wert 8 = 1000, Wert 7 = 0111)

Für die 4 Bildebenen ergeben sich folgende Werte:Wert 8 = 1000 0111 = 7

Page 36: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

36

Bit-Plane CodierungVerbesserung Verwende anstatt des natürlichen Binärcodes für Grauwerte den

einschrittigen Graycode g = gn... G3g2g1g0.

Natürlicher Binärcode lässt sich in Graycode umrechnen: b = b3b2b1b0 dann gilt:

g0 = b0 XOR b1 , g1 = b2 XOR b1 , g2 = b2 XOR b3 und g3 = b3

Beispiel: 4x4 Pixel-Bild B mit binären Grauwerten im Graycode g = g3g0g0g0

Page 37: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

37

Bit-Plane-CodierungBeobachtung: Bei der Verwendung von Graycode entstehen

weniger Wechsel. => Besser geeignet für Lauflängencodierung.

Page 38: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

38

Bit-Plane CodierungVergleich Bitplanes für Grauwerte in normalem Binärcode b = b7... b3b2b1b0

Bitplanes für Grauwerte in einschrittigen Graycode g = g7... g3g2g1g0

Page 39: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

39

Bit-Plane CodierungVergleich Bitplanes für Grauwerte in normalem Binärcode b = b7... b3b2b1b0:

Bitplanes für Grauwerte in einschrittigen Graycode g = g7... g3g2g1g0:

Page 40: 1 Vertiefungsstoff zum Thema Code und Codierung Themen Codierung von Zeichen in gebräuchlichen n-Bit-Codes –ASCII, Unicode, UTF Begriffe: Byte, KByte,

40

Applet zur JPEG KomprimierungDie zu übertragenden Daten werden

als „Schwingung“ s(t) gedeutet.Funktion s(t) wir angenähert durch eine Überlagerung von Basisschwingungen

mit verschiedenen Frequenzen.