~~NOTOC~~ ====== 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 {{:lehrkraefte:snr:informatik:glf22:python:st-galler-bahnhofsuhr-01.jpg?800|}} {{:lehrkraefte:snr:informatik:glf22:python:st-galler-bahnhofsuhr-02.jpg?800|}} {{:lehrkraefte:snr:informatik:glf22:python:st-galler-bahnhofsuhr-05.jpg?800|}} {{:lehrkraefte:snr:informatik:glf22:python:st-galler-bahnhofsuhr-06.jpg?800|}} Online-Binäruhr von Jens Gallenbacher (Knöpfe unten zum Einschalten von Erklärungen; erst grünen Knopf verwenden; Erklärungen verschwinden nach einiger Zeit, alternativ: "reload page"): https://www.abenteuer-informatik.de/bu.html * 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? Bei jede der 8 Positionen gibt es zwei Möglichkeiten (0 oder 1), also $2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 2^8 =256$ Möglichkeiten; anders ausgedrückt kann man die 265 Zahlen von $(00000000)_2=(0)_{10}$ bis $(11111111)_2=(255)_{10}$ 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). {{:lehrkraefte:snr:informatik:glf22:bits-and-bytes:de-morgansche-gesetze-in-logisim.png?nolink&600|}} ---- Zur Auflockerung während der obigen Themen Ausschnitte aus dem folgenden Video gezeigt: [[https://www.youtube.com/watch?v=QZwneRb-zqA|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): * Video 1: [[https://fginfo.ksbg.ch/~olaf/videos-glf22/logische-schaltungen/01-ziel-vier-bit-addierer.mp4|"Ziel: Bau eines 4-Bit-Addierers"]] oder [[https://bldsg-my.sharepoint.com/:v:/g/personal/olaf_schnuerer_ksbg_ch/EYLIL_khTIxCqwqjCXMzT-MB9_VsuozSAtIDZ8jPyfLyQw?e=vayXK4|dasselbe auf Stream (Geschwindigkeit regulierbar)]] * 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: [[https://fginfo.ksbg.ch/~olaf/videos-glf22/logische-schaltungen/02-einfuehrung-logisim.mp4|"Einführung in Logisim"]] oder [[https://bldsg-my.sharepoint.com/:v:/g/personal/olaf_schnuerer_ksbg_ch/EdXoaC5JIrZAlkfUMnEID6IBBkHw0XCEM7JaVwzT-9AKOg?e=fFqcdO|dasselbe auf Stream]] * Falls du selbst Notizen machst: In den folgenden Videos verwende ich die {{ :lehrkraefte:snr:informatik:glf22:bits-and-bytes:vorlagen-fuer-videos-halbaddierer-disjunktive-normalform-volladdierer-4-bit-addierer.pdf | hier verlinkte pdf-Datei}}. * Video 3: [[https://fginfo.ksbg.ch/~olaf/videos-glf22/logische-schaltungen/03-halbaddierer.mp4|"Halbaddierer bauen (inklusive erste Erklärung der disjunktiven Normalform)"]] oder [[https://bldsg-my.sharepoint.com/:v:/g/personal/olaf_schnuerer_ksbg_ch/ERzIhqPeAzpIrgUHIL2lQdUBeQSn6yx2T5MIh4VOgGimuQ?e=cOheBH|dasselbe auf Stream]] * Video 4: [[https://fginfo.ksbg.ch/~olaf/videos-glf22/logische-schaltungen/04-vier-bit-addierer.mp4|"Plan für den 4-Bit-Addierer (inklusive Volladdierer)"]] oder [[https://bldsg-my.sharepoint.com/:v:/g/personal/olaf_schnuerer_ksbg_ch/EZWs30CTPMBJmWTtJBGYTEkB6YrVvy6v130d18TqSy_60g?e=epHgPw|dasselbe auf Stream]] * NEU: DNF für Volladdierer gemeinsam; zwei Alternativen erklärt: mit Hilfe zweier Halbaddierer oder mit etwas Nachdenken (und zwei XOR-Gattern) * Video 5: [[https://fginfo.ksbg.ch/~olaf/videos-glf22/logische-schaltungen/05-DNF-erklaerung-per-siebensegment-inklusive-grobe-anleitung-zu-vier-bit-addierer-in-logisim.mp4|"Erklärung der disjunktiven Normalform (am Beispiel der Steuerung eines Segments einer Sieben-Segment-Anzeige)"]] oder [[https://bldsg-my.sharepoint.com/:v:/g/personal/olaf_schnuerer_ksbg_ch/EULB7cGT_zZLlkhXL3Lf45gBvrX-kxR53AVxyizvuQW78g?e=7dacRh|dasselbe auf Stream]] * Ü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: * Video 6: [[https://fginfo.ksbg.ch/~olaf/videos-glf22/logische-schaltungen/06-abschliessende-spielereien-mit-digitalanzeige.mp4|"Weitere Informationen zu Logisim, etwa digitale Anzeige"]] oder [[https://bldsg-my.sharepoint.com/:v:/g/personal/olaf_schnuerer_ksbg_ch/ESluc2SW0AxKmKEMVgKZVj4BmBnn6o0VkXJSNFmRDZu7gA?e=Y2Z1d1|dasselbe auf Stream]] * 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: {{:lehrkraefte:snr:informatik:glf22:bits-and-bytes:exklusives-oder.png?nolink&400|}} {{:lehrkraefte:snr:informatik:glf22:bits-and-bytes:halbaddierer.png?nolink&400|}} {{:lehrkraefte:snr:informatik:glf22:bits-and-bytes:drei-moeglichkeiten-va.png?nolink&800|}} {{:lehrkraefte:snr:informatik:glf22:bits-and-bytes:4-bit-addierer.png?nolink&800|}} Online-Alternativen zu Logisim: * https://logijs.com/editor * https://simulator.io/board * https://circuitverse.org/simulator Unterlagen zum aktuellen Thema von Ivo Blöchliger: * Videos zum Bauen von Halb-, Voll- und 4-Bit-Addierer: https://fginfo.ksbg.ch/dokuwiki/doku.php?id=lehrkraefte:blc:informatik:glf20:bitsundbytes-bitoperationen#addierer * Präsentation dazu und zu Weiterführendem: https://fginfo.ksbg.ch/dokuwiki/lib/exe/fetch.php?media=lehrkraefte:blc:informatik:glf20:bit-operationen.pdf 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 [[https://www.youtube.com/watch?v=QZwneRb-zqA|Video: Exploring how computers work]] von Sebastian Lague ist der Anfang einer Serie von Videos (die ich aber noch nicht angeschaut habe): * [[https://www.youtube.com/watch?v=I0-izyq6q5s|How Do Computers Remember?]] * [[https://www.youtube.com/watch?v=hEDQpqhY2MA|Visualizing Data with 7-Segment Displays]] * [[https://www.youtube.com/watch?v=_3cNcmli6xQ|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 ===== Farben und Speicherung von Bildern ===== Bearbeite das folgende Arbeitsblatt: {{ :lehrkraefte:snr:informatik:glf22:bits-and-bytes:speicherung-von-daten.pdf | Speicherung von Bildern}} ==== ppm-Datei ==== 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-Datei ==== SVG is great ===== Speicherung von Zahlen und Texten (ASCII und Unicode) ===== Bearbeite das folgende Arbeitsblatt: {{ :lehrkraefte:snr:informatik:glf22:bits-and-bytes:speicherung-von-daten-seiten-4-bis-9.pdf | Speicherung von Zahlen und Texten (ASCII, Unicode)}} ==== Mitschriebe ==== * 2aLIM: {{ :lehrkraefte:snr:informatik:glf22:bits-and-bytes:stellenwertsysteme-2alim-stand-2023-03-22.pdf |}} * 2kWG: {{ :lehrkraefte:snr:informatik:glf22:bits-and-bytes:stellenwertsysteme-2kwg-stand-2023-03-23.pdf |}} * 2lW: {{ :lehrkraefte:snr:informatik:glf22:bits-and-bytes:stellenwertsysteme-2lw-stand-2023-03-22.pdf |}} * 2rG: {{ :lehrkraefte:snr:informatik:glf22:bits-and-bytes:stellenwertsysteme-2rg-stand-2023-03-23.pdf |}} ==== Link zur Kursseite ===== [[lehrkraefte:snr:informatik:glf22|Zur Kursseite]]