Kapitel 3
Schaltnetze
Schaltfunktion: F: B7->B3 (mit B: bool'sche Menge)
y=(y1,y2,y3)=F(x1,x2,x3,x4,x5,x6,x7)
=> bool'sche Funktionen:
y1=f1(x1,...,x7)
y2=f2(x1,...,x7)
y3=f3(x1,...,x7)
=> bool'sche Funktion:
fi:B7->B hier i=1,2,3
=> allgemein gilt für eine bool'sche Funktion:
f:Bn->B
Darstellung:
a) Wertetabelle
b) Komposition aus grundlegenden Funktionen (z.B.: AND, OR, NOT, NOR, NAND)
hier interessant:
- Normalformen
- Darstellbarkeit (vollständige Operatorsysteme)
- minimale Formen
- einer bool'schen Funktion
- einer Schaltfunktion
Bool'sche Funktion per Wertetabelle (Tab. 3-1):
Index: | x1 | x2 | x3 | | f(x1,x2,x3)
|
0 1 2 3 4 5 6 7
| 0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
| |
0 0 0 1 0 1 0 1
|
Tab.3-1: bool'sche Funktion
Einschlägiger Index:
Nummer einer Zeile mit f(...)=1 (im Beispiel: 3,5,7)
Nichteinschlägiger Index:
Nummer einer Zeile mit f(...)=0 (im Beispiel: 0,1,2,4,6)
Min-Terme und die disjunktive Normalform DNF
mit i: Index
x1,...,xn :Argumente
i1,...,in :Werte der x1 bis xn in der Zeile i
mi(x1,...,xn)=
( boolsche Funktion über x1,...,xn, die nur in Zeile i eine 1 liefert )
= l1 AND l2 AND ... ln ,mit lj=xj ,falls ij=1
lj=(NOT xj) ,falls ij=0
Beispiele (beliebig gewählt):
m0=(NOT x1) AND (NOT x2) AND (NOT x3)
m3=(NOT x1) AND x2 AND x3
m6=x1 AND x2 AND (NOT x3)
Es ergibt sich damit folgende Tabelle (Tab. 3-2):
Index: | x1 | x2 | x3 | | f(x1,x2,x3) | | m0(x1,...) | m3(x1,...) | m6(x1,...)
|
0 1 2 3 4 5 6 7
| 0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
|
| 0 0 0 1 0 1 0 1
|
| 1 0 0 0 0 0 0 0
| 0 0 0 1 0 0 0 0
| 0 0 0 0 0 0 1 0
|
Tab.3-2: Min-Terme angewandt auf oben beschriebene boolsche Funktion
Normalformidee DNF:
1 - liefernde Stellen odern, d.h. Min-Terme werden disjunktiv verknüpft.
Disjunktive Normalform DNF :
Index: | x1 | x2 | x3 | | f(x1,x2,x3) | | m3(x1,...) | m5(x1,...) | m7(x1,...) | | m3 OR m5 OR m7
|
0 1 2 3 4 5 6 7
| 0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
|
| 0 0 0 1 0 1 0 1
|
| 0 0 0 1 0 0 0 0
| 0 0 0 0 0 1 0 0
| 0 0 0 0 0 0 0 1
|
| 0 0 0 1 0 1 0 1
|
Tab.3-3: DNF bei gegebenem Beispiel
=> OR-Verknüpfung der Min-terme der einschlägigen Indizes
=> m3 = NOT x1 AND x2 AND x3
m5 = x1 AND NOT x2 AND x3
m7 = x1 AND x2 AND x3
Darstellungssatz DNF:
Jede bool'sche Funktion kann eindeutig als "OR"-Verknüpfung der
Min-Terme der einschlägigen Indizes dargestellt werden.
hier:
f(x1,x2,x3)=
( NOT x1 AND x2 AND x3) OR
( x1 AND NOT x2 AND x3) OR
( x1 AND x2 AND x3)
=> daraus folgt auch:
{ AND, OR , NOT } ist ein vollständiges Operatorsystem
es ist möglich jede Funktion nur per AND, OR, NOT darzustellen.
Einschub:
Dualität von AND und OR (Tab. 3-4)
x | y | | AND | OR
|
0 0 1 1
| 0 1 0 1
|
| 0 0 0 1
| 0 1 1 1
|
Tab.3-4: Dualität von AND und OR
=> es gibt Max-Terme und eine KNF
Max-Terme und die konjunktive Normalform KNF
i-ter Max-Term wird dual zum Min-Term folgendermaßen definiert:
Mi(x1,...,xn)= L1 OR L2 OR ... OR Ln
mit Lj = NOT xj , falls ij=1
Lj = xj , falls ij=0
im Beispiel (die oben beschriebene bool'sche Funktion (Tab. 3-1)) ergibt sich somit:
(drei beliebig gewählte Max-Terme)
=> M0(x1,x2,x3)= x1 OR x2 OR x3
M3(x1,x2,x3)= x1 OR NOT x2 OR NOT x3
M6(x1,x2,x3)= NOT x1 OR NOT x2 OR x3
=> Betrachten wir dazu erneut die Tabelle zur bool'schen Funktion (Tab. 3-5):
Index: | x1 | x2 | x3 | | f(x1,x2,x3) | | M0(x1,...) | M3(x1,...) | M6(x1,...)
|
0 1 2 3 4 5 6 7
| 0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
|
| 0 0 0 1 0 1 0 1
|
| 0 1 1 1 1 1 1 1
| 1 1 1 0 1 1 1 1
| 1 1 1 1 1 1 0 1
|
Tab.3-5: Max-Terme angewandt auf oben beschriebene boolsche Funktion
=> Wertetabelle des i-ten Max-terms ist nur in Zeile i mit 0 belegt
=> es gilt:
mi = NOT Mi
Min-terme sind komplementär zu den entsprechenden Max-termen
z.B.: m3=NOT x1 AND x2 AND x3 M3=x1 OR NOT x2 OR NOT x3
NOT m3
=NOT (NOT x1 AND x2 AND x3)
=NOT(NOT x1) OR NOT x2 OR NOT x3
=x1 OR NOT x2 OR NOT x3
= M3
=> Normalformidee KNF
Max-Terme der 0-liefernden Stellen mit AND verknüpfen.
=> Konjunktive Normalform KNF
AND - Verküpfung der Max-Terme der nicht-einschlägigen Indizes:
f(x1,x2,x3)=
( x1 OR x2 OR x3) AND
( x1 OR x2 OR NOT x3) AND
( x1 OR NOT x2 OR x3) AND
.
.
.
=> Darstellungssatz ist dual zum Darstellungssatz der DNF
Vollständige Operatorsysteme
{ AND, OR, NOT } :
wegen DNF-Darstellungsatz
{ AND, NOT } :
weil OR durch NOT und AND definierbar ist:
x OR y = NOT(NOT x AND NOT y)
{ OR, NOT } :
weil AND durch NOT und OR definierbar ist:
x AND y = NOT(NOT x OR NOT y)
{ NAND } :
x NAND y ::= NOT(x AND y)
definierbar durch: NOT, AND
0 AND x = x NAND x = NOT(x AND x) = NOT 1 = 0
x AND y = (x NAND y) NAND (x NAND y)
{ NOR }:
x NOR y ::= NOT(x OR y)
dual zu NAND definierbar
Anmerkung:
NAND - vollständige Operatorsysteme
=> wenn man NAND-Bausteine realisieren kann,
kann man beliebige bool'sche Funktionen implementieren
z.B. TTL-Technologie
Ringsummennormalform RNF
XOR, Ringsumme, Antivalenz
x XOR y = (NOT x AND y) OR (x AND NOT y)
RNF aus DNF:
DNF : Oder-Verknüpfung der Min-Terme der einschlägigen Indizes
f(x1,x2,x3)=
( NOT x1 AND x2 AND x3) OR
( x1 AND NOT x2 AND x3) OR
( x1 AND x2 AND x3)
->RNF : OR durch XOR ersetzen:
f(x1,x2,x3)=
( NOT x1 AND x2 AND x3) XOR
( x1 AND NOT x2 AND x3) XOR
( x1 AND x2 AND x3)
Schaltnetze
Idee:
gegeben: Darstellung einer bool'schen Funktion per Komposition aus Grundfunktionen
z.B.: f(x1,x2,x3)=(NOT x1 AND x2 AND NOT x3) OR (x1 AND NOT x2 AND x3)
Überführen in Netzdarstellung (Abb. 3-1):
- Knoten für Grundfunktionen
- Verbindungen entsprechen den Kompositionen
Abb.3-1: Schaltnetzbeispiel
Schaltnetzentwurf:
- Schaltfunktion y = F(x)
- F: f1,...,fm Boolsche Funktionen
- fi Wertetabelle aufstellen
- eine Normalform aufstellen (2 Möglichkeiten):
- fi DNF aufstellen
- oder fi KNF aufstellen
- der Schaltplan (logischerweise auch hier 2 Möglichkeiten):
- fi DNF -> Schaltplan
- oder fi KNF -> Schaltplan
|
offene Probleme:
- Gatter und Leitungskosten -> Optimierungsbedarf
- Abweichungen: Technik <-> Ideal
- Laufzeiten
- Belastung der Ausgänge -> FanIn, FanOut
Halbaddierer
Addition von Binärziffern
Index |
x |
y |
R |
Ü |
0 1 2 3 |
0 0 1 1 |
0 1 0 1 |
0 1 1 0 |
0 0 0 1 |
|
R => Resultat Ü => Übertrag
|
Tab.3-6: Addition von Binärziffern (Halbaddierer)
Disjunktive Normalform (DNF):
R = (NOT x AND y) OR (x AND NOT y)
ü = x AND y
Nicht in DNF:
R = x XOR y

Abb. 3-2 Halbaddierer
Volladdierer
Addition zweier Binärziffern mit Übertrag
Index |
x |
y |
Üalt |
R |
Ü |
0
1
2
3
4
5
6
7
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
0
1
1
0
1
0
0
1
|
0
0
0
1
0
1
1
1
|
|
R(x,y,Üalt)=
|
( NOT x AND AND y AND Ü ) OR ( NOT x AND y AND NOT Ü ) OR
( x AND NOT y AND NOT Ü ) OR ( x AND y AND Ü )
= ( x XOR y ) XOR Ü => algebraische Umformung
hier: 1, 2, 4, 7
|
Ü(x,y,Üalt)=
|
( NOT x AND y AND Ü ) OR ( x AND NOT y AND Ü ) OR
( x AND NOT y AND NOT Ü ) OR ( x AND y AND Ü )
= ( x AND y ) OR (( x XOR y ) AND Ü ) => algebraische Umformung
hier: 3, 5, 6, 7 |
Tab. 3-7: Addition mit Übertrag (Volladdierer)
Abb. 3-3: Volladdierer
Allgemeine Regeln:
a XOR b = ( NOT a AND b ) OR ( a AND NOT b ) = ( a OR b ) AND ( NOT a OR NOT b )
NOT (a XOR b) = ( a AND b ) OR ( NOT a AND NOT b ) = ( NOTa OR b ) AND ( a OR NOT b )
R - Funktion:
R (x,y,Üalt)
= x XOR y XOR Üalt
= ( NOT x AND ( y XOR Üalt ) OR ( x AND NOT ( y XOR Üalt ))
= ( NOT x AND (( NOT y AND Üalt ) OR ( y AND NOTÜalt )))
OR ( x AND (( y AND Üalt ) OR ( NOT y AND NOT Üalt )))
(* a AND ( b OR c ) = ( a AND b ) OR ( a AND c ) => Ausmultiplizieren *)
= ( NOT x AND NOT y AND Üalt ) OR ( NOT x AND y AND NOT Üalt ))
OR (( x AND y AND Üalt ) OR ( x AND NOT y AND NOT Üalt ))
= ( NOT x AND NOT y AND Üalt ) OR ( NOT x AND y AND NOT Üalt )
OR ( x AND y AND Üalt ) OR ( x AND NOT y AND NOT Üalt )
(* => Umformung von oben *)
Ü - Funktion:
Ü (x,y,Üalt)
=( x AND y ) OR (( x XOR y ) AND Üalt )
= ( x AND y ) OR ((( NOT x AND y ) OR ( x AND NOT y )) AND Üalt)
= ( x AND y ) OR (( NOT x AND y AND Üalt ) OR ( x AND NOT y AND Üalt )
(* ( a AND b ) OR ( a AND NOT b ) = a => Resolution *)
= ( x AND y AND NOT Üalt ) OR ( x AND y AND Üalt ) OR ( NOT x AND y AND Üalt ) OR ( x AND NOT y AND Üalt )
= ( x AND y ) OR ( y AND Üalt ) OR ( x AND Üalt ) = ( x AND y )
OR ( x AND Üalt ) OR ( y AND Üalt )
(* => Umformung von oben *)
RV = x XOR y XOR Ü
ÜV = ( x AND y ) OR (( x XOR y ) AND Ü )
RV = RH2 ( RH1 ( x , y , Ü )
ÜV = ÜH1 OR ÜH2 ( RH1( x , y ) , Ü )

Abb. 3-4: Volladdierer (Halbaddierer <=> Gatter)
Addiernetz
Zwei 4-stellige Binärzahlen sollen addiert werden
- Entwurf über Wertetabelle:
=> 8 Eingänge = 23 Zeilen
- Entwurf durch Problemzerlegung:
=> 4 Stellen sind zu addieren , d.h. 3 Volladdierer und 1 Halbaddierer
Darstellung eines Addiernetzes ( siehe Bild 3.5 im Krumm-Skript )
Nach diesem Prinzip bietet auch ein Addiernetz für 32-bit-breite Zahlen keine Schwierigkeiten.
Aber Vorsicht: Laufzeitbetrachtung ( Gatterlaufzeit )
Addiernetz mit Übertrag - Vorausschau
Beachte: Übertrag wird von Addierer zu Addierer durchgeschleift => Laufzeitverzögerung
=>Durch Vorausschau Laufzeitverkürzung
Beispiel: 16-bit Addiernetz aus vier 4-bit Addierern
Übertrag-Vorausschau:
Übertrag für den nächsten 4-bit Addierer direkt aus den Eingängen der vorherigen Stufe.
Eingabe direkt an Vorausschau, Werte berechnen direkt den Übertrag
Mehr Hardware nötig, um die Geschwindigkeit zu steigern.
Funktion durch Problemanalyse: Ü = ( x3 AND y3) OR ... (siehe Krumm-Skript S.34 )
Optimierung
weniger Operationen, d.h. weniger Gatter
Techniken:- Algebraische Vereinfachung
- KV-Diagramme ( Karnaugh - Veitch )
- Algorithmus nach Quine / McCluskey
Kosten der Hardware - Implementierung vermindern:
- Anzahl der Gatter minimieren
- Gatter:
|
|

Abb. 3-5: Gatter (AND, OR, NOT)
Algebraische Vereinfachung
( Gesetze aus Kapitel 2.1 im Krumm-Skript)
die wichtigsten hier:
Absorption:
( x OR y ) AND x = x
( x AND y ) OR x = x
Resolution:
( x AND y ) OR ( NOT x AND y ) = y
( x OR y ) AND ( NOT x OR y ) = y
DNF: ( x AND y AND ... AND ... ) OR ( x AND y AND ... AND ... ) OR ...
KNF: ( x OR y OR ... OR ) AND ( x OR y OR ... OR ) AND ...
Beispiel:
( x1 AND NOT x2 AND x3 AND x4)
OR ( x1 AND NOT x2 AND NOT x3 AND x4)
OR ( x1 AND x2 AND x3 AND x4)
OR ( NOT x1 AND NOT x2 AND NOT x3 AND x4)
OR ( NOT x1 AND NOT x2 AND x3 AND x4)
= ( x1 AND NOT x2 AND x4 )
OR ( x1 AND x3 AND x4 )
OR ( NOT x2 AND NOT x3 AND x4 )
OR ( NOT x1 AND NOT x2 AND x4)
= ( NOT x2 AND x4 )
OR ( x1 AND x3 AND x4 )
OR ( NOT x2 AND NOT x3 AND x4)
=> Absorption ( NOT x2 AND x4 )
= ( NOT x2 AND x4 ) OR ( x1 AND x3 AND x4 ) => minimale disjunktive Form |
Namenskonventionen/-definitionen:
- x2 => ist ein Literal
- ( x1 AND x3 AND x4 ) => ist ein Implikant
- ( NOT x2 AND x4 ) sowie ( x1 AND x3 AND x4 ) sind Primimplikanten
Primimplikanten sind Implikanten, die nicht weiter vereinfacht werden können.
Implikanten
Index |
x0 |
x1 |
x2 |
f |
m2 |
m5 |
m6 |
m7 |
I25 |
I57 |
I257 |
0
1
2
3
4
5
6
7
| 0
0
0
0
1
1
1
1
| 0
0
1
1
0
0
1
1
| 0
1
0
1
0
1
0
1
| 0
0
1
0
0
1
1
1
| 0
0
1
0
0
0
0
0
| 0
0
0
0
0
1
0
0
| 0
0
0
0
0
0
1
0
| 0
0
0
0
0
0
0
1
| 0
0
1
0
0
1
0
0
| 0
0
0
0
0
1
0
1
| 0
0
1
0
0
1
0
1
|
Tab. 3-8: Beispiel
g ( x1, ... , xn ) ist Implikant von f ( x1 , ... , xn ): Aus g ( x1, ... , xn ) = 1 folgt f ( x1 , ... , xn ) = 1
- Ein Minterm eines einschlägigen Index ist Implikant
- f( x1, ... , xn ) ist Implikant
- Jede "OR"- Verknüpfung von Mintermen einschlägiger Indizes ist Implikant
- Jeder Implikant ist eine "OR"- Verknüpfung von Mintermen einschlägiger Indizes
f: "OR"- Verknüpfung von Implikanten, so daß alle 1-Stellen überdeckt werden (DNF)
( dual (KNF): f:"AND"-Verknüpfung von Implikanten, so daß alle 0-Stellen überdeckt werden)
Vereinfachungsidee: möglichst mächtige Implikanten => Primimplikanten
Primimplikanten
Index |
I26 |
I57 |
I67 |
0
1
2
3
4
5
6
7
| 0
0
1
0
0
0
1
0
| 0
0
0
0
0
1
0
1
| 0
0
0
0
0
0
1
1
|
Tab. 3-9: Primimplikanten
f = ( NOT x0 AND x1 AND NOT x2 ) OR <= m2
( x0 AND NOT x1 AND x2 ) OR <= m5
( x0 AND x1 AND NOT x2 ) OR <= m6
( x0 AND x1 AND x2 ) <= m7
= ( x1 AND NOT x2 ) OR <= I26
( x0 AND x2 ) OR <= I57
( x0 AND x1 ) <= I67
keine weitere Vereinfachung mehr möglich
KV - Diagramme (Karnaugh, Veitch)
Graphische Hilfsmittel, um Vereinfachungsmöglichkeiten zu suchen.

Abb. 3-6: Aufbau eines KV-Diagramms
Wertetabelle in der Fläche anordnen, so daß paarweise vereinfachbare Stellen nebeneinander liegen.
Index |
c |
b |
a |
f |
0
1
2
3
4
5
6
7 |
0
0
0
0
1
1
1
1 |
0
0
1
1
0
0
1
1 |
0
1
0
1
0
1
0
1
|
0
0
1 Zeile 2 mit Zeile 6 kombinieren
0
0
1 Zeile 5 mit Zeile 7 kombinieren
1
1 |
Tab. 3-10: Wertetabelle zum KV-Diagramm
2 - Einsen nach Resolution zusammenfassen!

Abb. 3-7: Zusammenfassen
KV - Diagramme
für 1 Argument (Tab. 3-11): |
|
|
 Abb. 3-8: KV-Diagramm (1 Argument)
|
für 2 Argumente (Tab. 3-12): |
|
Index |
b |
a |
0
1
2
3 |
0
0
1
1 |
0
1
0
1 |
|
 Abb. 3-9: KV-Diagramm (2 Argumente) |
für 3 Argumente (Tab. 3-13): |
|
Index |
c |
b |
a |
0
1
2
3
4
5
6
7 |
0
0
0
0
1
1
1
1 |
0
0
1
1
0
0
1
1 |
0
1
0
1
0
1
0
1 |
|
 Abb. 3-10: KV-Diagramm (3 Argumente) |
Vereinfachung: Primimplikanten
es gilt:
möglichst große rechteckige Flächen gefüllt mit Einsen der
Größe: 2, 4, 8, ...=2n
Minimierung von DF (disjunktive Form) mit Hilfe von KV-Diagrammen
Beispiel:

Abb. 3-11: Beispiel für die Minimierung einer DF
(NOT a AND NOT d) OR (NOT a AND b) OR (a AND NOT c AND d) = minimale disjunktive Form
Minimierung von KF (konjunktive Form) analog !
KV-Diagramm:
- einfaches graphisches Verfahren
- übersichtlich bis f : Bn -> B ; mit n <= 6
Bei mehr als 6 Argumenten:
Algorithmus nach Quine/McCluskey
1. Bestimmung aller Primimplikanten
2. kostenminimale Auswahl einer Menge von Primimplikanten die
ALLE 1-Stellen von f überdeckt
Primimplikantenbestimmung:
- Resolution
- Tabelle unterstützt Suche nach Resolutionsmöglichkeiten
Schaltfunktion: F: Bn -> B m
gemeinsame Minimierung:
f1: Bn -> B;
f2: Bn -> B;
...
fm: Bn -> B;
Terme mehrfach verwenden !
Primimplikantenbestimmung:
Start {mi ist Minterm eines einschlägigen Indizes von f}
1.Schritt
- Sortieren der mi nach steigender Anzahl nicht negierter Literale
- Einteilen zu Gruppen gleicher Anzahl nicht negierter Literale
2.Schritt Resolution:
- Suche nur in benachbarten Gruppen
- Ergebnisse -> neue Tabelle
- Iteration, bis stabil:
Beispiel:
allgemein:
Minterm mi
OR-Verknüpfung...binärer Index...dezimaler Index...Gruppe
( hier die einschlägigen Indizes an den Stellen 0,4,6,11,12,13,14 )
(x1 AND NOT x2 AND x3 AND x4)
OR...1011...11...3...IV
(x1 AND x2 AND NOT x3 AND x4)
OR...1101...13...3...IV
(x1 AND x2 AND x3 AND NOT x4)
OR...1110...14...3...IV
(NOT x1 AND x2 AND x3 AND NOT x4)
OR...0110...6...2...III
(x1 AND x2 AND NOT x3 AND NOT x4)
OR...1100...12...2...III
(NOT x1 AND x2 AND NOT x3 AND NOT x4)
OR...0100...4...1...II
(NOT x1 AND NOT x2 AND NOT x3 AND NOT x4)
OR...0000...0...0...I
In Tabellenform:
Tabelle 1
Gruppe |
Minterm |
Index; binär |
Index; dezimal |
I |
NOT x1 NOT x2 NOT x3 NOT x4 |
0000 |
0 |
II |
NOT x1 x2 NOT x3 NOT x4 |
0100 |
4 |
III |
x1 x2 NOT x3 NOT x4 NOT x1 x2 x3 NOT x4
|
1100 0110
|
12 6
|
IV |
x1 x2 x3 NOT x4 x1 x2 NOT x3 x4
x1 NOT x2 x3 x4
|
1110 1101
1011
|
14 13
11
|
Tab. 3-14: 1.Schritt
Tabelle2
Gruppe |
Minterm |
Index; binär |
Index; dezimal |
I' |
NOT x1 NOT x2 NOT x4 |
0*00 |
0,4 |
II' |
x2 NOT x3 NOT x4 NOT x1 x2 NOT x4
|
*100 01*0
|
4,12 4,6
|
III' |
x1 x2 NOT x4 x1 x2 NOT x4
x2 x3 NOT x4
|
11*0 110*
*110
|
12,14 12,13
6,14
|
Tab. 3-15: 2.Schritt
Tabelle3
Gruppe |
Minterm |
Index; binär |
Index; dezimal |
II' |
x2 NOT x4 x2 NOT x4
|
*1*0 *1*0
|
4,12,6,14 4,6,12,14
|
Tab. 3-16: 3.Schritt
Kostenminimale Auswahl benötigter Primimplikanten
|
0 |
4 |
6 |
11 |
12 |
13 |
14 |
x1 AND NOT x2 AND x3 AND x4 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
x1 AND x2 AND NOT x3 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
x2 AND NOT x4 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
NOT x1 AND NOT x3 AND NOT x4 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
4. |
|
|
1. |
|
2. |
3. |
Tab. 3-17: 4.Schritt: Die Auswahlmatrix
=> alle Primimplikanten benötigt
Nicht vollständig definierte Funktionen

Abb. 3-12: Schaltnetz bzgl. Umgebung
Eingänge:
kombinatorisch sind 23 Eingabemöglichkeiten vorhanden
aber:
spezielle Umgebung kann bestimmte Eingabe nicht erzeugen
-> Funktionswerte an dieser Stelle irrelevant
-> Freiheit zur Minimierung
|
x1 |
x0 |
f |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
2 |
1 |
0 |
1 |
3 |
1 |
1 |
undef. |
Tab 3-18: KV-Diagramm mit Don't Care

KV-Diagramm mit Don't Care
man kann für Don't Care einsetzen, was man braucht:
bei 0 lautet DF: (x0 AND NOT x1) OR (x1 AND NOT x0)
bei 1 lautet DF: x0 OR x1
Decoder/Demultiplexer

Abb. 3-14: Demultiplexer-Baustein
Index |
e |
S1 |
S0 |
a2 |
a1 |
a0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
1 |
- |
- |
- |
4 |
1 |
0 |
0 |
0 |
0 |
1 |
5 |
1 |
0 |
1 |
0 |
1 |
0 |
6 |
1 |
1 |
0 |
1 |
0 |
0 |
7 |
1 |
1 |
1 |
- |
- |
- |
Tab. 3-19: Wertetabelle: Demultiplexer
a0:

Abb. 3-15: KV-Diagramm für a0
a1:

Abb. 3-16: KV-Diagramm für a1
a2:

Abb. 3-17: KV-Diagramm für a2
Multiplexer

Abb. 3-18: Multiplexer-Baustein
minimierte DF (e0 AND NOT S1 AND NOT S2) OR (e1 AND S0 AND NOT S1) OR (S1 AND NOT e2)
Fehlerdiagnose:
- Hohe Ausschußrate bei Chipproduktion;
jeder produzierte Chip muß geprüft werden
- Chips mit vielen Eingängen
(z.B.: 24 Eingänge => 2 hoch 24 mögliche Eingaben)
->erschöpfender Test aller Kombinationen zu aufwendig
Einschränkende Fehlerannahmen z.B. nur Verbindungsunterbrechungen
Einschränkende Annahmen über Anzahl:
z.B. nur 1-fach Fehler
Nicht erschöpfende aber wesentlich aufwandsärmere Tests:
relativ wenige Eingaben werden überprüft

Abb. 3-19: möglicher Fehler Leitungsunterbrechung
Testermittlung über Ableitung einer boolschen Funktion
Idee:
Stellen verwenden, in denen sich eine Änderung
einer Eingabe ei als Änderung der Ausgabe zeigt.
z.B.: für e2
(0,-,0,1,0,0)
=>(0,0,0,1,0,0) und (0,1,0,1,0,0)
Suche solcher Stellen durch Ableitung von f nach e2
Ableitung einer bool'schen Funktion nach dem Argument xi
f:Bn->B (eine boolsche Funktion)
d.h.: y=f(x1,x2,...,xn)
Die Funktion
fx i:Bn-1->B mit
fx i(x1,...,xi-1,xi+1,...,xn)=
f(x1,...,xi-1,0,xi+1,...,xn) XOR f(x1,...,xi-1,1,xi+1,...,xn)
heißt Ableitung von f nach xi
Diskussion:
Gibt es für die Stelle (s1,...,si-1,si+1,...,sn)
fx i(s1,...,sn)=1 ,
dann muß f an den Stellen
Squer=(s1,...,si-1,0,si+1,...,sn) und
S,quer=(s1,...,si-1,1,si+1,...,sn)
unterschiedliche Ausgaben liefern.
Die Stellen Squer und S,quer bilden ein geeignetes Testmusterpaar, um
Unterbrechungen in der xi-Leitung von außen zu erkennen.
ein Beispiel:
f(x1,x2,x3)=( (NOTx1) AND x3) OR x2
Ableitung nach x1:
fx 1(x2,x3)=( ( (NOT 0) AND x3) OR x2) XOR ( ( (NOT 1) AND x3) OR x2)
=(x3 OR x2) XOR x2
=( (x3 OR x2) AND (NOT x2) ) OR ( ( NOT(x3 OR x2) ) AND x2)
=( x3 AND (NOT x2) ) OR ( (NOT x3) AND (NOT x2) AND x2)
= x3 AND (NOT x2)
Tab. 3-20: Ableitung nach x1
=>Testpaar: (0,0,1) , (1,0,1)
Ableitung nach x2:
fx 2(x1,x3)=( ( (NOT x1) AND x3) OR 0) XOR ( ( (NOT x1) AND x3) OR 1)
=((NOT x1) AND x3) XOR 1
=NOT ( (NOT x1) AND x3 )
= x1 OR (NOT x3)
Tab. 3-21: Ableitung nach x2
=>Testpaare:
(0,0,0) , (0,1,0)
(1,0,0) , (1,1,0)
(1,0,1) , (1,1,1)
Ableitung nach x3:
fx 3(x1,x2)=( ( (NOT x1) AND 0) OR x2) XOR ( ( (NOT x1) AND 1) OR x2)
= x2 XOR (NOT x1 OR x2)
=(x2 AND NOT ( (NOT x1) OR x2 ) ) OR ( (NOT x2) AND ( (NOT x1) OR x2) )
=( x2 AND x1 AND (NOT x2) ) OR ( (NOT x2) AND (NOT x1) ) OR ( (NOT x2) AND x2)
=( (NOT x2) AND (NOT x1) )
Tab. 3-22: Ableitung nach x3
=>Testpaar: (0,0,0) , (0,0,1)
Ergebnis:
Variable: | Testpaare:
|
x1 | 001,101
|
x2 | 000,010 100,110 101,111
|
x3 | 000,001
|
Auswahl einer minimalen Testmenge:
Menge T von Eingabekombinationen, so daß je xi ein Testpaar darin enthalten ist...
1) für x1 nur 1 Testpaar
-> 001 und 101 müssen in T aufgenommen werden
-> T={001,101}
2) für x3 nur 1 Testpaar
-> 000,001 -> T
-> T={000,001,101}
3) für x2 noch keinTestpaar ganz in T, aber
Ergänzung von 010 oder von 111 genügt
=> T={010,000,001,101}
oder
T={111,000,001,101}
Hazards
(engl.:Risiken,Gefahren)
Abweichungen eines Schaltnetzes von der logischen Vorgabe.
Bool'sche Funktion ist Identifizierung, insbesondere werden Laufzeiten vernachlässigt
Beispiel: f=(NOT x) AND y
Tab. 3-23: Beispiel - Hazard
Die Funktion im Schaltnetz:

Abb. 3-20: Beispiel - Hazard
das dazugehörende "Oszillographen-Bild" /Laufzeitverhalten:

Abb. 3-21: Laufzeitverhalten
ein weiteres Beispiel: (eines Schaltungshazard)
y=(NOT x) AND x
Tab. 3-24: Schaltungshazard
Die Funktion im Schaltnetz:

Abb. 3-22: Schaltnetz - Beispiel 2
das dazugehörende "Oszillographen-Bild" /Laufzeitverhalten:

Abb. 3-23: LZV - Beispiel 2
nun noch ein Beispiel eines Funktionshazards:
y=x1 AND x2
Tab. 3-25: Beispiel - Funktionshazard
an dieser Stelle nur noch das LZV:

Abb. 3-24: Beispiel - Funktionshazard (LZV)
Feststellung: Empfindlichkeit schon der bool'schen Funktion
gegen Laufzeitverschiebungen bei Eingabekombinationswechseln
=>Klassifikation von Hazards

Abb. 3-25: allgemeines Schaltnetz
die Eingabe wechselt von k=(k1,...,kn) auf k'(k'1,...,k'n)
a) f(k)=f(k')
aber y wechselt zwischenzeitlich den Zustand => statischer Hazard
b) f(k)=NOT f(k')
aber y führt mehr als ein Zustandswechsel aus => dynamischer Hazard
A) Zwischenkombination zwischen k und k'
(einige ki geändert, andere noch nicht, führen zum Hazard) => Funktionshazarad
B) Laufzeiteffekte in spezieller Schaltung führen zum Hazard => Schaltungshazard
Hazards können kombiniert auftreten:
Tab. 3-26: Kombination von Hazards
Beispiel: Statischer Funktionshazard ( Kombination von A und a )
f(x1,x2,x3)=(x1 AND x3) OR (x2 AND NOT x3 )
x1 | x2 | x3 | | f
|
0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
|
| 0 0 1 0 0 1 1 1
|
Tab. 3-27: Wertetabelle: statischer Funktionshazard
Wir versuchen einen Zustandswechsel, z.B.: von 110 auf 101
dann ergibt sich folgendes Problem:
x1 | x2 | x3 | |
|
1 1 1
| 1 0 0
| 0 0 1
| -> -> ->
| f=1 f=0 f=1
|
Tab. 3-28: Zustandswechselproblem beim statischen Funktionshazard
Beim Ðbergang von 110 auf 101 erhält f kurzfristig den Wert 0
Das Ganze im Laufzeitverhalten betrachtet:

Abb. 3-26: LZV beim statischen Funktionshazard
Beispiel: Statischer Schaltungshazard ( Kombination von B und a )
f(x1,x2,x3)=(x1 AND x3) OR (x2 AND NOT x3)
x1 | x2 | x3 | | f
|
0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
|
| 0 0 1 0 0 1 1 1
|
Tab. 3-29: Wertetabelle statischer Schaltungshazard
Funktionshazard kann nicht vorliegen (Es wechselt nur eine Eingabevariable)
x1 | x2 | x3 |
|
1 1
| 1 1
| 1 0
| -> f=1 -> f=1
|
Tab. 3-30: hier kein Zustandswechselproblem
ein mögliches Schaltnetz:

Abb. 3-27: Schaltnetz des statischen Schaltungshazards
Das ganze im Laufzeitverhalten betrachtet:

Abb. 3-28: LZV beim statischen Schaltungshazard
SATZ:
Alle Primimplikanten einer DNF in 1:1-Umsetzung in einem Schaltnetz:
keine statischen Schaltungshazards
Beispiel:
x1 | x2 | x3 | | f
|
0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
| 0 0 1 0 0 1 1 1
|
Tab. 3-31: Beispiel einer bool'schen Funktion

Abb. 3-29: das KV-Diagramm
f=(x1 AND x3) OR (x2 AND NOT x3) OR (x1 AND x2)
Das Schaltnetz:

Abb. 3-30: das Schaltnetz
Programmierbare Bausteine
1.) Integration lohnt nur bei großen Stückzahlen
2.) Hochintegration vermindert Kosten (Verdrahtung),
verbessert Leistungsparameter (Größe, Stromaufnahme, Geschwindigkeit)
3.) Hochintegriertes Schaltnetz ist sehr spezifisch für bestimmte Anwendungen
=> Konflikt
Lösung: Programmierbare Bausteine
1) Massenfertigung
2) Erst in Endphase:
Programmierung nach Anwendungsbedarf
ROM
Es sollten beliebige Schaltfunktionen
f:Bn->Bm mit n<=n und m<=m
durch programmierung realisierbar sein:
(n,m)-rom
programmierung:
binäre (2n x M)-Matrix entspricht folgender Wertetabelle
index | x2 | x1 | x0 | | fn | f3 | f2 | f1 | f0
|
0 1 2 3 4 5 6 7
| 0 0 0 0 1 1 1 1
| 0 0 1 1 0 0 1 1
| 0 1 0 1 0 1 0 1
|
| 0 0 0 0 0 0 1 1
| 0 0 0 1 1 1 0 0
| 0 0 1 0 1 1 0 1
| 0 1 1 0 0 1 1 0
| 0 1 0 1 0 1 0 1
|
Tab. 3-32: Beispielmatrix für ein ROM

Abb. 3-31: (N,M) - ROM
f1=(x1,...,xn)=M[Zahl(x1,...,xn),1]
Anmerkung:
Vorteil ROM: sehr universell
Nachteil ROM: sehr aufwendig
ROM und PLA im Krumm-Skript inklusive ihrer Realisierungen
Schaltwerke
Schaltnetz:

Abb. 3-32: das Modul
Funktionalität durch Funktion beschrieben:
y=F(aktueller Eingang)
Schaltwerk:
sequentielle Schaltung
=> Funktionalität:
Folge der Eingangsbelegungen seit Start wird auf Folge der Ausgangsbelegung abgebildet
y(t)=f(x(t))
-> Modell: Mealy-Automat
interner Zustand: Speicher
Einschub zum Thema: Speicher
Laufzeitspeicher <-> Haltespeicher
Laufzeitspeicher (Totzeitglieder):
y(t)=x(t-dt)
speichern entspricht verzögern um konstante Zeit Haltespeicher:
speichern entspricht verzögern bis Lesebefehl (Überschreibbefehl)

Abb. 3-33: 1-bit Haltespeicher
- Speicher: Typen
- Laufzeiteffekte, synchrone / asynchrone Schaltwerke
- Schaltwerk Entwurf
- Entwurf von Bausteinen
- Komplexe Speicherbausteine ( RAM¥s, PLA¥s)
Haltespeicher

Abb. 3-34: Modul eines Haltespeichers

Abb. 3-35: LZV eines Haltespeichers
Speicher: spezielles Schaltwerk
einfache Funktionalität

Abb. 3-36: zugehöriges Übergangsdiagramm
<din, Schreib!>
NOT din AND NOT Schreib! 00
NOT din AND Schreib! 01
din AND NOT Schreib! 10
din AND Schreib! 11
=> Halten, Lesen
=> Schreiben
Asynchrone Schaltwerke:
(näheres hier)

Abb. 3-37: Asynchrones Schaltwerk -Modul

Abb. 3-38: Asynchrones Schaltwerk -LZV
Synchrone Schaltwerke:
(näheres hier)

Abb. 3-39: Synchrones Schaltwerk -Modul

Abb. 3-40: Synchrones Schaltwerk -LZV
Asynchrone Schaltwerke:
Entwurf eines 1-bit Haltespeichers
RS - FlipFlop ( Reset, Set - FlipFlop )
set = 1 schalten, wenn 0 sonst nichts machen
reset = 1 schalten, wenn 1 sonst nichts machen
Verboten: set =1 und reset = 1 gleichzeitig
Grundidee: Schleife aus zwei Negationen speichert einen Wert
RS - FlipFlop: Entwurf

Abb. 3-41: Übergangsdiagramm und KV-Diagramm
Qneu = NOT R AND ( Qalt OR S ) = R NOR ( Qalt NOR S ) = ( Qalt NOR NOT S ) NOR R
Laufzeiteffekte bei verbotener Kombination
- Schwingen möglich
- intendierte Funktionalität
Baustein Asynchrones RS - FlipFlop
meist genutzte 1-bit Speicherzelle ( Register, Teilsynchroner Speicher, statische RAM¥s )
Synchrone Schaltwerke
Um negative Auswirkungen von Laufzeiteffekten auszuschließen,
werden Eingänge nur zu bestimmten Zeitpunkten ausgewertet.
- Zeitpunkte werden über Takteingang signalisiert
- Taktwahl so, daß Eingänge mit hoher Wahrscheinlichkeit eingeschwungen sind
Zeitpunkt = kurzes Zeitintervall
Pegelsteuerung |  Abb. 3-42 |
Flankensteuerung, positiv |  Abb. 3-43 |
Flankensteuerung, negativ |  Abb. 3-44 |
Im folgenden:
- Synchrone FlipFlops
- Entwurf synchroner Schaltwerke
Synchrone Flip Flops
Synchrone RS - FlipFlops
( siehe Bilder im Krumm-Skript )
Master / Slave: Wichtig, wenn Ausgänge wieder auf Eingänge zurückgeführt werden
RS - FlipFlop: Ansteuertabelle
Qt |
Qt+1 |
R |
S |
0 |
0 |
- |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
- |
|
|
0 speichern |
1 einschreiben |
1 einschreiben |
0 speichern |
|
Eingabe 11 verboten |
Tab. 3-33: RS-FlipFlop - Ansteuertabelle
Wie müssen die Eingaben angesteuert werden, um Zustandswechsel zu erzielen?
Takt wird hier vernachlässigt
Im folgenden:
verschiedene FlipFlop - Varianten charakterisiert durch ihre Ansteuertabelle:
RS - FlipFlop Reset / Set
JK - FlipFlop Reset / Set / Toggle
T - FlipFlop Toggle / Keep
D - FlipFlop Delay
=> Register des Prozessors
Synchrones JK - FlipFlop
( siehe Krumm - Skript Seite 54 )
Ansteuerfunktion:
S = NOT Q AND J
R = Q AND K
Qt |
J |
K |
Qt+1 |
R |
S |
0 |
0 |
0 |
0 |
- |
0 |
0 |
0 |
1 |
0 |
- |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
- |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
- |
1 |
1 |
1 |
0 |
1 |
0 |
|
 |
Tab. 3-34 und Abb. 3-45 Implementierung eines synchronen JK-FlipFlops
Synchrones T - FlipFlop
( siehe Krumm - Skript Seite 54 )
Ansteuerfunktion:
T = 0 => J = 0; K = 0
T = 1 => J = 1; K = 1
T |
Qt |
Qt+1 |
J |
K |
0 |
0 |
0 |
0 |
- |
0 |
1 |
1 |
- |
0 |
1 |
0 |
1 |
1 |
- |
1 |
1 |
0 |
- |
1 |
Tab. 3-35: Ansteuertabelle eines synchronen T-FlipFlops
Synchrones D - FlipFlop
( siehe Krumm-Skript Seite 54 )
Ansteuerfunktion:
D = 0 => R = 1; S = 0
D = 1 => R = 0; S = 1
Entwurf synchroner Schaltnetze
Vorgehen:
1.) Funktionalität per Mealy-Automaten spezifizieren
2.) Zustandskodierung wählen
3.) Schaltnetze per Wertetabellen:
a. Zustandsübergang
b. Ausgabe
4.) Auswahl der Speicherbausteine
5.) Ansteuerschaltnetze entwerfen
6.) Ansteuerschaltnetze minimieren
7.) Schaltplan erstellen
Im Folgenden: Beispiele
- Serienaddierer
- Serien-/Parallelwandler
Besonderheiten:
- mehr als ein FF im SW
- günstige und ungünstige FF-Wahl
- günstige und ungünstige Zustandskodierung
Entwurf eines Serienaddierers
Idee:
- Addiernetz (Paralleladdierer)
zwar schnell, aber gatteraufwendig
- durch Schaltwerke (sequentielle Schaltkreise)
neue Dimension: Zeit
=> durch Mehraufwand an Zeit (Taktzyklen)
Einsparung an Gattern
=> Serienaddierer
Entwurf eines Serienaddierers
1. Mealy-Automat
Aus Problembetrachtung:
Übertrag ist zu speichern -> 1 Bit-Speicher -> 2 Zustände
( Bild S. 55 im Krummskript )
2. Schaltnetze Zustandsübergang, Ausgabe
ü entspricht Zustandt+1 : f(xt,yt,Zustandt)
( üt entspricht Zustandt )
s entspricht Ausgabet:g(xt,ytZustandt)
3. Schaltnetze aus Wertetabellen
( Wertetabelle auf S.56 im Krummskript )
Ausgabefunktion : per KV-Diagramm
Zustands-/Übergangsfunktion:
FlipFlop-Auswahl
( Schaltbild S.57 im Krummskript )
(Einschub: Beispiel 3-Bit-Wandler )
4. Schaltnetz-Entwurf