Digitaltechnik: Grundlagen

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 B¹ = {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 2ⁿ geordneten n-Tupel mit Elementen aus B¹. 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(X₁) 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 B¹. 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 F₁: 01₂= 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 F₁offenbar 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 : 0101₂= 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 0₈, ... , 7₈(000₂... 111₂) und hexadezimale Zahlen von 0₁₆, ... , F₁₆(0000₂... 1111₂)

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 = 12₁₀= 1100₂, b = 7₁₀= 0111₂

dann ist

b’ = 1000₂

à 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’’ = 1000₂+ 0001₂= 1001₂

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:

69₁₀: 5₁₀= 13₁₀Rest 4₁₀

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 10₁₀bzw. 1010₂:

Beispiel zur Umwandlung von dual nach dezimal mittels Divisionsverfahren:

Im Beispiel soll die Zahl 101100000₂in eine Dezimalzahl gewandelt werden

Abbildung in dieser Leseprobe nicht enthalten

Der Quotient dieser ersten Operation wird nun wiederum durch 1010₂geteilt:

Abbildung in dieser Leseprobe nicht enthalten

Der resultierende Quotient lässt sich nicht mehr durch 1010₂teilen. Daher kann keine weitere Division durch 1010₂mehr 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: Quotient₁Rest₁Rest_1+nà 11₂101₂10₂à 352₁₀

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

à 439629₁₀= 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 2⁷ = 128 verschiedene Bitmuster, die auch als die ganzen Zahlen 0 – 127 (hex: 00₁₆-7F₁₆) interpretiert werden können.

Die ersten 32 ASCII-Zeichencodes (00₁₆bis 1F₁₆) 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 21₁₆bis 7E₁₆sind 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 1100₂= 12₁₀.

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 X_i= 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 M_iist 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 M_idargestellt 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

[…]