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: Bool'sche Funktion per Wertetabelle (Tab. 3-1):
Index:x1x2x3 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:x1x2x3 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:x1x2x3 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)
xy ANDOR
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:x1x2x3 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
Schaltnetz (abb3-1.jpg)
Abb.3-1: Schaltnetzbeispiel
Schaltnetzentwurf:
  1. Schaltfunktion y = F(x)
  2. F: f1,...,fm Boolsche Funktionen
  3. fi Wertetabelle aufstellen
  4. eine Normalform aufstellen (2 Möglichkeiten):
    1. fi DNF aufstellen
    2. oder fi KNF aufstellen
  5. der Schaltplan (logischerweise auch hier 2 Möglichkeiten):
    1. fi DNF -> Schaltplan
    2. 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
(abb3-2.jpg)
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)
Volladdierer (abb3-3.jpg)
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 ) , Ü )
Volladdierer (abb3-4.jpg)
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: Kosten der Hardware - Implementierung vermindern:
  • Anzahl der Gatter minimieren
  • Gatter:
Gatter (abb3-5.jpg)
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:

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 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.
Aufbau eines KV-Diagramms (abb3-6.jpg)
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!
Zusammenfassen (abb3-7.jpg)
Abb. 3-7: Zusammenfassen
KV - Diagramme
für 1 Argument (Tab. 3-11):  
Index a
0
1
0
1
KV-Diagramm (1 Argument) (abb3-8.jpg)
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
KV-Diagramm (2 Argumente) (2804b7.jpg)
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
KV-Diagramm (3 Argumente) (2804b8.jpg)
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:
Beispiel für die Minimierung einer DF(abb3-11.jpg)
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

Nicht vollständig definierte Funktion (abb3-12.jpg)
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 (abb3-13.jpg)
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
Decoder/Demultiplexer (abb3-14.jpg)
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:
(abb3-15.jpg)
Abb. 3-15: KV-Diagramm für a0
a1:
(abb3-16.jpg)
Abb. 3-16: KV-Diagramm für a1
a2:
(abb3-17.jpg)
Abb. 3-17: KV-Diagramm für a2
Multiplexer
(abb3-18.jpg)
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
(abb3-19.jpg)
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)
x2x3fx 1
0
0
1
1
0
1
0
1
0
1*
0
0
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)
x1x3fx 2
0
0
1
1
0
1
0
1
1*
0
1*
1*
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) )
x1x2fx 3
0
0
1
1
0
1
0
1
1*
0
0
0
Tab. 3-22: Ableitung nach x3
=>Testpaar: (0,0,0) , (0,0,1) Ergebnis:
Variable: Testpaare:
x1001,101
x2000,010
100,110
101,111
x3000,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
xyf
0
0
1
1
0
1
0
1
0
1
0
0
Tab. 3-23: Beispiel - Hazard
Die Funktion im Schaltnetz:
erstes Hazardbeispiel(abb3-20.jpg)
Abb. 3-20: Beispiel - Hazard
das dazugehörende "Oszillographen-Bild" /Laufzeitverhalten:
LZV erstes Hazardbeispiel(abb3-21.jpg)
Abb. 3-21: Laufzeitverhalten
ein weiteres Beispiel: (eines Schaltungshazard) y=(NOT x) AND x
xf
0
1
0
0
Tab. 3-24: Schaltungshazard
Die Funktion im Schaltnetz:
2tes Hazardbeispiel(schaltungshazard)(abb3-22.jpg)
Abb. 3-22: Schaltnetz - Beispiel 2
das dazugehörende "Oszillographen-Bild" /Laufzeitverhalten:
LZV Schaltungshazardbeispiel(abb3-23.jpg)
Abb. 3-23: LZV - Beispiel 2
nun noch ein Beispiel eines Funktionshazards: y=x1 AND x2
x2x2f
0
0
1
1
0
1
0
1
0
0
0
1
Tab. 3-25: Beispiel - Funktionshazard
an dieser Stelle nur noch das LZV:
LZV eines Fkt.hazards(abb3-24.jpg)
Abb. 3-24: Beispiel - Funktionshazard (LZV)
Feststellung: Empfindlichkeit schon der bool'schen Funktion gegen Laufzeitverschiebungen bei Eingabekombinationswechseln =>Klassifikation von Hazards
Standartschaltnetzmodul(abb3-25.jpg)
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:
Hazardab
A
B
1
3
2
4
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 )
x1x2x3f
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:
x1x2x3  
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:
LZV des stat. Fkt.hazard(abb3-26.jpg)
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)
x1x2x3f
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)
x1x2x3 
1
1
1
1
1
0
-> f=1
-> f=1
Tab. 3-30: hier kein Zustandswechselproblem
ein mögliches Schaltnetz:
Schaltnetz des stat. Schaltungshazard(abb3-27.jpg)
Abb. 3-27: Schaltnetz des statischen Schaltungshazards
Das ganze im Laufzeitverhalten betrachtet:
LZV des stat. Schaltungshazard(abb3-28.jpg)
Abb. 3-28: LZV beim statischen Schaltungshazard

SATZ: Alle Primimplikanten einer DNF in 1:1-Umsetzung in einem Schaltnetz: keine statischen Schaltungshazards Beispiel:
x1x2x3 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
KV-Diagramm (abb3-29.jpg)
Abb. 3-29: das KV-Diagramm
f=(x1 AND x3) OR (x2 AND NOT x3) OR (x1 AND x2) Das Schaltnetz:
Primimplikanten (abb3-30.jpg)
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
indexx2x1x0 fnf3f2f1f0
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
ROM-Baustein (abb3-31.jpg)
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:
Schaltnetz (abb3-32.jpg)
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)
Speichermodul (abb3-33.jpg)
Abb. 3-33: 1-bit Haltespeicher

Haltespeicher

Modul eines Haltespeichers (abb3-34.jpg)
Abb. 3-34: Modul eines Haltespeichers
LZV eines Haltespeichers (abb3-35.jpg)
Abb. 3-35: LZV eines Haltespeichers
Speicher: spezielles Schaltwerk einfache Funktionalität
Ðbergangsdiagramm (abb3-36.jpg)
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)
Asynchrones Schaltwerk (abb3-37.jpg)
Abb. 3-37: Asynchrones Schaltwerk -Modul
Asynchrones Schaltwerk (abb3-38.jpg)
Abb. 3-38: Asynchrones Schaltwerk -LZV

Synchrone Schaltwerke:

(näheres hier)
Synchrones Schaltwerk (abb3-39.jpg)
Abb. 3-39: Synchrones Schaltwerk -Modul
Synchrones Schaltwerk (abb3-40.jpg)
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
RS-FlipFlop (abb3-41.jpg)
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 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. Zeitpunkt = kurzes Zeitintervall
PegelsteuerungPegelsteuerung (abb3-42.jpg)
Abb. 3-42
Flankensteuerung, positivPegelsteuerung (abb3-43.jpg)
Abb. 3-43
Flankensteuerung, negativPegelsteuerung (abb3-44.jpg)
Abb. 3-44
Im folgenden:

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
(abb3-45.jpg)
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