This is an old revision of the document!
Bits and bytes
Stellenwertsysteme
Per E-Tafel erklärt:
- 2023: Schreibweise in Steinzeit, Römerzeit, heute (Dezimalsystem = Zehnersystem = Stellenwertsystem zur Basis 10 mit den 10 Ziffern 0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
- Fünfersystem
- Umrechnung Fünfersystem → Zehnersystem
- Schreibweise mit Index unten
- Umrechnung Zehnersystem → Fünfersystem:
- Subtraktionsmethode: Höchste Fünferpotenz so oft wie möglich abziehen, dann mit der verbleibenden Zahl weitermachen
- Divisionsmethode: Sukzessive Division mit Rest durch 5: Die sich ergebenden Reste ergeben die Ziffern im Fünfersystem von rechts gelesen.
- Kurzschreibweise für Divisionsmethode und Beweis
- Primarschule im Fünferland: Alles im Fünfersystem:
- zähle von 0 bis $(32)_{10}$;
- schreibe das Kleine Einspluseins auf;
- schreibe das Kleine Einmaleins auf;
- addiere zwei Zahlen schriftlich;
- multipliziere zwei Zahlen schriftlich;
- St. Galler Bahnhofsuhr ablesen
- Binärsystem = Dualsystem = Zweiersystem
- Warum? Computer rechnen im Binärsystem (einfacher als etwa Zehnersystem, da nur zwei Zustände (AN/ON/1/wahr/true und AUS/OFF/0/falsch/false) unterschieden werden müssen; Computer unterscheiden meist “high voltage”/“(Strom-)Spannung” und “low voltage”/“keine Spannung”)
- Umrechnungen wie oben, etwa 2023 im Binärsystem angeben per Divisionsmethode!
- Primarschule im Zweierland: Zählen, Additions- und Multiplikationstabellen, schriftliches Addieren und Subtrahieren.
Logik und logische Schaltungen
Ziel: Baue eine logische Schaltung, die zwei Binärzahlen addiert!
- Bezeichnungen:
- Bit = binary digit = Binärziffer, also 0 oder 1
- byte = Folge von 8 Bit = 8-stellige Binärzahl (oder im Kontext von Speicherplatz (etwa Grösse von Festplatten) die Möglichkeit zur Speicherung einer solchen Zahl)
- Wie viele verschiedene Binärzahlen kann man in einem byte speichern?
- Boolesche/logische Verknüpfungen: AND (= logisches Und = Konjunktion), OR (= logische Oder = Disjunktion), NOT (= logische Verneinung = Negation), jeweils mit Wahrheitstabelle, wobei wir 0 statt falsch und 1 statt wahr schreiben
- AND, OR, NOT als logische Gatter gezeichnet (wie später ähnlich in Logisim)
- mathematische Schreibweise:
- $x \wedge y$ statt $x \text{ AND } y$
- $x \vee y$ statt $x \text{ OR } y$
- $\overline{x}$ statt $\text{NOT } x$ (manchmal statt der Überstreichung auch $\neg x$)
- Aufgabe: Wahrheitstabelle ausfüllen (sechs Spalten, zwei Eingänge/Inputs, vier Ausgänge/Outputs):
- Eingänge $a$ und $b$;
- Ausgänge $\overline{a \wedge b}$, $\overline{a \vee b}$, $\overline{a} \wedge \overline{b}$, $\overline{a} \vee \overline{b}$;
- Was fällt auf?
- Per obiger Aufgabe “de morgansche Gesetze” $\overline{a \wedge b} = \overline{a} \vee \overline{b}$ und $\overline{a \vee b} = \overline{a} \wedge \overline{b}$ für alle $a, b \in \{0, 1\}$ bewiesen (da für alle möglichen Belegungen der Variablen $a$ und $b$ auf beiden Seiten des Gleichheitszeichens dasselbe herauskommt).
- Es gibt viele andere ähnliche Gesetze, siehe etwa https://de.wikipedia.org/wiki/Boolesche_Algebra#Definition
- Insbesondere darf man wegen der Assoziativgesetze
- $x \wedge y \wedge z$ und
- $x \vee y \vee z$ schreiben (ohne Klammern).
Zur Auflockerung während der obigen Themen Ausschnitte aus dem folgenden Video gezeigt:
Video: Exploring how computers work
- nach Erklärung logischer Gatter: Video bis 3:00 (oder gar 3:55, also vor nand);
- nach de Morgan bis 5:00 (Gesetze erklären, warum NAND zweier verneinter Eingänge ODER ergibt);
- später eventuell bis zum Ende schauen, beispielsweise bis 8:10 als Wiederholung/Motivation für 4-Bit-Addierer.
Wie Computer Binärzahlen addieren (inklusive Disjunktive Normalform)
Lernziele: In der folgenden, relativ langen Aufgabe (Zeitaufwand ca. 2 Doppellektionen) wirst du lernen:
- was die disjunktive Normalform (DNF) ist: Wie man zu einer gegebenen Wahrheitstafel einen logischen Ausdruck findet, der nur die logischen Standardgatter AND, OR, NOT verwendet; insbesondere ist jede Wahrheitstafel durch einen logischen Ausdruck (und damit eine logische Schaltung) realisierbar;
- was ein Halbaddierer ist;
- was ein Volladdierer ist;
- was ein 4-Bit-Addierer ist bzw. genauer: wie man dem Computer schriftliches Addieren beibringt, indem man Halb- und Volladdierer geschickt kombiniert;
- wie man mit “Logik-Simulator-Software” logische Schaltungen entwirft und simuliert - wir verwenden die Software “logisim”.
Baue anhand der folgenden Anleitungen einen 4-Bit-Addierer mit Logisim (bitte alles zu Logisim Erklärte sofort selbst ausprobieren; bei den theoretischen Erklärungen gerne mitschreiben):
- Installiere Logisim über den folgenden Link (vermutlich wirst du ausserdem Java installieren müssen - während der Logisim-Installation wirst du hoffentlich auf die entsprechende Java-Installations-Webseite geleitet): https://sourceforge.net/projects/circuit/
- Video 2: "Einführung in Logisim" oder dasselbe auf Stream
- Falls du selbst Notizen machst: In den folgenden Videos verwende ich die hier verlinkte pdf-Datei.
- NEU: DNF für Volladdierer gemeinsam; zwei Alternativen erklärt: mit Hilfe zweier Halbaddierer oder mit etwas Nachdenken (und zwei XOR-Gattern)
- Überlege dir die logischen Ausdrücke für $c$ und $s$ (mit Hilfe der disjunktiven Normalform).
- Entwirf das Bauteil “Volladdierer” mit Logisim (verwende eine der drei oben erklärten Möglichkeiten).
- Kombiniere einen Halb- und drei Volladdierer zu einem 4-Bit-Addierer. Hinweis: Deine Schaltung wird in etwa so aussehen wie das Diagramm im Video.
Bonus-Material:
- Statt den Volladdierer per “Disjunktiver Normalform” zu bauen, kann man auch zwei Halbaddierer verwenden, vgl. etwa https://de.wikipedia.org/wiki/Volladdierer#Realisierungen
Diverse Screenshots:
Computer können natürlich viel mehr, als nur Binärziffern addieren, aber dafür haben wir leider keine Zeit, vgl. aber der folgende Abschnitt.
Bonus: Weiterführendes Material
Sinnvolle weiterführende Fragen sind beispielsweise:
- Wie speichert man ein Bit bzw. eine Binärzahl?
- Wie arbeitet ein Computer schrittweise ein Programm ab?
- Was passiert eigentlich genau, wenn ich eine Taste auf der Tastatur drücke?
Hier einige Empfehlungen:
- ein nettes Spiel (aber nicht ganz einfach): https://nandgame.com/
- Das bereits verwendete Video Video: Exploring how computers work von Sebastian Lague ist der Anfang einer Serie von Videos (die ich aber noch nicht angeschaut habe):
- eventuell ergänzen, falls es weitergeht
- Im ersten Video der obigen Serie werden empfohlen:
- eher universitäres Niveau: https://www.nand2tetris.org/
- Videos von Ben Eater, vgl. etwa https://eater.net/. Er wiederum empfiehlt das Buch “Digital Computer Electronics” von Albert Paul Malvino und Jerald A. Brown, vgl. https://archive.org/details/367026792DigitalComputerElectronicsAlbertPaulMalvinoAndJeraldABrownPdf1.
- In dem Buch “Abenteuer Informatik” von Jens Gallenbacher wird ein Mikroprozessor vorgestellt (aber nicht ausführlich erklärt), mit dem man Online experimentieren kann:
- Conway's Game of Life in Logisim: https://www.youtube.com/watch?v=M2qJ1pv3hf0
Speicherung von Bildern
ppm-Datei
Alle Zeilen, die mit # beginnen, sind Kommentare und können weggelassen werden.
P3 # "P3" means this is an RGB color image in ASCII 5 6 255 # "255" is the maximum value for each color # end of header, data below 255 255 255 255 255 255 255 0 0 255 255 255 255 255 255 255 255 255 255 0 0 255 0 0 255 0 0 255 255 255 255 0 0 255 0 0 255 0 0 255 0 0 255 0 0 0 0 255 0 0 255 0 0 255 0 0 255 0 0 255 0 0 255 255 255 255 0 0 255 255 255 255 0 0 255 0 0 255 255 255 255 0 0 255 0 0 255 0 0 255
svg-Datei
<svg height="600" width="500"> <polygon points="0,300, 400,0, 500,200" style="fill:red"/> <polygon points="0,300, 400,300, 500,600, 0,550" style="fill:blue"/> <polygon points="300,400, 400,400, 400,500, 300,500" style="fill:orange;stroke:cyan;stroke-width:20"/> <circle cx="80" cy="70" r="40" stroke="orange" stroke-width="5" fill="yellow"/> <text x="80" y="160" text-anchor="middle" fill="blue" transform="rotate(-50.2 80,160)">SVG is great</text> </svg>