UR MI Informatik SS13 02a Bits Bytes Kodierung Update1

Raphael Wimmer · Lehrstuhl für MedieninformatikInstitut für Information und Medien, Sprache und KulturFakultät für Sprach-, Literatur- und Kulturwissenschaften

Bits, Bytes und KodierungVorlesung “Einführung in die Informatik und Medieninformatik | SS 2013

Vorlesung Einführung in die Medieninformatik · I: Bits, Bytes und Kodierung · 25.04.2013 · Raphael Wimmer · Universität Regensburg 2/29

Übersicht

Zahlensysteme, Hexadezimalzahlen Repräsentation von Daten im Rechner Binäre Kodierung von Zahlen

● Zweierkomplement● Fließkommazahlen

Binärkodierung beliebiger Daten


Hexadezimalzahlen


Kodierung (ganzer) Zahlen (n) auf der Basis von Stellenwertsystemen der Form

Gebräuchlich: Binär-, Oktal-, Dezimal-, und Hexadezimalsytem (Basen 2, 8, 10, 16)

Systeme mit einer Basis > 10 benötigen zusätzliche Ziffern für die Codierung

Zahlensysteme

Stellender Anzahl

)0 ,ganzzahlig ( Ziffern

emsZahlensyst des Basis

:mit 1

0

=<≤=

=

⋅= ∑−

=

N

Bbbb

B

Bbn

ii

N

i

ii



Hexadezimal/Dezimal

21C16256 16 1

= 540

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 1 2 3 4 5 6 7 8 9 A B C D E F

Es können Groß- oder Kleinbuchstabenverwendet werden.

0XEE = 0xee


Warum Hexadezimalzahlen?

→ Hexadezimalzahlen benötigen weniger Stellen als Dezimalzahlen und sind leicht in Binärdarstellung umzurechnen

1234567890 in Binärdarstellung:

0b1001001100101100000001011010010

In Hexadezimaldarstellung:

0x499602D2


Repräsentation im Rechner


Bits & Bytes

Bit:

● Binärziffer (Binary Digit), Stelle einer Binärzahl („Das niedrigste Bit ist gesetzt, also ist die Zahl ungerade“)

● Maßeinheit für Datenmenge („Zum Speichern der Matrikelnummer benötigen wir 32 bit“)

Byte:

● Binärzahl mit 8 Bit (z.B. „0b01100110“)

● 256 verschiedene Werte

● in der Regel kleinste Einheit für Zugriff auf Daten

● lässt sich als zweistellige Hexadezimalzahl darstellen (0x00 - 0xff)


Halbbyte (links, rechts, high end, low end, Nibble) (Maschinen-)Wort: zwei Byte oder auch: Anzahl der von

einem von-Neumann-Rechner in einem Schritt zu verarbeitenden Byte (also: 4 Byte bei einer 32 Bit-Architektur etc.)

Größenbezeichner (SI-Einheiten): kilo (k, 103), mega (M, 106), giga (G, 109), tera (T, 1012), peta (P, 1015), exa (E, 1018)

1 Kilobyte = 1 kB 1 Kilobit = 1 kb

Achtung: Manchmal wird in der Informatik „kilo“ = 210 verwendet. Für diese Einheit (1024 statt 1000) ist die Bezeichnung „kiB“ statt „kB“ (und MiB, GiB, …).

Weitere Größeneinheiten


Datentypen

● Ein oder mehrere Bytes können zur Speicherung von bestimmten Datentypen verwendet werden

● Wie eine bestimmte Folge an Bytes interpretiert werden soll, muss im Programm oder der Programmiersprache definiert werden.

● Speicherndes und lesendes Programm müssen gleiche Definitionen für Datentypen verwenden


Datentypen II

● Typische Datentypen in Programmiersprachen:● char/byte (1 Byte): Zeichen, ganze Zahl, Bitmuster (sehr flexibel!)

● int (4 Byte): Ganze Zahl

● float (4 Byte): Fließkommazahl

● Signed und Unsigned● Jeder Datentyp für ganze Zahlen kann entweder nur positive (unsigned) oder

positive und negative (signed) Werte speichern

● unsigned char: nur positive Zahlen, Wertebereich 0 – 255

● signed char (= char): negative Zahlen durch Zweierkomplement dargestellt,Wertebereich: -128 – +127


RAM und HDD

RAM (Random Access Memory): Hauptspeicher im Rechner

HDD (Hard Disk Drive): Festplatte

Daten werden binär gespeichert:

● elektrisch geladene / ungeladene Zellen im RAM

● magnetisierte / unmagnetisierte Positionen auf der HDD

http://commons.wikimedia.org/wiki/File:Disque_dur.jpg http://commons.wikimedia.org/wiki/File:256MB_Memory.jpg


Digitale Speicherung

RAM

1

0


Speicherreihenfolge: Least Significant Bit ist relevant

011001012

LSB

oder

1 2 4 8 16 32 64 128

LSB (least significant bit)128 64 32 16 8 4 2 1

Notwendige Unterscheidung, wenn man auf der Ebene einzelner Bits arbeitet.

101001102

In der Regel übernimmt das Betriebssystem die korrekte Interpretation


Überlauf / Overflow

Überlauf geschieht, wenn das Ergebnis einer Rechenoperation nicht mehr in den vorgesehenen Datentyp passt.

Triviale Behandlung: „überstehende“ Bits werden abgeschnitten

Problem: Information geht verloren, falsches Ergebnis entsteht

Aber: elegante Tricks werden möglich, die dieses Verhalten ausnutzen

LSB

128 64 32 16 8 4 2 1

+

=


Codierung eines Wertebereiches von 2n (z.B. für n = 8)• 0• positive Zahlen bis 2n-1 (hier: 1 … 7 )• negative Zahlen bis -2n (hier: -8 … -1)

Idee („Zweierkomplementdarstellung“): • höchstwertiges Bit (links) dient der Codierung des Vorzeichens

• 0 +→

• 1 -→

Vorzeichen einer Zahl ändern (d.h. eine negative Zahl generieren):

• Alle Bits invertieren (1 0, 0 1)→ →

• 1 addieren, eventuellen Überlauf ignorieren

Vorteil: positive und negative Zahlen können direkt addiert/subtrahiert werden

Darstellung negativer Zahlen


Zweierkomplementdarstellung

Beispiel (4 bit)

0 = 0000

1 = 0001

2 = 0010

3 = 0011

4 = 0100

5 = 0101

6 = 0110

7 = 0111

-1 = 1111

-2 = 1110

-3 = 1101

-4 = 1100

-5 = 1011

-6 = 1010

-7 = 1001

-8 = 1000


Nachkommastellen


Binäre Nachkommastellen

● Wie kann ich Nachkommastellen darstellen?

● → 0b0,1

1/81/41/21

1,1012

1,101101/10001/1001/101


Binäre Festkommazahlen

Idee: erste N Bits reserviert für Stellen vor dem Komma, restliche Bits für Stellen nach dem Komma.

Nachteil: Position des Kommas muss bei Definition des Datentyps festgelegt werden. Daher geringe Flexibilität

LSB,

101010102

,


Trick: Exponentialschreibweise

● 123 * 103

● = 12,3 * 104

● = 1,23 * 105

● Generell: Normalisierung auf eine Vorkommastelle üblich


entspricht der Binärzahl {Vorzeichen} 1,{Signifikand} * 2{Exponent}

Exponent: -126 bis +127

Zu gewünschten Exponent wird vor dem Speichern ein Bias (hier: 127) addiert.

z.B. Exponent 2 biased Exponent 129 (= 0b10000001)→

Sonderregeln um 0, ±×∞, NaN zu speichern

Fließkomma-Zahlen: IEEE 754

Beispiel: 32 Bit Float (Single Precision)

Vorze

ichen

(0 →

+, 1

→ -

)

Biased Exponent: 8 Bit Signifikand: 23 Bit

LSBLSB


Beispiel

2.25 als Single Precision Float:

a) Umwandeln in Binärdarstellung

→ 2.25 == 0b10.01

b) Verschieben der Kommastelle hinter die erste '1'

→ 0b10.01 == 0b1.001 * 21

c) Bias zum Exponenten hinzufügen

→ 1 + 127 = 128 = 0b10000000

d) Speicherung im IEEE-754-Format

→ [0][10000000][00100000000000000000000]

Vorze

ichen

Biased Exponent: 8 Bit Signifikand: 23 Bit

LSBLSB


Binärkodierung beliebiger Daten


Codierung: Zuordnungen zwischen Zeichen- oder Wortvorräten

Z.B. kann jede Dezimalzahl durch eine Folge von Ziffern codiert werden

Z. B. Binärrepräsentation eines Schriftalphabets: Für jedes Zeichen (z. B. ‚A‘) definiert die Codierungsvorschrift, welches Element / Wort zuzuordnen ist (z. B. 0100 0001 als 8Bit ASCII-Binärcode für ‚A‘).

Einsatz von Codebäumen z. B. bei der Datenkompression: Ermitteln einer kompakteren / kürzeren Repräsentation für gegebenes Datenmaterial (siehe Entropie-Codierung)

Codes und Codierung


Bit als kleinste Informationseinheit – binäre Codierung (i. d. Regel eines Wahrheitswertes – wahr oder falsch)

Unterste Ebene der Repräsentation von Information durch Daten

Durch Bitfolgen von n Bits lassen sich 2n verschiedene "Einzelentscheidungen" codieren• Beispiel "Woher weht der Wind?" (Gumm / Sommer 2006:6): – 8

Alternativen -> 3Bit sind erforderlich:• Süd = 000, West = 001, Nord = 010 , Ost = 011, Südost = 100,

Nordwest = 101, Nordost = 110, Südwest = 111

Binärcodierung


Notwendig für die Repräsentation von Text: Kodierung des Alphabetes einer Sprache sowie weiterer Elemente (Sonderzeichen, Interpunktion etc.)

Auf der Basis eines Zeichensatzes (interne) Grundlage: Binärkodierung, z. B. 7 Bit ASCII, 8 Bit

ISO-8859, 16 Bit Unicode (= ISO 10646 Universal Character Set UCS) etc.

-> vgl. JOOP: Unicode-Zeichenverwendung in Java möglich

Textkodierung


Gumm, Heinz-Peter; Sommer, Manfred (20067). Einführung in die Informatik. München: OldenbourgHerold, Helmut; Lurz, Bruno; Wohlrab, Jürgen (2007). Grundlagen der Informatik. Praktisch- Technisch – Theoretisch. München et al: Pearson Studium.

Literatur zu dieser Einheit

Documents

UR MI Informatik SS13 02a Bits Bytes Kodierung Update1