Leseprobe
Inhalt
1. Einleitung
1.1 Begriffsdefinitionen
1.2 Vor- und Nachteile der Digitaltechnik
1.3 Digitale / Binäre Signale
2. Mathematische Grundlagen
2.1 Die boolesche Funktion
2.1.1 Alle Funktionen einer Variablen
2.1.2 Alle Funktionen zweier Variablen
2.1.3 Funktionen von n Variablen
2.2 Boolesche Algebra
2.2.1 Ein Axiomsystem
2.2.2 Wichtige Rechenregeln
2.3 Dualzahlen
2.3.1 Umwandlung von Dualzahlen
2.3.2 Rechenoperationen mit Dualzahlen
2.3.2.1 Duale Addition
2.3.2.2 Duale Subtraktion
2.3.2.3 Duale Multiplikation
2.3.2.4 Duale Division
2.3.3 Definition von positiven und negativen Dualzahlen
3. Codierungsverfahren
3.1 Der BCD Code
3.2 Der Zählcode
3.3 Der 1 – aus – 10 – Code
3.4 Der 3 – Exzeß – Code
3.5 Der Aiken – Code
3.6 Der Gray – Code
3.7 Der Libaw-Craig-Code (Johnson-Code
3.8 Der ASCII – Code
4. Darstellung, Synthese und Analyse boolescher Funktionen
4. 1 Spezielle Diagramme
4.1.1 Venn – Diagramme
4.1.2 Karnaugh – Diagramme (K(V)-Diagramme
4.2 Spezielle Terme
4.2.1 Konjunktionsterme
4.2.2 Disjunktionsterme
4.3 Zweistufige Normalformen
4.3.1 Disjunktive Normalform (ODER-Normalform
4.3.2 Konjunktive Normalform (UND-Normalform
4.4 Vereinfachung nach Quine und McCluskey
4.4.1 Spaltendominanzprüfung
4.4.2 Zeilendominanzprüfung
5. Optimierung von Schaltnetzen
5.1 Verwendete Schaltgatter in der Digitaltechnik
5.1.1 AND und NAND Gatte
5.1.2 OR und NOR Gatte
5.1.3 Inverte
5.1.4 Äquivalenzelemen
5.1.5 Antivalenzelemen
5.2 Verknüpfung logischer Gatte
5.2.1 Gatter mit mehreren Eingängen
5.2.2 Verknüpfung mehrerer Gatte
5.2.3 Substitution durch NOR- oder NAND-Verknüpfungen
6. Schaltungsentwurf digitaler Schaltungen
6.1 Aufbau einer Wechselschaltung
6.2 Aufbau einer 2-aus-3-Schaltung
7. Flip – Flop – Schaltungen
7.1 Allgemeine Vereinbarungen für Flip-Flops
7.1.1 Darstellung und Funktionsweise
7.1.2 Statische und dynamische Betrachtung
7.2 Das zustandgesteuerte RS / SR Flip-Flop
7.3 Das taktzustandgesteuerte RS / SR Flip-Flop
7.4 Das taktflankengesteuerte RS / SR Flip-Flop
7.5 Das JK Flip-Flop
7.6 Das T Flip-Flop
7.7 Das D Flip-Flop
7.8 Taktsteuerung und Rücksetzen von Flip-Flops
8. Register- und Speicherschaltungen
8.1 Flip-Flop Speiche
8.1.1 Der Wortspeicher (Register
8.1.2 Das Schieberegiste
8.1.2.1 Schieberegister mit serieller Eingabe
8.1.2.2 Ringregister mit serieller Eingabe
8.1.2.3 Schieberegister mit paralleler Eingabe
8.2 Zählerschaltungen
8.3 Entwurf von Zählschaltungen
8.3.1 Entwurf eines synchronen 8-4-2-1-BCD-Zählers
8.3.2 Entwurf eines synchronen 3bit-Zählers
9. Rechenschaltungen
9.1 Der Halbaddiere
9.2 Der Volladdiere
9.3 4bit Parallel-Addierschaltung
9.4 4bit Seriell-Addierschaltung
9.5 Carry-look-ahead-Addiere
9.6 Subtraktionsschaltung
10. Digitale Auswahl- und Verbindungsschaltungen
10.1 Multiplexer und Demultiplexe
10.2 2x4-Bit zu 4-Bit Datenselekto
10.3 Komparatorschaltung
10.4 DA- und AD-Wandle
10.4.1 Digital – Analog – Wandle
10.4.2 Analog – Digital – Wandle
10.5 Encoder- /Decoderschaltungen
11. Die Automatentheorie
11.1 Analyse der Verhaltensweise eines Automaten
11.1.1 Graphen eines Automaten
11.1.2 Die Automatentafe
11.1.3 Das Programmablaufdiagramm
11.2 Entwurf eines Fahrkartenautomaten
Formelsammlung zur Digitaltechnik
Tabellenverzeichnis
Abbildungsverzeichnis
Literaturverzeichnis
1. Einleitung
1.1 Begriffsdefinitionen
Die Digitaltechnik befasst sich mit der Umsetzung von analogen (wertkontinuier-lichen) in digitale (wertdiskrete) Signale und umgekehrt (ADU: Analog-Digital-Umwandlung / DAU: Digital-Analog-Umwandlung).
Die Verarbeitung und Darstellung von Informationen ist mit eingeschränkten Zeichenvorrat gegeben (0 / 1; high / low; wahr / falsch). Dieser eingeschränkte Zeichensatz dient zur einfachen physikalischen Realisierung. Demnach werden zwei Wertigkeiten verwendet:
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 1.1.1: Anwendungsbereich der digitalen Wertigkeiten
Herkunft „digital“:
Digitus (lat.) = Finger à Semantik: Mit Hilfe der Finger
Digit (engl.) = Ziffer, Stelle à Semantik: in abzählbarer Form
1.2 Vor- und Nachteile der Digitaltechnik
Vorteile:
-Digitale Signale lassen sich einfacher und weniger störanfällig übertragen. Sie unterliegen keiner Fehlerfortpflanzung.
-Digitale Signale lassen sich leicht kodieren (dekodieren) und sind somit gut zur Datenübertragung auch für weite Strecken geeignet.
-Digitale Signale lassen sich leicht konstruieren. Sie lassen sich einfach in Rechnern, Mikroprozessoren, Gatterbausteinen verarbeiten und speichern.
-Miniaturisierung elektronischer Bauelemente / höhere Leistungsfähigkeit der Bauelemente (Speicherkapazität, Rechnerleistung, Transistorenzahl) führt zu zunehmender Digitalisierung.
Nachteile:
-Digitale Systeme sind langsamer als analoge Systeme. In der Hochfrequenz-technik dominiert die Analogtechnik.
-Anzahl der benötigten Schaltungsbestandteile ist um ein Vielfaches höher als bei analogen Systemen (wird durch eine hohe Integrationsdichte auf entsprechende Chips kompensiert).
-Informationsverlust bei der Umwandlung analoger in digitale Informationen. Mathematisch kann dieses Phänomen als Rundungsfehler bezeichnet werden, welcher aufgrund der stets begrenzten Anzahl von Stellen immer auftritt.
-Analoge Anzeigen sind anschaulicher und schneller zu erfassen, weil Proportionen dargestellt werden. (Vergleiche Wertetabelle (digital) und Balkendia-gramm (analog)).
1.3 Digitale / Binäre Signale
Digitale Signale oder Größen bestehen aus abzählbaren Elementen. Die Elemente können 2, 3 oder mehr Zustände haben:
-Binäre Signale: Es gibt genau zwei Zustände (Binäre Digitaltechnik),
-Digitale Signale: Es gibt mehrere, endliche Zustände.
Zum Verständnis verwenden wir den Begriff Digitaltechnik für binäre Signale. Es gibt immer nur 2 Zustände (wahr/falsch, 0/1, low/high).
Die Information von binären Signalen erfolgt sequentiell mit der Zeit. Ein einzelnes binäres Zeichen wird Bit genannt. Folgende Konventionen sind weiterhin im Umfang dieser Veranstaltung gängig:
Abbildung in dieser Leseprobe nicht enthalten
Abb. 1.3.1: Bit – Definition
Die digitalen Signale werden mithilfe von Spannungen übertragen. Es gibt verschiedene Logik-Familien (TTL, CMOS, ...), die mit verschiedenen Spannungspegeln zu Detektion der beiden Zustände arbeiten.
Beispiele für Spannungen sind hierbei:
Abbildung in dieser Leseprobe nicht enthalten
Tab. 1.3.1: Auszug von Spannungspegeln
verschiedener Logikfamilien
Bei den Pegeln aus Tab. 1.3.1 ist darauf zu achten, dass sie lediglich einen Wert für die jeweilige Logikfamilie angeben. Aus den Datenblättern der verschiedenen Bausteine ist aber zu entnehmen, dass die tatsächlichen High- und Low- Pegel nicht an festen Spannungen sondern an Spannungsbereiche orientiert sind. Um der verwendeten Logik zu genügen muss der angelegte Pegel also in den vorgegebenen Spannungsbereich passen um eine korrekte Verarbeitung des Signals zu gewährleisten. Ebenso ist darauf zu achten, dass in den Datenblättern die Ausgänge eines Logikbausteins ebenfalls keine feste Spannung sondern vielmehr einen Spannungsbereich angeben.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 1.3.2: Spannungsbereiche in der Digitaltechnik (Beispiel TTL)
2. Mathematische Grundlagen
2.1 Die boolesche Funktion
Die gewohnte Schreibweise einer Funktion F von n Variablen gilt hier für einen Spezialfall von Variablenwerten aus der zweielementigen Menge {0, 1}.
Abbildung in dieser Leseprobe nicht enthalten
Dabei muss man sich unter den Symbolen 0 und 1 nicht notwendig die ganzen (reellen) Zahlen 0 und 1 vorstellen, sondern einfach die beiden Elemente des Binärraums B1 = {0, 1}. Wichtig ist, dass bei booleschen Funktionen auch der Funktionswert Y nur 0 oder 1 sein kann. In moderner Notation schreibt man für boolesches F auch
Abbildung in dieser Leseprobe nicht enthalten
ist dabei der n-dimensionale Binärraum im Sinne des kartesischen Produktes (x):
Abbildung in dieser Leseprobe nicht enthalten
also die Menge aller 2n geordneten n-Tupel mit Elementen aus B1. Man nennt diese n-Tupel auch n-dimensionale Binärvektoren. F nach (2.1.2) bildet also derartige Vektoren auf die Menge {0, 1} ab. Für n = 3 lautet (2.1.3) beispielsweise
Abbildung in dieser Leseprobe nicht enthalten
2.1.1 Alle Funktionen einer Variablen
Eine reelle Funktion Y = F(X1) wird graphische gerne mittels eines Koordinaten-systems wie in Abb. 2.1.1.1 zu sehen dargestellt. Die Darstellung einer booleschen Funktion vereinfacht sich für ein reelles B1. Die Bilder 2.1.1.2a bis 2.1.1.2d zeigen sämtliche booleschen Funktionen einer Variablen. Die Tabelle 2.1.1.1 die zuge-hörigen Funktionstafeln (Wahrheitstabellen).
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2.1.1.1: Graphische Darstellung einer reellen Funktion einer reellen Variablen
Wird Tabelle 2.1.1.1 um 90° im Uhrzeigersinn gedreht, sind die Funktionsspalten gerade die dual codierten Funktionsindizes. Beispielsweise ergibt die Spalte zu F1: 012= 1.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2.1.1.2: Graphische Darstellung aller booleschen Funktionen
einer Variablen
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2.1.1.1: Alle booleschen Funktionen einer Variablen
Die algebraischen Darstellungen zu Tabelle 2.1.1.1 lauten
Abbildung in dieser Leseprobe nicht enthalten
wobei F1offenbar stets sein Argument invertiert.
Definition (Negation):
heisst Negation (Verneinung) von . Es können auch Funktionen negiert werden. Aus (2.1.1.1) folgt beispielsweise
Abbildung in dieser Leseprobe nicht enthalten
Definition (Literal):
Die Größe , die also wahlweise oder sein kann, heißt Literal. Literale sind nützlich, wenn man auch negierte Variablen als Quasivariablen nutzen möchte, z.B. wenn die Ausführung der Negation keine Mühe bereitet.
2.1.2 Alle Funktionen zweier Variablen
Boolesche Funktionen von zwei Variablen kann man gemäß Abb. 2.1.2.1 veranschaulichen.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2.1.2.1: Einheitswürfel zur Darstellung boolescher Funktionen
von zwei Variablen
Auch in Tabelle 2.1.2.1 sind die Spalten-n-Tupel von unten nach oben gelesen die dualcodierten Funktionsindizes.
Beispielsweise ergibt die Spalte zu F1 : 01012= 5.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2.1.2.1: Tabelle aller booleschen Funktionen zweier Variablen
Einige der zweistelligen Funktionen haben Namen die in der folgenden Tabelle aufgelistet sind:
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2.1.2.2: Tabelle Prominente Funktionen zweier Variablen
Die Operatoren sind also im Einzelnen:
- Überstreichung für die Negation
für logisches UND ( vom lateinischen aut)
für logisches ODER ( vom lateinischen vel)
für die Äquivalenz
für die Antivalenz
Üblicherweise werden die Überstreichungen zur Negation nicht nur über dem Operanden, sondern in der Regel auch über den Variablen angewendet. Beide Formen sind korrekt, jedoch führt die einfach Negation des Operanden oft zu Verwirrungen:
Abbildung in dieser Leseprobe nicht enthalten
Bezüglich der Notation ist es international üblich, das Konjunktionszeichen wegzulassen. Das geht gut dank der Vorrangregel „Konjunktion vor Disjunktion, Äquivalenz, Antivalenz“, wobei für die letzten drei Operationen keine Vorrangregel üblich ist. Beispielsweise gilt:
Abbildung in dieser Leseprobe nicht enthalten
Die nahe liegende Ausdrucks weise von „ “ sollte jedoch vermieden werden.
2.1.3 Funktionen von n Variablen
Bei mehr als zwei Variablen wird jede graphische Darstellung zunehmend schwierig. Gewiß kann ein Hyperwürfel gezeichnet und in jeden Koordinaten-n-Tupel-Punkt der jeweilige Funktionswert eintragen werden, allerdings wird diese Zeichnung bei auch sehr unübersichtlich. Daher muss man sich bei Problemstellungen mit n Variablen mehr und mehr der Algebra anvertrauen.
Boolesche Funktionen sind auch für durch Funktionstafeln darstellbar (vgl. Tab. 2.1.3.1). Dabei bedeutet : Wahrheitswert (Funktionswert) zum i-ten Argument von F. Nach (2.1.2) gilt stets .
Bezüglich der Funktionen einer Variablen sei an Tabelle 2.1.1.1 erinnert. Funktionstafeln boolescher Funktionen von n Variablen haben stets Zeilen, wobei in der F-Spalte jeweils 0 oder 1 steht.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2.1.3.1: Funktionstafel mit „Wahrheits“-Werten von ;
Jede Funktion F hat ihre eigene „Funktions-Spalte“
2.2 Boolesche Algebra
Die boolesche Algebra umfasst eine Menge boolescher Objekte und ein Bündel von Rechenregeln, nach denen aus gegebenen Objekten neue bestimmt werden können. Da diese Objekte nicht nur Variablen, sondern auch Funktionen oder (boolesche) Teile von ihnen sein können, werden nun als „Variablen“ die Symbole A, B, C, ... (evtl. mit Indizes) benutzt.
2.2.1 Ein Axiomsystem
Seien A, B, C, ... boolesche Größen, also A, B, C, ... . Folgende Axiome sollen das Rechnen mit booleschen Größen bestimmen:
a) Kommutativgesetz der Konjunktion:
. (2.2.1.1)
b) Idempotenzgesetz der Konjunktion:
c) Kommutativgesetz der Disjunktion:
d) Idempotenzgesetz der Disjunktion:
e) Assoziativgesetz der Konjunktion:
f) Assoziativgesetz der Disjunktion:
g) Erstes Distributivgesetz:
h) Zweites Distributivgesetz:
i) Existenz des Identitätselements der Konjunktion:
j) Existenz des Identitätselements der Disjunktion:
Als Grundlage aller Rechenoperationen gilt die Funktionstafel der Konjunktion und Disjunktion:
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2.2.1.1: Grundlegende Funktionstafel der
Konjunktion und Disjunktion
2.2.2 Wichtige Rechenregeln
Neben den Axiomen aus dem vorherigen Abschnitt werden häufig die folgenden Rechenregeln benutzt:
Abbildung in dieser Leseprobe nicht enthalten
Weiterhin kommen verschiedene Absorptionsregeln zum Gebrauch die einen booleschen Ausdruck umformen/kürzen:
Abbildung in dieser Leseprobe nicht enthalten
Neben den bislang vorgestellten Regeln und Axiomen sind die wahrscheinlich wichtigsten Rechenregeln die von De Morgan. Diese Regeln befassen sich mit der Umformung boolescher Funktionen durch Ändern der Negation, Operanden und Variablen:
Abbildung in dieser Leseprobe nicht enthalten
und
Abbildung in dieser Leseprobe nicht enthalten
(2.2.2.8) ergibt sich leicht aus (2.2.2.7) mit Hilfe von (2.2.2.1): Liest man (2.2.2.7) von Rechts nach Links, so erhält man den Ersatz von A bzw. B durch bzw. nach (2.2.2.1)
Abbildung in dieser Leseprobe nicht enthalten
Zwei weitere wichtige Rechenregeln betreffen die Darstellung (den Ersatz) von Antivalenz und Äquivalenz durch UND, ODER und NICHT. Es gelten
Abbildung in dieser Leseprobe nicht enthalten
für die Antivalenz bzw.
Abbildung in dieser Leseprobe nicht enthalten
für die Äquivalenz.
Gelegentlich werden zur Verkürzung von Rechnungen gern die folgenden Regeln für die Antivalenz angewandt:
Abbildung in dieser Leseprobe nicht enthalten
Negation boolescher Ausdrücke:
Neben den obigen Regeln gibt es noch den shannonschen Inversionssatz, der die Negation beliebig komplizierter boolescher Ausdrücke betrifft.
SATZ: Shannonscher Inversionssatz
Jede nur mit den Operatoren UND, ODER und NICHT gebildete Schaltfunktion kann dadurch negiert werden, dass die Operatoren für UND und ODER miteinander vertauscht werden und jedes Literal negiert wird.
Abbildung in dieser Leseprobe nicht enthalten
Wobei die letzte Klammer ausführlich geklammert ist. Danach wird der Shannonsche Inversionssatz angewendet:
Abbildung in dieser Leseprobe nicht enthalten
2.3 Dualzahlen
2.3.1 Umwandlung von Dualzahlen
Dualzahlen sind Zahlen die mit den Ziffern 0 und 1 gebildet werden. Innerhalb einer n-stelligen Dualzahl c hat die i-te Stelle von Rechts den Wert , d.h. die Dualzahl
Abbildung in dieser Leseprobe nicht enthalten
hat den gleich bezeichneten Zahlenwert
Abbildung in dieser Leseprobe nicht enthalten
wobei 0 und 1 die ganzen Zahlen Null und Eins sind.
Beispiel:
Abbildung in dieser Leseprobe nicht enthalten
Bei der umgekehrten Umwandlung von Dezimalzahlen in Dualzahlen, müssen probeweise alle Zehnerpotenzen gebildet werden, bis erstmal mindestens die Dezimalzahl erreicht ist. Ist beim n-ten Vergleich erwiesen, dass c eine Zweierpotenz ist, so ist offenbar
Abbildung in dieser Leseprobe nicht enthalten
Andernfalls gilt offenbar
Abbildung in dieser Leseprobe nicht enthalten
Beispiel zur Umrechnung Dezimal à Dual:
Die Zahl c = 73 soll als Dualzahl dargestellt werden. Als Hilfestellung dienen die Ergebnisse aus den Zweierpotenzen.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2.3.1.1: Zweierpotenzen
Berechnung:
Abbildung in dieser Leseprobe nicht enthalten
Zu konvertieren bleibt
Abbildung in dieser Leseprobe nicht enthalten
Offenbar gilt wiederum:
Abbildung in dieser Leseprobe nicht enthalten
Zu konvertieren bleibt
Abbildung in dieser Leseprobe nicht enthalten
Antwort:
Abbildung in dieser Leseprobe nicht enthalten
Die Umwandlung der Dualzahl in andere Zahlensysteme funktioniert nach dem gleichen Prinzip wie die Umrechnung von Dual nach Dezimal oder umgekehrt. Die am häufigsten vorkommenden Zahlensysteme sind dabei die Oktal- und Hexadezimalsysteme. Die Oktalzahlen haben dabei einen Wertebereich von 08, ... , 78(0002... 1112) und hexadezimale Zahlen von 016, ... , F16(00002... 11112)
Beispiel für Oktalzahldarstellung:
Beispiel für Hexadezimaldarstellung
2.3.2 Rechenoperationen mit Dualzahlen
Grundsätzlich gilt, dass vor jeder Rechenoperation die zu behandelten Zahlen im gleichen Zahlensystem vorhanden sind. Gegebenenfalls müssen alle Zahlen in Dualzahlen gewandelte werden bevor mit der Rechenoperation begonnen werden kann. Die Probe der richtigen Berechnung kann in jedem Zahlensystem vollzogen werden. Es bietet sich an, diese Probe parallel zur Berechnung im Dezimalzahl-system nachzuvollziehen.
2.3.2.1 Duale Addition
Wie in allen Zahlensystemen ist neben dem Zählen, also der Addition der 1, die Addition beliebiger positiver Zahlen die fundamentale Rechenoperation. Das gleichzeitige Addieren mehrerer Zahlen ist grundsätzlich nicht üblich. Bei der Addition von a und b zu c wird in der i-ten Stelle wie folgt gerechnet:
Abbildung in dieser Leseprobe nicht enthalten
2.3.2.2 Duale Subtraktion
Die Subtraktion zweier Dualzahlen stellt sich als schwieriger heraus, da wie aus der folgenden Übersicht zu erkennen ist, in einem Fall Das Ergebnis negativ werden müsste:
Abbildung in dieser Leseprobe nicht enthalten
Bei der Subtraktion wird um dieses Problem zu lösen mit einem Trick gearbeitet. Das vorliegende Beispiel soll sich auf den Fall
beschränken. Anstatt b zu subtrahieren, addiert man , das Zweierkomplement von b, und lässt im Ergebnis in Form der höchstwertigen 1 weg. Der Grund für dieses Vorgehen ist die Einfachheit mit der gebildet werden kann. Das Rezept zur Vorgehensweise lautet:
a) b durch das Einerkomplement b’ ersetzen, d.h. durch , wobei in c (2.3.1.1) einfach Nullen und Einsen miteinander zu vertauschen sind,
b) b’ um eins hochzählen/inkrementieren à b’’.
Beispiel zur Subtraktion von Dualzahlen:
Seien
a = 1210= 11002, b = 710= 01112
dann ist
b’ = 10002
à Schritt a) der Vorgehensweise ist erfüllt, und damit das Einerkomplement gebildet.
Im Zweiten Schritt wird der Subtrahend (b’) um 1 inkrementiert um das Zweierkomplement zu erhalten:
b’’ = 10002+ 00012= 10012
Das nun gebildete Zweierkomplement wird zum ursprünglichen Minuenden (a) addiert um die tatsächliche Differenz zu erhalten:
Abbildung in dieser Leseprobe nicht enthalten
Taucht bei der Subtraktion zweier n-stelliger Dualzahlen im Ergebnis bei n + 1 ein Übertrag auf, so ist das Ergebnis positiv. Ergebnisse ohne Übertrag bei n + 1 sind negativ. Der Wert an der Stelle n + 1 wird bei der Ergebnisdarstellung weg gelassen. Die Ausprägung ob das Ergebnis positiv oder negativ ist, wird vorerst durch die vorgestellten gewohnten Zeichen „+“ und „-“ dargestellt.
Es bedarf einer Definition der einzelnen Wertigkeiten einer Dualzahl und der Dimension des verwendeten Tupel um bestimmen zu können welche Wertigkeiten eine Stelle i in der Dualzahl hat (1 oder 0 = Zahl ; 1 oder 0 = positiv oder negativ). Siehe dazu Abschnitt „Definition von positiven und negativen Dualzahlen“.
2.3.2.3 Duale Multiplikation
Die Multiplikation von Dualzahlen kann im Prinzip wie im Dezimalsystem erfolgen. Der Multiplikand wird als erstes Zwischenergebnis genommen, falls die Einerstelle des Multiplikators eine 1 enthält. Dazu wird der um eine Stelle links geschobene (also verdoppelte) Multiplikand addiert, falls die Zweierstelle des Multiplikators eine 1 enthält. Ebenso verfährt man mit allen weiteren Stellen des Multiplikators, bis dieser vollständig abgearbeitet ist.
Beispiel zu Multiplikation von Dualzahlen:
Es soll mit Dualzahlen berechnet werden, 5 sei der Multiplikand, 6 der Multiplikator:
Abbildung in dieser Leseprobe nicht enthalten
2.3.2.4 Duale Division
Die Division von Dualzahlen kann ebenfalls in enger Anlehnung an die Division von Dezimalzahlen erfolgen. Sie wird hier ausführlich diskutiert. Die automatisierte Division im Rechner wird wie im folgenden Beispiel gerechnet:
6910: 510= 1310Rest 410
Im Dualzahlensystem sieht diese Berechnung wie folgt aus:
Abbildung in dieser Leseprobe nicht enthalten
Das Rezept für die Vorgehensweise bei der Division dualer Zahlen lautet wie folgt:
a) Divisor (Nenner N) möglichst weit nach links schieben, bis er höchstens gleich dem Dividenden ist (Zähler Z). Der so links verschobene Divisor ist der Anfangswert des „Arbeitsdivisors“ D.
b) Den „Arbeitsrest“ R = Z – D bilden. Ist R < N, so endet der Algorithmus hier, wobei R der Divisionsrest ist und an den vorläufigen Quotienten noch L Nullen rechts angehängt werden.
c) D um eine Stelle nach rechts schieben, und L um eins dekrementieren. Ist R D, eine 1 an den vorläufigen Quotienten anfügen und mit b) fortfahren. Sonst eine 0 an den vorläufigen Quotienten rechts anfügen und an den Beginn von c) zurückkehren.
Das Divisionsverfahren kann ebenso angewendet werden um beispielsweise eine Dualzahl in eine Dezimalzahl umzuwandeln. Der Divisor bei dieser Umwandlung wäre dann 1010bzw. 10102:
Beispiel zur Umwandlung von dual nach dezimal mittels Divisionsverfahren:
Im Beispiel soll die Zahl 1011000002in eine Dezimalzahl gewandelt werden
Abbildung in dieser Leseprobe nicht enthalten
Der Quotient dieser ersten Operation wird nun wiederum durch 10102geteilt:
Abbildung in dieser Leseprobe nicht enthalten
Der resultierende Quotient lässt sich nicht mehr durch 10102teilen. Daher kann keine weitere Division durch 10102mehr durchgeführt werden.
Die Dezimalzahl setzt sich nunmehr aus den Ergebnissen der Teilberechnungen zusammen. Dabei werden die letzen Ergebnisse der dualen Division an erster Stelle geschrieben: Quotient1Rest1Rest1+nà 1121012102à 35210
2.3.3 Definition von positiven und negativen Dualzahlen
Der Computer arbeitet mit festgelegter Dimension des Tupels (festgelegter Anzahl n von Stellen). Die werthöchste Stelle ist bekannt und wird als Vorzeichenstelle verwendet. Die Vorzeichenregel soll in folgender Tabelle anhand eines 4bit Bus dargelegt werden:
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2.3.3.1: Definition positiver und negativer Dualzahlen
3. Codierungsverfahren
Die Digitaltechnik befasst sich mit der Codierung und Übertragung von Daten. Unter den Codes versteht man hierbei die Systeme der Verständigung. Analog zu weltweit genutzten Codes die in Form von verschiedenen Schriftarten oder Sprachen genutzt werden (chinesische Schriftzeichen – arabische Schriftzeichen – kyrillische Schriftzeichen – ...), ist es bei der Digitaltechnik ebenso notwendig einen Code zu wählen um eine gemeinsame Kommunikation zwischen Sender und Empfänger garantieren zu können. Die Codierung ist also notwendig und erfordert eine vereinbarte Symbolik/Semantik um letztlich Informationen austauschen zu können. Im einfachsten Fall ergeben sich hierbei aus Buchstaben Wörter und aus Wörtern Sätze/Nachrichten wenn der Code sinnvoll kombiniert angewendet wird.
In der Digitaltechnik wird grundlegend als Unterscheidungsmerkmal der Wort- und der Zifferncode benannt. Der Wortcode beinhaltet die Umwandlung von Dezimal-zahlen und Dualzahlen. Der Zifferncode die Umwandlung von Ziffern und BCD-Zahlen.
3.1 Der BCD Code
Der BCD-Code (Binary Coded Decimals) oder 8-4-2-1-Code kodiert die Dezimal-ziffern von 0 bis 9. Eine Ziffer wird dabei von vier Binärstellen beschrieben und heißt Tetrade (griech. Vierergruppe). Die binären Zahlen die im 4bit System über die 9 hinausgehen landen in der Pseudotetrade. „Pseudo“ daher, da der Binärzahl keine Ziffer im Dezimal-system zugewiesen werden kann. Eine n-stellige Dezimalzahl wird im BCD-Code also durch n-Tetraden dargestellt:
Abbildung in dieser Leseprobe nicht enthalten
à 43962910= 0100 0011 1001 0110 0010 1001
3.2 Der Zählcode
Der Zählcode basiert auf einfachsten Theorien. Bei dieser Art der Codierung werden 10 Stellen die jeweils eine Wertigkeiten von 1 darstellen gesetzt oder nicht gesetzt (s. Tab. 3.2.1). Vorteile dieser Darstellung sind die leichte Lesabarkeit und die einfach Codierung. Allerdings ist der Zählcode mit einem hohen Aufwand beim Speichern der Information und bei Übertragung der Information verbunden. Anwendung für dieses Codierungsverfahren finden teilweise noch bei der Fernsprechvermittlung statt.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 3.2.1: Der Zähl-Code
3.3 Der 1 – aus – 10 – Code
Eine Weiterentwicklung aus dem Zählcode stellt der 1 – aus – 10 – Code dar. In diesem wird lediglich ein Bit pro Ziffer gesetzt, was die Lesbarkeit kaum beeinträchtigt. Der entscheidende Nachteil ist jedoch ebenso wie beim Zählcode dass sehr hoher Aufwand betrieben muss um verhältnismäßig wenige Informationen zu speichern. Ebenso bei der Übertragung eines 1-aus-10-codes ist erhöhter Aufwand notwendig da sehr viel übertragen werden muss um wiederum verhältnis-mäßig wenige Informationen zu erhalten.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 3.3.1: Der 1 – aus – 10 – Code
3.4 Der 3 – Exzeß – Code
Mit dem 3-Exzeß-Code wurde ein symmetrischer 4bit-Code entwickelt der 0000 & 1111 nicht beinhaltet. Die übrigen Ziffern werden symmetrisch codiert. Die übrigen 4bit Zahlen die nicht in Dezimalziffern gewandelt werden können sind wiederum in Pseudotetraden zusammengefasst:
Abbildung in dieser Leseprobe nicht enthalten
Tab. 3.4.1: Der 3 – Exzeß – Code
3.5 Der Aiken – Code
Der Aiken-Code basiert ebenso wie der 3-Exzeß-Code auf Symmetrie. Allerdings sind die Wertigkeiten 0000 und 1111 mit einbezogen.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 3.5.1: Der Aiken – Code
3.6 Der Gray – Code
Beim Gray-Code wird beim Übergang von einer Dezimalziffer zur nächsten lediglich eine Stelle in der Binärzähl geändert.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 3.6.1: Der Gray – Code
3.7 Der Libaw-Craig-Code (Johnson-Code)
5bit-Darstellung einer Ziffer im Dezimalsystem. Mit Johnson-Code wird der Johnson-Zähler realisiert. Es handelt sich um einen numerischen Code der jeder Ziffer einer Dezimalzahl einen dualen Code zuweist
Abbildung in dieser Leseprobe nicht enthalten
Tab. 3.7.1: Der Libaw-Craig-Code (Johnson-Code)
3.8 Der ASCII – Code
Der im Allgemeinen wahrscheinlich bekannteste Code ist der ASCII (American Standard Code for Information Interchange). ASCII wurde 1967 erstmals als Standard veröffentlich und 1986 zuletzt aktualisiert. Die Zeichenkodierung definiert 128 Zeichen, davon 33 nicht-druckbare sowie 95 druckbare.
Jedem Zeichen wird ein Bitmuster aus 7bit zugeordnet. Da jedes Bit zwei Werte annehmen kann, gibt es 27 = 128 verschiedene Bitmuster, die auch als die ganzen Zahlen 0 – 127 (hex: 0016-7F16) interpretiert werden können.
Die ersten 32 ASCII-Zeichencodes (0016bis 1F16) sind für Steuerzeichen reserviert. Das sind Zeichen die keine Schriftzeichen darstellen, sondern die zur Steuerung von solchen Geräten dienen, die ASCII verwenden (Bsp. Drucker). Die Codes 2116bis 7E16sind alle druckbaren Zeichen, die sowohl Buchstaben, Ziffern und Satzzeichen (s. Tab. 3.8.1) enthalten.
Abbildung in dieser Leseprobe nicht enthalten
Tab. 3.8.1: Der ASCII – Code
4. Darstellung, Synthese und Analyse boolescher Funktionen
Die Lehre der digitalelektronischen Schaltnetze ist durch einige spezielle Diagramme geprägt, welche wichtige Darstellungs- und sogar Arbeitshilfen sind. Außerdem wird hier über spezielle Terme der innerhalb von Schaltfunktionen und – darauf auf-bauend – über Normalformen von Schaltfunktionen gesprochen.
4. 1 Spezielle Diagramme
Die speziellen Diagramme der Theorie der Schaltnetze haben teils Tafelcharakter, teils sind es auch speziell gerichtete Graphen. Alle hier vorgestellten Diagramme sind unschätzbare Arbeitshilfen.
4.1.1 Venn – Diagramme
Venn-Diagramme dienen zur Darstellung algebraischer Verknüpfungen von Mengen, wobei die Elemente der Grundmengen als Punkte der Zeichenebene dargestellt werden. Für endliche Mengen, die uns hier ausschließlich interessieren, zeigt Abb. 4.1.1.1 die Vereinigungsmenge und den Durchschnitt zweier Mengen A und B mit den Elementen bzw. .
Genauer hat man in Abb. 4.1.1.1:
A = , B = ,
Durchschnittsmenge:
Vereinigungsmenge: .
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.1.1.1: Venn-Diagramm von Vereinigungsmenge und Durchschnitt
Folgende Abb. 4.1.1.2 zeigt das Venn-Diagramm zur Darstellung der Komplementbildung A’ = W \ A. A’ ist dabei die Menge derjenigen Elemente von W, die nicht zu A gehören.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.1.1.3: Zur Komplementierung der Grund-
verknüpfungen von Mengen
4.1.2 Karnaugh – Diagramme (K(V)-Diagramme)
Karnaugh – Diagramme (auch Karnaugh-Veitch-Diagramme gennant) sind spezielle Venn-Diagramme. Genauer sind es quadratische oder aus zwei Quadraten gebildete Rechteckfelder (Tafeln) aus kleinen Quadraten, in die die Funktionswerte einer Aufgabenstellung eingetragen werden. Gewisse Mengen von mit 1 beschrifteten kleinen Quadraten werden durch Konturen gebündelt (verschmolzen), die sich wie bei Venn-Diagrammen durchdringen können. Der besondere Nutzen besteht darin, dass durch die Verschmelzung meist einfachere/kürzere Funktionsdarstellungen gewonnen werden, solange die Anzahl der Variablen 5 nicht übersteigt. Die Tafeln für K-Diagramme werden induktiv durch Spiegelung gebildet: Zur Erzeugung der K-Tafel für m-dimensionale Funktionen wird die K-Tafel für (m – 1)-dimensionale Funktionen durch Spiegelung verdoppelt. Die jeweils neu hinzu kommende Variable hat in der alten Tafel den Wert 0, in der neuen Hälfte der neuen Tafel den Wert 1. Aus der Konstruktion für K-Tafeln nach Abb. 4.1.2.1 ist ersichtlich, wie man den kleinen quadratischen Feldern der fertigen K-Tafel die Argument-n-Tupel zuzuordnen hat, um auf die angegebenen Nummern zu kommen. Man stellt fest, dass jedem Quadrat eineindeutig der gespiegelte Vektor von ohne Kommata, d.h. als Dualzahl interpretiert, zugeordnet wird:
Abbildung in dieser Leseprobe nicht enthalten
Beispielsweise hat das kleine Quadrat aus Abb. 4.1.2.1 ganz unten rechts, das zu
gehört, die Nummer 11002= 1210.
Um auf die Anwendung des K-Diagramms eingehen zu können müssen zunächst verschiedene Grundlagen zu speziellen Termen erarbeitet werden. Mit Hilfe dieser können boolesche Funktionen im K-Diagramm dargestellt und vereinfacht werden.
Das K-Diagramm dient letztlich lediglich zur Darstellung und Vereinfachung komplexer Funktionen.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.1.2.1: Konstruktion von Karnaugh-Tafeln
In obiger Abbildung sind die Bereiche mit Xi= 1 durch geschweifte Klammern bezeichnet, an denen Xi steht. Die Kästchennummern sind die Dezimalzahlen zu den Dualzahlen von (4.1.2.1).
4.2 Spezielle Terme
In der booleschen Algebra ist es nützlich bestimmten Funktionsdarstellungen spezielle Namen zu geben. Es geht dabei um Darstellungen die nur die Konjunktion oder nur die Disjunktion enthalten.
4.2.1 Konjunktionsterme
Ein Konjunktionsterm T ist eine spezielle boolesche Funktion. Er entsteht durch konjunktive Verknüpfung von Literalen:
Abbildung in dieser Leseprobe nicht enthalten
mit für Funktionen von n Variablen.
Definition Minterm:
Ein Minterm Miist ein Konjunktionsterm maximaler Länge, also bei eine Konjunktion von n Literalen mit jeweils unterschiedlichen Indizes.
Verschmelzung von Konjunktionstermen:
Gewisse Minterme lassen sich paarweise zu einem um ein Literal kürzeren Konjunktionsterm zusammenfassen:
Abbildung in dieser Leseprobe nicht enthalten
Voraussetzung dafür ist offensichtlich, dass die beiden Minterme sich nur in einem Literal unterscheiden, welches der eine Normal und der andere negiert enthält. Dieser Verschmelzungs- und Verkürzungsprozeß lässt sich fortsetzen.
Beispiel anhand der Verschmelzung von 4 Mintermen:
Zu verschmelzen seien 4 Minterme von 4 Variablen. Gegeben sind (wobei Minterme mit Midargestellt werden):
Abbildung in dieser Leseprobe nicht enthalten
Offenbar sind
Abbildung in dieser Leseprobe nicht enthalten
die Ergebnisse lassen sich noch weiter verschmelzen zu
Abbildung in dieser Leseprobe nicht enthalten
Dieser zweistufige Verschmelzungsvorgang lässt sich nun mühelos in der K-Tafel in einem Schritt durchführen. Gegeben Seien hierbei wiederum die 4 Minterme mit vier Variablen. Wird die K-Tafel nach dem vorgestellten Spiegelprinzip gebildet, so müssen nur die entsprechenden Kästchennummern mit einer 1 versehen werden (s. Abb. 4.2.1.1). Die Minterme entsprechen dabei folgender Dual-/Dezimalzahl (vgl. (4.1.2.1) Spiegelung der Vektoren):
Wird in die somit ermittelten Kästchen der Wert 1 eingetragen kann über eine Verschmelzung die resultierende Funktion ermittelt werden:
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.2.1.1: Zusammenfassung von Mintermen im K-Diagramm
Zusammenfassend kann also gesagt werden, dass zu Beginn immer eine Aufgabenstellung steht die mehrere boolesche Gleichungen beinhaltet. Um diese Gleichungen zusammenfassend zu vereinfachen, werden die Literale in einer K-Tafel dargestellt. Durch Bildung einheitlicher Pakete (in diesem Fall werden Kästchen mit 1 zusammengefasst) erlangt man in wenigen Schritten eine vereinfachte Darstellung der gegebenen Aufgabenstellung. Ein weiteres Beispiel soll den Umgang mit dem K-Diagramm verdeutlichen. Gegeben Sei durch eine nicht bekannte Aufgabenstellung das K-Diagramm in Abb. 4.2.1.2. Durch Verschmelzung sind nun alle Minterme aus diesem K-Diagram zu ermitteln.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.2.1.2: Beispiel für K-Diagramm (Verschmelzung)
Zur Vereinfachung und besseren Übersicht können die Nullen aus der Tafel einfach weg gelassen werden, da sie für die Bildung der Verschmelzungen ohne Belang sind. Aus Abb. 4.2.1.2 wird deutlich, dass Verschmelzungen auch über den Rand der K-Tafel hinaus möglich sind. Letztlich können jedoch nur waagerechte und Senkrechte Verschmelzungen erfolgen. Einzige Ausnahme bilden die Ecken der Tafel. Diese können auch über den Rand miteinander verschmelzen. Das vorläufige Ergebnis kann nunmehr aus Abb. 4.2.1.2 abgelesen werden:
Abbildung in dieser Leseprobe nicht enthalten
Die aus dem K-Diagramm abgeleitete Funktion kann sicherlich noch vereinfacht werden, worauf jedoch an dieser Stelle noch nicht näher eingegangen wird. Zunächst sollen noch die Disjunktionsterme beschrieben werden.
4.2.2 Disjunktionsterme
Ein Disjuntionsterm entsteht durch disjunktive Verknüpfungen von Literalen:
Abbildung in dieser Leseprobe nicht enthalten
mit für Funktionen von n Variablen.
Definition Maxterm:
Disjunktionsterme maximaler Länge n, wobei n die Anzahl der Funktionsvariablen ist, heißen Maxterme. Alternativ kann bei Kenntnis des Mintermbegriffs gesagt werden: Ersetzt man in einem Minterm die Konjunktion durch die Disjunktion, so entsteht ein Maxterm. Die einfache Invertierung des Rechenoperators ist allerdings nicht erlaubt.
Analog zu den Mintermen einer Funktion gibt es also auch die Maxterme einer Funktion. Nach der Regel von De Morgan gilt folgender einfache Sachverhalt: Jeder Maxterm ist die Negation eines Minterms und umgekehrt (s. (4.2.2.2)).
Bei den K-Diagrammen werden nach diesem Sachverhalt Maxterme als fast vollständig aufgefüllte Tafeln dargestellt. (Bspsweise) Nur ein einziges kleines Quadrat (Kästchen) enthält die Null. Als Standardnumerierung für Maxterme bietet sich die Umformung nach folgender Gleichung an, in der der Minterm mit Standardindex i gemeint ist:
Abbildung in dieser Leseprobe nicht enthalten
Nach (4.2.2.2) bei Funktionen mit 4 Variablen ist also
Abbildung in dieser Leseprobe nicht enthalten
Abb. 4.2.2.1: Maxterm
[…]
- Arbeit zitieren
- Thomas Bertel (Autor:in)Prof. Dr. Albrecht Kunz (Autor:in), 2013, Digitaltechnik: Grundlagen, München, GRIN Verlag, https://www.grin.com/document/263575
Kostenlos Autor werden
Kommentare