1. Einleitung

In der ersten Vorlesung wurde ein Zusammenhang aufgezeigt zwischen den Programmen und Algorithmen der täglichen Praxis und den notwendigen 'Akteuren', die solche Programme abarbeiten müssen. Akteure können Menschen sein oder geeignete Automaten. Als Repräsentant der Automaten wurde informell das Konzept einer Turingmaschine vorgestellt. Es wurde dann gefragt, wie man von diesem logischen Konzept eines Automaten zu einer physikalisch realisierten Maschine kommen kann, die die Eigenschaften eines solchen Automaten besitzt. Am Gang dr Technikentwicklung wurde verdeutlicht, wie die 'Zustände' eines Automaten sich durch technische Vorrichtungen immer besser realisieren lassen. Schliesslich wurde am Beispiel der modernen Transistoren gezeigt, wie sich damit Maschinenzustände als schaltbare logische Zustände realisieren lassen. Eine Querbeziehung zu biologischen Strukturen der Informationsverarbeitung (Neuron, Nervengewebe) wurde angedeutet.

In der heutigen Vorlesung wird es darum gehen, das Verständnis physikalisch realisierter Schaltlogik am Beispiel der modernen Transistortechnik weiter zu vertiefen. Nach einer kurzen Übersicht über die physikalischen Kennwerte einiger wichtiger Schaltungsfamilien wird das Konzept der Schaltalgebra (Boolschen Logik) eingeführt, es werden logische Zusammenhänge zwischen unterschiedlichen Schaltungen aufgezeigt, es werden Schaltungsbeispiele vorgestellt und es wird der Einfluss des Zeitfaktors in realen Schaltungen thematisiert.

START

In der letzten Vorlesung ist am Beispiel eines (pnp-)Tranistors als Schalter die Grundidee vermittelt worden, wie man mit einem Transistor einen 'Schalter' realisieren kann, der in dem speziellen Fall sogar noch das Signal invertierte. Ein als 'low' bezeichnetes Eingangssignal (an der Basis) wurde zu einem als 'high' bezeichneten Ausgangssignal am Kollektor, und umgekehrt.

Um die weiteren Überlegungen mit logischen Gattern zu verstehen, seien hier einige Grundbegriffe noch geklärt.

Zunächst muss festgelegt werden, welche physikalischen Werte den logischen Bezeichnungen 'high' bzw. 'low' (oder auch 'true' versus 'false' oder '1' versus '0') entsprechen sollen. in der sogenannten positiven Logik wird die Bezeichnung high dem Wert '+5V' (oder auch '+3.5V') zugeordnet und die Bezeichnung low dem Wert 0V. In der sogenannten negativen Logik ist dies genau umgekehrt.

Um Signalstörungen zu minimieren, wurden bestimmte Signalpegel vereinbart, so dass das H-Signal in einem vereinbarten Störabstand zum L-Signal liegt. Bei standard CMOS-Bausteinen liegt der verbotene Bereich z.B. zwischen +1.5V und +3.5V.

Ferner ist aufgrund physikalischer Gegebenheiten davon auszugehen, dass der Übergang von einem L-Zustand in einen H-Zustand eine gewisse Zeit benötigt. Diese Signalanstiegszeit t_a wird gemessen zwischen 10% der Signalspannung und zwischen 90%. Entsprechend gibt es eine Signalabfallzeit t_f sowie die eigentliche Signaldauer t_d.

Empfängt eine digitale Schaltstufe ein Signal, dann benötigt die Verarbeitung des Signals grundsätzlich auch Zeit, d.h. das Signal am Ausgang der Schaltstufe ist um eine gewisse Zeit verzögert. Diese Impulsverzögerungszeit t_d (d:= delay) wird einmal gemessen zwischen den Zeitpunkten, an denen die ansteigenden Flanken des Eingangssignals und des Ausgangssignals 50% ihrer maximalen Höhe erreicht haben (= t_d1) oder an jenen Zeitpunkten, an denen die abfallenden Flanken des Eingangs und des Ausgangssignals 50% ihrer maximalen Höhe erreicht haben (= t_d2).

Eine andere wichtige Kenngrösse ist noch der Fan-out; dies ist die Anzahl der Eingänge von nachfolgenden Schaltstufen, die an einen Ausgang angeschlossen werden können. Der Fan-out liegt in der Regel mindestens bei 10, bei einer Reihe von Schaltkreisfamilien aber auch über 100.

Unbenutzte Eingänge von Schaltkreisen müssen grundsätzlich an die Betriebsspannung oder an Masse gelegt werden (oftmals über einen Schutzwiderstand).

Die wichtigsten Schaltkreisfamilien sind in unipolarer Technik die CMOS-Familie (mit verschiedenen Untergruppen) sowie in bipolarer Technik die TTL-Familie (mit sehr vielen Untergruppen) sowie die ECL-Familie. Für Details sei auf die entsprechende Literatur verwiessen.

START

Nachdem nun die Grundbegriffe für physikalische logische Schaltungen bereitgestellt sind, sollen jetzt jene logischen Funktionen kurz erläutert werden, die bei der Realisierung von logischen Schaltungen wichtig sind.

Ausgangspunkt ist die Tatsache, dass sich mit Gattern physikalisch Schaltungen realisieren lassen, die mit den Eingängen x₁, ..., x_n eine Funktion f_i realisieren, deren Wert am Ausgang y erscheint. Nach Vereinbarungen können die Eingänge nur die Werte H (high) oder L (low) annehmen, entsprechend der Ausgang y. Danach hat man mit n-vielen Eingängen 2ⁿ-viele unterschiedliche Belegungen der Eingänge, denen man einen Wert für y zuordnen muss. Im Prinzip kann man dies über einfache Tabellen -mittels einer sogenannten Wahrheitswert-Tabelle- realisieren.

Eine Wahrheitswert-Tabelle enthält für jeden Eingang eine Spalte und für jede Zeile der Tabelle, die einer möglichen Belegung aller Eingänge entspricht, legt man einen Funktionswert y fest.

x ist eine BOOLSCHE_LOGIK (BL): BL(x) iff x = < < BA, BV,BOOL>, BF > mit

1. BA ist die Menge der Boolschen Ausdrücke, BV ist die Menge der Boolschen Variablen, BOOL = {H,L}) und BF ist die Menge der Boolschen Funktionen, und es gilt:

2. Für jedes b in BF gilt: b ist eine Funktion und b in pow(BOOLⁿ x BOOL)

1. Die Menge BV ist eine Teilmenge der Menge BA der Boolschen Ausdrücke

2. Wenn b in BF und x in BVⁿ, dann ist b(x) auch ein Boolscher Ausdruck.

3. Nur was nach (i) und (ii) gebildet wurde, ist ein Boolscher Ausdruck.

Historisch war es der englische Mathematiker G.BOOLe, der 1854 solche Ausdrücke in seinem 'Treatise on the Laws of Human Thouht' systematisch untersucht hatte. Deswegen nennt man solch Ausdrücke auch 'Boolsche Ausdrücke'. Boolsche Ausdrücke haben eine direkte Beziehung zur Aussagenlogik (dier hier nicht weiter behandelt wird; siehe dazu die Vorlesung über Mathematik); im Falle der Aussagenlogik identifiziert man die Boolschen Ausdrücke mit aussagenlogischen Ausdrücken und die Boolschen Funktionen sind aussagenlogische Junktoren. Ferner kann man diese Sachverhalte auch mit den Ausdrucksmitteln eines mathematischen Verbandes analysieren.

In einer konkreten Boolschen Logik BL* muss man u.a. festlegen, welche konkreten Boolschen Funktionen gelten sollen. Fünf konkrete Boolsche Logiken BL1, ..., BL5 sind historisch und systematisch von Interesse.

In der Boolschen Logik BL1 sollen folgende drei Funktionen gelten:

1. f₁ (Negation, '~'): f₁(H) = L und f₁(L) = H

2. f₂ (AND, KONJUNKTION, UND, '&'): f₂(H,H) = H, f₂(L,H) = L, f₂(H,L) = L, f₂(L,L) = L

3. f₃ (OR, DISJUNKTION, ODER, '+'): f₃(L,L) = L, f₃(H,H) = H, f₃(H,L) = H,f₃(L,H) = H

Schreibweisen: Statt 'f₂(x,y)' kann man auch schreiben 'x & y' oder 'xy'. Entsprechend statt 'f₃(x,y)' kann man auch schreiben 'x+y'. Statt 'f₁(x) schreibt man auch '~x' oder 'x' mit einem Schrägstrich über dem x (in HTML noch nicht darstellbar). Treten alle Funktionen in einem Ausdruck auf, dann gelten die Prioritäten '~ > & > +'.

Im zuvor zitierten Werk von G.BOOL konnte BOOL den Satz beweisen, dass sich alle n-stelligen Boolschen Funktionen auf eine Kombination aus den drei Funktionen BF1 = {f₁,f₂,f₃} zurückführen lassen. Dies bedeutet, dass die Menge BF1 logisch vollständig ist.

Da die folgenden Gleichungen gelten:

kann man die Logik BL1 noch vereinfachen zu den Logiken BL2 oder BL3:

In der Boolschen Logik BL2 sollen folgende zwei Funktionen gelten:

1. f₁ (Negation, '~'): f₁(H) = L und f₁(L) = H

2. f₂ (AND, KONJUNKTION, UND, '&'): f₂(H,H) = H, sonst f₂() = L

In der Boolschen Logik BL3 sollen folgende zwei Funktionen gelten:

1. f₁ (Negation, '~'): f₁(H) = L und f₁(L) = H

2. f₃ (OR, DISJUNKTION, ODER, '+'): f₃(L,L) = L, sonst f₃() = H

Anmerkung: Wir behalten in BL2 und BL3 die Nummerierung der Boolschen Funktionen mit f₂ bzw. f₂ aus dem vorausgehenden Beispiel bei.

Aus der Geschichte der Aussagenlogik ist bekannt, dass man die Anzahl der Funktoren bis auf einen verringern kann. Eine Variante geht zurück auf den russisch gebürtigen amerikanischen Mathematiker H.M.Sheffer (1883 - 1964), der 1913 bewiessen hat, dass man mit einem 'Negatdisjunktor' ''|' := ~(x & y)' (=NAND)(der sogenannte Sheffersche Strich) alle anderen Boolschen Funktoren herleiten kann.

In der Boolschen Logik BL4 (Sheffersche Logik)soll folgende Funktion gelten:

1. f₄ (NAND, SHEFFERSCHER STRICH,NEGIERTES UND; '|'): f₄(L,L) = H, sonst f₃() = L

Historisch soll aber Ch.S.PEIRCE schon lange vor SHEFFER entdeckt haben, dass man eine Aussagenlogik mit nur einem Junktor realisieren kann. Der Peircesche Junktor ist dual zu Sheffers Strich: '\|/ := ~(x + y)' (NOR).

In der Boolschen Logik BL5 (Peircesche Logik) soll folgende Funktion gelten:

1. f₅ (NOR, PEIRCESCHER OPERATOR, NEGIERTES ODER; '\|/'): f₅(L,L) = H, sonst f₃() = L

Wie schon erwähnt, kann man die Boolsche Logik auch mit den Mitteln eines mathematischen Verbandes analysieren, in dem die Distributivgesetze gelten, insbesondere gilt 'xy + xz = x(y + z)'. Ferner zeigt sich, dass AND und OR dual zueinander sind; man kann Formeln mit AND in Formeln mit OR umwandeln, indem man die Wahrheitswerte invertiert:

START

4. Aussagenlogische Normalformen

Für die spätere Anwendung in komplexen logischen Schaltungen -sogenannten 'Programmierbaren Logikbausteinen (siehe dort)- ist es hilfreich, sich auch mit den sogenannten aussagenlogischen Normalformen vertraut zu machen. Insbesondere benutzt man die Konjunktive Normalform (KNF) oder die Disjunktive Normalform (DNF)

Ein Ausdruck ist in der Konjunktive Normalform (KNF) wenn er nur die Boolschen Funktionen '~', '&' und '+' enthält und es gilt, dass im Klammerbereich der Negation '~' keine andere boolsche Funktion mehr auftritt (auch kein zweites Negationszeichen '~') und wenn im Klammerbereich von jedem Disjunktionszeichen '+' kein Undzeichen '&' auftritt. Man hätte also Ausdrücke der Form E₁ & ... & E_k und jedes E_i wäre von der Form X₁ + ... + X_m mit X_j eine Boolsche Variable 'A' oder deren Negation '~A'.

Ein Ausdruck ist in der Disjunktiven Normalform (DNF) wenn er nur die Boolschen Funktionen '~', '&' und '+' enthält und es gilt, dass im Klammerbereich der Negation '~' keine andere boolsche Funktion mehr auftritt (auch kein zweites Negationszeichen '~') und wenn im Klammerbereich von jedem Konjunktionszeichen '&' kein Oderzeichen '+' auftritt. Man hätte also Ausdrücke der Form E₁ + ... + E_k und jedes E_i wäre von der Form X₁ & ... & X_m mit X_j eine Boolsche Variable 'A' oder deren Negation '~A'.

Man kann beweisen, dass sich jeder boolsche Ausdruck äquivalent in eine der beiden Normalformen umformen lässt.

Eine mögliche Umformungsvorschrift für Disjunktive Normalformen ist die folgende:

1. Gegeben sei ein Ausdruck, der nur die Funktionen '~', '&' und '+' enthält.

2. Das Negationszeichen wird solange 'nach innen' geschoben, bis jedes Negationszeichen nur noch eine einzelne Aussagenvariable bindet. Man benutzt dazu die Äquivalenzen: '~(A & B) gdw ~A + ~B)' und '~(A + B) gdw ~A & ~B' und '~~A gdw A'.

3. Es muss jetzt das Funktionszeichen '&' so verschoben werden, dass im Klammerbereich von '&' kein Disjunktionszeichen '+' mehr auftritt. Dazu benutzt man die Äquivalenzen: 'A & (B + C) gdw (A & B)+(A & C)' sowie '(A + B) & C gdw (A & C)+(B & C)'

Eine mögliche Umformungsvorschrift für Konjunktive Normalformen ist die folgende:

1. Gegeben sei ein Ausdruck, der nur die Funktionen '~', '&' und '+' enthält.

2. Das Negationszeichen wird solange 'nach innen' geschoben, bis jedes Negationszeichen nur noch eine einzelne Aussagenvariable bindet. Man benutzt dazu die Äquivalenzen: '~(A & B) gdw ~A + ~B)' und '~(A + B) gdw ~A & ~B' und '~~A gdw A'.

3. Es muss jetzt das Funktionszeichen '+' so verschoben werden, dass im Klammerbereich von '+' kein Konjunktionszeichen '&' mehr auftritt. Dazu benutzt man die Äquivalenzen: 'A + (B & C) gdw (A + B)&(A + C)' sowie '(A & B) + C gdw (A + C)&(B + C)'

Beispiel für Disjunktive Normalform:

1. ~( ( (A + B) & ~B ) + (C & B) )

   Negation nach innen

2. ~((A + B) & ~B) & ~(C & B)

   Negation nach innen

3. (~(A + B) + ~~B) & (~C + ~B)

   Negation nach innen

4. (( ~A & ~B) + B) & (~C + ~B)

   Konjunktion schieben

5. ( ~A & ~B)& (~C + ~B) + (B & (~C + ~B)

   Konjunktion schieben

6. ( ~A & ~B & ~C) + ( ~A & ~B) + (B & ~C) + (B & ~B)

Den letzten ausdruck kann man mittels der zuvor genannten Gesetze weiter vereinfachen:

1. ( ~A & ~B & ~C) + ( ~A & ~B) + (B & ~C) + (B & ~B)

2. ( ~A & ~B & ~C) + ( ~A & ~B) + (B & ~C) (mit A+0 = A)

Die formale Symmetrie der beiden Normalformen ist augenfällig und man spricht hier von dualen Formen. Dabei ist unter dem zu einem Ausdruck A* dualen Ausdruck derjenige Ausdruck B* zu verstehen, der aus A* dadurch entsteht, dass die Zeichen der Boolschen Funktionen '+' und '&' gegeneinander ausgetauscht werden. Zum Beispiel gehört zum Ausdruck

~((A & B) + ~C)

der duale Ausdruck:

~((A + B) & ~C)

Es lässt sich folgender Dualitäts-Satz beweisen (siehe dazu auch [HILBERT/ ACKERMANN 1972:19f]): "Ist A* eine Aussageform, die sich die sich nur mit Hilfe von '~', '+' und '&' aufbaut, so erhalten wir eine zu '~A*' äquivalente Aussageform, indem wir von A* zur dualen Aussageform übergehen, und darin jede Aussagevariable, die nicht unmittelbar negiert vorkommt, durch die negierte Aussagenvariable und jede negierte Aussagevariable, durch die einfache ersetzten"

So gehört also zum Ausdruck

 ~((A & B) + ~C)

der duale Ausdruck:

~((A + B) & ~C)

und es gilt dann die Äquivalenz:

 ~~((A & B) + ~C)  gdw    ~((~A + ~B) & C)

Formt man diese beiden ausdrücke mit den obigen Gesetzen schrittweise um, dann erhält man:

 ((A & B) + ~C)  gdw    ~(~A + ~B) + ~C)

 ((A & B) + ~C)  gdw    (A & B) + ~C)

START

Es wird jetzt anhand von einfachen Boolschen Funktionen gezeigt, wie diese zu realisieren sind:

1. A + B & C

2. (A + B)(A + C)

3. A(B + C)

4. AB + AC

5. A(A + B)

6. ~(AB)

7. ~(A + B)

8. ~(~A & ~B)

9. ~(A & ~B)

START

6. Karnaugh-Maps und Quine McClusky-Verfahren

In den folgenden Vorlesungen wird man die logischen Normalformen dazu benutzen, um Aufgabenstellungen in komplexe boolsche Funktionen zu transformieren und mit Hilfe solcher Funktionen dann digitale Schaltungen zu bauen. In diesem Kontext ist es dann nicht unerheblich, ob man die Komplexität der logischen Ausdrücke reduzieren kann, da eine solche Reduzierung direkt mit einer Kosteneinsparung einhergeht. Will man solch eine Komplexitätsreduktion nur anhand von logischen Umformungen vornehmen (siehe die vorausgehende Tabelle), stoesst man in der Praxis sehr schnell auf Grenzen. Aus diesem Grunde haben sich in der Praxis zwei Verfahren herausgebildet, die diese Reduktionen vereinfachen: Karnaugh-Tabellen und das Verfahren von Quine Mc-Clusky.

Zu den Karnaugh-Tabellen gibt es zwei gute Einführungen von Jack W. Crenshaw betitelt A primer on Karnaugh maps sowie Return to Karnaugh's isle. Für bis zu 4 Variablen sind die Karnaugh-Tabellen recht brauchbar; bei mehr als 4 Variablen werden sie unübersichtlich und ab 6 sind sie eigentlich nicht mehr nutzbar.

Will man mehr als 6 Variablen verarbeiten, letztlich beliebig viele, dann bietet sich ein Verfahren nach Quine McClusky an. Im Prinzip werden hier --ähnlich wie bei den Karnaugh-Tabellen-- die Primimplikanten mit Hilfe von Tabellen ermittelt. Im Gegensatz zur Karnaugh-Methode laesst sich das QMC-Verfahren aber gut als Algorithmus implementieren. Eine sehr gute Einführung zum QMC-Verfahren samt Beschreibung eines Algorithmus bietet George Vastianos unter dem Titel Boolean functions' minimisation software based on the Quine-McCluskey method.

Eine ebenfalls gute Einführung --allerdings ohne Algorithmus-- liefert Jack W. Crenshaw All about Quine-McClusky.

Einige öffentlich zugängliche Programme seien hier genannt: ein Programm mit Source-Kode findet man bei Thomas Pollak mit seinem Quine McClusky Simplification Tool (qmc). Dies ist ein C++-Programm, das befehlszeilenorientiert läuft oder mit einem Tcl/Tk-GUI. Es verarbeitet bis zu 9 Variablen. Es bietet Quellkode-Varianten für Linux, windows und DOS und ist opensource.

Ein sehr leistungsstarkes Online-Toole ist die Software von Christian Gottschall von der Universität Wien. Hier kann man die unterschiedlichsten Umformungen vornehmen lassen.

Mehrere Simulatoren der Universität Ilmenau zum Thema Karnaugh und QMC. Speziell die Seite zum QMC-Verfahren samt Erklärungen dürfte hilfreich sein.

START

7. Übungsaufgaben

1. Entwickeln Sie wenigstens ein Beispiel, in dem eine Schaltung mit 5 Gattern vorkommt, die dann durch äquivalente Schaltungen mit weniger Gattern ersetzt wird. Geben Sie die zugehörigen boolschen Funktionen sowohl in Formelschreibweise an wie auch in Diagrammschreibweise .

2. Ein bekannter Junktor ist auch die ausagenlogische Implikation (Zeichen: '=>'), bekannt auch als 'Wenn ... dann ...', mit (A => B) = (~A + B) bzw. ~(A & ~B). 'A => B' gesprochen: Wenn A dann B. Formen Sie folgende umgangssprachlichen Ausdruck unter Verwendung des Operators '=>' in einen boolschen Ausdruck um:
   "Wenn kein Feuer ausbricht, dann kann Peter zu Hause bleiben, dann hat die Feuerwehr Feierabend."
   Übersetzen Sie diesen Ausdruck mit dem Operator '=>' in einen boolschen Ausdruck ohne den Operator '=>' um. Geben Sie dazu auch eine Schaltung an.

3. Es sei angenommen, dass die Gatter, die Sie in ihren vorausgehenden Schaltungen verwenden, eine Gatterlaufzeit von 2 ns [Nanosekunden] haben während die Signallaufzeit auf den normalen Leitungen mit 0 ns angenommen wird. Stellen Sie fest, ob durch diese Gatterlaufzeiten die Logik ihrer Schaltungen eventuell gestört wird.

4. Auf wieviele Variablen kann man den folgenden Ausdruck verkürzen, ohne seine Aussage zu verfälschen?

   Y = ABCD+~A~B~C~D+A~D+~AB~C+~BD+~AB~C+AB~CD+BCD+~AC~D

5. Entwerfen Sie die logische Formel und die Schaltung für die Anzeige von 4-Bit-Zahlen in einer 7-Segment Anzeige mit den folgenden Bezeichnungen:

   

   
   7-Segment Anzeige

   Die Wahrheitswertabelle für die Zuordnung von 4-Bit-Zahlen zu den Segmenten lautet wie folgt (A ist höchstwertiges Bit):

   A	B	C	D	a	b	c	d	e	f	g
   0	0	0	0	1	1	1	1	1	1	0
   0	0	0	1	0	1	1	0	0	0	0
   0	0	1	0	1	1	0	1	1	0	1
   0	0	1	1	1	1	1	1	0	0	1
   0	1	0	0	0	1	1	0	0	1	1
   0	1	0	1	1	0	1	1	0	1	1
   0	1	1	0	1	0	1	1	1	1	1
   0	1	1	1	1	1	1	0	0	0	0
   1	0	0	0	1	1	1	1	1	1	1
   1	0	0	1	1	1	1	1	0	1	1

6. Wenden sie auf das Beispiel mit der 7-Segment Anzeige die Karnaugh-Tabellen an.

7. Wenden sie auf das Beispiel mit der 7-Segment Anzeige das Verfahren von Quine McClusky an.

START