Digitale Codierungen

Term	Definition
Basis (Radix)
Ziffernmenge
Darstellung einer Zahl (Polynom)
Stellenwertigkeit an der Position

Beispiele
Dezimalsystem	Oktalsystem
Dualsystem	Hexadezimalsystem

Dezimal- zu Dualsystem: Rechts shift ist eine Division durch 2 Es entsteht nur dann ein Rest, wenn die Bitstelle ist. Beispiel: Resultat:	Zähler Nenner Resultat Rest 25 2 12 1 12 2 6 0 6 2 3 0 3 2 1 1 1 2 0 1
Dual- zu Dezimalsystem bei Nachkommastellen: Links shift ist eine Multiplikation mit 2 Beispiel: Resultat:	a b Resultat Rest 0.1875 2 0.375 0 0.375 2 0.75 0 0.75 2 1.5 1 0.5 2 1 1

Erweiterung der Darstellung einer Zahl:

Beispiel:

Beispiel:

Bei einen Überlauf ():

Dann wäre

1. Rechnen in Bit

   • Übertrag aus dem MSB wird verworfen (gerechnet wird in )

2. als Zweierkomplement

   • Additives Inverses von ist:

   • Praktische Berechnung:

     • Bits invertieren:
     • addieren

Subtraktion wird durch Addition des Komplements ersetzt

Graphische Veranschaulichung für Wortbreite von 3 Bit

unsigned: Überlauf von auf	signed: Überlauf von auf

Term	Definition
set bit (gesetztes Bit)
cleared bit (gelöschtes Bit)
LSB	Least Significant Bit (Bit )
MSB	Most Significant Bit (Bit ) in einer -stelligen Binärzahl
Nibble	Binärzahl mit 4 Bit
Oktett	Binärzahl mit 8 Bit
Byte	Oktett

Binär	Näherung	Binärpräfix	Dezimal	Dezimalpräfix
		Ki - Kibi		K - Kilo
		Mi - Mebi		M - Mega
		Gi - Gibi		G - Giga
		Ti - Tebi		T - Tera
		Pi - Pebi		P - Peta
		Ei - Exbi		E - Exa

1. Umformen in Potenzschreibweise
2. Addition der Exponenten
3. Umformen in Präfixschreibweise

Beispiel:

Erst wenn man die Codierung kennt, kann man daten richtig interpretieren.

• Negative Zahlen

  • Vorzeichen-Bit
  • Einerkomplement
  • Exzess-Code

• Sehr grosse und kleine Zahlen

  • Fixkomma ist unflexibel
  • 334 Milliarden + 0.00001

• Genauigkeit

  • 0.1 ist im Dualsystem nicht exakt darstellbar
  • Rundungsfehler unvermeidbar

• Nicht nur Zahlen

  • Textdarstellung
  • Zeichenkodierungen

Jede Codierung optimiert eine andere Eigenschaft

• Betrag mit Vorzeichen: Intuition
• Einerkomplement: Einfache Negation
• Zweierkomplement: Arithmetische Effizienz
• Exzess: Vergleichbarkeit/Sortierung

Binär	Betrag mit V.	EinerK.	ZweierK.
00000000	0 0	0 0	0 0	-8-8
00010001	1 1	1 1	1 1	-7-7
00100010	2 2	2 2	2 2	-6-6
00110011	3 3	3 3	3 3	-5-5
01000100	4 4	4 4	4 4	-4-4
01010101	5 5	5 5	5 5	-3-3
01100110	6 6	6 6	6 6	-2-2
01110111	7 7	7 7	7 7	-1-1
10001000	0 0	-7-7	-8-8	0 0
10011001	-1-1	-6-6	-7-7	1 1
10101010	-2-2	-5-5	-6-6	2 2
10111011	-3-3	-4-4	-5-5	3 3
11001100	-4-4	-3-3	-4-4	4 4
11011101	-5-5	-2-2	-3-3	5 5
11101110	-6-6	-1-1	-2-2	6 6
11111111	-7-7	0 0	-1-1	7 7

Erstes Bit signalisiert, ob Zahl positiv () oder Negativ () ist.

Problem: Bekannte Rechenregeln funktionieren nicht.

Von allen bits wird das Komplement gebildet.

Problem:

Nach der Komplementbildung wird addiert.

Darstellung vorzeichenbehafteter Zahlen durch Verschiebung des Wertebereichs.

Statt negativer Zahlen wird ein Offset (Bias) addiert

Gegeben	Codierung	Decodierung
Basis Wortbreite Bias typischerweise:	mit

Skalierte Ganzzahl

Pro	Contra
Einfache Implementierung	Fester Wertebereich
Deterministische Genauigkeit	Feste Auflösung
Keine Exponentendarstellung	Überlauf bei grossen Zahlen
Schnelle Berechnung	Ungeeignet für stark unterschiedliche Grössenordnungen

Wertebereich bei Bit und Nachkommabits

	Ganzzahlbereich	Reeller Bereich
unsigned
signed

Kleinster darstellbarer Schritt:

Absoluter Fehler:

Relativer Fehler:

Addition, Subtraktion und Zweierkomplement sind wie bei Ganzzahlen

• Addiert man zwei Fixkommazahlen mit , so muss um Bits nach rechts geschoben werden.

Multiplikation und Division verschieben das Komma

• Multipliziert man zwei Fixkommazahlen , dann ist

muss für jede Zahl berücksichtigt werden

• Wird von den meisten Programmiersprachen kaum unterstützt
• Meist von Hand in Kommentaren
• Limitiert die Zahlen auf Bereiche, die zur Compilezeit bekannt sind
• unflexibel und fehleranfällig, aber performant

	Exponent	Mantisse

Fall	Vorzeichenbit	Exponent	Mantisse	Beispielwert
Positive Null
Negative Null
Positive Unendlichkeit
Negative Unendlichkeit
NaN	oder		mindestens ein Bit	Nicht darstellbare Werte
Subnormale Zahlen	oder		mindestens ein Bit	(positiv)
Normalisierte Zahlen	oder	alles ausser und	beliebig	Alle regulären Werte

Viele Zahlen können nicht präzise dargestellt werden

• • Abbruch nach 23 Bits
  • Beispiel:

• Präzision für “Single Precision”:

  • ist die kleinste relative Differenz nahe 1

1. Hidden Bit ergänzen

2. Exponenten vergleichen

   • Wenn unterschiedlich: Bei kleinerer Zahl Mantisse nach rechts schieben

3. Vorzeichen berücksichtigen

   • Gleiche Vorzeichen: Addieren
   • Unterschiedliche Vorzeichen: Subtrahieren
4. Addition/Subtraktion der Signifikanden

5. Falls Carry = 1: Normalisieren

   • Erhöhe Exponent um 1
   • Schiebe Signifikand um 1 nach rechts
6. Hidden Bit entfernen

Format	Bits	Vorzeichen	Exponent	Mantisse	Bias
Single	32	1	8	23	−127
Double	64	1	11	52	−1023

• Grösserer Exponent grösserer Wertebereich

• Grössere Mantisse höhere Präzision

  • Single Precision:
  • Double Precision:

• Interpretation

• Single signifikante Dezimalstellen
• Double signifikante Dezimalstellen

• Text besteht aus einer endlichen Folge von Zeichen: Buchstaben, Zahlen, Satzzeichen usw.

• Alle Zeichen stammen aus einer endlichen Menge , dem Zeichensatz (character set)

  • Jedem Zeichen kann eindeutig eine natürliche Zahl zugeordnet werden

• Ein Encoding (character encoding, Zeichenkodierung) ist eine bijektive Funktion , die jedem Zeichen eine natürliche Zahl zuordnet

  • Text mit Zeichen kann als endliche Folge von kodierten Zeichen beschrieben werden

American Standard Code for Information Interchange

• Grösse des Zeichensatzes: (nicht 8 Bit!)

• 8-Bit-ASCII sind Extended ASCII-Varianten und nicht standardisiert, sondern Codepages – bspw.: − ISO-8859-1 (Latin-1)

  • für westeuropäische Sprachen mit zusätzlichen Buchstaben wie ä, ö, ü, é usw.

  − Windows-1252

  • Microsoft-Codepage – weitgehend wie ISO-8859-1 mit typografischen Zeichen wie €, “ usw.

  − Codepage 437

  • IBM-PC-Zeichensatz mit grafischen Symbolen, Linienzeichen und Sonderzeichen
• Enthält druckbare (darstellbare) Zeichen und (nicht darstellbare) Steuerzeichen (0x00=NUL, 0x07=BEL, …)

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0

NUL 00

SOH 01

STX 02

ETX 03

EOT 04

ENQ 05

ACK 06

BEL 07

BS 08

TAB 09

LF 0A

VT 0B

FF 0C

CR 0D

SO 0E

SI 0F

1

DLE 10

DC1 11

DC2 12

DC3 13

DC4 14

NAK 15

SYN 16

ETB 17

CAN 18

EM 19

SB 1A

ESC 1B

FS 1C

GS 1D

RS 1E

US 1F

2

SP 20

! 21

“ 22

# 23

$ 24

% 25

& 26

‘ 27

( 28

) 29

* 2A

+ 2B

, 2C

– 2D

. 2E

/ 2F

3

0 30

1 31

2 32

3 33

4 34

5 35

6 36

7 37

8 38

9 39

: 3A

; 3B

< 3C

= 3D

> 3E

? 3F

4

@ 40

A 41

B 42

C 43

D 44

E 45

F 46

G 47

H 48

I 49

J 4A

K 4B

L 4C

M 4D

N 4E

O 4F

5

P 50

Q 51

R 52

S 53

T 54

U 55

V 56

W 57

X 58

Y 59

Z 5A

[ 5B

\ 5C

] 5D

^ 5E

_ 5F

6

` 60

a 61

b 62

c 63

d 64

e 65

f 66

g 67

h 68

i 69

j 6A

k 6B

l 6C

m 6D

n 6E

o 6F

7

p 70

q 71

r 72

s 73

t 74

u 75

v 76

w 77

x 78

y 79

z 7A

{ 7B

| 7C

} 7D

~ 7E

DEL 7F

Globale Zeichennummerierung

• ASCII-kompatibel
• 1 bis 4 Byte pro Zeichen
• Häufige (westliche) Zeichen kurz
• Seltene (westliche) Zeichen länger
• Das erste Byte verrät, wie viele Bytes folgen
• Unicode = Codepoint
• UTF-8 = Bytecodierung

Codepoint-Bereich	Bytes	Bitmuster
U+0000 - U+007FU+0000 - U+007F	11	0xxxxxxx0xxxxxxx
U+0080 - U+07FFU+0080 - U+07FF	22	110xxxxx 10xxxxxx110xxxxx 10xxxxxx
U+0800 - U+FFFFU+0800 - U+FFFF	33	1110xxxx 10xxxxxx 10xxxxxx1110xxxx 10xxxxxx 10xxxxxx
U+10000 - U+10FFFFU+10000 - U+10FFFF	44	11110xxx 10xxxxxx 10xxxxxx 10xxxxxx11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

• Erstes Byte zeigt Länge
• Folgebytes beginnen mit
• ASCII-Zeichen (0-127) bleiben unverändert

Gegeben: Unicode-Codepoint U

1. Bestimme den Wertebereich → Anzahl Bytes.
2. Schreibe U in Binärdarstellung.
3. Fülle die Bits in die x-Positionen des passenden Musters ein.
4. Wandle in Hex um.

Gegeben: Bytefolge

1. Lies das erste Byte.
2. Bestimme anhand der führenden Bits die Länge.
3. Entferne die Strukturpräfixe (110, 10, etc.).
4. Füge die restlichen Bits zusammen.
5. Interpretiere als Codepoint.

UTF-16

• Meist 2 Bytes pro Zeichen
• Zeichen ausserhalb der BMP (Basic Multilingual Pane) benötigen in UTF-16 sogenannte Surrogate Pairs (4 Bytes)
• Nicht ASCII-kompatibel

Vorteil:

• Häufig effizient für asiatische Sprachen

Nachteil:

• Komplexere Handhabung

UTF-32

• Immer 4 Bytes pro Zeichen
• Direkter Zugriff auf Codepoints
• Sehr speicherintensiv

Encoding	Länge	Vorteil	Nachteil
UTF-8	1-4 Byte	ASCII-Kompatibel, effizient	Variable Länge
UTF-16	2-4 Byte	Teils effizient	Surrogate-Komplexität
UTF-32	4 Byte	Sehr einfach	Hoher Speicherbedarf

Unicode ist als Zahlenraum definiert:

Das sind mögliche Codepoints. Dieser Raum ist in Planes (Ebenen) aufgeteilt.

Die BMP umfasst bis , also: . Das sind genau 16 Bit.

In der BMP liegen:

• ASCII
• Lateinische Schriftzeichen
• Griechisch
• Kyrillisch
• Hebräisch
• Arabisch
• Viele asiatische Zeichen
• Mathematische Symbole
• Satzzeichen

• Eine Aussage ist entweder wahr () oder falsch ()
• Aussagen können logisch verknüpft werden

Kommutativität Assoziativität

Distributivität Absorption

( schreibt man auch als oder oder , als oder )

Dualitätsprinzip: Ersetze in einer wahren Gleichung und , Ergebnis bleibt wahr.

Term	Definition
Literal	Variable oder Negation einer Variablen: (positiver Literal), oder (negatives Literal)
Konjunktionsterm	Konjunktion von Literalen:
Disjunktionsterm	Disjunktion von Literalen:
Minterm	Konjunktionsterm, der alle Parameter der Funktion enthält:
Maxterm	Disjunktionsterm, der alle Parameter der Funktion enthält:

Standardisierte Schreibweise. Vorteile:

• aus Wahrheitstabelle konstruierbar
• Vereinfachung systematisch möglich
• Umsetzung als Schaltung (AND-OR-Structure) direkt ableitbar

in Term ist in DNF, wenn er eine ODER-Verknüpfung von UND-Verknüpfungen ist, z.B.:

Da eine höhere Bindungsstärke als hat, sind die Klammern nicht zwingend notwendig. Die kanonische DNF (KDNF) ist die Disjunktion der Minterme.

Je grösser die Blöcke, desto einfacher wird das Ergebnis. Dabei müssen aber bestimmte Regeln eingehalten werden:

• Die Blöcke müssen immer rechteckig sein und
• die Grösse einer Zweierpotenz haben, also 2, 4, 8, 16, 32, …
• Die Blöcke können auch über den Rand hinaus gehen und mit der gegenüberliegenden Seite verbunden werden,
• Blöcke können sich teilweise überlappen. Das kann sinnvoll sein, wenn dadurch grössere Blöcke entstehen.
• Werte, die sowohl einfach als auch negiert vorkommen, werden gestrichen
• Ein Block wird nur berücksichtigt, wenn seine Einsen nicht vollständig in anderen Blöcken enthalten sind. Andernfalls entsteht ein nichtessentieller Term, der redundant ist, da andere Terme bereits die gleichen Variablenbelegungen abdecken und nicht weiter vereinfacht werden können.

OK			NOK

Universalbaustein praktisch (in CMOS schnell sowie einfach aufzubauen) funktional vollständig: jede Boolesche Funktion lässt sich nur mit NAND realisieren.

OP	impl
NOT
AND
OR

Boolesche Logik realisiert binäre Addition XOR bildet die Addition zweier Bits ab (im Zahlenraum mit nur und , also ), AND bildet den Übertrag ab Addition mod 2 Übertrag
Halbaddierer (half adder) Kann 2 einstellige Binärzahlen addieren Hat 2 Eingänge () und 2 Ausgänge ()
Volladdierer (full adder) Hat 3 Eingänge ()
4-Bit Ripple carry adder Jedes Bit muss auf das Carry-Bit des letzten Volladierers warten
Carry Look-Ahead adder Reduziert propagations-delay durch komplexere hardware

• Abgeschlossen: Jede Operation erzeugt wieder ein Element in
• Es existiert das neutrale Element ( für die Addition, für die Multiplikation)
• Jedes Element ist sein eigenes additives Inverses.
• Addition und Multiplikation sind kommutativ und assoziativ.
• Es gilt das Distributivgesetz.

Darstellung	Beispiel
Zahl
Vektor
Polynom

Polynome erlauben

• Verschiebungen elegant zu beschreiben
• Redundanz strukturiert zu erzeugen
• Generatorpolynome (zyklische Codes)
• CRC-Rechnung als Polynomdivision

Polynomaddition in	Polynommultiplikation in

NAND Game

nand2tetris

In realen Systemen trifft Unsicherheit auf. Diese lässt sich nicht exakt vorhersagen, sondern nur statistisch beschreiben. Dafür verwenden wir Wahrscheinlichkeit.

Term	Definition
Disjunke Ereignisse	Ereignisse, die sich gegenseitig ausschliessen. Beispiel: ist gerade oder ungerade
Zufallsvorgang	Ein Vorgang mit mehreren möglichen Ergebnissen, dessen Ausgang nicht sicher vorhergesagt werden kann
Zufallsexperiment	Zufallsvorgang, der geplant ist und kontrolliert ablauft

Term	Definition
Ergebnismenge	Die Ergebnismenge eines Zufallsvorgangs umfasst alle möglichen Ausgänge des Experiments. Sie wird mit dem Symbol (Omega) bezeichnet. Die Anzahl aller möglichen Ergebnisse der Ergebnismenge wird mit bezeichnet.
Ergebnis	Ein einzelner möglicher Ausgang heisst Ergebnis
Ereignis	Ein Ereignis ist eine Teilmenge der Ergebnismenge

Für jedes Ereignis gilt .

Term	Eigenschaft
Sicheres Ereignis	Die Wahrscheinlichkeit der gesamten Ergebnismenge ist
Unmögliches Ereignis	Die Wahrscheinlichkeit der leeren Menge ist
Additionsregel	Für zwei Ereignisse und : Für disjunkte Ereignisse:
Gegenereignis	Wird notiert als und hat die Eigenschaft .

Wahrscheinlichkeit, dass oder auftritt:

Wahrscheinlichkeit, dass zuerst und dann auftritt:

Wenn ein Experiment eine Anzahl verschiedener und gleich möglicher Ausgänge hervorbringen kann und einige davon als günstig anzusehen sind, dann ist die Wahrscheinlichkeit eines günstigen Ausgangs gleich dem Verhältnis der Anzahl der günstigen zur Anzahl der möglichen Ausgänge.

Dabei gilt:

• : Ergebnismenge (alle möglichen Ergebnisse)
• : betrachtetes Ereignis
• : Anzahl günstiger Ergebnisse
• : Anzahl aller möglichen Ergebnisse

Laplace-Wahrscheinlichkeit erfordert Berechnung von Anzahlen. Kombinatorik ist die Mathematische Technik hierfür.

	Wiederholung	Keine Wiederholung
Anordnung	Permutation mit Wiederholung	Permutation ohne Wiederholung
Geordnete Auswahl	Variation mit Wiederholung	Variation ohne Wiederholung
Ungeordnete Auswahl	Kombination mit Wiederholung	Kombination ohne Wiederholung

Anordnung von Objekten, die nicht alle voneinander unterscheidbar sind ( Subsets mit gleichen Objekten).

Anordnung von Objekten, die alle unterscheidbar sind.

• Reihenfolge spielt eine Rolle
• Elemente dürfen mehrfach vorkommen

• Reihenfolge spielt eine Rolle
• Elemente dürfen nicht mehrfach vorkommen

• Reihenfolge spielt keine Rolle
• Elemente dürfen mehrfach vorkommen

• Reihenfolge spielt keine Rolle
• Elemente dürfen nicht mehrfach vorkommen

Anzahl der Möglichkeiten
Optionen Auswählen		Beachtung der Reihenfolge
		✓	✗
Wiederholung erlaubt	✓
	✗

Die hypergeometrische Verteilung ist ein Modell, das verwendet wird, um die Wahrscheinlichkeit von Erfolgen (gewünschten Ergebnissen) aus den gesamt möglichen Erfolgen aus Objekten in Ziehungen zu berechnen.

Ein Bitfehler bezeichnet die inkorrekte Wiedergabe eines Bits während der Datenübertragung oder ‐speicherung. Das bedeutet, dass ein Bit von 0 zu 1 oder von 1 zu 0 fälschlicherweise geändert wird. Die Wahrscheinlichkeit, dass ein Datenblock der Grösse Bits bei einer Fehlerrate von fehlerhaft ist, kann mit folgender Formel berechnet werden:

Copy codeCopyCopied! Bitübertragung │ ┌────┴────┐ Korrekt Fehler 1-p p Copy codeCopyCopied! Bitübertragung │ ┌────┴────┐ Korrekt Fehler 1-p p

Wahrscheinlichkeit für genau Fehler in einem Datenblock mit Bits bei Bitfehlerrate (Binomialverteilung):

Jede mögliche Fehleranordnung hat die Wahrscheinlichkeit

Es gibt solche Anforderungen. Darum gilt

Die Binomialverteilung beschreibt, wie wahrscheinlich es ist, dass bei unabhängigen Versuchen genau Erfolge auftreten.

In unserem Kontext bedeutet das:

• = Anzahl übertragener Bits
• = Bitfehlerwahrscheinlichkeit
• = Anzahl Fehler

Wie wahrscheinlich ist Ereignis , wenn Ereignis bereits eingetreten ist? Formelle Schreibweise: .

Allgemein gilt für die bedingte Wahrscheinlichkeit:

Voraussetzung ist dabei, dass gilt:

Die Formel bedeutet:

• Im Nenner steht die Wahrscheinlichkeit der Bedingung .
• Im Zähler steht die Wahrscheinlichkeit, dass sowohl als auch eintreten.

Man betrachtet also nur noch den Teil des Wahrscheinlichkeitsraums, in dem gilt, und fragt dann, wie gross darin der Anteil der Fälle ist, in denen zusätzlich eintritt.

Daraus folgt die Multiplikationsregel:

Aus der Definition folgt direkt eine wichtige Umformung:

Ebenso gilt auch:

Setzt man die beiden Ausdrücke gleich, erhält man

Durch Umstellen ergibt sich das Bayes-Theorem:

Diese Formel erlaubt es, Wahrscheinlichkeiten umzukehren: Aus der Wahrscheinlichkeit von unter der Bedingung kann die Wahrscheinlichkeit von unter der Bedingung berechnet werden.

Angenommen ein Ereignis kann durch mehrere verschiedene Ursachen entstehen. Seien

Ereignisse, die

• sich gegenseitig ausschließen
• zusammen den gesamten Ereignisraum bilden

Dann gilt für jedes Ereignis :

Diese Formel nennt man den Satz der totalen Wahrscheinlichkeit. Sie beschreibt die Gesamtwahrscheinlichkeit eines Ereignisses als Summe aller möglichen Fälle, in denen es entstehen kann.

Zwei Ereignisse und heissen unabhängig, wenn das Eintreten des einen Ereignisses keinen Einfluss auf die Wahrscheinlichkeit des anderen hat. Dann gilt:

Das bedeutet: Auch wenn bereits eingetreten ist, bleibt die Wahrscheinlichkeit von unverändert. Setzt man das in die Multiplikationsregel ein, erhält man:

Die Informationstheorie versucht, mathematisch zu messen:

• wie viel Information Ereignisse enthalten

  • ein sehr erwartbares Ereignis liefert wenig Information
  • ein überraschendes Ereignis liefert viel Information
• wie unsicher eine Informationsquelle ist
• wie effizient Informationen codiert werden können.

Die Entropie ist dabei die zentrale Grösse, die die durchschnittliche Informationsmenge einer Quelle beschreibt.

Die Einheit der Information ist das Bit.

Der Informationsgehalt eines Symbols ist ein Mass dafür, wie viel Information das Symbol trägt, basierend auf seiner Wahrscheinlichkeit des Auftretens .

Der Entscheidungsgehalt einer Quelle gibt an, wie viel Information im Durchschnitt benötigt wird, um ein Ereignis aus gleich wahrscheinlichen unterschiedlichen Ereignissen zu identifizieren.

Die Entropie beschreibt den durchschnittlichen Informationsgehalt / durchschnittliche Unsicherheit einer Quelle.

Ergebnis ist sicher	Ergebnis tritt nie auf Trägt 0 zur Entropie bei	Minimum: deterministische Quelle Maximum: gleichverteilte Quelle

Die Redundanz beschreibt den Anteil vorhersehbarer Information / den Unterschied zwischen dem maximal möglichen Entscheidungsgehalt und der tatsächlichen Entropie der Quelle.

Hohe Redundanz	Geringe Redundanz
Quelle stark vorhersehbar	Quelle nahe maximaler Unsicherheit

Eine Quelle mit hoher Redundanz enthält viele regelmässige Strukturen oder Abhängigkeiten. Diese können genutzt werden, um Daten effizienter zu codieren oder zu komprimieren.

Idealerweise sollte die Länge eines Codeworts dem Informationsgehalt des Symbols entsprechen:

Da Codewörter jedoch aus einer ganzen Anzahl Bits bestehen müssen, wird aufgerundet:

Die mittlere Codewortlänge ist definiert als der gewichtete Durchschnitt der Längen der Codewörter, wobei jedes Gewicht der Auftretenswahrscheinlichkeit des entsprechenden Symbols gleich ist.

Es gilt für jeden Code

Die Redundanz des Codes ist die Differenz zwischen der mittleren Codewortlänge und der Entropie der Quelle.

Interpretation: Beschreibt, wie ineffizient die Codierung ist / Verlust durch nicht-optimalen Code.

Ein Code besitzt die Präfixeigenschaft, wenn kein Codewort der Anfang eines anderen Codeworts ist. Präfixcodes sind wichtig, weil sie eine eindeutige und sofortige Decodierung ermöglichen.

Symbol Code A 00 B 1010 C 110110 D 111111

Das Shannon-Theorem beschreibt die theoretischen Grenzen der Datenkompression. Für jede Informationsquelle mit mittlerer Codewortlänge und deren Entropie gilt:

• Entropie ist die theoretische Mindestlänge eines Codes / Grenze der Kompression
• Praktische Codes können dieser Grenze sehr nahe kommen.

Diskrete Quellen ohne Gedächtnis haben Symbole, die unabhängig von vorherigen Symbolen auftreten. Jedes Symbol aus einem endlichen Set tritt mit einer Wahrscheinlichkeit auf. Verbundwahrscheinlichkeit für die beiden Zeichen und lautet:

In der Praxis sind nur wenige Datenquellen vollständig gedächtnislos. Häufig hängt die Wahrscheinlichkeit eines Zeichens vom vorhergehenden Zeichen ab. Solche Kontextabhängigkeiten lassen sich mit bedingten Wahrscheinlichkeiten beschreiben:

Für zwei aufeinanderfolgende Zeichen gilt:

Mit

ergibt sich

Interpretation

• : Unsicherheit über das erste Zeichen
• : “Verbundentropie” = Unsicherheit über zwei aufeinanderfolgende Zeichen
• : verbleibende Unsicherheit über wenn bereits bekannt ist

Da Kontextinformation Unsicherheit reduziert, gilt:

Interpretation: beschreibt, wie viel “überflüssige Struktur” in der Quelle steckt / Potenzial für Kompression.

Kontext reduziert Unsicherheit

• Entropie sinkt
• Redundanz steigt

Anwendungen:

Datenkomprimierung

• Verlustfrei
• Verlustbehaftet

Verschlüsselung

• Symmetrisch
• Asymmetrisch

Kompression ist nur möglich, wenn Redundanz vorhanden ist.

Art der Redundanz	Beispiel	Verfahren
Wiederholungen	AAAAAAAA	“Run-Length-Encoding (RLE)” (Seite 1)
Ungleiche Wahrscheinlichkeiten	häufige Zeichen	“Huffman-Codierung” (Seite 1)
Muster / Struktur	ABCABCABC	“Lempel-Ziv-Codierung (LZ77)” (Seite 1)

Statistische Verfahren	z.B. Huffman-Codierung für die deutsche Sprache nutzen bekannte Wahrscheinlichkeiten	Eigenart der Daten (Wahrscheinlichkeiten) werden berücksichtigt
Adaptive Verfahren	z.B. Huffman-Codierung mit gemessener Häufigkeitsverteilung lernen Wahrscheinlichkeiten während der Codierung
Wörterbuchbasierte Verfahren	z.B. LZ77, LZ78, LZW, DEFLATE nutzen wiederkehrende Muster im Datenstrom	Eigenart der Daten (Wahrscheinlichkeiten) werden nicht explizit berücksichtigt – stattdessen Muster

Ziel der Quellencodierung:

• Verfahren zur Entwicklung eines präfixfreien Codes mit minimaler mittlerer Codewortlänge
• Rekursives Verfahren, d.h. der Binärbaum wird nicht von der Wurzel, sondern von den Blättern aus entwickelt

Kerngedanke

• Häufige Zeichen kurze Codes
• Seltene Zeichen lange Codes

Verfahren

1. Sortiere Zeichen nach Wahrscheinlichkeit
2. Kombiniere die zwei kleinsten
3. Ersetze sie durch neuen Knoten
4. Wiederhole, bis ein Baum entsteht
5. Weise 0 / 1 entlang der Kanten zu

Der Huffman-Code ist nicht eindeutig – aber immer optimal (bzgl. mittlerer Länge).

• Wiederholungen werden nicht mehrfach gespeichert, sondern gezählt.
• wird bei vielen Bildformaten benutzt zum Beispiel BMP, PCX und TIFF.
• gehört zu musterbasierten Verfahren
• Spezialfall von Lempel-Ziv

• sehr einfach
• sehr schnell
• keine Wahrscheinlichkeiten nötig

Kerngedanke

• Wiederholungen ersetzen durch: Symbol,AnzahlSymbol,Anzahl

Gut geeignet für

• lange Wiederholungen
• Bilder (z.B. einfarbige Flächen)
• einfache Muster

Schlecht geeignet für

• zufällige Daten
• häufige Wechsel

Kerngedanke

• Muster werden wiedererkannt und ersetzt durch Verweis auf vorherige Sequenz

Grundidee

Zwei Bereiche

• Search Buffer Vergangenheit
• Look-Ahead Buffer Zukunft

Grosser Buffer	Kleiner Buffer
Bessere Kompression, weil längere Muster erkennbar	Schneller, weil weniger speicher
Langsamer	Schlechtere Kompression

Codierung

• Statt Zeichen: Distanz,Länge,SymbolDistanz,Länge,Symbol

  • Distanz wie weit zurück
  • Länge wie lang das Muster
  • Symbol nächstes Zeichen

Die Lempel‐Ziv‐Welch‐Komprimierung ist ein Verfahren zur verlustfreien Datenkompression, das auf der Lempel‐Ziv‐ Komprimierung aufbaut. Sie verwendet ein Wörterbuch, um wiederkehrende Sequenzen zu identifizieren und durch kürzere Codes zu ersetzen.

1. Beginne mit einem Wörterbuch, das bereits alle möglichen Einzelzeichen enthält.
2. Suche im Wörterbuch die längste Sequenz, die mit den nächsten Zeichen der Eingabe übereinstimmt.
3. Speichere den Index des gefundenen Wörterbucheintrags.
4. Erstelle einen neuen Eintrag im Wörterbuch mit der gefundenen Sequenz, gefolgt vom nächsten Zeichen der Eingabe.
5. Verschiebe das Eingabefenster um die Anzahl der codierten Zeichen.
6. Wiederhole den Prozess, bis alle Zeichen codiert sind.

• Superposition

  • Ein Qubit kann gleichzeitig und repräsentieren. Mehrere Qubits können dadurch alle möglichen Zustände gleichzeitig darstellen.

• Beispiel

• Interferenz

  • sind Amplituden. Zwei Qubits können sich gegenseitig beeinflussen, indem die Amplituden mittels Interferenz verstärkt oder ausgelöscht werden

  • Quantenalgorithmen verändern gezielt die Amplituden:

    • richtige Lösungen werden verstärkt
    • falsche Lösungen werden abgeschwächt

• Verschränkung

  • Verschränkung bedeutet, dass zwei Qubits einen gemeinsamen Zustand besitzen, der sich nicht in zwei unabhängige Einzelzustände zerlegen lässt.
  • Misst man eines der Qubits, ist der Zustand des anderen sofort festgelegt

Gesamtübersicht des CPU Zyklus

1. Fetch: Instruktion aus RAM lesen
2. Decode: Opcode interpretieren
3. Operand-Fetch: Speicherwerte laden
4. Execute: ALU rechnet
5. Writeback: Ergebnis ins Register
6. IP erhöhen