So, schönen guten Tag.
Ich begrüße Sie zur letzten Vorlesung in diesem Jahr,
Grundlageninformatik II.
Ich denke, das ist schon wieder etwas laut.
Ich mache mal wieder ein bisschen leiser.
Jetzt dürfte es in Ordnung sein.
Bei der Zahl von Personen heute reicht das sicherlich so.
Letztes Mal haben wir uns beschäftigt mit Aspekten der physikalischen
Realisierung.
Da hatten wir uns schon einiges angeschaut.
Ich hatte Ihnen den Transistor gezeigt, den NMOS Transistor.
Ich hatte Ihnen den PMOS Transistor gezeigt.
Dann hatten wir uns einige einfache Schaltungen angeschaut.
Zunächst war es der Inverter.
NMOS, PMOS Transistoren zusammen ein CMOS Inverter.
Sehr einfaches Schaltbild.
Dann hatten wir ein NAND und NOR Schaltbild uns angeschaut und
gesehen, wie man daraus dann noch mehr machen kann.
Ich hatte Ihnen dann gezeigt ein Transfergatter und wir hatten dann
gesehen, wie man daraus ein Verzögerungselement baut mit einem nicht
überlappenden Zwei-Phasen-Takt, der dafür sorgt, dass man Werte
reinschreiben und wieder auslesen kann.
Schön gesteuert.
Wir hatten dann gesehen, wie man solche Schaltungen tatsächlich
erstellt.
Im Full-Custom-Entwurf gemalt als Rechtecke in verschiedenen Farben,
die jeweils die Materialien darstellen und die dann genau die Vorlage
darstellen für den Herstellungsprozess.
Ich hatte Ihnen dann gezeigt, wie das tatsächlich aussieht, wenn man
zum Beispiel einen Inverter malt, könnte er so angeordnet sein.
Also ein bisschen platzsparend hier, ein bisschen kompakt
zusammengebaut.
Und auf die Art und Weise kann man also sehr genau dafür sorgen, an
welcher Stelle auf einem Chip tatsächlich solche Elemente dann
angesiedelt sind.
Ich hatte Ihnen dann etwas erzählt über den Entwurf auf höheren
Abstraktionsebenen.
Wir hatten uns angeschaut, Anforderungen für den Hardware-Entwurf,
Hardware -Software-Codesign.
Ich habe Ihnen etwas erzählt über diese verschiedenen Ebenen, die man
sich anschauen muss, von der abstrakten Ebene bis runter zur
Fertigung.
Und wir hatten dann als nächstes uns angeschaut, ein Beispiel für eine
Beschreibung von Komponenten mithilfe einer Hardware
-Beschreibungssprache, VHDL, wo man einerseits die Struktur definiert
und dann auch das Verhalten beschreiben kann.
Hier dargestellt am Beispiel eines Halbadierers.
Dann waren wir zum Volladierer gekommen, hatten den abstrakt definiert
und kamen dann zur internen Struktur, in dem wir dann drei Komponenten
dort drin hatten, zwei Halbadierer und ein Oderglied, das wir zunächst
mal deklarieren mussten.
Dann wurden die initialisiert, zwei Komponenten, jeweils Halbadierer,
eine Komponente Odergatter.
Die Variablen wurden entsprechend abgebildet auf die Ports von den
Komponenten und dadurch ergibt sich dann die Struktur eines
Volladierers.
Das war das Beispiel, wie man also solche Hardware-Bausteine bauen
kann.
Ich hatte Ihnen dann noch etwas erzählt über die Varianten des
Hardware -Entwurfs mit FPGAs und mit ASICs, also völlig in Hardware
fest oder noch etwas weich, in dem man zur Laufzeit noch solche
Bereiche konfigurieren kann.
Das war dieses Bild gewesen von einem FPGA mit den einzelnen
Komponenten, einen Ausgabekomponenten, Verbindungen, die man
programmieren kann und die Configurable Logic Blocks, die man einfach
durch Setzen von Bits entsprechend konfiguriert für die Schaltung, die
man dort realisieren möchte.
Eine wesentliche Technologie, um Schaltungen heutzutage schnell zu
realisieren.
Und das war es dann eigentlich in dem Kapitel und wir kommen dann
heute zu dem nächsten Kapitel, nämlich zum Kapitel Kodierung,
Zahlendarstellungen, was ich heute noch anfangen möchte und Ihnen
einiges erzählen möchte darüber, wie wir Informationen im Rechner
darstellen.
So, wie macht man das?
Worum geht es überhaupt?
Es geht darum, dass wir irgendwelche Informationen darstellen, hier
ist noch kurz eine Übersicht darüber, was wir uns alles anschauen
werden und was wir darstellen müssen, das sind unterschiedlichste
Zahlen, also irgendwelche Ziffern oder Buchstaben oder ähnliches und
die Frage ist, wie macht man das intern?
Man kann eine Zahl 2 zum Beispiel mit 4-Bit oder auch mit 2-Bit
natürlich darstellen in der Dualdarstellung.
Sie können es aber auch in der sogenannten EPSIDIC-Darstellung,
Extended Binary Coded Decimal Interchange Code, ein Standard für die
Darstellung von Zeichen, die werden wir noch genauer ansehen.
Ich kann aber auch den sogenannten XS3-Code verwenden, bei dem ich
einfach 3 draufaddiere auf die Zahlen und dann habe ich hier statt der
2 eine 5 dargestellt.
Wann jemand weiß, das ist ein XS3-Code, ist das die entsprechende
Darstellung der 2.
Nur um hier diese Ziffer 2 oder Zahl 2 darzustellen, gibt es
verschiedenste Möglichkeiten, kann man sich überlegen, was man machen
will.
Diese Zeichenfolge O-T-T-O kann man natürlich auch unterschiedlich
darstellen und hier sehen Sie die Darstellung in ASCII, American
Standard Code for Information Interchange, also Standardisierungen für
die Repräsentation von Zeichen der realen Welt in interne
Darstellungen.
Das ist hier eine typische ASCII-Code-Darstellung.
Und üblicherweise in Ihren Rechnern sind intern Zeichen im ASCII
-Format dargestellt.
Was wir alles darstellen müssen, sind einerseits Zahlen, dann hatten
wir schon Texte, wir haben Wahrheitswerte und bei Zahlen, was sind
eigentlich Zahlen?
Das können natürliche Zahlen sein, das können ganze Zahlen sein,
rationale Zahlen, reelle Zahlen.
Leider können wir etwas außerhalb von Q, außerhalb der rationalen
Zahlen nicht darstellen im Rechner, können also keine irrationalen
Zahlen darstellen, weil Sie für irrationale Zahlen unendlich viele
Ziffern bräuchten, um die Zahlen darzustellen.
Das steht Ihnen leider nicht zur Verfügung.
Im Rechner haben Sie immer eine endliche Genauigkeit, eine begrenzte
Genauigkeit und damit nur rationale Zahlen.
Also das ist schon mal eine interessante Erkenntnis.
Wir werden aber sehen, wie wir trotzdem versuchen, reelle Zahlen
irgendwie sinnvoll darzustellen.
Und ansonsten gibt es natürlich auch noch Sprache, Bilder, Videos und
so weiter.
Sehr viele verschiedene Objekte des täglichen Lebens, die man
darstellen möchte.
Sie könnten sich auch überlegen, wie man irgendwelche...
Also etwas, was man noch nicht darstellen kann, das sind Gerüche zum
Beispiel.
Das ist etwas, was man gerne haben würde, wenn man einen Kinofilm
sieht, wenn man dann Gerüche auch noch darstellen könnte, könnte man
auch Gerüche übertragen.
Etwas, was in Filmen sicherlich die Realität etwas verbessern würde,
aber ob man das immer will, weiß ich nicht.
Es gibt jedenfalls verschiedenste Dinge der normalen Erfahrungswelt,
die man irgendwie im Rechner darstellen möchte.
Und Sie wissen, was wir heute alles versuchen darzustellen, das geht
also über Zahlen und Texte deutlich hinaus.
Intern wird aber alles irgendwie in binärer Form mit Nullen und Einsen
dargestellt.
Und natürlich, was hier noch stand, alle möglichen Datentypen.
Sie wollen natürlich nicht nur von Nullen und Einsen reden, sondern
Sie wollen irgendwelche abstrakten Datentypen haben.
Dann ist das Problem natürlich, wie man das darstellen kann.
Sie haben nur zwei Werte, das ist auch eine sehr effiziente Art der
Darstellung, kann man auch zeigen, dass man damit sehr effizient
Informationen repräsentieren kann.
In dem Sinne, dass man wenig Redundanz da drin hat.
Und im Prinzip, sagte ich schon, alle Objekte werden als Folgen über
die Menge 0,1 dargestellt.
Und was ich natürlich machen muss, ist, ich muss die Zahlen nicht nur
in einem Rechner darstellen, ich muss sie auch übertragen können von
einem Rechner zum anderen.
Ich muss wissen, dass das, was ich in einem Rechner intern dargestellt
habe, im anderen Rechner auch genauso interpretiert wird.
Wenn ich also hier irgendeinen Text habe, ich übertrage ihn in einen
anderen Rechner, dann muss das, was hier lesbar war, muss hier auch
wieder lesbar sein.
Und dann kommen natürlich noch verschiedene andere Sachen dazu, über
einfache Nachrichtenübertragung, die Bildsignalübertragung,
Fernsehübertragung und ähnliches, Fernsehbilder.
Das Thema der Geheimhaltung ist natürlich wichtig, früher war das ein
reines militärisches Thema, heutzutage wissen wir, es ist ein
Standardthema der Kommunikation und auch für E-Commerce und
Vertragsschließungen usw.
Digitale Signaturen und ähnlich interessant, Übersetzung,
Informationen übersetzen.
Wir haben ja im KIT ein Service, bei dem Vorlesungen automatisch in
andere Sprachen übersetzt werden, also automatisch in Englisch oder in
Spanisch, die beiden stehen zur Verfügung.
Das wird von der Gruppe von Enviable gemacht.
Ist eine interessante Art, wie man also jemandem, der eine Sprache
nicht versteht, das nahe bringen kann.
Es gibt Varianten, wo man ins Telefon reinspricht, mit jemandem
spricht in Japan, und der hört im gleichen Tonfall, wie man das auf
Deutsch sagt, das gleiche auf Japanisch, aus dem Telefonhörer, weil es
intern übersetzt wird.
Das sind also alles Dinge, Übersetzungen, noch eine andere Sache als
einfach nur Übertragung von Daten.
Also Vielfalt von Problemen, wenn es darum geht, Informationen im
Rechner darzustellen und dann die im Rechner gefundene Darstellung
wieder nach außen zu visualisieren oder hörbar zu machen oder was
immer man damit machen muss, hat das erfahrbar zu machen usw.
Sie können auch Informationen haptisch versuchen darzustellen, indem
sie irgendwie merken anhand einer Oberfläche, dass da irgendwelche
Dinge sich verändern.
So können zum Beispiel Blinde problemlos mit dem Rechner
kommunizieren, weil die eine haptische Informationsleiste haben
unterhalb des Bildschirms und darauf mitgeteilt bekommen, was auf dem
Bildschirm zu sehen ist.
Faszinierend, wie man damit Informationen aus dem Rechner darstellen
kann.
Aber das sind eben alles unterschiedliche Arten, wie gesagt,
Informationen zu repräsentieren.
Wir werden uns nun mit ganz wenigen Teilaspekten beschäftigen.
Diese ganzen anderen Dinge, die ich gerade erwähnt habe, kommen hier
fast alle nicht vor.
Ich will also einfach Ihnen sagen, wie man auf einfachste Art und
Weise überhaupt davon reden kann, dass man etwas codiert.
Wenn ich etwas codiere, dann habe ich irgendein Alphabet und noch ein
Alphabet, ein anderes Alphabet, eventuell ein anderes Alphabet und
möchte jetzt etwas darstellen.
Ich möchte ein Zeichen aus dem einen Alphabet durch eine Folge von
Zeichen in dem anderen Alphabet darstellen.
Das ist eine Codierung.
Also ich hatte gesagt, die Zahl 2 können wir darstellen durch zum
Beispiel 0010 wäre eine Codierung.
Da würde ich der 2 diese Folge von Ziffern zuordnen.
Abbildung von Dezimalziffern auf binäre Ziffern.
Das wäre eine Codierung.
Der Bildbereich heißt dann der Code und das einzelne Wort ist das
Codewort.
Also das C von A wäre dann die Menge alter Codewörter und jedes
einzelne ist ein Codewort.
Ein ganz einfaches Beispiel, das Sie vielleicht kaum noch kennen.
Ich nehme an, Sie haben mal irgendwann ein solches altes Telefon
gesehen mit einer Wählscheibe.
Diese Wählscheibe codiert die Zahlen, die hier drauf sind, wenn man
hier irgendwo reintippt und so rüber geht.
Jetzt hätte ich eigentlich das animiert haben müssen, wenn ich da
raufgehe, dass sich das tatsächlich bewegt.
So schön ist das nicht.
Aber Sie wissen, was passiert, wenn man die Wählscheibe dreht.
Sie läuft zurück.
Und beim Zurücklaufen werden zwei Zeichen im Prinzip erzeugt,
beziehungsweise wird ein Zeichen immer wieder erzeugt, also einen hier
als L gekennzeichnet.
Das ist eine einfache Zählcodierung.
Da werden die Ziffern einfach durch eine Anzahl von solchen Ls
codiert.
Dann entsteht noch ein O und damit sind sie unterschieden.
Und damit kann ich also problemlos Zahlen darstellen.
Einfache Zählcodierung, wie man das im Telefon früher immer so gemacht
hat.
Heutzutage natürlich anders.
Ein anderes Beispiel ist die Morse-Codierung, auch eine Art der
Kommunikation über Morse-Zeichen.
Sie kennen das mit zwei verschiedenen Zeichen, kurz und lang.
Mit dit und da und so weiter.
Und so kann man Zeichen darstellen.
Also SOS kennen Sie dreimal kurz, dreimal lang, dreimal kurz.
Das ist also gerade die Darstellung von S, O und S.
Sehr einfache Darstellung.
Es wird immer noch durchaus mit Morse-Zeichen kommuniziert, vor allen
Dingen in irgendwelchen militärischen Bereichen.
Und das Interessante ist, dass wir hier diese Zeichen, die ich auf der
vorigen Folie in der Tabelle hatte, die Codierung findet man hier in
einem Code-Baum.
Das heißt hier haben wir zum Beispiel gekennzeichnet, also in dem Baum
sind die langen Zeichen, diese Striche sind angegeben, die gehen immer
nach rechts hierbei und nach links.
Da habe ich nicht angedeutet, dass hier jeweils ein Punkt im Prinzip
stehen müsste.
Das heißt ein E ist ein Punkt, ein I sind zwei Punkte.
Wenn ich also das Wort Eis darstellen möchte, ein Punkt, dann zwei
Punkte und dann drei Punkte.
Ja, ist das jetzt das Wort Eis oder ist das etwas ganz anderes?
Ist das vielleicht E, I, E und dann nochmal irgendwas dahinter?
Wenn ich eine solche Folge habe, was stellt die eigentlich dar?
Also wenn ich die einfach so aneinanderschreibe, ist das schwierig.
Woran liegt das?
Das E ist ein Zeichen und es hat den gleichen Anfang wie das I.
Das hier war das E, das ist das I, das ist das S.
Und ich kann nicht feststellen, wo dann hier eigentlich der
Unterschied ist.
Das führt schon auf ein typisches Problem hin.
Also die Kodierung einer Folge von Kodwörtern muss natürlich möglich
sein, wenn Sie Folgen von Zeichen haben, müssen Sie aus den
Kodwörtern, aus der Folge der Kodwörter wieder eindeutig
zurückschließen können, auf das, was Sie kodiert hatten, weil Sie die
Informationen wiedergewinnen wollen.
Also das ist ein Problem, wenn man die Morse-Kodierung so auffasst.
Man hat natürlich, wenn man Morse, wenn man das anwendet, hat man
normalerweise immer so einen kleinen Zwischenraum hier drin.
Und das kann man sich dann, da kann man sich darauf schulen, dass man
das hört, wo die Unterschiede sind, wo die kurzen Lücken sind zwischen
den einzelnen Zeichen.
Und dann kann man das erkennen.
Das muss man natürlich intern auch darstellen.
Also das ist ein Problem, auf das wir gleich wieder zurückkommen
werden.
Mal kurz jetzt zu den Arten von Kodierungen.
Ich kann natürlich solche Abbildungen von einem Alphabet auf Wörter
über dem anderen Alphabet sehr unterschiedlich machen.
Ich kann zum Beispiel einfach ein Zeichen in ein anderes Zeichen
abbilden.
Das wäre eine einfache Schiffrierung durch Substitution, macht man zum
Teil in kryptografischen Verfahren.
In einfachen kryptografischen Verfahren, in Stromschiffrierungen, wo
man also irgendeine Textfolge hat und die direkt übersetzt jedes
Zeichen in die schiffrierte Folge, dann ist das eine solche
Schiffrierung.
Aber eine sehr einfache.
Dann könnte ich sagen, ich stelle jedes Zeichen durch eine Bitfolge
fester Länge dar.
Alles die gleiche Länge.
Also zum Beispiel die Ziffern von 0 bis 9 einfach als 0000, 0001, 0010
und das letzte wäre dann die 1001, die 9.
Das wäre also eine Darstellung der Ziffern von 0 bis 9.
Und alle mit 4 Bits.
Eine Blockodierung mit 4 Bits.
Ich könnte allgemein sagen, wenn ich jetzt auf die Binärkodierung
gehe, dann sage ich jetzt auf die Bullshit-Folge, auf 011, dann nenne
ich das eine Binärkodierung.
Meine Beispiele waren eigentlich fast alles Binärkodierungen.
Und dann ist dort eine Blockkodierung mit Länge N, wäre dann eine N
-Bit -Kodierung.
Also dieses Binary-Coded-Decimal, was ich hier gerade gemacht habe,
wäre eben eine 4-Bit-Kodierung.
Wenn ich jetzt einzelne Zeichen kodieren kann, dann machen wir
natürlich, wie wir das sonst auch schon öfter mal gesehen hatten, eine
natürliche Fortsetzung dieser Abbildung von einem Alphabet auf die
Menge der Wörter über dem Alphabet.
Und dann habe ich also für das leere Wort gerade das leere Wort als
Abbildung.
Und wenn ich ein längeres Wort abbilde, dann muss ich halt die
einzelnen Zeichen sukzessive kodieren und habe dann eben die Folge der
Zeichen als Fortsetzung der Abbildung des Alphabets.
Und natürlich ist auf dem Alphabet selber diese Fortsetzung identisch
mit der Abbildung C.
Das kennen Sie alles aus unseren anderen Überlegungen, als wir andere
Abbildungen erweitert hatten von Alphabeten auf Wortmengen.
Und wenn ich jetzt die Zählkodierung anschaue, dann habe ich eben hier
das, was wir vorher schon gesehen hatten, hier gar kein Problem mit
der Darstellung.
Wenn ich also die Folge 2, 1, 4 mit der Zählkodierung darstelle,
bekomme ich hier ein solches Wort und man sieht sofort, aha, hier sind
also die drei Zeichen, 2, 1 und 4, wo jeweils das gekennzeichnet ist.
Bei der Morse-Kodierung, da ist also etwas schwierig, hier zwei
Wörter, Esel und Seine oder Sen haben das gleiche Bild.
Die Frage ist, wie kann man das irgendwie unterscheiden.
Es ist offensichtlich, wenn ich nur die Morse-Kodierung nehme, dann
habe ich dafür keine eindeutige Umkehrabbildung, das wäre nicht
sinnvoll.
Ich muss also, um das formal machen zu können, muss ich das ein
bisschen anders betrachten.
Zunächst mal die formale Voraussetzung.
Ich verlange zunächst mal, dass die Abbildung injektiv ist.
Was injektiv ist, wissen Sie, dass also keine zwei Elemente das
gleiche Bild haben.
Also wenn die beiden ungleich sind, dann sind die Bilder auch
ungleich.
Und für ein injektives F habe ich natürlich immer eine
Umkehrabbildung.
Das habe ich auch für die Morse-Kodierung, habe ich auch eine
Umkehrabbildung.
Aber bei der Morse-Abbildung kann ich es halt nicht erweitern, da hat
die natürliche Fortsetzung keine Umkehrabbildung.
Die ist nicht mehr injektiv.
Und wenn ich eine injektive Kodierung habe, dann heißt also die
Umkehrabbildung hier auch Dekodierung.
Und wenn jetzt eine solche Abbildung, eine Kodierung, die sogenannte
Phano -Abbildung erfüllt, dann kann man zeigen, dass dann eine
Umkehrung der natürlichen Fortsetzung möglich ist.
Also was ist die Phano-Bedingung?
Die Phano-Bedingung sagt Folgendes aus.
Kein Kodwort ist Anfang eines anderen Kodwortes.
Also wenn ich zwei Kodwörter habe, U und W,
dann ist es klar, dass ich kein anderes Wort haben kann.
Also wenn ich zwei Wörter habe, U und W, lassen Sie mich das richtig
aufmalen.
Ich habe U, ich habe W, das ist hier irgendein Wort, das ist irgendein
Wort.
Und wenn ich jetzt irgendeinen V habe hier drin, hier vorne, da ein UV
und ich sage W ist gleich UV.
Wenn jetzt W gleich UV ist, wenn die beiden gleich sind, dann wäre ja
das unser...
Zwei Kodwörter, U und W, das sind U und W.
Und jetzt füge ich hier hinten noch ein Wort V hinten zu und wenn dann
das UV gleich W ist, dann muss V gleich Lambda sein.
Das heißt, das U kann kein nicht trivialer Präfix von dem Wort W sein,
das ist alles.
Und beim Morse-Alphabet, da war das so, dass die Wörter fast alle
Präfix eines anderen Kodwortes waren.
Weil wir da von der Wurzel immer runter gelesen haben, zu einem
Zeichen, auf den einzelnen Knoten runter bis zu den Blättern.
Und da ist natürlich auf diesem Pfad von der Wurzel bis zu einem
Blatt, ist jedes Zeichen oder jedes Kodwort für ein Zeichen Präfix
eines anderen Kodwortes.
Also bei der Morse-Bedingung ist die Fano-Bedingung nicht erfüllt, bei
der Morse-Kodierung ist die Fano-Bedingung nicht erfüllt.
Morse-Kodierung hier ist eben nicht injektiv, wenn ich aber die
erweitere um eine Lücke und einfach nach jedem Morse-Kodwort noch
diese Lücke hinzufüge, das wäre diese Kodierung, die Kodierung mit
Lücke, dann ist die Abbildung natürlich nach wie vor injektiv und auch
das CML-Stern, die Fortsetzung ist injektiv, erfüllt die Fano
-Bedingung und jetzt wäre also für diese beiden Wörter, Esel und
Seine, wäre hier durch dieses Doppelkreuz gekennzeichnet, wo die
Trennung ist zwischen den einzelnen Zeichen und damit kann ich sie
eindeutig dekodieren.
Das ist die ganze Anforderung, ich muss in der Lage sein, eindeutig
festzustellen, welches Zeichen dort jeweils kodiert ist.
Also Fano-Bedingung sagt aus, es ist kein Kodwort, Präfix eines
anderen Kodworts und damit ist die Erweiterung, die natürliche
Fortsetzung auf Wörter dieser Kodierung ist dann auch wieder injektiv
und hat eine Umkehrabbildung.
Das also zu diesen formalen Bedingungen für eine Kodierung.
Es ist klar, wenn das C-Stern injektiv ist, ist natürlich das C auch
injektiv.
Andersherum, wenn das C, die Kodierung selber injektiv ist und C die
Fano -Bedingung erfüllt, dann ist auch C-Stern injektiv.
Das kann man beweisen.
Das ist aber relativ naheliegend, wie man das machen kann.
Da muss man sich einfach die Bedingungen nochmal anschauen.
Jetzt kommen wir schon zu den ersten interessanten Überlegungen mit
solchen Kodierungen.
Ich möchte gerne Fehler erkennen und korrigieren können.
Warum bin ich daran interessiert?
Ich will Daten ablegen im Rechner.
Ich hatte gesagt, wir schicken irgendwelche Informationen von einem
Ort zum anderen Ort und auf so einem Transportweg kann es passieren,
dass einzelne Zeichen fehlerhaft werden, dass sie beschädigt werden.
Bei Nullen und Einsen kann es sein, dass ein Bit kippt und auf einmal
haben Sie Fehler.
Auch wenn Sie etwas im Speicher ablegen, wieder auslesen, kann es
sein, dass Sie ein falsches Signal bekommen, dass Sie also ein
falsches Bit lesen und dann müssen Sie damit geeignet umgehen können.
Sie müssen zumindest erkennen können, dass ein Datum falsch war.
Das heißt, ich möchte also erreichen, dass ich solche Fehler erkenne.
Und das Beste ist natürlich, wenn ich trotz des Auftretens von
gewissen leichten Fehlern in der Lage bin, das richtige Wort auch aus
dem Fehlerhaften wieder zurückzugewinnen.
Und das schauen wir uns gleich mal an, wie man das machen kann.
Wir gucken dabei nur die N-Bit-Kodierungen an, also eine feste
Blockkodierung mit irgendwelchen N-Bits, 8, 16, 32 oder irgendetwas,
Wortbreiten eines Rechners, typische Blockkodierungen.
Und jetzt muss man sich überlegen, wie kann ich überhaupt über Fehler
reden.
Da rede ich über einen Abstand zwischen zwei Wörtern.
Ich habe also hier ein Wort und ich habe ein anderes Wort, meinetwegen
das übertragene Wort.
Und jetzt schaue ich mir die einzelnen Zeichen an.
Und wann immer ich hier Unterschiede habe, also hier eine 0, da eine
1, dann muss ich das zählen.
Diese Positionen zähle ich alle auf.
Das ist also die Summe aller unterschiedlichen Positionen.
Dieses H von XIYI ist gerade gleich 1, wenn die ungleich sind und nur
umsonst.
Damit habe ich den Abstand zwischen zwei Wörtern.
Die Anzahl der sich unterscheidenden Positionen zwischen zwei Wörtern.
Damit habe ich also eine Abstandsdefinition und kann jetzt sagen, was
die Hemmingzahl eines Codes ist.
Ein Code war eine Menge von Codewörtern.
Ich habe also hier eine Reihe von solchen Codewörtern.
Und jetzt ist die Hemmingzahl gerade der minimale Hemmingabstand
zwischen irgendwelchen zwei Codewörtern.
Ich schaue mir also alle Abstände an zwischen diesen verschiedenen
Codewörtern und das Minimum dieser Abstände ist meine Hemmingzahl.
Warum brauche ich das?
Schauen wir uns erst mal Beispiele an.
Eins aus zehn Codierungen für Dezimalziffern.
Ich sagte, ich kann Dezimalziffern mit 4 Bit darstellen.
Ich kann es natürlich auch mit 10 Bit darstellen.
Da habe ich hier jeweils ein Bit auf 1, die anderen alle auf 0.
Und die Position, an der die 1 steht, gibt mir gerade an die Zahl, die
codiert wird.
Wenn ganz rechts eine 1 steht, ist das die 0.
Und ansonsten, wenn sie ganz links steht, habe ich die 9 dargestellt.
Eine sehr einfache Codierung mit sehr vielen zusätzlichen Bits, die
wir hier haben.
Wie sieht das mit den Hemmingzahlen aus hier?
Das ist unsere Codierung.
Die Hemmingabstände sind hier für je zwei Wörter.
Ich habe immer genau zwei Positionen, wo sie sich unterscheiden.
Die haben nämlich alle an verschiedenen Stellen die 1.
Und das sind genau die beiden Stellen, wo sie sich unterscheiden.
Wir haben also alle einen Abstand von 2.
Das heißt, die Hemmingzahl in dem Fall für diesen Code ist 2.
Weil das der minimale Hemmingabstand ist zwischen zwei Codewörtern.
Und damit ist schon eines klar.
Wenn ich jetzt ein Codewort hätte, das den Abstand 1 hat, oder wenn
ich ein Wort bekommen würde, das den Abstand 1 hat zu einem Codewort,
dann wüsste ich, das ist falsch.
Das kann dann nicht drin sein.
Die haben alle den Abstand 2.
Also wenn da auf einmal eine 1 drinstehen würde, dann hätte ich zu
diesem Codewort, C6 und C9, hätten in dem Fall gerade den Abstand 1.
Das heißt, da ist irgendwas falsch.
Ich würde also sehen, dieses Wort, das ich übertragen habe, wenn da
eine 1 steht, das ist dann kein Codewort mehr.
Da ist ein Fehler drin, aber ich kann es erkennen.
Nun ist die Frage, kann ich solche Abstandsinformationen auch
verwenden, um Fehler zu korrigieren.
Also es ist offensichtlich, ein Fehler ist erkennbar, wenn durch ihn
kein anderes Codewort entstehen kann.
Wenn ich also ein Bit kippe hier drin, eine 1 zu einer 0 mache oder
irgendwo eine 1 da reinschreibe, eine 0 zu einer 1 mache, solange nur
ein Bit verändert wird, entsteht kein anderes Codewort.
Ich müsste ja zwei verändern, damit ein anderes Codewort steht, wegen
des Hemianabstands 2.
Und korrigierbar, wenn ein erkannter Fehler durch genau ein Codewort
entstanden sein kann.
Das ist hier ein Problem, wenn ich irgendein fehlerhaftes Wort habe,
zum Beispiel das hier unten, dann wüsste ich ja nicht, ist jetzt diese
1 hier falsch oder ist die 1 dort falsch.
Dann hätte ich also das Problem, ich kann nicht sagen, ist das
richtige Ziffer eine 9 oder eine 6.
Also Abstand 2 reicht dann noch nicht.
Wir schauen uns das gleich mal an.
In einem anderen Beispiel, hier haben wir einen anderen Code, drei
Codewörter, x, y, z, die hier einfach so grafisch dargestellt sind, im
Raum angeordnet.
Und wenn wir uns das jetzt mal anschauen, das Wort z, das würde mit
einem Fehler, zum Beispiel wenn hier noch eine 1 hinkommt, hätte das
hier einen gewissen Abstand.
Ich könnte jetzt durch eine Reihe von Veränderungen feststellen, oder
könnte ich natürlich durch Bitveränderungen von z nach y kommen.
Ich könnte also hier einmal durch eine Folge von Veränderungen, durch
eine Folge von Fehlern, das z bis in ein y, ein anderes Wort
verändern.
Analog natürlich könnte ich aus dem z ein x machen, durch eine Reihe,
durch entsprechend viele Fehler, oder aus dem x ein y.
Und jetzt sieht man natürlich, der Abstand insgesamt ist 6.
Es sind 6 Positionen, wo die sich unterscheiden.
Gilt für je zwei von diesen x, y und z.
Und wenn ich jetzt mich in diesem Bereich bewege, also wenn der
Abstand zu dem z meinetwegen gerade 2 ist, 1 oder 2, dann gehe ich
davon aus, das ist ein Einfach- oder Zweifachfehler und der kann nur
aus dem Wort z heraus entstanden sein.
Also wenn ich ein solches Wort hier empfange und ich nehme an, ich
habe nur Einfach- oder Zweifachfehler und keine Achtfachfehler zum
Beispiel, dann wäre ich sicher, dass das das richtige Wort war.
Wenn ich einen größeren Abstand habe, dann könnte ich es nicht mehr
zuordnen.
Auch beim Dreifachfehler wüsste ich nicht, kommt der jetzt aus dem z
oder aus dem y.
Und bei den anderen, da weiß man, wenn es noch mehr Fehler wären, dann
würde ich eigentlich dieses Codewort eher dem y zuordnen und nicht
mehr dem z.
Also das würden wir dann annehmen, dass wir nur ein Einfach- oder
Zweifachfehler haben und dann könnte ich die erkennen.
Auf jeden Fall, wenn ich eben weiß, ich betrachte die Erkennbarkeit
von Fehlern, dann kann ich mir Folgendes überlegen.
Ich kann alle Fehler erkennen, also k Fehler erkennen, ein Einfach-,
Zweifach - oder Dreifachfehler, wenn ich bis zu k Stellen eines
Codeworts verändern kann und kein anderes Codewort entsteht.
Das wären bei dem Beispiel hier also ein Fünffachfehler.
Das heißt, dieser Code aus drei Codewörtern wäre fünf Fehler
erkennbar.
Das kann ich erkennen.
Korrigieren kann ich alles, was ich eindeutig zuordnen kann zu dem
Ausgangswort.
Also, wenn ich einen Code habe oder eine Codierung, dann sage ich, die
ist k Fehler korrigierbar, wenn ich durch Verfälschung von bis zu k
Stellen eines Codeworts immer noch eindeutig das Original-Codewort
ermitteln kann.
Das heißt, dann muss dieses k kleinergleich des halben Hemming
-Abstands sein.
Also, durch Verfälschung von bis zu k Stellen eines Codeworts kann das
richtige Codewort eindeutig ermittelt werden.
Also, das ist eine Codierung, die einen Hemming-Abstand hat, der Größe
2k plus 1.
Ist k Fehler korrigierbar und der Code ist also immer Hemming-Zahlen
minus 1 erkennbar.
Das sind also einfache Überlegungen.
Ich brauche den halben Abstand, damit ich korrigieren kann und zu
erkennen, ist irgendeine Stufe dazwischen eben ausreichend.
Das kann ich auch nochmal so visualisieren, durch Kreise, wenn ich die
anordne im Raum in einer sinnvollen Art und Weise.
Ein Code ist k Fehler erkennbar, wenn alle k Kreise um die Codewörter
kein anderes Codewort enthalten.
Also kein Codewort liegt im k-Kreis eines anderen Codeworts.
Die Codierung ist hc minus 1 Fehler erkennbar.
hc ist die Hemming-Zahl.
Und andersrum, k Fehler korrigierbar, dann müssen alle k-Kreise des
Jungts sein.
Jede Codierung ist hc halbe minus 1 Fehler korrigierbar.
Also alles, was kleiner ist als der halbe Abstand, ist korrigierbar.
Und schauen wir uns diese 1 aus 10 Codierung nochmal an.
Da war die Hemming-Zahl 2.
Das heißt, wir haben ein Fehler Erkennbarkeit, wir können nichts
korrigieren.
Wenn wir eine andere Codierung betrachten, bei der wir hier die a, b,
c, d durch diese Bitfolgen darstellen.
Hier ist die Hemming-Zahl gleich 3.
Können Sie sich leicht überlegen, dass hier jeweils zwei Codewörter
den Abstand mindestens 3 haben.
Einige haben sogar einen höheren Abstand.
Also hier a und d haben zum Beispiel einen Abstand 4.
Aber der kleinste Abstand ist 3.
Hier a und b haben gerade den Abstand 3.
Also ist in diesem Fall eine 2-Fehler-Erkennbarkeit gegeben und eine 1
-Fehler -Korrigierbarkeit.
Und das ist also eine wichtige Eigenschaft.
Die Zahlen, die bei Ihnen im Rechner gespeichert werden, sind alle mit
solchen Fehlercodes versehen, sodass Sie solche 1-Fach-Fehler, in der
Regel sogar 1-Fach-Fehler-Erkennbarkeit garantiert haben.
Wenn Fehler erkannt wurden, dass Sie also diese 1-Fach-Fehler auch
korrigieren können.
Wenn Sie 2-Fach-Fehler haben, kriegen Sie eine Fehlermeldung und Sie
haben Speicherfehler.
Wenn wir diesen Code nochmal betrachten, mit diesen drei Codewörtern
mit Abstand 6, da habe ich eben 5-Fehler-Erkennbarkeit und 2-Fehler
-Korrigierbarkeit.
Weil ich beim Abstand 3 nicht weiß, ist das aus dem einen oder dem
anderen Codewort entstanden.
Das zu dieser Fehlererkennbarkeit und das Ganze versucht man natürlich
irgendwie systematisch zu machen.
Man hat also irgendeinen Code, jetzt möchte man Fehlererkennbarkeit
machen.
Dann hängt man zum Beispiel einfach ein Parity-Bit an, Paritäts-Bit,
sodass die Anzahl der Einsen in jedem Codewort einheitlich gerade oder
ungerade ist.
Das kann man natürlich problemlos machen, Sie haben hier irgendeine
Anzahl von Codewörtern und egal, welchen Abstand Sie jeweils haben,
wenn Sie jetzt hier am Ende noch ein Prüf-Bit anhängen, das gleich 0
oder 1 ist, je nachdem, wie die Anzahl der Einsen in den einzelnen
Codewörtern ist, dann können Sie natürlich sofort erkennen, wenn ein
Bit verändert wurde, weil Sie dann nicht mehr die entsprechende
Parität haben.
Weil Sie dann aus einer geraden Anzahl von Einsen eine ungerade
gemacht haben oder umgekehrt.
Also solche Codierungen mit einem Paritäts-Bit, die haben eine
Hemmingzahl größer gleich 2, das heißt, Sie haben zumindest eine
Einfachfehlererkennbarkeit.
Und Sie können das Ganze auch erweitern, Sie können hier noch mehr
anhängen und man kann das noch anders machen.
Ich kann auch zum Beispiel einen größeren Block von Wörtern,
meinetwegen einen ganzen Block von 6 oder 8 oder 7 solchen Wörtern, da
kann ich einfach einen Kontrollblock hinten dranhängen und jedes Bit
hier drin bezieht sich in irgendeiner Form auf Paritätspositionen in
den anderen Wörtern, die hier drinstehen.
Dann können Sie einen ganzen Block von Zahlen absichern durch eine
Folge von Kontrollziffern.
Das macht man auch bei anderen Dingen, wenn Sie sich anschauen,
Kontonummern oder Matrikelnummern oder was immer, wenn irgendwelche
Zahlen folgen, Sie identifizieren oder irgendwie wichtig sind,
versucht man, die abzusichern, dass Sie durch einfache Fehler, indem
Sie eine Ziffer falsch schreiben, nicht ein falsches Konto bezeichnen,
sondern das wird erkannt und als ungültig abgewiesen.
Es gibt für Fehlererkennung und Fehlerkorrektur eine umfangreiche
Theorie, Fehlererkennender, Fehlerkorrigierender Codes, es gibt
algebraische Codierungen, es gibt verschiedenste Sachen.
Da kann man eine ganze Vorlesung drüber halten, nur über
Codierungstheorie.
Das würde ich nicht machen.
Wir sind damit schon um diese Fehlerabsicherung durch.
Ich wollte nur andeuten, man muss den Aspekt der fehlerhaften Daten
berücksichtigen und man macht das durch solche Bits zur Codesicherung.
In den Übungen haben Sie Gelegenheit, darauf nochmal genauer
einzugehen.
Das nächste ist, ich möchte möglichst effizient etwas darstellen.
Sie werden häufiger mal irgendeine Datei in einem ZIP-Format
darstellen wollen.
Sie komprimieren eine Datei.
Das heißt, Sie wollen möglichst wenig Redundanz in der Information
haben, die Sie ablegen oder in den Werten haben, die Sie ablegen.
Sie wollen also alles, was in Redundanz in Ihrer ursprünglichen Datei
war, rauswerfen, um möglichst wenig Speicherplatz zu brauchen.
Zum Teil haben Sie da erstaunliche Möglichkeiten, Informationen zu
komprimieren.
Die Idee ist, dass man sich anschaut, wie häufig sind eigentlich
irgendwelche Zeichen in einem Zeichenvorrat vorhanden.
Ich gebe Ihnen mal hier ein Beispiel.
Nein, das habe ich hier nicht.
Das kommt auf der nächsten Folie.
Da bin ich ziemlich sicher.
Ich habe hier gleich ein paar andere Begriffe.
Sie können also zum Beispiel in der deutschen Sprache die Häufigkeit
der einzelnen Zeichen sich anschauen.
Das E kommt zum Beispiel ganz oft vor.
Das Z oder das Y vor allem kommt sehr selten vor.
Und wenn Sie dann effizient abbilden wollen, kodieren wollen, dann
würden Sie ein kurzes Kotwort nehmen für die häufigen Zeichen und ein
längeres für die weniger häufigen Zeichen.
Dadurch hätten Sie insgesamt den Aufwand für die Abspeicherung eines
Textes reduziert.
Dann würden Sie also keine Blockkodierung mehr nehmen oder N-Bit
-Kodierung, sondern Sie würden die nur notwendige Anzahl von Zeichen
oder von Bits verwenden, um entsprechend der Häufigkeitsverteilung der
Zeichen etwas zu kodieren.
Die Voraussetzung dafür ist natürlich, dass Sie wissen, welche
Häufigkeitsverteilung Sie haben.
Sie können da unterschiedlich vorgehen.
Sie können sagen, ich habe einen Text der deutschen Sprache, dafür
kenne ich eine Häufigkeitsverteilung, ich habe eine Standardkodierung
für Zeichen für ein Alphabet, wenn es ein deutscher Text ist.
Ich kann auch ein Dokument nehmen und zähle einfach von vorne bis
hinten die ganzen Zeichen durch, habe dann die Häufigkeitsabhängige
Verteilung und kann dann speziell für dieses Dokument eine Kodierung
machen, die dann zu einem deutlich kleineren Dokument führt.
Das kann also passieren, auf eine einfache Art und Weise.
Sie müssen dann aber natürlich diese Häufigkeitsverteilung irgendwie
ermitteln und dann können Sie kodieren.
Sie brauchen die Wahrscheinlichkeitsfunktion, Sie brauchen natürlich
eine injektive Kodierung, die die Fano-Bedingungen erfüllt, damit Sie
wieder umkehrbar eindeutig dekodieren können.
Und wenn wir uns dann anschauen, ein Alphabet A, das jetzt kodiert
wird im Hinblick auf eine solche Häufigkeitsverteilung, dann sind also
die Längen der einzelnen Kodwörter unterschiedlich.
Für jedes Zeichen haben Sie eine bestimmte Länge.
Und Sie haben eine Häufigkeit dieses Zeichens.
Das heißt, Sie schauen sich im Prinzip eine Tabelle an, wo hier die
einzelnen Zeichen sind, ich sage mal einfach A bis Z, und hier steht
dann jeweils die Häufigkeit des Auftretens und die Kodlänge.
Also hier steht dann meinetwegen P von A mal Länge von C von A und so
weiter.
Und das Ganze summieren Sie auf und das nennt man dann die Kodlänge.
Die Länge, die Summe der Längen der Kodwörter, die Sie benötigen, um
die einzelnen Zeichen darzustellen, jeweils multipliziert oder
gewichtet mit der Häufigkeit Ihres Auftretens.
Das ist die Kodlänge.
Also Häufigkeit heißt eben Wahrscheinlichkeit, Zahl zwischen 0 und 1.
Und eine Kodierung ist optimal, wenn diese Kodlänge den minimalen Wert
hat.
Wenn ich also keine Kodierung finden kann, die zu einer kürzeren
Kodlänge führt.
Und ich werde Ihnen jetzt ein Verfahren vorstellen, um eine optimale
Kodierung zu erreichen.
Hier kommt jetzt die Tabelle für die Häufigkeit des Auftretens von
Buchstaben, zum Beispiel im Englischen und Deutschen.
Da sehen Sie einige ähnliche Häufigkeiten.
Das E taucht im Englischen nicht ganz so oft auf wie im Deutschen.
Das Y taucht im Englischen deutlich häufiger auf als im Deutschen.
Deswegen wissen Sie auch, dass hier, wenn Sie sich das anschauen, Y
und Z genau entgegengesetzt häufig.
Das heißt, deswegen haben wir ja auf einer Tastatur in der Regel, in
der englischen Tastatur, gerade die Position von Y und Z vertauscht.
Also das sind so typische Häufigkeiten.
Einiges ist ähnlich, einiges ist anders.
Sie würden also entsprechend dieser Häufigkeit kodieren wollen.
Und eine optimale Kodierung ist in der Regel nicht eindeutig bestimmt.
Sie muss nur zu einer minimalen Kodlänge führen, aber es kann viele
Möglichkeiten geben, eine solche minimale Kodlänge zu erreichen.
Und ich zeige Ihnen jetzt einen ganz einfachen Algorithmus dafür.
Das ist der Algorithmus von Huffman.
Und dieser Huffman hatte eine ganz einfache Idee.
Der sagte, wenn wir hier eine Folge von Zeichen haben und ich gehe mal
davon aus, wir haben irgendwelche Zeichen, ich schreibe hier einfach
mal hin, A, B, C, D, E, F.
Stellen Sie sich vor, die hätten diese Häufigkeiten in irgendeinem
Text.
Jetzt natürlich müsste ich sagen, die Summe dieser Häufigkeiten,
Quatsch, diese einzelnen Häufigkeiten geteilt durch die Summe aller
Häufigkeiten, dann hätte ich jeweils Zahlen zwischen 0 und 1.
Ich habe mir das Dividieren erspart, nehme nur diese Zahlen.
Ich bilde also Knoten, für jedes Zeichen bilde ich einen Knoten, in
dem jeweils die Wahrscheinlichkeit drinsteht oder die Häufigkeit.
Da habe ich also hier einen Knoten, da einen, da einen, da einen, da
einen und da einen.
So, das sind meine Häufigkeiten.
Und jetzt nehme ich, das steht hier, das ist die Menge aller meiner
Knoten, ich nehme zwei Knoten her, mit den geringsten Bewertungen, mit
den kleinsten Bewertungen.
In dem Fall wären das die Knoten 5 und 7.
Und ich bilde dafür einen neuen Knoten.
Ich vereinige die beiden zu einem neuen Knoten und schreibe dort die
Summe der Häufigkeiten rein.
Das wäre hier 12.
Dann mache ich weiter.
Ich nehme die beiden kleinsten, das wäre hier 12 und 13.
Die baue ich zusammen und habe dann daraus 25.
Jetzt hätte ich die Wahl, habe ich hier 25 übrig, 20, 25 und 30.
Ich könnte also zum Beispiel diese beiden zusammenfügen, hätte 45.
Und jetzt müsste ich diese beiden zusammenfügen und würde daraus jetzt
55 machen.
Und dann würde ich noch 45 und 55 zusammenfügen und hätte hier
insgesamt 100.
Das ist genau das, was hier steht.
Solange die Menge der Knoten größer als 1 ist, also der noch nicht
verwendeten Knoten größer als 1 ist, nehme ich zwei solche Knoten raus
und verbinde die.
Bilde also neue Knoten mit der Summe der jeweiligen
Wahrscheinlichkeiten.
Und jetzt kommt der nächste Schritt.
Die Kanten habe ich schon eingefügt.
Das war das, was wir gerade gemacht haben.
Und jetzt beschrifte ich jede nach links verlaufende Kante mit 0.
0, 0, 0, 0.
Nach links hätten wir hier nochmal eine, das wären alle nach links
verlaufenden Kanten, alle nach rechts verlaufenden Kanten mit 1.
1, 1, 1, 1, 1.
Jetzt habe ich Kanten mit 0 und 1 beschriftet.
Und abschließend ordne ich jedem Blatt als Codewort die Folge der
Kantenbeschriftungen zu.
Also zum Beispiel dem F die Folge der Kantenbeschriftungen.
Die Frage ist, welche nehme ich jetzt?
Nehme ich 1, 0 oder nehme ich 0, 1?
Also ich würde sagen, ich nehme die 0, 1 für F.
Für das E hätten wir 1, 1.
Für das D hätten wir 1, 0.
Für das C hätten wir 0, 0, 1.
Für das B hätten wir in dem Fall 0, 0, 0, 1.
Und für das A hätten wir 0, 0, 0, 0.
Und Sie sehen, wir haben unterschiedlich lange Codewörter.
Und meine Wahl der Reihenfolge von der Wurzel jeweils zu dem Blatt
machte durchaus Sinn.
Hätten wir das andersrum gemacht, hätte ich von dem Blatt zur Wurzel
codiert, dann hätte ich hier zum Beispiel bei dem F, dann hätte ich
dort 1, 0 stehen gehabt.
Und ich hätte bei C 1, 0, 0 stehen gehabt.
Und dann wäre die 1, 0 und hier würde dann 1, 0, 0 stehen.
Dann wäre das F, ein Anfangscodewort oder das Codewort für F ein
Anfang des Codeworts für C.
Dann wäre die Fano-Bedingung nicht erfüllt.
Ich muss also dafür sorgen, dass diese Fano-Bedingung immer schön
erfüllt ist.
Also das geht nicht, das geht auch nicht.
Das D war natürlich nicht 1, sondern das war 1, 0.
Ich muss dafür sorgen, dass die Fano-Bedingung erfüllt ist, dass kein
Codewort Anfangsstück eines anderen Codeworts ist.
Und wenn ich von der Wurzel zu den Blättern laufe, jeder Weg von der
Wurzel zu einem Blatt hat gerade die Eigenschaft, dass die alle
unterschiedlich sind.
Kein solcher Weg von der Wurzel zu einem Blatt ist Anfangsstück eines
anderen Weges von der Wurzel zu einem Blatt.
Bei der Morse-Codierung hatten wir auch einen Baum und aus dem Baum
die Codierung abgelesen.
Da waren wir aber nicht zu den Blättern gegangen, sondern hatten jedem
Knoten auf dem Weg bereits ein Codewort zugeordnet.
Das waren jeweils gerade natürlich Präfixe voneinander.
Das also hier ist der einfache Algorithmus von Huffman.
Ich gebe Ihnen noch ein anderes Beispiel dafür.
Hier haben wir jetzt die Ziffern von 0 bis 9.
Wir nehmen an, wir haben diese Wahrscheinlichkeitsverteilung, die hier
angegeben ist.
Und jetzt müssen wir entsprechend suchen, die beiden, die die
niedrigste Bewertung haben.
Die niedrigste Bewertung haben hier die Ziffern 8 und 9.
Ich könnte 9 mit 8, 9 mit 7 oder 9 mit 6 kombinieren.
Ich kombiniere einfach jetzt hier 8 und 9.
Da kommt dann 0,09 raus.
Dann müsste ich als nächstes, bleibt mir keine andere Wahl, als jetzt
6 und 7 zu kombinieren.
Da kommt dann 0,1 raus.
Dann sind die nächstkleineren, gerade hier die 4 und 5, die muss ich
auch zusammenbauen.
0,07, 0,06, 0,13.
Jetzt bleibt hier übrig die 0,08 und die 0,09 hier rechts.
Da werden die beiden zusammengefügt zu 17.
Und entsprechend muss ich jetzt die nächsten kleineren suchen.
Dann hätte ich hier die 0,01 und 0,13, die ich zusammenfügen muss, zu
0,23.
Anschließend hätte ich die 0,15 und die 0,20.
Stimmt nicht, 0,17 und 0,15, gibt 0,32.
Dann hätte ich als nächstes die 0,23 und die 0,20, die beiden, gibt 0
,43.
Und jetzt habe ich noch 0,25 und 0,32, die ich kombinieren muss.
Und anschließend 0,43 und 0,57, gibt 100 bzw.
1,0.
Also das ist die einfache Art, wie wir ganz systematisch aus solchen
Wahrscheinlichkeiten einen Code konstruieren.
Der Code dadurch, dass wir jetzt Nullen reinschreiben und Einsen.
Und dann einfach zum Beispiel, wenn wir das Codewort für die Zahl 6
haben wollen, gehen wir von der Wurzel aus nach oben und lesen einfach
die Ziffern ab an den Kanten, also in dem Fall 0,1,1,0.
Sehr einfache Art der Codierung.
Das ist etwas, was man auch sehr schön in den Übungen machen kann.
Auch in Situationen, wo man sein Wissen relativ kurzfristig darstellen
muss, kann man sowas auch sehr schön immer als Aufgabe stellen.
Also Huffman-Codierungen sind eine sehr beliebte Art, wie man Wissen
aus der Vorlesung abfragt.
Das nochmal zurück zu diesem Abbild und das war das, was wir gerade
gemacht hatten hier rechts.
Ich kann jetzt dann diese Codierung hier damit definieren.
Die Menge der Codewörter sehen Sie.
Codewörter der Länge 2 bis Länge 5.
Entsprechende Wahrscheinlichkeiten.
Und wenn Sie sich jetzt anschauen, die Codelänge.
Die Codelänge in dem Fall, das war ja die Summe der gewichteten Längen
der Codewörter.
Die ist in dem Fall 3,04.
Wenn Sie eine 4-Bit-Codierung hätten, wäre die Codelänge 4.
Weil alle die Länge 4 hätten, dann wäre die Codelänge 4.
Hier haben wir eine Codelänge von 3,04.
Das ist also besser als eine 4-Bit-Codierung.
Obwohl Sie hier einige Zeichen mit 5-Bit kodieren.
Aber Sie haben eben die häufigen mit 2-Bit kodiert, deswegen haben Sie
einen Gewinn.
Und diese Codelänge 3,04 ist optimal für diese
Wahrscheinlichkeitsverteilung.
Ich habe also bei der Codierung nach Huffman immer Codewortfolgen
optimaler Länge.
Und das muss man natürlich beweisen, kann man beweisen, geht über
diese Vorlesung hinaus.
Es ist eines der Standardverfahren zur Datenkompression.
Man macht allerdings noch ein bisschen mehr.
Es gibt Verfahren wie Lempel-Ziff, da wird noch mehr gemacht.
Da schaut man sich nicht nur einzelne Zeichen an, sondern man schaut
sich Zeichenfolgen an.
Wenn ich einfach Zeichenfolgen betrachte, deren Wahrscheinlichkeiten
sind wieder anders als Wahrscheinlichkeiten des Auftretens von
einzelnen Zeichen.
Und auf die Art und Weise könnte ich also jetzt Zeichenfolgen
entsprechend Codewörter zuordnen und kann dadurch eine noch stärkere
Komprimierung erreichen.
Und bei diesen ZIP-Verfahren, da wird immer die beste Art der
Codierung genommen, damit man bei einer solchen häufigkeitsabhängigen
Codierung dann die minimale Anzahl an Bits hat.
Natürlich muss man sich über eines im Klaren sein.
Wenn man so etwas macht, dann gehen so diese Dinge, die wir vorher
hatten, wie Fehlererkennbarkeit, Fehlerkorrektur verloren.
Haben Sie eine Frage?
Selbstverständlich.
Das muss mit angegeben sein, nach welchem Verfahren das komprimiert
wurde, damit Sie das wieder zurück abbilden können.
Sie müssen ja die Abbildung haben, damit Sie die Umkehr-Abbildung dann
anwenden können.
Das ist klar.
Aber das sind Standardarten, wie man Daten komprimiert.
Und Huffman-Verfahren ist das Einfachste, das eben auf jeden Fall für
diese Arten, wenn ich nur einzelne Buchstaben codiere, dann einen
optimalen Code liefert für die gegebene Häufigkeitsverteilung.
Und damit kommen wir schon zum nächsten Thema, nämlich der Darstellung
von Zeichen und Ziffern.
Das war jetzt einfach Allgemeinkodierung mit Fehlererkennbarkeit,
Fehlerkorrigierbarkeit und jetzt diese Redundanzbeseitigung, optimale
Codes.
Und jetzt wollen wir tatsächlich Zeichen und Ziffern im Rechner
darstellen.
Und das soll natürlich möglichst billig sein, das muss schnell sein
und auch zuverlässig.
Die Operationen müssen zuverlässig sein und wir müssen sehen, wie wir
das am besten hinbekommen.
Wir haben feste Zeichensätze, in der Regel sind das unsere Zeichen des
lateinischen Alphabets.
Aber es kann ja sein, dass Sie nicht im lateinischen Alphabet
schreiben, sondern im kyrillischen Alphabet oder im chinesischen
Alphabet oder in noch irgendwelchen.
All das muss man heutzutage berücksichtigen, werden Sie noch sehen,
wie man das macht.
Schriftzeichen, lateinische Schrift sind aber nicht nur die 26
Buchstaben, wir haben auch noch Ziffern, wir haben Sonderzeichen, die
wir darstellen müssen und dann kommen Sie auf einen etwas größeren
Umfang von Zeichen, die Sie darstellen müssen.
Auf jeden Fall müssen Sie in der Repräsentation genügend Bits zur
Verfügung haben, um den Zeichenvorrat richtig abzubilden.
Und man macht das in dem Fall durch eine Block-Codierung.
Und ein gebräuchlicher Code ist zum Beispiel der ASCII-Code, American
Standard Code for Information Interchange.
Was sehen Sie hier alles in der Tabelle?
Da sehen Sie alle Zeichen, die dargestellt sind und zwar durch sieben
Bits.
Mit sieben Bits können Sie 128 Zeichen darstellen und man verwendet
manchmal auch 8-Bit.
Es gibt also 7-Bit-ASCII-Code und 8-Bit-ASCII-Code.
Beim 8-Bit-ASCII-Code haben Sie entsprechend 256 Zeichen.
Beim 7-Bit-ASCII-Code haben Sie ein Bit von einem Byte noch zur
Verfügung, um zum Beispiel das Paritätsbit zu verwenden, um Fehler zu
erkennen.
Also wenn Sie eine fehlererkennende Darstellung haben wollen, nehmen
Sie ein 7-Bit-ASCII-Code und haben dann dieses Paritätsbit noch zur
Verfügung.
Wenn Sie 8-Bit verwenden, dann ist in einem Byte kein Platz mehr für
diese Fehlererkennung.
So, schaut man sich das an, was haben wir für Zeichen?
Zunächst mal ist hier ein Block von sogenannten Steuerzeichen.
Was sind das für Steuerzeichen?
Das ist zum Beispiel hier ein Line Feed oder ein Feed Forward oder ein
Syn für Sync oder Negative Acknowledge.
Was haben wir noch alles drin?
Das ist ein Acknowledge.
Dann haben wir, naja, alles mögliche.
Alle möglichen Steuerzeichen, Controls and Carriage Return, Line Feed,
CR.
Also viele verschiedene Zeichen, die man aus der Datenübertragung halt
irgendwie kennt, die muss man alle darstellen können, damit man bei
der Übertragung zum Beispiel von einer Schreibmaschine auf die andere,
von einem TLS-Gerät auf das andere, auch in der Lage ist, nicht nur
die Folge der Zeichen darzustellen, sondern wenn ich hier irgendwas
geschrieben habe, ich habe da diese Codes dargestellt, muss natürlich
klar sein, dass ich mit der Klammer auf in der nächsten Zeile anfange.
Also Carriage Return, Zeilenvorschub muss mit da drin sein.
Und halt viele andere Sachen auch.
Dann muss ich natürlich auch den Zwischenraum darstellen können und so
weiter.
Dann habe ich Satzzeichen, ich habe Klammern und ähnliches, ich habe
Plus, Minus, Mal und so weiter.
Dann habe ich die Ziffern, 0 bis 9, ich habe Vergleichsoperationen,
ich habe Großbuchstaben, ich habe Kleinbuchstaben und Sie sehen, die
Distanz im Codewort zwischen Großbuchstaben und Kleinbuchstaben ist
immer gleich.
Wenn Sie also auf einem ASCII-Code, wenn Sie dort auf alle Zeichen 32
drauf addieren, von dem Zeichen 49 oder mit dem numerischen Wert 49,
wenn Sie daraus 81 machen, dann haben Sie aus einem Großbuchstaben ein
Kleinbuchstaben gemacht.
Das heißt, die Operation 32 drauf addieren auf den numerischen Wert
eines dargestellten Zeichens, liefert eine Veränderung von Groß- und
Kleinbuchstaben.
Wenn Sie 32 abziehen, haben Sie Klein- und Großbuchstaben verändert.
Das ist also eine Art, wie Sie Zeichen darstellen können.
Hier ganz am Ende nochmal ein Steuerzeichen, ein Delete-Zeichen.
Also das ist die Tabelle, wie Sie diese sieben Bit codieren.
Sie haben hier aus den sieben Bit, die werden aufgeteilt in zwei
Teile, X und Y.
X liefert gerade die Spaltenadresse, Y die Zeilenadresse.
Also die ersten drei Bits sind hier die Spalten und die nächsten vier
Bit geben gerade die Zeile an.
Damit haben Sie die jeweiligen sieben Bit für die Darstellung solcher
Zeichen.
Das ist der ASCII-Code.
Die nächste Folie gibt den EPSIDIC-Code.
Extended Binary Coded Decimal Interchange Code.
Ich sage, es ist wichtig, dass man weiß, wie eine Zeichenfolge
übertragen wird und im jeweiligen Rechner dargestellt wird.
Das interessante ist, IBM hat in ihren Rechnern alles im EPSIDIC-Code
dargestellt.
Auf zum Beispiel Rechnern von DEC, Digital Electric, die haben alles
im ASCII-Code dargestellt.
So, nun müssen Sie auf folgende Sachen aufpassen.
Wir haben wieder hier vorne, hier sind es acht Bits.
Hier ist es so, dass Sie jeweils auch wieder die ersten geben die
Spalte an, die zweiten die Zeile.
Insofern zweimal vier Bit.
Sie haben wieder links die ganzen Steuerzeichen.
Dann haben Sie einige leere Felder, da ist gar nichts kodiert.
Hier haben Sie auch leere Felder, da könnte man noch was
reinschreiben, ist bei dieser Darstellung nicht geschehen.
Und jetzt haben Sie hier natürlich auch Unterschiede zwischen Groß-
und Kleinbuchstaben.
Aber der Abstand ist anders.
Und bei dem vorherigen Code, bei diesem hier, da ist es so, wenn Sie
von einem Buchstaben zum nächsten wollen, aber wenn Sie von A bis Z
meinetwegen durchzählen wollen, das geht in einigen
Programmiersprachen, dass Sie Charakter-Datentyp nehmen, um eine
Schleife zu programmieren, um eine Vorschleife zu programmieren, dass
Sie über die Kodierung von solchen Zeichen iterieren, da können Sie
hier einfach von A bis Z 26 Zeichen durchzählen.
Wenn Sie das hier machen im EPSI-Decode von A bis Z, da würden Sie
diese ganzen Zeichen auch noch mitzählen, das dürfen Sie natürlich
nicht.
Also wenn Sie das Codewort nehmen für das Zeichen I und eins
draufzählen, dann ist das nicht das Zeichen J, sondern ist das ein
Zeichen, das hier gar nicht vorkommt, also gar nicht abgebildet ist.
Das heißt, man muss genau wissen, wie Zeichen intern dargestellt
werden, wenn man nämlich die interne Darstellung der Zeichen in einem
Programm zum Beispiel verwendet, dann muss man wissen, sind diese
Zeichen in meinem Rechner im ASCII-Code oder im EPSI-Decode
dargestellt.
Wenn sie im EPSI-Decode dargestellt sind, muss ich ganz anders mit
diesen Zeichen operieren, als wenn die im ASCII-Code dargestellt sind.
Sehr schlecht.
Ist aber leider so.
Und das hat natürlich zu ziemlich vielen Problemen geführt.
Aber man kommt natürlich damit zurecht, man kann sich darauf
einstellen.
Und es gibt jetzt noch eine andere Art, die Zeichen darzustellen.
Ich hatte schon gesagt, wir haben ja nicht nur lateinische Zeichen.
In der westlichen Welt natürlich haben wir nur lateinische Zeichen.
Aber es gibt ja auch noch andere.
Und es gibt also hier vorne in diesem kleinen Anfangsstück hier, hier
haben wir also Zeichen, bei denen wir eine Codierung mit 16 Bit pro
Zeichen.
Da haben wir einen kleinen Bereich für ASCII und EPSI-Decode.
Und dann kommen sehr viele andere wie Hangul, dann gibt es hier
irgendwelche privat verwendeten Sachen.
Es gibt chinesische Zeichen, japanische, koreanische und was immer Sie
sich noch vorstellen können.
Also viele verschiedene Zeichen, die man darstellen möchte.
Mit 16 Bit kann man halt 65.000 Zeichen darstellen.
Man hat das Ganze sogar noch erweitert um weitere 16 Bit-Bereiche und
kann damit etwa eine Million Zeichen auf eine definierte Art und Weise
repräsentieren.
Und ich kann damit international zwischen verschiedenen Rechnern
problemlos kommunizieren.
Wenn ich Unicode verwende, ist es klar, welches Zeichen gemeint ist.
Das ist wichtig, dass man solche Codierungen hat, weil man damit eben
Informationen international sinnvoll anbieten kann.
Ich kann eben einfach vorsehen, dass irgendwelche Informationen
standardmäßig mit chinesischen oder mit lateinischen oder kyrillischen
Zeichen dargestellt werden.
Und ich bewege mich in einem Codierungsschema, diesem Unicode.
Wenn Sie da mehr darüber wissen wollen, schauen Sie nach bei Unicode
.org oder schauen Sie bei Wikipedia nach.
Bei Unicode.org finden Sie alle relevanten Informationen über diese
sehr vereinheitlichte Codierung aller Zeichensätze, die wir uns in der
Welt vorstellen.
Damit ist also auch diese Codierung von einfachen Zeichen zunächst mal
behandelt.
Das nächste ist, wir wollen in einem Rechner natürlich auch rechnen,
wir müssen Ziffern darstellen können.
Das können wir machen natürlich mit ASCII und EPSILIC, ist aber ein
bisschen viel, wenn wir 7-Bit oder 8-Bit verwenden, um eine Ziffer
darzustellen.
Ziffern haben wir ja nur 10 zur Verfügung.
Da reichen 4-Bit aus.
Man kann das machen über spezielle Codierungen, wie eben den Binary
Coded Decimal Code, wo Sie einfach, das hatte ich vorhin schon
angedeutet, von 0 bis 9 alle 4-Bit-Codierungen verwenden, numerisch so
abgebildet.
Ich kann auch den XS3-Code verwenden, da verschiebe ich alles um 3,
also die 0 wird durch 3 dargestellt, die 9 entsprechend durch 12.
Dann gibt es einen sogenannten Icon-Code, da sehen Sie, dass 0 bis 4
sind numerisch richtig dargestellt und 9 bis 5 sind genau andersrum
dargestellt, nämlich rückwärtsgezählt von dem maximalen numerischen
Codewort, der 15, 14, 13, 12 und so weiter runter.
Und so haben Sie dann die Ziffern 9 bis 5.
Eine andere Art der Darstellung.
Oder ein 2-aus-5-Code, mit 5-Bit können Sie die Zahlen auch
darstellen, da würden Sie jeweils mit zwei Einzeln pro Codewort die
Ziffern von 0 bis 9 darstellen, hätten dann eine andere Art, die aber
schöne fehlerkorrigierende Eigenschaften hat.
Also, verschiedene Möglichkeiten und diese Codierungen haben viele
verschiedene Eigenschaften, über die ich aber hier eigentlich, ich
kann ganz kurz erwähnen, BCD-Codierung ist sehr nah an dem numerischen
Wert, deswegen kann ich damit sehr schön rechnen.
Stellenwertigkeit ist genau wie bei der Binär-Codierung einfach zu
codieren.
Dann bei der XS3-Codierung, da ist das Ganze symmetrisch, ich habe
also eine Darstellung, wenn ich mir den Zahlenstrahl hier anschaue,
dann habe ich also, wenn das hier 0 bis 9 ist, 0 bis 9, dann habe ich
jetzt die dargestellt, ich muss ja noch mit den 4-Bit-Zahlen bis 15,
dann verschiebe ich das Ganze von 3 bis 12 und dann sind diese gerade
symmetrisch zu dem jeweiligen Rand dargestellt.
Also das hat auch eine gewisse sinnvolle Eigenschaft.
Außerdem tauchen nur Nullen und nur Einsen nicht auf als Ziffern, auch
das ist wichtig.
Es gibt sogenannte Burst-Fehler, bei denen Sie nur Nullen auf einmal
schreiben oder nur Einsen bei der Datenübertragung, dann haben Sie
sofort eine Möglichkeit zu erkennen, aha, wenn da 4 Nullen stehen, das
ist keine gültige Ziffer, sondern das ist einfach ein technischer
Fehler.
Und wenn Sie sich diese 2-aus-5-Codierung anschauen, da ist es so,
dass wir hier 10 verschiedene Codewörter damit darstellen können.
Wir haben einen Fehler Erkennbarkeit, damit zu rechnen ist aber
schwierig, weil wir hier nicht so einfach addieren, subtrahieren,
multiplizieren können, wie wir das mit den anderen Darstellungen
können.
Und damit bin ich schon über diese Ziffern-Darstellung durch.
Das Wesentliche, was ich Ihnen in diesem Abschnitt vermitteln muss,
ist, wie man eigentlich mit reellen Zahlen umgeht.
Und das, wir werden vielleicht nicht ganz so weit kommen heute, aber
fast so weit.
Ich möchte Zahlen darstellen können, möchte nicht nur Ziffern
darstellen, sondern möchte Zahlen darstellen.
Und wenn ich Zahlen darstelle, Sie wissen das, kann ich das
Dezimalsystem nehmen, kann das Dualsystem nehmen oder ein anderes 2
hoch K System, einfache Konvertierbarkeit, ich möchte einfach rechnen
können.
Ich kann die binärdezimale Codierung nehmen, das ist das EBCDIC, wo
die binärdezimale Codierung von 0 bis 9 drin vorkommt.
Die werden wir aber nicht nehmen, das wären aber potenzielle
Möglichkeiten.
Also hier wäre die BCD-Codierung, damit könnte ich natürlich die Zahl
13 durch zwei 4-Bit-Kombinationen darstellen.
Ich kann damit gut rechnen, aber wir werden im Weiteren nur das
Dualsystem betrachten und müssen uns jetzt anschauen, wie wir
überhaupt Zahlen darstellen wollen, was wir eigentlich darstellen
müssen.
Ist das, wenn ich mir den Zahlenstrahl anschaue, hier ist die 0,
welche Zahlen stelle ich da?
Ich habe nur eine feste Zahl von Bits zur Verfügung, ich habe
meinetwegen 32-Bit-Zahlen.
Dann kann ich irgendwelche Zahlenbereiche darstellen.
Das Gewünschte wäre natürlich, dass wir irgend so einen Zahlenbereich
links und rechts von der 0 darstellen können, fester Größe, das sollte
ein zusammenhängender Bereich sein, möglichst keine Lücken.
Sie werden sehen, bei natürlichen Zahlen, bei ganzen Zahlen können wir
das machen, ohne Lücken.
Bei reellen Zahlen geht es nicht, da sind zwischen je zwei Zahlen
Lücken von Zahlen, die wir nicht darstellen können.
Also negative Zahlen müssen wir vernünftig darstellen können.
Rationale, reelle Zahlen, wie sieht das mit der Genauigkeit aus, mit
Rundungsfehlern und Ähnlichem.
Und wie kann ich operieren darauf, wie kann ich rechnen, wenn ich zwei
Operanden habe, X und Y, und die beiden kodiere, intern darstelle,
möchte ich Operationen intern zur Verfügung haben, mit denen ich auf
diesen Zahlen oder den kodierten Zahlen rechnen kann, meinetwegen
addieren, subtrahieren, multiplizieren und dividieren kann.
Und das Ergebnis, was rauskommt, also die Verknüpfung der beiden
kodierten Werte, soll das gleiche sein, als wenn ich die Originalwerte
verknüpft hätte mit der Operation und anschließend kodiert hätte.
Also dieser Weg hier muss gleich sein wie der Weg, ein sogenanntes
kommutatives Diagramm, damit das Ganze auch korrekt ist.
Solche Überlegungen müssen wir machen, wie kann ich die arithmetischen
Operationen sinnvoll machen, sodass ich tatsächlich korrekte
Ergebnisse rausbekomme.
Und damit werden wir uns jetzt beschäftigen, wie kann man das also
hinbekommen, wie kann man sinnvoll kodieren.
Wir fangen an mit den natürlichen Zahlen, das kennen Sie alle aus der
Schule, die Dualdarstellung.
Wir haben eine Dualdarstellung einer Zahl mit N-Bit, sagen wir es C2,N
von X, ist gerade die Dualdarstellung.
Das ist alles bekannt.
Arithmetische Operationen sind sehr einfach, wenn Sie hier zwei Zahlen
haben, 17 und 7.
Sie wollen die subtrahieren, dann schreiben Sie hier halt die 17 hin,
hier unten steht die 7 und dann müssen Sie halt entsprechend
subtrahieren und Sie sehen, es kommt dann hier gerade die Zahl 10
raus.
Sie wissen, wie man das stellengerecht als alles macht und damit
können wir also problemlos subtrahieren.
Sie können Zahlen multiplizieren, 5 mal 3 gibt 15.
Wie multiplizieren wir, das hatten wir schon gesehen bei dem seriellen
Multiplizierer, den ich Ihnen dargestellt habe.
Wir nehmen die Bits der einen Zahl hier, die Bits von dem Operanten,
genau andersrum.
Ich habe hier die Bits genommen, die beiden Einsen, das ist die 5, das
ist die 3.
Ich habe also hier die 1 genommen, habe die 5 hingeschrieben, nochmal
eine 1, um eine Stelle versetzt die 5 hingeschrieben.
Die nächsten Bits sind alles Nullen, da schreibe ich die Nullen im
Prinzip versetzt nochmal hin.
Ich muss alles aufaddieren und bekomme dann eine Zahl, die hat gerade
doppelt so viele oder 2, in dem Fall also gerade nicht 5 Bits, sondern
1, 2, 3, 4, 5, 6, 7, 8, 9 Bits, 2n-1, wenn Sie n Bits haben.
Und wir nehmen normalerweise dann die letzten Bits als Wert wieder
raus, beziehungsweise nicht 4, wir wollten ja 5 Bits zahlen, also das
hier, die letzten 5 Bits wären die richtigen Bits für das Produkt.
Wenn Sie natürlich 17 mal 7 rechnen würden, oder irgendwelche anderen
Zahlen modifizieren würden, wenn Sie n gleich 5 haben, dann kann es
passieren, dass Sie auf einmal in diesem Bereich auch 1 entstehen,
dann würden Sie über die Möglichkeit mit 5 Bit etwas darzustellen
hinausgehen, Sie hätten Ihren Zahlenbereich verlassen.
Da muss man natürlich aufpassen.
Also arithmetische Operationen mit 5 Bit-Zahlen sind nicht
abgeschlossen, der darstellbare Zahlenbereich kann überschritten
werden, Sie kennen das aus Java-Programmierung, Sie können auf Byte
rechnen, Sie können auf einfachen Integer-Zahlen rechnen, Sie können
auf größeren Zahlenbereichen rechnen, aber Sie haben immer eine feste
Anzahl von Bits und damit eine feste Anzahl von Zahlen, die Sie
darstellen können.
Sie dürfen diesen Zahlenbereich nicht überschreiten, wenn das
passiert, bekommen Sie eine Fehlermeldung.
Natürliche Zahlen waren einfach darzustellen, das Problem kommt mit
den ganzen Zahlen, bei denen wir ja in der Lage sein wollen, auch
negative Zahlen darzustellen.
Die Frage ist, wie macht man das denn?
Wie kann man eine negative Zahl darstellen?
Wir kennen das natürlich aus der Arithmetik, ich kann eine Zahl 5 und
ich kann eine Zahl plus 5 und minus 5 hinschreiben.
Ich nehme einfach ein Zeichen davor, das mir darstellt, ob das ein
positives oder negatives Vorzeichen ist.
Könnte ich natürlich einfach mit 0 und 1 machen.
1 für negativ, 0 für positiv.
Das wäre also die naheliegende Art, wie man das machen könnte.
Allgemein ist es so, dass ich einen Zahlenbereich habe, in dem
negative Zahlen vorkommen und positive.
Das wären meine negativen, das die positiven.
Und ich möchte eine Codierung haben, bei der genau diese Zahlen
sinnvoll dargestellt werden, mit meinen N-Bits, die ich zur Verfügung
habe, möglichst symmetrisch zum Nullpunkt, möglichst genauso viele
negative wie positive Zahlen.
Und ich möchte einfach darauf rechnen können.
Und das schauen wir uns einfach mal an.
Da gibt es verschiedene Möglichkeiten.
Vorzeichen, Betracht hatte ich gerade erwähnt.
Die einfachste Art, das zu tun.
Das Interessante ist aber, wenn Sie jetzt zum Beispiel die 5 sich
hernehmen.
Ich habe hier irgendwie 4 Bits zur Verfügung.
Die Zahl 5 wäre 1, 0, 0, 1.
Quatsch, Entschuldigung.
1, 0, 1.
Und minus 5 würde ich dann so darstellen.
Das wäre jetzt minus 5.
Wenn ich aber im Rechner intern zum Beispiel vergleichen wollte, das
ist meinetwegen eine Zahl a, das ist eine Zahl b.
Jetzt vergleiche ich im Rechner, ob a kleiner als b ist.
Ja, dann würde, wenn Sie nur diese numerischen Werte sich anschauen,
dann würden ja hier stehen die beiden Darstellungen, da wäre es so,
dass das a kleiner als b ist.
Tatsächlich ist das b, gibt aber hier vorne an, dass das ein
Minuszeichen ist.
Das heißt, das b ist ja eigentlich eine negative Zahl und ist
natürlich kleiner als das a.
Also bei Größenvergleichen muss man aufpassen, dass man dieses Zeichen
nicht falsch hier interpretiert.
Ich möchte also eigentlich etwas so darstellen, dass auch in der
codierten Darstellung nachher die numerischen Eigenschaften der
Codewörter die gleichen sind wie die, die ich vorher habe im Original.
Das heißt, bei der Darstellung auf meinem, also wenn ich jetzt das mit
N -Bit-Zahlen mache, dann habe ich hier die 0 und hier irgendwie den
dargestellten Bereich und dann sollen eigentlich wieder hier die
negativen und die positiven so dargestellt werden.
Wie kann ich das denn hinkriegen?
Eine Möglichkeit wäre, die Exzess-Q-Darstellung zu nehmen.
Ich schiebe einfach alles genau um den Betrag nach rechts.
Ich schreibe einfach hier, die kleinste Zahl war das xu.
Ich addiere einfach xu auf alle meine Zahlen und dann würde die
Bitfolge 0000, also die werden nur Nullen, wären praktisch das xu.
Ich muss also von jeder dargestellten Zahl genau dieses xu
subtrahieren und dann hätte ich also eine solche Transformation, dann
hätte ich also genau das auf die Art und Weise dargestellt.
Einfach nach rechts verschoben.
Da hätte ich genau die Eigenschaft, dass die negativen immer noch
links sind von den positiven Zahlen.
Auch in der Darstellung im Rechner.
Dann gibt es eine sogenannte Komplementdarstellung.
Ich habe die Null und irgendeine große Zahl K und jetzt stelle ich die
Zahl X dar und das Minus-X stelle ich so dar, dass ich einfach von dem
K das X subtrahiere.
Dann ist das X und dieses hier wäre also Minus-X.
Noch eine andere Art der Darstellung.
Erwähnen die ja genau irgendwie, also wieder anders als das, was ich
vorher sagte mit Vorzeichen, Betrag und Komplement.
Völlig andere Art, etwas positiv und negativ darzustellen.
Und im Rechner finden Sie tatsächlich entweder diese Xsq-Darstellung
oder die Komplementdarstellung, kommt sehr häufig vor bei ganzen
Zahlen, manchmal oder in einigen, also bei den reellen Zahlen finden
Sie sowohl die Vorzeichen-Betrag-Darstellung als auch die Xsq
-Darstellung.
Und da kommen wir später noch drauf, wie das kombiniert wird.
Und man verwendet also diese drei Möglichkeiten intensiv im Rechner
für unterschiedliche Zwecke.
Also wenn ich hier bei der Komplementdarstellung habe ich natürlich in
der Mitte die Skala, die gibt mir gerade die Grenze an zwischen den
darstellbaren negativen und positiven Zahlen.
Und hier habe ich also die positiven links von den negativen Zahlen.
Muss man wissen, wie man damit dann entsprechend umgeht.
Genauer schauen wir uns jetzt Standard-Komplementdarstellung an, die
sogenannte Zwei-Komplementdarstellung und die Eins
-Komplementdarstellung.
Das sind übliche Arten, wie man ganze Zahlen darstellt im Rechner.
Und das geht los mit der Zwei-Komplementdarstellung.
Die heißt deswegen Zwei-Komplementdarstellung.
Und ich sehe gerade, ich bin mit der Zeit so weit, dass ich eigentlich
jetzt aufhören möchte und Ihnen dieses dann in der ersten Vorlesung im
neuen Jahr erzählen werde, am 7.
Januar, Mittwochmorgen.
Am 24.
Morgens möchte ich keine Vorlesung mehr halten, deswegen ist die
nächste Vorlesung erst am 7.
Januar.
Und ich möchte jetzt damit diesen Teil beenden und zu einem noch ganz
kurz ein paar Minuten verwenden, um etwas anderes zu tun, Ihnen etwas
anderes zu zeigen.
Ist ja eine letzte Vorlesung für Weihnachten, da muss ich Ihnen auch
mal ein bisschen was anderes darstellen können.
Also beenden wir mal hier die Präsentation und wir laden uns mal ganz
kurz ein anderes Programm.
Sie wissen ja, dass ich hier einen Tablett, also ich verwende ja
diesen Bildschirm, der so schön Touchscreen ist und mit dem Stift
bearbeitet werden kann.
Und mit dem Stift kann man ja malen.
Ich kann zum Beispiel hier einfach irgendwas malen.
Und ich kann hier noch irgendwas malen.
Ich kann also hier so etwas... da habe ich jetzt was anderes gemacht.
Ich kann also hier irgendwas reinmalen.
Wenn ich jetzt sage, das Ganze soll animiert werden, dann wandert das
auf einmal nach unten und läuft weg.
Da können Sie noch nicht viel sehen.
Ich kann das Ganze auch festmachen.
Ich habe nicht mehr so viel Zeit, deswegen zeige ich Ihnen, was man
mit solchen Dingen alles tun kann.
Ich kann also solche Objekte definieren.
So kann ich das machen und so.
Und wenn ich das jetzt hier animiere, dann dreht sich das auf einmal.
Also hier werden auch immer Dinge, die ich einfach male, auf meinem
Bildschirm interpretiert als physikalische Objekte.
Und jetzt habe ich so ein paar Sachen hier vorbereitet.
Ich zeige Ihnen mal ein sehr schönes, das habe ich nicht selber
gemalt, sondern das ist aus einer Bibliothek.
Nein, möchte ich nicht retten.
Ich zeige Ihnen mal eine sehr schöne Zeichnung, nämlich diese hier.
Das sind alles nur irgendwelche Rechtecke, die einfach so
hingezeichnet wurden mit verschiedenen Eigenschaften.
Ich kann die Eigenschaften der Elemente hier definieren, das war von
Gummi oder Stahl.
Diese Dinge hier, die so mit Ziegelsteinen symbolisiert sind, die sind
nicht beweglich.
Der gelbe Strich hier gibt die Schwerkraft an.
Und jetzt lasse ich das mal loslaufen.
Das ist ein Domino-Effekt, den Sie hier sehen.
Sie sehen, diese Elemente, die bewegen sich genau entsprechend in
physikalischen Gesetzen.
Und dann werden alle möglichen Dinge hier tatsächlich bewegt.
Und es passiert hier alles mögliche.
Und dann ist interessant, was da alles so abläuft.
Selbst dieser Ball da, der wird jetzt auch noch weggeworfen.
Und das ist natürlich mit viel Trick gemalt, sodass das hier genau so
abläuft.
Wenn ich hier die Schwerkraft verändere, die meinetwegen in diese
Richtung laufen lasse, dann werden die alle anders laufen.
Dann können die natürlich gar nicht mehr umfallen, weil die einfach
nach links rüber laufen.
Mehr passiert dann nicht.
Wenn ich die Schwerkraft wieder verändere und meinetwegen die nach
oben laufen lasse, dann haben wir wieder was anderes.
Dann würden die hier einfach nach oben wegwandern.
Das wollen wir eigentlich auch nicht.
Also Sie sehen, man kann hier verschiedenste Dinge mitmachen.
Und hier ist ein anderes Beispiel.
Wir können hier zum Beispiel einen...
Richtig, der Offroader, der ist auch ganz nett.
Das ist einfach nur ein rechtes Rechteck mit zwei Rädern, die hat man
hier dargestellt.
Hier ist ein kleiner Felsbrocken, der da runterfällt.
Und Sie sehen, jetzt ist also dieser kleine Auto in der Lage, da
hochzufahren.
Das ist einfach nur gezeichnet und entsprechend interpretiert.
Entsprechend den Eigenschaften, die man da ganz einfach durch einen
Klick dargestellt hat.
Und jetzt ist die Zeit aber wirklich fast um.
Und jetzt kann man natürlich ganz andere Sachen damit auch noch
darstellen.
Ich kann also zum Beispiel das hier nehmen.
Und jetzt ist die Zeichnung wieder zu klein für diese Auflösung.
Sie können sich vorstellen, was hier rechts eigentlich zu sehen ist
auf dem Bild.
Geht leider über den darstellbaren Bereich bei dieser Auflösung
hinaus.
Und wenn ich das hier animiere, dann wird die Botschaft Frohe
Weihnachten etwas ins Wanken kommen und fällt in Sicht zusammen.
Ich wünsche Ihnen also allen Frohe Weihnachten, guten Rutsch ins neue
Jahr.
Ich hoffe, dass Sie sich ein bisschen erholen können.
Und wir sehen uns dann am 7.
Januar wieder.
Und für alle die, die jetzt so nett hier ausgehalten haben.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, das reicht gerade.
Sie dürfen sich alle einen kleinen Weihnachtsmann abholen, weil Sie
heute noch gekommen sind.
Vielen Dank, das war es für heute.