Bits and bytes

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.

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.

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”.

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.

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):
  • How Do Computers Remember?
  • Visualizing Data with 7-Segment Displays
  • Experimenting with Buses and Three-State Logic
  • 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 (und ich schliesse mich der Empfehlung an) “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:
  • https://www.abenteuer-informatik.de/modellprozessor.html
  • https://www.abenteuer-informatik.de/mips.html
• Conway's Game of Life in Logisim: https://www.youtube.com/watch?v=M2qJ1pv3hf0

Alle Zeilen in der folgenden Dati, 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 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>

• 2aLIM: stellenwertsysteme-2alim-stand-2023-03-22.pdf
• 2kWG: stellenwertsysteme-2kwg-stand-2023-03-23.pdf
• 2lW: stellenwertsysteme-2lw-stand-2023-03-22.pdf
• 2rG: stellenwertsysteme-2rg-stand-2023-03-23.pdf

Zur Kursseite