close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

B

EinbettenHerunterladen
Digitaltechnik I
02()11 C 05()10 C 06()10 C 07()01
Inhalt
1
Digitale Schaltnetze
1.1 Elementare binäre Logikfunktionen und Logikbausteine . . . . . . DT 1.1
1.1.1
1.1.2
1.1.3
1.1.4
Binäre BOOLEsche Algebren und das GALOIS-Feld GF(2) . . . . . . . . . . . . .
Binäre Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Elementare Logikbausteine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Einige technische Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
4
5
9
1.2 Darstellung binärer Logikfunktionen . . . . . . . . . . . . . . . . . . . . . . . DT 1.2
1.2.1
1.2.2
1.2.3
1.2.4
Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Disjunktive und konjunktive Formen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ringsummendarstellungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BOOLEsche Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
7
8
1.3 Entwurf und Optimierung von Schaltnetzen . . . . . . . . . . . . . . . . . DT 1.3
1.3.1
1.3.2
1.3.3
1.3.4
1.3.5
Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Grafische Verfahren (KARNOUGH-VEITCH-Diagramme) . . . . . . . . . . . . . .
Verfahren von QUINE und MC CLUSKEY (QMC-Verfahren) . . . . . . . . . . .
Struktursynthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Technische Aspekte (Stufigkeit, Laufzeitprobleme, Zellenlogik) . . . . . .
1.4 Spezielle Schaltnetze
Zuordner. Umschlüßler. Multiplexer/Demultiplexer. Rechenschaltungen
2
Digitale Schaltwerke
2.1 Elementare Speicherbausteine
Monoflops. B-Flipflops. A-Flipflops. Z-Flipflops
2.2 Entwurf und Optimierung von synchronen Schaltwerken
Tabellenverfahren. Übertragungsgleichungen. Übergangsgleichungen. Technische Aspekte
2.3 Spezielle Schaltwerke
Register. Zähler und Taktverteiler. Rechenwerke (ALUs)
2.4 Abstrakte Automaten (Zustandsmaschinen, FSM)
MOORE. MEALY. MEDWEDEW
3
Fehler: Erkennung, Behandlung, Vermeidung
1
4
6
13
16
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-1
1
Digitale Schaltnetze
1.1
Elementare binäre Logikfunktionen und -bausteine
1.1.1
1.1.2
1.1.3
1.1.4
Binäre BOOLEsche Algebren und das GALOIS-Feld GF(2)
Binäre Funktionen
Elementare Logikbausteine
Einige technische Details
1.1.1 Binäre BOOLEsche Algebren und das GALOIS-Feld GF(2)
Wir definieren den binären BOOLEschen Raum der endlichen Dimension r:
B
; r =B
; ×B
;r-1
B
; 1 = {0, 1}
oder kürzer unter Benutzung der in [1] definierten Notation:
; ×B
; r - 1).
B
; r := (r=1 : {0, 1} | B
Die r-Tupel a=(ar-1, ...a 1, a 0) mit a i0 B
; , i=0(1)r-1, heißen “Binärvektoren der Länge
r”.
Die algebraische Struktur (B
; , v, w) heißt eine “binäre BOOLEsche Algebra”, wenn für
3
alle (a,b,c) 0 B
; folgende Axiome (BA0), ... (BA5) gelten:
Tabelle 1.1-1: Axiome einer binären BOOLEschen Algebra
(BA0)
avb 0 B
; und awb 0B
;
Abgeschlossenheit
(BA1)
avb = bva und awb = bwa
Kommutativität
(BA2)
av(bvc) = (avb)vc und aw(bwc) = (awb)wc
Assoziativität
(BA3)
av(awb) = a und aw(avb) = a
Absorption
(BA4)
av(bwc) = (avb)w(avc) und
Distributivität
aw(bvc) = (awb)v(awc)
(BA5)
›(¬a 0B
; )(¬(¬(a) = a))
Komplementarität
Die ersten vier Axiome sind die Verbandsaxiome. Eine binäre BOOLEsche Algebra kann
daher als binärer komplementärer distributiver Verband betrachtet werden.
In der Literatur wird eine binäre BOOLEsche Algebra oft auch durch die algebraische
Struktur (B
; , v, w,¬) beschrieben. ¬ wird in diesem Fall als eine einstellige binäre
Funktion interpretiert. (BA5) wird dann zu dem Axiom (BA5'):
(BA5')
av(¬bwb) = a und aw(¬bvb) = a.
Negation
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-2
In der obigen Aufstellung der Axiome erkennt man das Dualitätsprinzip, das wir wie
folgt formulieren:
Dualitätsprinzip
Jeder Satz der Verbandstheorie geht durch Dualisieren wieder in einen Satz der
Verbandstheorie über.
(B
; , v, w, x)
º (B; , w, v, Gx)
“xG” steht für “¬x”
Aus den Axiomen (A1), ... (A5) lassen sich folgende Regeln (R1), ... (R7) ableiten:
Tabelle 1.1-2: Regeln in binären BOOLEschen Algebren
(R1)
ava=a
awa=a
Idempotenz
(R2)
¬(¬a) = a
Involution
(R3)
¬a v a = 0 und a v 0 = 0
Nullelement
(R4)
¬a w a = 1 und a w 1 = 1
Einselement
(R5)
a v 1 = a und a w 0 = a
neutrale Elemente
(R6)
(R7)
(avbv...nvm) w (avbv...n
&vm) = avbv...m und
(awbw...nwm) v (awbw...n
&wm) = awbw...m
¬(a v b) = ¬a w ¬b und
¬(a w b) = ¬a v ¬b
Kürzungsregeln
Theoreme von
DE MORGAN
GALOIS-Felder der Ordnung pn sind endliche Körper (M,r,u) mit pn Elementen aus M,
wobei n0N
; \{0} und p eine Primzahl ist. Ein Körper ist ein nullteilerfreier kommutativer Ring mit Einselement bezüglich der multiplikativen Verknüpfung, dessen vom
Nullelement verschiedene Elemente auch bezüglich der multiplikativen Verknüpfung
; ,r,u,) gelten für alle (a,b,c)
u eine ABELsche Gruppe bilden. Für den binären Körper (B
0 B; 3 die folgenden Axiome (G0), ... (G5). Hieraus lassen sich die Regeln (GR1), ... (GR4)
ableiten.
GALOIS-Felder mit p=2 finden im Bereich der Technischen Datenverarbeitung Anwendung bei der
— Theorie der (zyklischen) Gruppenkodes,
— Behandlung von Schaltfunktionen,
— systematischen Fehlersuche in digitalen Schaltkreisen.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-3
Tabelle 1.1-3: Axiome für GF(2)
(G0)
arb0 B
; und aub0 B
;
Abgeschlossenheit
(G1)
ar(brc) = (arb)rc und au(buc) = (aub)uc
Assoziativität
(G2)
arb = bra und aub = bua
Kommutativität
(G3)
ar0 = a und au1 = a
neutrale Elemente
(G4)
›(sa 0 B
; )(sa r a = 0) und
a=|0 ] ›(a-10 B
; )(aua-1 = 1)
inverse Elemente
(G5)
au(brc) = (aub)r(auc)
Distributivität der u
bezüglich der r
Tabelle 1.1-4: Regeln in GF(2)
(GR1)
au0 = 0
(GR2)
¬arb = ¬(arb)
(GR3)
¬ar¬b = arb
(GR4)
œ x0 B; ((x=0)
| v (aux = bux) Y a = b)
Wir zeigen nun, daß (B
; ,:
|,v) ein GF(2) ist.
Für alle (a,b,c) 0 B
; gelten:
(G0)
a:| b0B
; und avb0B
;
(G1)
a:| (b:| c) = (a:| b):| c und a(bvc) = (avb)vc
(G2)
a:| b = b:| a und avb = bva
(G3)
a:| 0 = a und av1 = a
(G4)
Das bezüglich :
| inverse Element von a=0 ist gleich 0 und von a=1 ist gleich
1; denn 0:| 0 = 0 und 1:| 1 = 0.
Das bezüglich v inverse Element von a=1 ist 1, da 1v1=1 gilt. Der Fall a=0
braucht gemäß (G4) in Tabelle 1.1.1-3 nicht betrachtet zu werden.
(G5)
av(b:| c) = avb :| avc
Hinweis:
Man beachte, daß wir von der Prioritäten-Reihenfolge gemäß DIN 66000
Gebrauch machen.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-4
1.1.2 Binäre Funktionen
2
Es gibt 22 mögliche Zuweisungen von Bitmuster-Paaren zu einem Binärwert. Das
entspricht den Schaltfunktionen
f: B
;2 6 B
;.
Die 16 möglichen Binärfunktionen sind in der folgenden Tabelle 1.1.1-5 zusammengefaßt.
Tabelle 1.1-5: Die 16 möglichen Binärfunktionen zweier Variablen
DÄ a = 0 1 0 1
Verknüpfung
Darstellung in
(B; , v, w)
b=0011
0
avb
b6
|a
b
a6
|b
a
a:
|b
awb
aw
ðb
a:b
¬a
a6b
¬b
b6a
a ðv b
1
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Bezeichnung
a v ¬a
avb
¬a v b
b
a v ¬b
a
(a v ¬b)w(¬a v b)
awb
¬(a w b)
(a w¬b)v(¬a w b)
¬a
¬a w b
¬b
a w ¬b
¬(a v b)
a w ¬a
Nullfunktion
Konjunktion
Inhibition
Identität
Inhibition
Identität
Antivalenz
Disjunktion
PEIRCE-Funktion
Äquivalenz
Negation
Implikation
Negation
Implikation
SHEFFER-Funktion
Einsfunktion
Nach DIN 66000 hat die höchste Priorität (0) die Negation, dann folgen jeweils gleichberechtigt v,w,vð,wð und 6,:,:
|, siehe nachfolgende Tabelle 1.1-6, in der wir auch andere
Schreibweisen aufgeführt haben.
Tabelle 1.1-6: Prioritäten und Schreibweisen von Binäroperatoren
Priorität
DIN 66000
VHDL
0
¬ bzw. G
NOT
1
v
w
ðv
ð
w
AND
OR
NAND
NOR
2
6
:, /
|, /
:
|
XNOR
XOR
sonstige
'
&, •,*
+
|
|
w
e
†,r, |, ~
/ ,w
!,#
Inhibition: d, 6
|
G wird überstreichend, ¬, / und NOT werden präfix, ' (selten auch /) wird postfix, die
übrigen Operatoren werden infix benutzt.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-5
Wir halten uns weitestgehend an die Schreibweise nach DIN 66000 und lehnen insbesondere + für w und • für v strikt ab, da dies Ringoperatoren mit unterschiedlicher
Priorität impliziert, aber keine gleichberechtigten Verbandsoperatoren. Andererseits ist
die DIN-Schreibweise mit den ggf. zahlreichen Klammerpaaren bei größeren Ausdrücken umständlich und wenig übersichtlich, so daß wir folgende Schreibweisen
ebenfalls zulassen, obgleich sie nicht DIN-konform sind:
“a w (b v c)” }~~| “a w bc”
“¬(ab)” }~~| “ ab ”
Auf eine besondere Schreibweise für fortlaufende NAND2- und NOR2-Verknüpfungen, wie sie DIN 66000 vorsieht, sei besonders hingewiesen:
“(...(x0 vð x1) vð ...xn-1)” }~~| “vð(x0, x1,...xn-1)”
“(...(x0 wð x1) wð ...xn-1)” }~~| “wð(x0, x1,...xn-1)”
Es handelt sich also nicht um NAND- bzw.
NOR-Gatter mit n Eingängen, sondern jeweils
um eine Kettenschaltung von n-1 NAND2- bzw.
NOR2-Gattern.
Abb. 1.1-1: Kettenschaltung
Wie aus Tabelle 1.1-5 hervorgeht, läßt sich jede binäre Funktion zweier Variabler in (B
;,
v, w) darstellen. Dieser Sachverhalt gilt auch für Binärfunktionen mit n>2 Variablen, n
endlich.
1.1.3 Elementare kombinatorische Logikbausteine
Wir verstehen unter elementaren kombinatorischen Logikbausteinen solche Logikbausteine, die einfache (elementare) binäre Logikfunktionen realisieren und weder Rückkopplungen noch innere Zustände aufweisen (kombinatorische Logik). Solche Bau;n 6 B
; eine solche Funktion, nennen
steine werden auch als Gatter bezeichnet. Ist fn: B
wir das Gatter ein “fn-Gatter”. Befinden sich in einem Baustein k gleiche f n-Gatter, so
nennen wir einen solchen Baustein einen “kfn-Baustein”.
Technisch lassen sich Gatter auf vielfältige Weise realisieren; Beispiele sind in der
Tabelle 1.1-7 aufgeführt.
Tabelle 1.1-7: Einige technische Realisierungsformen von Logikgattern
Technologie
Logikelement
Binärwert 0
Binärwert 1
Schalter, Relais
Fluidik
RTL, DTL, TTL, ECL
Kontakt
Ventil
Spannung
offen (O)
geschlossen
niedrig (L, low)
leitend (L)
offen
hoch (H, high)
Wir beschränken uns auf TTL-Gatter; zu CMOS-Gattern siehe [15].
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-6
Die Gatter werden in ihrem technischen (physikalischen) Verhalten tabellarisch beschrieben (Funktionstafeln). Dabei spielen die Spannungsbereiche L und H zur Binärwertdefinition eine wichtige Rolle:
Tabelle 1.1-8: Spannungsbereiche, Grenzwerte [9, 13, 14]
Standard-TTL
Eingänge
Ausgänge
Grenzwerte
weitere Daten
(bausteinabhängig)
L-Pegel
H-Pegel
UiL #0,8 V
UiH $2,0 V
UoL #0,4 V
UoH $2,4 V
UiL min = -1,5 V
UiH max = 5,5 V
UB = 5,0 V ± 10%,
tpd = (2...100) ns
Aus den Eingangs- und Ausgangspegeln ist der Störspannungsabstand von StandardTTL-Gattern direkt zu ermitteln:
USL = UiL max - UoL max = 0,4 V,
USH= UoH min - UiH min = 0,4 V.
Es sind zwei Zuordnungen der Spannungsbereiche L und H (wir sprechen zukünftig
von “Pegeln”) zu den binären Logikwerten 0 und 1 möglich:
(a) positive Logik: (L,H)W (0,1)
(b) negative Logik: (H,L)W (0,1)
Wenn nichts anderes vereinbart wird, geht man von positiver Logik aus. Dem Übergang von der einen in die andere Logik entspricht die Anwendung des Theorems von
DE MORGAN. Die Schaltzeichen der digitalen Informationsverarbeitung nach DIN
40700 Tl.12 sehen für den Übergang von positiver zu negativer Logik das Symbol
vor (Polaritätsindikator: Bei Eingängen wird dem H-Pegel der Binärwert 0, dem
L-Pegel der Binärwert 1 zugeordnet, bei Ausgängen dem Binärwert 0 der H-Pegel, dem
Binärwert 1 der L-Pegel); für den Übergang von negativer zu positiver Logik ist das
dazu spiegelbildliche Symbol
vorgesehen.
Beispiele:
(1) Negation
Kontaktplan
Funktionstafel
(2) Konjunktion
npn-Transistor in
Emitterschaltung
Wahrheitstafel
Kontaktplan
Diodenlogik
Funktionstafel
Wahrheitstafel
a
Y
a
Y
a
b
Y
a
b
Y
L
H
H
L
0
1
1
0
L
L
H
H
L
H
L
H
L
L
L
H
0
0
1
1
0
1
0
1
0
0
0
1
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-7
In den technischen Unterlagen zu Logikbausteinen wird nur die physikalische Wirkungsweise und diese in Form der Funktionstafeln beschrieben. Das logische Verhalten kann sich der Anwender daraus selbst ableiten und in Wahrheitstafeln darstellen,
wobei, wie wir weiter oben gesagt haben, positive oder negative Logik zugrundegelegt
werden kann. Wir haben in den Beispielen durchgängig (eingangs- und ausgangsseitig) positive Logik vorausgesetzt (Standard-Fall).
Einige technische Realisierungen von elementaren Standard-TTL-Logikbausteinen mit
Gegentakt-Endstufe (totem pole) bzw. offenem Kollektorausgang (open collector, o.c.)
haben wir in der folgenden Tabelle zusammengestellt.
Tabelle 1.1-9: Einige Standard-TTL-Gatter-Bausteine [9, 14]
Baustein-Struktur
Gegentakt-Endstufe
Endstufe mit offenem Kollektor
6 Inverter
7404
7405, 7406, 7407, 7416, 7417
4 UND2
3 UND3
2 UND2
7408
7411
7421
7409
7415
4 ODER2
7432
4 NAND2
3 NAND3
2 NAND4
NAND8
NAND13
7400, 7437
7410
7420, 7440
7430
74133
7401, 7403, 7426, 7438
7412
7422
4 NOR2
3 NOR3
2 NOR4
2 NOR5
7402, 7428
7427
7425
74260
7433
4 EXOR2
4 EXNOR2
7486
74135
74136
74266
Alle hier aufgeführten Bausteine mit Ausnahme der Bausteine 7486, 74135, 74136 und
74266 sind sogenannte SSI-Bausteine (SSI: small scale integration), zu denen auch
Monoflop- und Flipflop-Bausteine gehören. Die eben genannten vier Ausnahmen
gehören zur MSI-Technologie (MSI: medium scale integration). Die nächst höhere Integrationsstufe heißt LSI (large scale integration), danach kommen VLSI (very large scale
integration) und ULSI (ultra high scale integration).
Eine ebenfalls häufig, wenn auch nicht einzeln, sondern innerhalb eines Logikgatters
realisierte binäre Funktion ist die Inhibition. Sie wird dann als Tor-Funktion (gate)
bezeichnet. Die entsprechenden Signaleingänge haben dann Namen wie /G, /EN,
/STRB (G: gate, EN: enable, STRB: strobe). Für die Tor-Funktion sieht die DIN 40700
die sogenannte Abhängigkeitsnotation vor; wir geben hierfür zwei Beispiele [4].
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-8
Beispiele für die Abhängigkeitsnotation:
]
]
Abbildungen
1.1-2 ... -5: Zur Abhängigkeitsnotation
Tabelle 1.1.1-10: Abhängigkeiten (Auswahl aus DIN 40900 Tl.12)
... -Abhängigkeit
Art
G
V
C
EN
N
M
v
w
Steuerung
Freigabe
Negation
Modus
Wirkung bei
1-Zustand
Freigabe
1-Zustand
Freigabe
Freigabe
Invertierung des Zustands
Freigabe (Modus gewählt)
0-Zustand
Sperren
Freigabe
Sperren
Sperren
Sperren (Modus nicht
gewählt)
Weitere Abhängigkeiten sind A (Adresse), R (Rücksetzen), S (Setzen) und Z (Verbindung).
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-9
1.1.4 Einige technische Details
Wir beschränken uns hier bei der Behandlung einiger technischer Einzelheiten auf die
Standard-TTL-Technologie [3, 4, 7, 8, 9, 13, 14]; CMOS-Bausteine werden in [8, 9,15]
eingehender abgehandelt.
Eingangslast, Ausgangsbelastbarkeit
Beispiel: NAND2-Gatter (7400: 4 NAND2)
Abb.1.1-6:
Gehäuse des SN7400
(Draufsicht)
Abb 1.1-8: Isink
Abb. 1.1-7: 1/4 SN7400
Abb. 1.1-9: Iload
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-10
Tabelle 1.1-11: Eingangslast und Ausgangsbelastbarkeit
Zust.
Bedingungen für das ansteuernde
Gatter (wc: worst case)
max. Eingangslast
max. Ausgangsbelastbarkeit
0
T3 gesperrt und T4 leitend
UOL = 0,4 V
IIL = 1,6 mA
Isink = 16 mA
1
T3 leitend und T4 gesperrt
UOH = 2,4 V
IIH = 40 µA
Iload = -400µA
Eingangslast (Eingangslastfaktor; fan-in) und Ausgangsbelastbarkeit (Ausgangslastfaktor; fan-out) werden normiert. Bei Standard-TTL-Bausteinen bedeutet ein Eingangslastfaktor FLA=1, daß der Eingang des angesteuerten Gatters bei 2,4 V höchstens
40 µA von dem ansteuernden Ausgang aufnimmt und höchstens 1,6 mA bei 0,4 V an
diesen abgibt. Ein Ausgangslastfaktor für ein Standard-TTL-Gatter von z.B. FLA=10
bedeutet, daß der Ausgang des Gatters bis zu 10 Eingänge des Eingangslastfaktors 1
treiben (also bei 2,4 V mindestens 400µA abgeben und bei 0,4 V mindestens 16 mA
aufnehmen) kann. Überschreitungen der Lastfaktoren führen zu Signalpegeln außerhalb der Norm und damit zu ungesicherten Logikpegeln, ggf. auch zur Zerstörung
der Bausteine (insbesondere durch Parallelschalten von Ausgängen außer bei o.c.- und
TS-Bausteinen). In aller Regel gilt für Standard-TTL-Bausteine, daß der fan-in gleich 1
und der fan-out gleich 10 sind, jedoch müssen Einzelheiten anhand der Datenblätter
nachgeprüft werden.
Im Zusammenhang hiermit sei auf folgende Besonderheiten hingewiesen.
1.
Beschaltung unbenutzter Eingänge
konjunktive Verknüpfung: AvB = AvBvBv... = AvBv1v...
disjunktive Verknüpfung: AwB = AwBwBw... = AwBw0w...
Bei der ersten Alternativen wird allerdings der fan-in mit jedem parallel angeschlossenen Eingang entsprechend erhöht. Schließt man dagegen mit dem neutralen Element ab, wirkt sich dies nicht als zusätzliche Eingangslast aus, jedoch wird
dadurch die Verzögerung der Ausgangsflanke erhöht.
2.
Zusammenschaltung von Ausgängen
Außer bei Gattern mit offenem Kollektor (o.c.: open collector) oder mit TristateAusgängen (TS) ist das Zusammenschalten von Ausgängen unzulässig; die Bausteine können dadurch zerstört werden. Denn nehmen wir an, daß ein Ausgang
auf H, der andere auf L liegt. Dann müßte der auf L liegende Ausgang praktisch
den Kurzschlußstrom des auf H liegenden Ausgangs aufnehmen. Damit wächst
das L-Potential des L-Ausgangs auf Werte >0,4 V an, gelangt also in den "verbotenen Bereich", und außerdem steigt die Verlustleistung am leitenden Transistor T4
des L-Ausgangs (Totem-Pole-Schaltung, s. Abb. 1.1.1-7), der Baustein arbeitet nicht
mehr korrekt oder wird (bei mehr als zwei derart zusammengeschalteten Ausgängen) zerstört.
Dagegen erlauben o.c.- und TS-Bausteine die elektrische Verknüpfung von Ausgängen. Damit können Busleitungen realisiert werden (mehrere Ein- und Ausgänge an einer Leitung). Busse werden heute fast ausschließlich mit TS-Bausteinen
realisiert.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-11
Bausteine mit offenenem Kollektor-Ausgang (TTL)
Sie haben zwei Anwendungsbereiche:
(a) Anschluß an eine höhere Spannung
(b) Realisierung einer verdrahteten UND-Funktion (bei anderen Technologien auch
ODER-Funktion)
Der o.c.-Ausgang muß über einen externen Kollektorwiderstand RL an die Versorgungsspannung UB gelegt werden, der für die betreffende Anwendung berechnet
werden muß. Wir geben hier zwei Berechnungsbeispiele (worst case: ungünstigster
Fall).
(a) Anschaltung an U>UB
worst case: RL $ (U - Ue)/Ie
Ue: zulässige Eingangsemitterspannung
Ie : zulässiger Eingangsemitterstrom
(die übrigen Emittereingänge seien
auf Masse gelegt)
Abb. 1.1-10: Pegelwandlung
Weitere Anwendungen: Treiben von LEDs, Lämpchen, Aktoren
(2) Zusammenschalten von o.c.-Ausgängen
worst case:
Abb. 1.1-11:
Verdrahtetes UND
(WAND, wired
AND)
RL $
( UB - UOL ) / ( Isink,max - K×Isink )
RL #
( UB - UOH ) / ( N×IOH - K×Iload )
K:
Anzahl der von Y zu treibenden Gattereingänge
Y=
Y1vY2v...YN
(WAND)
DIN-Symbolik:
 o.c. mit Dominanz des H-Pegels (H-Typ)
 o.c. mit Dominanz des L-Pegels (L-Typ)
Anwendungen: Eindrahtbus-Technik mit N Sendern und K Empfängern (mehrere
Sender können senden); logische Verknüpfung von IRQ - Leitungen
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-12
Tristate-Gatter
Für Bussysteme, bei denen immer nur einer von N Sendern senden kann, wurden die
Tristate-Ausgänge entwickelt (auch "three-state"-Logik). Solche Ausgänge können
außer den Zuständen L und H auch einen sehr hochohmigen Zustand Z (high impedance) einnehmen, gesteuert von einem zusätzlichen Signaleingang. Der Z-Zustand
entspricht dann praktisch einer Abkopplung des Bausteins von der Busleitung.
Abb. 1.1-12: TS-Prinzip
Bus:
Abb. 1.1-13: Zeitdiagramm für TSBus-Signale
System von Leitungen, an denen mehrere Teilnehmer (Sender und Empfänger)
angeschlossen sind. Bei Mikrorechnern unterscheidet man zwischen Adreß-,
Daten- und Steuerbus sowie ggf. weiteren Spezialbussen.
Ein Bus, auf dem alle Leitungen in beiden Richtungen (Sender-Empfänger)
benutzt werden, heißt “bidirektional”. Der Datenbus ist bidirektional
(CPU ÁÀ Speicher, E/A).
Ein Bus, auf dem die Leitungen nur in einer Richtung benutzt werden, heißt
“unidirektional”. Der Adreßbus ist unidirektional (CPU À Speicher, E/A).
Der Steuerbus (Kontrollbus) von Mikrorechnern wird allgemein als bidirektional bezeichnet. Das ist streng genommen nicht korrekt, da (von gelegentlichen Ausnahmen abgesehen) alle Leitungen unidirektional sind, davon einige
Signale nur zur CPU, einige nur von der CPU weg (CPU W Speicher, E/A)
führen. Insofern träfe eine Bezeichnung wie “bi-unidirektional” eher zu.
Realisiert werden Busse fast ausschließlich durch TS-Gatter, in Sonderfällen
auch durch o.c.-Gatter (hierzu gehören die party-line-Systeme).
Schaltzeiten
Im stromlosen Zustand haben die Emitter des Eingangstransistors eine parasitäre
Kapazität von (0,5...1,5) pF. Wird 1-Signal an einen Emitter gelegt, wird daher die
Eingangsflanke abgeflacht, wobei sich eine Zeitkonstante von etwa 4 ns ergibt. Je
unbenutztem Eingang verzögert sich das Ausgangssignal um 1 ns (die Schaltschwelle
liegt bei etwa 1/4 von UB). Diese Verzögerungszeit wird t pLH (Stufenverzögerungszeit,
propagation delay time) benannt. Sie ist u.a. von der Technologie, der Komplexität des
Bausteins und vom fan-out sowie von der Temperatur abhängig. Die sich bei H/LSignalwechsel ergebende Verzögerungszeit heißt tpHL.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.1-13
Tabelle 1.1-11: Stufenverzögerungen
Baustein
SN74...
00
LS00
L00
S00
H00
tpLH/ns
typ.
11
9
35
3
6
max.
22
20
60
4,5
10
tpHL/ns
typ.
max.
7
10
31
3
6
15
20
60
5
10
Abb. 1.1-14: Zur Stufenverzögerung
Stufenverzögerungen werden durch die Boolesche Algebra in keiner Weise erfaßt.
Daher liefert auch eine Schaltung, wie in Bild 1.1-15 gezeigt, am Ausgang unabhängig
vom Eingang und zu jeder Zeit ein Nullsignal. Berücksichtigt man allerdings die
Abb. 1.1-15: Zum statischen Hasard
Abb.1.1-16: Statisches Hasard
Stufenverzögerung und bildet zeitabschnittsweise die Ausgangsfunktion, erhält man einen kurzen Impuls ((statisches) Hasard,
hazard), wie in Bild 1.1.1-16 gezeigt. Falls nicht beabsichtigt, sind solche Impulse
Störimpulse. Andererseits beruhen beispielsweise flankensensitive Gattereingänge
gerade auf solchen Effekten (siehe Flipflops).
Anmerkung: Bei SPS tritt ein solches statisches Hasard (bei korrekter Programmierung) nicht auf, weil
A innerhalb eines Zyklus' berechnet wird. Will man ihn trotzdem simulieren, muß eine externe Verbindung vom Ausgang des letzten Inverters zum Eingang des UND-Gatters gelegt werden (siehe
Praktikums-Versuch DT1-1). Bei ungeschickter Programmierung S nämlich durch Herbeiführung
sogenannter impliziter Speicher S können solche Seiteneffekte auch entstehen.
Literatur
[1]
Torsten Drescher
Rechnerstrukturen I: Notationen (NOT)
FH Köln, Abt. Gummersbach: Scriptum
[2]
Georg Roch, Torsten Drescher, Thomas Uessem, Rudolf Wiebelitz
PLUTO – Eine Klasse von Fachsprachen für mathematisch-wissenschaftliche
Disziplinen. PL/INF: Eine PLUTO-Sprache für die Theoretische Informatik
Universität - Gesamthochschule - Siegen, Abt. Gummersbach: Technischer
Report TR 78-8
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
Lorenz Borucki
Digitaltechnik
B. G. Teubner, Stuttgart
Peter Pernards
Digitaltechnik I
Digitaltechnik II
Hüthig
DT 1.1-14
ISBN 3-519-26415-3
ISBN 3-7785-2155-1
ISBN 3-7785-2278-7
Walter Ameling
Digitalrechner 2
Vieweg
ISBN 3-528-06495-1
Wolfgang Giloi, Hans Liebig
Logischer Entwurf digitaler Systeme
Springer
ISBN 3-540-06067-7
Wilhelm Jutzi
Digitalschaltungen
Springer
ISBN 3-540-59412-4
Ralph Weißel, Franz Schubert
Digitale Schaltungstechnik
Springer
ISBN 3-540-57012-8
Eberhard Kühn
Handbuch TTL- und CMOS-Schaltungen
Hüthig
ISBN 3-7785-2144-6
Dieter Bochmann, Bernd Steinbach
Logikentwurf mit XBoole
Verlag Technik
ISBN 3-341-01006-8
Garret Birkhoff, Thomas C. Bartee
Angewandte Algebra
R. Oldenbourg
ISBN 3-486-34231-2
Uwe Haferstroh
Digitale Schaltwerke
Lexika
ISBN 3-920353-73-0
[13]
(Texas Instruments Deutschland GmbH)
Das TTL-Kochbuch
[14]
(Texas Instruments)
TTL Data Book, Vol. 1
TTL Data Book, Vol. 2
ISBN 3-88078-078-1
ISBN 3-88078-079-X
Don Lancaster
Das CMOS-Kochbuch
IWT
ISBN 3-88322-002-7
[15]
(TM 650/0573)
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-1
1.2. Darstellung binärer Logikfunktionen
1.2.1 Begriffe
Jede binäre BOOLEsche Funktion f:B
; n6B
; ist durch eine Tabelle mit 2n Zeilen (eindeutig)
darstellbar.
Seien i0{0,1,... 2n-1} die Zeilennummer (Index) und (in-1 ... i1i0)2 die Dualdarstellung von
i in der Tabelle von f. Dann heißt
mi: B
; n6B
; mit
mi(x0,x1,... xn-1) :=
wobei
i
xj j '
i
i
i
n&1
1
0
xn&1
v . . . x1 v x0 ,
xj , falls ij ' 1
, der i-te Minterm von f.
xj sonst
Ferner heißt
Mi: B
; n6B
; mit
Mi(x0,x1,... xn-1) :=
wobei
i
xj j '
i
i
i
n&1
1
0
xn&1
w . . . x1 w x0 ,
xj , falls ij ' 0
xj sonst
, der i-te Maxterm von f.
Statt “Minterm” sind auch die Bezeichnungen “Vollkonjunktion” und “vollständiges
Monom”, statt “Maxterm” ist auch die Bezeichnung “Volldisjunktion” gebräuchlich.
In Mintermen und in Maxtermen sind also stets alle Variablen (in negierter oder
nichtnegierter Form) vorhanden. Es gilt offenbar:
Mi ' mi .
Die f beschreibende Tabelle kann also eine der beiden zueinander äquivalenten
Formen haben, die wir in Tabelle 1.2-1 und in Tabelle 1.2-2 allgemein dargestellt haben.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
Tabelle 1.2-1: Mintermtafel
i
xn-1...x1x0
0
0 ... 0 0
1
0 ... 0 1
.
...
.
.
2n-1 1 ... 1 1
DT 1.2-2
Tabelle 1.2-2: Maxtermtafel
mi
f
i
xn-1...x1x0
Mi
f
xn&1 ... x1 x0
xn&1 ... x1 x0
f(0)
f(1)
0
1
.
.
.
2n-1
0 ... 0 0
0 ... 0 1
...
xn&1 w... x1 w x0
xn&1 w... x1 w x0
f(0)
f(1)
1 ... 1 1
xn&1 w... x1 w x0
...
xn&1 ... x1 x0
f(2n-1)
...
f(2n-1)
Wir haben das Argument von f hier mit der Dualdarstellung des zugehörigen Index'
identifiziert.
1.2.2 Disjunktive und konjunktive Formen
Aus der Mintermtafel erkennt man, daß f immer dann gleich 1 ist, wenn einer der
Minterme gleich 1 ist, d.h. es gilt:
f(x0,x1, ... xn-1) =
w ci mi x0 , x1 , . . . xn&1
i
mit ci0B
;.
Die disjunktive Verknüpfung von Monomen heißt auch “Polynom”, die Darstellung
mit Mintermen heißt “disjunktive Normalform” (DNF). (Die vereinzelt zu findende
Formulierung "kanonische disjunktive Normalform" ist ein Hendiadyoin, also Unsinn.)
Ebenso erkennt man aus der Maxtermtafel bei Betrachtung der Maxterme, die gleich 0
sind, folgendes:
f(x0,x1, ... xn-1) =
v ci Mi x0 , x1 , . . . xn&1
i
mit ci0B
;.
Diese Darstellung von f durch disjunktive Verknüpfung der verschwindenden Maxterme heißt konjunktive Normalform (KNF). (Die vereinzelt zu findende Formulierung
"kanonische kojunktive Normalform" ist ein Hendiadyoin, also ebenfalls Unsinn.)
Offenbar gelten:
DNF f ' KNF f
und
KNF f ' DNF f ,
wie es auch aufgrund des Dualitätsprinzips zu erwarten war. Wenn Realisierungsgesichtspunkte dem nicht im Wege stehen, verwendet man diejenige Form, die weniger Terme enthält (im folgenden Beispiel also die KNF).
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-3
Beispiel
i CBA
(DÄ)
0
1
2
3
4
5
6
7
000
001
010
011
100
101
110
111
Mi
f(A,B,C)
DNF(f)
= m0 v m1 v m5 v m6 v m7
= C B A v C B A v C B AvC B Av C B A
KNF(f)
= M2 v M3 v M4
= (C v B v A)(C v B v A)(C v B v A)
CvBvA
CvBvA
CvBvA
1
1
0
0
0
1
1
1
mi
CBA
CBA
CBA
CBA
CBA
KNF(&)
f
KNF f
= M0M1M5M6M7
=
=
=
=
M0 M1 M5 M6 M7
M0 v M1 v M5 v M6 v M7
m0 v m1 v m5 v m6 v m7
DNF(f)
#
Die Bedeutung von DNF und KNF liegt in ihrer Eindeutigkeit, d.h. jede binäre
BOOLEsche Funktion läßt sich auf genau eine Weise durch eine DNF oder durch eine
KNF darstellen. Wir zeigen dies für die DNF einer n-stelligen Funktion f(x0,x1,...xn-1).
Sei I = {0,1,...2n-1}. Seien ferner I* = {i0I | f(i)=1} und g :=
w mi .
i0 I(
Sei nun j0I. Dann kann mj=1 oder m j=0 sein. Ist m j=1, dann ist j0I*, und damit ist
m j Minterm in . Da mj=1, ist auch g=1 und hat denselben Wert wie f.
Ist aber mj=0, dann gilt j 0
| I*, und mj ist kein Bestandteil von g. Somit gilt
w m( i = 0.
óI
Damit ist die Existenz der DNF gezeigt.
Wir zeigen nun deren Eindeutigkeit. Dazu nehmen wir an, es gäbe zwei voneinander verschiedene DNF-Darstellungen für f(x0,x1,...xn-1).
Sei J* = {i0I | f(i)=1} mit J*=|I*. Dann müßten
w mi = w m( i = f gelten. Es gibt aber
i0 I (
i0 J
in I* wenigstens ein Element kóJ* oder es gibt in J* wenigstens ein Element póI*.
Dann gelten für diese Indizes:
w mi k
i 0 I(
= 1 bzw.
w mi p
i 0 I(
=0
= 0 bzw.
w mi p
i0 J(
= 1.
und
w mi k
i0 J(
Das sind aber – im Widerspruch zur gemachten Annahme – unterschiedliche
DNF-Darstellungen von f(x0,x1,...xn-1).
#
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-4
Die DNF einer binären BOOLEschen Funktion stellt bezüglich ihrer Realisierung eine
zweistufige UND-vor-ODER-Lösung dar, die sich zudem noch auf sehr einfache Weise
in eine zweistufige NAND-vor-NAND-Lösung umsetzen läßt (Theorem von DE MORGAN). Nach dem Dualitätsprinzip gilt Entsprechendes für die KNF einer binären
BOOLEschen Funktion (ODER-vor-UND und NOR-vor-NOR):
w mi ' v m( i
i0 I (
i0I
bzw.
v Mi ' w M( i .
i0 I (
i0I
Beispiel:
x = m 0 v m1 v m5 v m6 v m7
= m0 m1 m5 m6 m7
= CvBvA
CvBvA
v
v
CvBvA
v
CvBvA
v
CvBvA
bzw.
x = M 2M 3M 4
= M2 w M3 w M4
= CwBwA
w
CwBwA
w
CwBwA

Aus der DNF läßt sich auch eine Tabellenform ableiten, die nur die Zeilen enthält, für
die f=1 wird, also genau die Indizes aus I*; sie wird auch als Binärvektorliste (BVL)
bezeichnet. Wir machen hiervon selten Gebrauch, werden aber, um Schreibarbeit zu
sparen, die DNF bzw. die BVL auch in der Form “ f ' < i ,(. . . > ”angeben. Im obigen
i0I
Beispiel würden wir “x = <0,1,5,6,7>” schreiben.
Die Verwendung von Indizes legt auch eine Standardisierung der KV-Tafel-Darstellung nahe. Wir verwenden hier die folgende Standardisierung (Index = Exponent
von Zweierpotenz):
x0
x0
1
0
x1
x0
3
2
1
0
x1
3
7
6
2
1
5
4
0
x2
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-5
x4
x0
x1
x0
3
7
6
2
11
15
14
10
9
13
12
8
1
5
4
0
x1
x3
x0
19
23
22
18
3
7
6
2
27
31
30
26
11
15
14
10
25
29
28
24
9
13
12
8
17
21
20
16
1
5
4
0
x2
x2
x3
x2
Abbildungen 1.2-1,...4: Grund-KV-Tafeln; Abbildung 1.2-5: erweiterte KV-Tafel 1)
Ab 5 Variablen sind sog. “erweiterte KV-Tafeln” anzulegen, bei denen Vereinfachungen zusätzlich durch Übereinanderlegen der Grund-KV-Tafeln erkannt werden müssen (bspw. sind <15> und <31> benachbart), was mit zunehmender Variablenzahl
immer schwieriger wird: hier sind algorithmischen Verfahren wie dem von QUINE und
MCCLUSKEY der Vorzug zu geben. Wir verwenden die standardisierten Formen gem.
Abbn. 1.1.2-1...5 als Hilfs-KV-Tafeln und tragen genau dort Einsen ein, wo dies die
DNF bzw. BVL oder eine andere DF erfordern. (Dualitätsprinzip: Es werden genau
dort Nullen eingetragen, wo dies die KNF oder eine andere KF erfordern.)
1
) Eine Alternative, bei der zusammengehörige Bereiche besser zu erkennen sind, sieht
beispielsweise folgendermaßen aus:
Hier können 2n-Blöcke zur
x4
Vereinfachung ähnlich leicht
x0
x0
wie bei den KV-Tafeln für
drei oder vier Variable gefun3
7
6
2
18 22 23 19
den werden, ohne die Teilx1
tafeln gedanklich über- ein11 15 14 10 26 30 31 27
x3
ander legen zu müssen.
9
13 12
8
24 28 29 25
1
5
4
x2
0
16
20
21
Weiterer Übungs-Vorschlag:
Erstellung der standardisierten Hilfs-KV-Tafel für 6 Variable.
17
x2
Beispiel:
x(A,B,C) = <0,1,5,6,7>
A
B
1
1
1
1
1
C
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-6
Disjunktive und konjunktive Formen
disjunktive Form (DF):
konjunktive Form (KF):
Disjunktion einzelner Konjunktionen
Konjunktion einzelner Disjunktionen
DF bzw. KF entstehen aus DNF bzw. KNF, wenn sich diese vereinfachen lassen. Die an
einer DF bzw. KF beteiligten Konjunktionen bzw. Disjunktionen werden auch als
“innere Ausdrücke” bezeichnet; DF und KF selbst sind dann “äußere Ausdrücke”.
Aus der DNF läßt sich auch eine andere Form der tabellarischen Darstellung ableiten,
wenn man nämlich außer 0 und 1 ein weiteres Symbol für solche Fälle einführt, in
denen es gleichgültig ist, ob 0 oder 1 vorliegt (“don't care”). Hierfür haben sich die
Symbole /
0 , * und - eingebürgert; wir bevorzugen “-”. Tabellen dieser Art, in denen
dann nur noch die Indizes aus I* (s. S. 1.2-3) aufgeführt werden, nennen wir verkürzte
Tabellen (auch als “Ternärvektorlisten” (TVL) bezeichnet, was wir für unglücklich
halten, da “-” nicht tatsächlich einen dritten Zustand symbolisiert und sich auf {0,1,-}
auch keine der theoretisch möglichen ternären Logiken entwickeln lassen). Das
Verfahren, von einer Wahrheitstafel zu einer verkürzten Tabelle zu gelangen, wird
auch als Blockbildung bezeichnet.
Beispiel:
f A, B, C ' B C
w
BC
w
ABC
CBA
f(A,B,C)
00-
1
101
1
A&
BC
11-
1
BC
innere Konjunktionen
&&
B
C

Eine verkürzte Darstellung ist natürlich nicht mehr eindeutig; denn im obigen Beispiel
wäre ja auch beispielsweise f(A,B,C) = A B
& v &
B &
C v B C eine zu oben äquivalente
Darstellung und würde zu der folgenden verkürzten Wertetafel führen:
CBA
f(A,B,C)
-01
1
00-
1
&&
B
C
11-
1
BC
innere Konjunktionen
A&
B
Eine weitere dazu äquivalente Darstellung
ist f(A,B,C) = A B
&v&
B&
C v B C v A C. Der
Term AC ist dabei überflüssig (redundant);
redundante Terme werden im Zuge der
Schaltungsoptimierung nach Kostengesichtspunkten eliminiert.
Sei f eine Funktion von n Variablen. Die DF enthält dann k innere Konjunktionen von
ri Variablen, wobei ri#n, i=0(1)k-1. Wir nennen ri den Grad der (i-ten) inneren Konjunktion; er ist identisch mit der Anzahl der für das betreffende UND- oder NANDGatter erforderlichen Eingänge.
Sei nun di = n-ri (diese Differenz kann auch als Anzahl der mit “-” markierten Stellen in
einer Indexblocknotation interpretiert werden). Dann liegt für d=0 ein Minterm vor; er
belegt in der KV-Tafel für n Variable genau ein Feld. Ist d=1, so werden zwei einander
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-7
benachbarte Felder belegt usf., allgemein werden 2d benachbarte Felder belegt. Man
findet sie anhand einer verkürzten Wertetafel, indem man in einer Indexblocknotation
alle “-” sämtliche 0-1-Kombinationen durchlaufen läßt.
Beispiel:
CBA
f(A,B,C)
Indizes
00 -
1
0,1
101
1
5
11 -
1
6,7
A
B
1
1
1
1
1
C
1.2.3 Ringsummendarstellungen
DNF und KNF basieren auf binären BOOLEschen Algebren. Betrachten wir nun die
Struktur (B
; ,:
|,v). Dies ist ein kommutativer binärer BOOLEscher Ring (auch "SCHEGALKIN-Algebra") mit der additiven Verknüpfung :
| und der multiplikativen Verknüpfung
v. Da AvB = A:
| B:| AB, läßt sich jede beliebige binäre BOOLEsche Funktion also auch in
einer Form, die nur diese Ring-Verknüpfungen enthält, darstellen. Man nennt eine
solche Darstellung Ringsummenform (RF) (auch “Antivalenzform”(AF)). Enthält die
RF ausschließlich Minterme, heißt sie Ringsummennormalform (RNF). Enthält sie
keine negierten Variablen (x
& = x|
:1), heißt sie komplementfreie RNF (kRNF). Die RNF
enthält, wie man zeigen kann, genau die Minterme der DNF:
f x0, x1, . . . xn&1 '
:
ci mi , ci0B; .
i0I (
Sie läßt sich - ähnlich wie bei DNF und KNF - durch schrittweise Anwendung des
Entwicklungssatzes
x i f(x0, ...xi-1,0,xi+1, ...xn-1) :| xi f(x0, ...xi-1,1,xx+1, ...xn-1)
f(x0, ...xi-1,xi,xi+1, ...xn-1) = &
oder kürzer
f(x0, ...xn-1) = &
x i v f(x
&i) :| xi v f(xi)
herleiten. Praktischer in der Handhabung ist die erste Fassung.
Beispiel:
f(A,B,C) = C B A v C B A v C B A v C B A v C B A
= C B A :| C B A :| C B A :| C B A :| C B A
(DNF)
(RNF)
= (C:1)(B
|
:1)(A
|
:1)
| :(C
| :1)(B
|
:1)A
|
:C(B
|
:1)A
|
:CB(
|
:1)
| :CBA
|
= 1:A
| :B
| :C
| :AB
| :AC
|
:BC
|
:ABC
|
:A
| :AB
| :AC
|
:ABC
|
:AC
|
:ABC
|
:BC
|
:ABC
|
:ABC
|
...
= 1:B
| :C
| :AC
|
:ABC
|
(kRNF)
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-8
und in ähnlicher Weise:
&vBCvA&
BC
f(A,B,C) = &
BC
= (B:1)(C
|
:1)
| :BC
|
:A(B
|
:1)C
|
...
= 1:B
| :C
| :AC
|
:ABC
|

Bei der zweiten Formel haben wir Gebrauch gemacht von dem
Satz:
Jede DF, die ausschließlich paarweise disjunkte Konjunktionen enthält, läßt sich
unmittelbar in die korrespondierende RF überführen.
Denn es gilt:
a v b v c = a :| b :| ab :| c :| ac :| bc :| abc = a :| b :| c ] ab v ac v bc = 0.
Hinweis: Man sagt auch, die Teilfunktionen ab, ac und bc seien zueinander orthogonal.
1.2.4 Boolesche Differentiation
Aus der Definition des Differentialquotienten
d
f x % ªx & f x
f x ' lim
ªx60
dx
ªx
läßt sich die Definition des BOOLEschen Differentialquotienten ableiten:
d
f(x) = f(x:1)
| :| f(x)
dx
=
f'(x)
f 1 :| f 0 , falls x ' 0 ,
f 0 :| f 1 sonst
= f(1) :| f(0)
= f(1) :| f(0)
Von größerem Interesse ist für uns die Ableitung einer n-stelligen binären BOOLEschen
Funktion nach einer bestimmten Variablen.
Wir definieren:
fx '
i
Mf x0 , . . . xn&1
Mxi
' f x0 , . . . xn&1
/
:| f x0 , . . . xn&1
xi'0
/
xi'1
als die “partielle Ableitung von f(x0,x1, ...xn-1) nach xi”. Das Attribut “partiell” werden
wir uns künftig sparen.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-9
Hinweis. Für bestimmte Fälle müssen wir x und Gx wie zwei getrennte Variablen ansehen und entsprechend f danach differenzieren. Wir sprechen dann von "scharfer" (partieller) Differentiation: f\x bzw.
f\xG, deren Ergebnisse nicht gleich sein müssen. Wir wollen nicht verschweigen, daß diese Form der
Differentiation in der Literatur aber nicht beschrieben ist. Es gelten aber: f\x = (xf)x und f\xG = (x
Gf)x.
Beispiel:
&Cv&
B&
CvBC
= AB
f(A,B,C)
fA = f(A
&) :| f(A)
=&
B&
C v B C :| &
BCv&
B&
CvBC
= (B:C) :| &
BvC
BC
= B :| C :| 1 :| &
B :| C :| &
= B :| C :| 1 :| B :| 1 :| C :| BC :| C
= C :| BC
=&
BC
fB = f(B
&) :| f(B)
= AC v &
C :| C
&v&
AC
= (A v &
C)C
=&
Av&
C
fC = f(C) :| f(C) = &
B :| AB
&vB
= B :| 1 :| A :| B :| AB
= 1 :| A :| AB
=&
AvB

Abschließend wollen wir noch einige Eigenschaften der Ableitungen zusammenstellen.
(1) fx ' fx
Dies ist unmittelbar einsichtig (Kommutativität
der Antivalenz).
(2) fx ' fx
fx = f x |
: fx
= f(x
&) :| 1 :| f(x) :| 1
&) :| f(x)
= f(x
= fx
(3) fx
y
i
' fx
(4) fx = 0,
y
Auch dies ist unmittelbar einsichtig (Assoziativität und Kommutativität der Antivalenz).
falls f nicht von xi abhängt. Insbesondere sind die Ableitungen
von 0 und 1 nach xi gleich 0.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
(5) x0 x1 . . . xi&1 x i xi%1 . . . xn&1
xi
DT 1.2-10
= x0 x1 . . . xi&1 xi%1 . . . xn&1
Die Ableitung eines Monoms nach einer in ihm enthaltenen Variablen entspricht
deren Streichung aus dem Monom.
Auch dieser Satz ist unmittelbar einzusehen.
(6) f
v
g
x
= f gx :| g fx :| fx gx
Produktregel Konjunktion
(7) f
w
g
x
= f gx :| g fx :| fx gx
Produktregel Disjunktion
(8) f :| g
x
= fx :
| gx
gliedweise Differentiation
f :| g
x
=
f :| g |
f :| g |
|
:
= f(&
x ) :| g(&
x ) :| f(x):| g(x)
x'0
= f(&
x)
x'1
:| f(x):| g(&
x ) :| g(x)
= fx :| gx
(9) Sei f(x0, ...xn-1) = f(g(x0, ...xk-1),xk, ...xn-1)
Dann ist
fx = fg
i
gx
v
i
implizite Teilfunktion
für i=0(1)k-1.
Wir zeigen dies unter Benutzung des Entwicklungssatzes für die RNF:
f(x0, ...xi-1,xi,xi+1, ...xn-1) = xi f(x0, ...xi-1,1,xx+1, ...xn-1) :| &
x i f(x0, ...xi-1,0,xi+1, ...xn-1)
= xi fx :| f(xi=0)
f=&
g f(g
&,xk, ...xn-1) :| g f(g,xk, ...xn-1)
= (g:| 1)f(g
&,xk, ...xn-1) :| g f(g,xk, ...xn-1)
= g f(g
&,xk, ...xn-1) :| f(g,xk, ...xn-1) :| f(g
&,xk, ...xn-1)
&,xk, ...xn-1)
= g fg :| f(g
Jetzt ist fx zu bilden, wobei wir wegen (8) gliedweise differenzieren dürfen:
i
fx = g v fg
i
| fx g, x k, . . . xn&1
:
xi
i
Der rechte Term ist gleich Null, da er nicht von xi abhängig ist. Auf den linken
wenden wir die Produktregel an und erhalten:
fx = g v fg
i
= g fg
Da auch
fx = fg
i
fg
v
xi
xi
xi
| gx
:
i
fg :
| gx
i
fg
xi
= 0, weil fg von xi unabhängig ist, erhalten wir schließlich:
gx , w.z.z.w.
i
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-11
Anmerkung
Im Entwicklungssatz lassen sich fx
i
und f(xi=0) weiterentwickeln:
f(x0, ...xi-1,xi,xi+1, ...xn-1) = xi fx :| f(xi=0)
i
= xixi+1 fx x :| xi fx (xi+1=0) :
| xi+1 fx (xi=0) :| f(xi=0,xi+1=0)Setzt man das Verfahi i+1
i
i
ren fort, bis alle Variablen "verbraucht" sind, erhält man eine Darstellung, aus der man
aus dem Vergleich mit der komplementfreien RF
f(x0, ...xn-1)
= a :|
= a0x0 :| a1x1 :| ...an-1xn-1 :|
= a01x0x1 :| a12x1x2 :| ...an-2,n-1xn-2xn-1 :|
...
= a01...n-1x0x1...xn-1
die Koeffizienten der komplementfreien RF durch die Ableitungen von f ermitteln
kann:
a = f(x0=0, ...xn-1=0),
a0 = fx , a1 = fx , ... an-1 fx
0
1
a01 = fx
0
, ... an-1 n-2 = fx
x1
n-2
n-1
xn-1
,
,
...
a01 ...n-1 = fx
0
x1 . . . xn - 1
Anwendungen der booleschen Differentiation
Zwei der wichtigsten Anwendungen sind:
— Erstellen von Testvektoren für Digitalschaltungen,
— formale Untersuchungen an Schaltwerken (Entwicklung im TDI-Labor).
Wir gehen in den entsprechenden Kapiteln näher auf diese Anwendungen ein.
Hinweis
Der Kalkül der BOOLEschen Differentiation [3] erlaubt es nicht, nach einer Ableitung
nach x und einer solchen nach &
x zu unterscheiden, vielmehr ist ja nach Regel (1)
. Man kann natürlich für einen Augenblick &
x = x' setzen und nach x' differenziex ' f
ren und die Ersetzung danach wieder rückgängig machen. Dann gilt fx ' fx nicht
mehr allgemein. Diese Art der Differenzierung hatten wir in einem Hinweis weiter
oben als "scharfe" (partielle) Differentiation f\x = (xf)x bzw. f\xG = (xGf)x bezeichnet.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.2-12
Literatur
[1]
[2]
[3]
[4]
Dieter Bochmann
Einführung in die strukturelle Automatentheorie
Carl Hanser
ISBN 3-446-11981-7
Dieter Bochmann, Bernd Steinbach
Logikentwurf mit XBOOLE
Verlag Technik
ISBN 3-341-01006-8
Walter Oberschelp, Gottfried Vossen
Rechneraufbau und Rechnerstrukturen
R. Oldenbourg
ISBN 3-486-22167-1
Garret Birkhoff, Thomas C. Bartee
Angewandte Algebra
R. Oldenbourg
ISBN 3-486-34231-2
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
1.3
DT 1.3-1
Entwurf und Optimierung von Schaltnetzen
1.
2.
3.
4.
5.
Einführung
Grafische Verfahren (KARNOUGH-VEITCH-Diagramme)
Verfahren von QUINE und MC CLUSKEY (QMC-Verfahren)
Struktursynthese
Technische Aspekte (Stufigkeit, Laufzeitprobleme, Zellenlogik)
1.3.1 Einführung
Wir gehen davon aus, daß eine Tabelle Grundlage für den Entwurfsprozeß einer
Logikschaltung ist. Diese Tabelle entsteht als Endprodukt eines Analyseprozesses, auf
den wir hier nicht eingehen. Bei Schaltwerken beschreibt diese Tabelle, die wir Funktionstabelle nennen wollen (es ist auch die Bezeichnung Wahrheitstabelle üblich), den
Zusammenhang zwischen n Eingangsvariablen en und k Ausgangsvariablen qk, wobei
die Ausgangsvariablen bei Schaltnetzen – wir betrachten derzeit nur diese – von den
Eingangsvariablen und nur von den Eingangsvariablen abhängen, d.h. es gelten:
qi = fi(ej) mit i=0(1)k-1 und j=0(1)n-1.
Hierfür ist auch eine Matrixschreibweise üblich:
q = f(e).
e nennt man den Eingangsvektor, q nennt man den Ausgangsvektor. Durch Eintragen
der möglichen Bitmuster (Belegungen) für e entsteht eine Eingabematrix, der eine
entsprechende Ausgabematrix gegenüber steht. In dieser sind möglicherweise zu
gewissen Eingangsmustern keine Ausgangsmuster angegeben oder nicht definierbar.
In diesen Fällen liegen don't-care-Situationen vor, die Zustände sind redundant. Sie
können für die Schaltungsvereinfachung oder zur Erkennung von Fehlersituationen
herangezogen werden.
Im Zuge der Optimierung von Schaltungen werden Verfahren zur Schaltungsvereinfachung angewandt. So wollen wir “Optimierung” vereinfachend auch verstehen,
obwohl dabei u.a. auch noch Aspekte einer günstigen Bausteinauswahl, der Vermeidung von Laufzeiteffekten usw. einbezogen werden können.
Mögliche Minimierungsverfahren sind:
– formale Minimierung
– grafische Verfahren (hier: Verfahren von KARNOUGH und VEITCH)
– tabellarisch-algorithmische Verfahren (hier: Verfahren von QUINE und MCCLUSKEY)
Zur quantitativen Beurteilung einer optimierten Schaltfunktion ist eine Kostenfunktion vorgeschlagen worden, die wir hier vorstellen wollen. Zuvor sollen noch einige
Begriffe eingeführt werden, denen man im Zusammenhang mit der Schaltungssynthese und -optimierung häufig begegnet.
Begriffe
Wir setzen für die folgenden Betrachtungen wieder eine binäre BOOLEsche Algebra (B
;,
v, w) voraus. Obwohl die Axiomatik dieser algebraischen Struktur eine vollständige
Gleichwertigkeit der beiden Verbandsoperatoren und damit auch der beiden kano-
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-2
nischen Formen DNF und KNF ausweist, wird der DNF in der Literatur (und Praxis)
eine gewisse Vorrangstellung eingeräumt (dem wir uns durch die früher getroffene
Konvention, Klammern zu sparen, wenn wir das Konjunktionssymbol schreiben, ja
auch partiell angeschlossen haben). Dieser Vorgehensweise schließen wir uns aus
Gründen der Einfachheit im Folgenden an.
Sei B eine Menge von Variablen, die genau die Werte aus B
; annehmen; wir nennen sie
BOOLEsche Variable (dabei lassen wir "binär" weg, da wir nur binäre BOOLEsche
Algebren betrachten). Gilt cardB=n, so schreiben wir auch Bn.
Wir definieren die Begriffe (binärer) BOOLEscher Ausdruck und dessen Stufigkeit.
Technische Aspekte dieser Definitionen werden in Abschnitt DT1.2-5 behandelt.
Ein Element x 0 BcB
; heißt ein "(binärer) BOOLEscher Ausdruck erster Stufe".
Die Ausdrücke (x1 v... xn) und (x1 w... xn) mit xi 0 Bn , 1#i#n, heißen "(binäre)
BOOLEsche Ausdrücke kter Stufe", wenn gilt:
(œ(xi)(xi ist ein binärer BOOLEcher Ausdruck höchstens (k-1)ter Stufe)) v (›(xi)(xi ist
ein binärer BOOLEscher Ausdruck (k-1)ter Stufe)).
Der Ausdruck xG heißt ein "(binärer) BOOLEscher Ausdruck kter Stufe", wenn x ein (binärer)
BOOLEscher Ausdruck kter Stufe ist.
Für die Menge BOOLEscher Ausdrücke über B schreiben wir auch B(B).
Als zwei weitere wichtige Begriffe definieren wir Monom und Polynom.
Seien
(i1, ...in)0B
; n und (a1, ...an)0Bn.
Dann heißt ein BOOLEscher Ausdruck a0B(B) ein (binäres BOOLEsches) Monom
über B, wenn gilt:
i
i
(a = a1 1, . . . an n ) w (a 0B
; ).
n ist die Länge des Monoms. Ein Monom a0Bk heißt vollständig, wenn seine
Länge gleich k ist.
Ein BOOLEscher Ausdruck p0B(B) heißt ein (binäres BOOLEsches) Polynom über
B, wenn gilt:
(p = m1 v ... mn) v œ(1#j#n)(mj ist ein Monom über B).
n ist die Länge des Polynoms. Ein um mehrfach vorkommende Monome
bereinigtes Polynom heißt vollständig, wenn es nur aus vollständigen Monomen
besteht oder gleich 0 ist.
Anmerkung
An sich müßten die Bezeichnungen "Monom" und "Polynom" nach ihren Operatoren differenziert
werden. Da wir uns weiter oben auf die – zugegebenermaßen einseitige – Bevorzugung der DF geeinigt
haben, sehen wir von einer solchen Differenzierung hier ab.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-3
Die Minimierungsverfahren von Schaltfunktionen beruhen in den einfacheren Fällen
auf der konsequenten Anwendung von Absorptionsaxiom und der daraus ableitbaren
Kürzungsregel. Bei der Kürzungsregel werden zwei vollständige Monome gekürzt,
wenn sie sich nur in einer Variablen derart unterscheiden, daß diese Variable in dem
einen Monom direkt, im andern negiert vorkommt. Das neu entstandene Monom kann
ggf. mit einem weiteren Monom derselben Länge gekürzt werden, wenn dieses dieselben Variablen enthält und die Voraussetzungen der Kürzungsregeln erfüllt.
Beispiele
(1) abcd v abcGd v G
abd = abd v G
abd = bd
G bcGd v Gabd = abcd v Gabd = bcd v Gabd
(2) abcd v a
Bei (1) konnte zweimal die Kürzungsregel angewandt werden, bei (2) war das nicht
möglich; hier konnte allerdings zweimal das Absorptionsaxiom zur Vereinfachung
genutzt werden.
O
Der bei einer solchen Vereinfachung entstandene neue Term "überdeckt" die vereinfachten Terme. Für unsere beiden Beispiele gelten daher u.a.:
Gabd 6 bd, abcd 6 bd und Gabcd 6 Gabd,
wie man leicht nachprüft. Hieraus leitet sich auch die Bezeichnung Primimplikant
(Primterm) ab für ein Monom minimaler Länge. Im Beispiel (2) ist beispielsweise bcd
ein Primterm; denn er ist nicht weiter verkürzbar und überdeckt die ganze Funktion,
d.h. es gilt abcd v a
G bcGd v Gabd 6 bcd, wie einfach nachzuprüfen ist.
Verschmelzung zweier Monome
Haben zwei Monome mj und mk folgende Form:
mj = xium und mk = xi'wm
; 2, i'=&i , und u bzw. w enthalten nur Variable, die nicht in m und nicht
mit (i,i')0B
in w bzw. u enthalten sind,
dann lassen sie sich zu dem Monom
m' = ж(mj,mk) = uwm
verschmelzen. Hierfür gilt:
m' 6 mj v mk,
das heißt, die Disjunktion der beiden Monome überdeckt die Verschmelzung der
beiden Monome.
Beispiel: ж(ab
&c, bcd
&e) = acd
&e; dagegen können ab
&c und &
a bcd
&e nicht verschmolzen werden, da sich die beiden Monome in a und b unterscheiden!
BIRKHOFF und BARTEE haben ein Verfahren angegeben [5], wie man formal durch
Verschmelzung von Monomen die vollständige Menge der Primimplikanten einer
Funktion ermitteln kann, das wir hier kurz vorstellen.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-4
BIRKHOFF und BARTEE haben gezeigt [5], daß für ein Polynom P, das zwei Monome m und m' enthält, P v ж(m,m') = P gilt. Dabei wird von der Eigenschaft
ж(m,m')6m v m' Gebrauch gemacht.
&v&
ad
Beispiel: f(a,b,c,d) = abc v acd
Das erste und das letzte Monom lassen
sich zu bcd verschmelzen; das ist ein
weiterer Primimplikant von f, und es
gelten, wie man sich leicht anhand einer einfachen Rechnung klarmacht, in
der Tat
ж(abc,a
&d) 6 abc v &
a d und
a
b
1
1
1
1
1
1
d
1
c
&d) = f.
f v ж(abc,a
ж(abc,a
&d) = bcd
Aus diesen Eigenschaften der Verschmelzung von Monomen eines Polynoms P
leiten die oben genannten Autoren folgendes (hier geeignet modifizierte) Verfahren zur Ermittlung der vollständigen Menge der Primterme von P ab.
(1) Überdeckt ein Monom ein anderes, so ist das andere zu streichen (entspricht dem Absorptionsaxiom).
(2) Lassen sich zwei Monome verschmelzen, ist das entstehende Monom
disjunktiv zum Polynom hinzuzufügen, falls es nicht bereits von einem
anderen Monom des Polynoms überdeckt wird.
Beispiel:
f = abc&
dw&
a b&
c d w bcd w &
a&
bd
= f w ж(a b c &
d , b c d ) w ж(&
a b&
c d , b c d ) w ж(&
a b&
c d ,&
a&
b d ) w ж(b c d , &
a&
b d)
dw&
a b&
c d w bcd w &
a&
b d w abc w &
a bd w &
a&
cd w &
a cd
= abc&
= bcd
w
&
a&
bd
w
abc
w
&
a bd
w
&
a&
cd
w
&
a cd
Genau dieselben sechs Primterme liefert auch das QUINEsche Termvergleichsverfahren (siehe weiter unten), wie man sich leicht überzeugen kann.

Der Sonderfall u=1 und w=1 führt zur Verschmelzung zweier Minterme, die sich in
genau einer Variablen unterscheiden. In diesem Fall gelten zusätzlich
m' 6 mj und m' 6 mk,
was einer Vereinfachung gleichkommt. Hierauf beruht das (Term-Vergleichs-)Verfahren von QUINE. Auch der Fall entweder u=1 oder w=1 führt zu einer Vereinfachung, so
daß beispielsweise (im ersten Fall)
x wm
ж(xm, &
x wm) = wm mit wm6&
gilt.
Beispiele
(1)
f = ab v &
b c v ac
Da ж(ab,b
&c)=ac gilt, ist ac ein redundanter Term, mithin ist f=ab v &
b c.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
(2)
DT 1.3-5
f= &
a&
b c v bc
Hier liefert ж(&
a&
b c,bc)=a
&cd einen in f redundanten Term.
Kostenfunktion
Die Kosten für eine Digitalschaltung hängen ab von
— der Anzahl der Gatter
— der Anzahl der Schaltstufen
— der Anzahl der Eingänge
— der Anzahl der Negationen
— der Anzahl der verwendeten Gattertypen
— dem Fan-in und dem Fan-out
— der verwendete Technologie
Für eine gegebene Technologie werden die Kosten hinreichend beschrieben, wenn man
sich auf die Zahl der Eingänge beschränkt.
Eine einfache Kostenfunktion für eine Schaltfunktion läßt sich folgendermaßen rekursiv angeben:
n
n
i'1
i'1
k(x1 v ... xn) = j k(x i) % n und k(x1 w... xn) = j k(x i) % n ,
k(x) = 0, k(0) = 0, k(1) = 0,
k(¬xi) = k(xi).
Demnach werden die Gattereingänge je Stufe bestimmt und anschließend addiert.
Negationen kosten nichts (was i.a. nicht ganz realistisch ist; aber häufig – beispielsweise bei Flipflops oder bei Treiberausgängen – liegen die Signale sowohl in negierter
als auch in direkter Form vor).
Diese einfache Kostenfunktion kann auf Schaltungen angewandt werden, die UND-,
ODER-, NICHT-, NAND- und NOR-Gatter enthalten. Für andere Gatter, beispielsweise Antivalenzgatter (a:| b ist im Sinne der oben gegebenen Definition kein binärer
BOOLEscher Ausdruck!), müßten ggf. andere Kostenfaktoren eingeführt werden.
Eine besondere Situation ergibt sich, wenn mehrere Schaltfunktionen derselben Eingangsvariablen bzw. Teilmengen hiervon optimiert werden sollen. Man spricht dann
von einem Funktionsbündel. Hier kann man die Kostenfunktion minimieren, indem
man möglichst viele gemeinsame Teilfunktionen bildet. Ein Algorithmus auf dieser
Basis wurde von BARTEE angegeben.
Auf die einfache formale Vorgehensweise, die Kürzungsregeln konsequent anzuwenden, gehen wir nicht näher ein; sie war Bestandteil der Lehrveranstaltung Theoretische
Informatik. Es sei nur angemerkt, daß dieses Verfahren Intuition und Erfahrung
erfordert, um sicher zum Ziel zu führen. Darum wurden grafische und tabellarische
Verfahren entwickelt, die schneller und sicherer zu einer optimierten Lösung führen.
Auf etwas komplexere formelmäßige Verfahren werden wir im Abschnitt "Strukturanalyse" noch zurückkommen.
1.3.2 Grafische Verfahren (KARNOUGH-VEITCH-Diagramme)
BOOLEsche Ausdrücke über Bn mit n#6 lassen sich noch recht gut mit KV-Tafeln
vereinfachen; das haben Sie bereits in der Lehrveranstaltung Theoretische Informatik
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-6
gelernt. Wir wollen uns hier nur noch einmal klar werden, was die Grundlagen dieses
Verfahrens sind. Wir tun dies auf der Basis der DNF, wohl wissend, daß durch Dualisieren natürlich auch ein Verfahren zur Auswertung der KNF angegeben werden
kann.
Die zu betrachtende Schaltfunktion sei y = f(x), wobei x die Dimension n habe. Liegen
l<n nicht definierte Belegungen von x vor, so lassen diese sich in einer Teilfunktion
(x) darstellen. Damit können wir y* = f(x) v (x) ansetzen, wobei natürlich die
Implikation y 6 y* gilt. Über diese l redundanten, durch (x) repräsentierten Terme
kann bedarfsweise bei der Vereinfachung verfügt werden.
Die KV-Tafel ist so konstruiert, daß direkt benachbarte Felder zwei vollständige
Monome repräsentieren, die der Kürzungsregel R(6) (s. DT 1.1) genügen. Faßt man sie
also zusammen, entsteht ein um eine Variable gekürztes Monom. Faßt man vier direkt
benachbarte Felder, lassen sich vier Monome um zwei Variablen kürzen usf., allgemein
lassen sich 2k direkt benachbarte Felder um k Variablen kürzen. Die (x) zugehörigen
Terme sind genau dann in den Zusammenfassungsprozeß einzubeziehen, wenn sie zur
Vereinfachung beitragen.
Sie haben gelernt, y* in eine KARNOUGH-VEITCH-Tafel (KV-Tafel) einzutragen, die
damit y* in der Form der DNF repräsentiert, und zwar in der Weise, daß das vollständige Polynom y über Bn alle zugehörigen Felder mit 1 belegt und das vollständige
Polynom (x) die entsprechenden Felder mit X belegt. Die auf diese Weise vereinfachte Schaltfunktion yE ist, wenn wir das Verfahren richtig durchgeführt haben, d.h.
insbesondere nicht neue Redundanzen geschafft haben, die gesuchte Minimallösung.
Beispiele
(1) Ein Problem werde durch eine Wahrheitstafel der folgenden Art beschrieben.
DÄ
D
C
B
A
Y
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
—
—
—
0
1
0
0
0
0
1
0
1
1
Hilfs-KV-Tafel:
A
B
3
7
6
2
11
15
14
10
9
13
12
8
1
5
4
0
D
C
Y: <7,12,14,15>; : <3,4,5>
A
V
B
1
1
1
1
V
V
C
D
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-7
Man erkennt sofort, daß es nur eine optimale Lösung gibt, bei der man noch nicht
einmal Gebrauch von redundanten Termen machen mußte. Diese Lösung lautet
Y
E = ABC v &
ACD.
Auch Y' = ABC v BCD v &
A CD wäre eine richtige vereinfachte Lösung, aber nicht
die optimale. Durch formelmäßige Umformungen sofort zum ErgebnisY
E = ABC v
&CD zu kommen, ist ziemlich unwahrscheinlich.
A
(2) Daß es auch mehr als genau eine optimale Lösung gibt, zeigt das folgende Beispiel, bei dem wir nur die KV-Tafel wiedergeben.
Mögliche Lösungen sind:
a
b
1
1
1
1
1
c
Bild 1.3-1: Funktion mit zwei optimalen
Vereinfachungsmöglichkeiten
ac
G v Gac v ab und acG v Gac v bc.
Alle Monome sind hier Primterme. In
beiden Lösungsfällen sind die Terme
acG und a
G c beteiligt. Sie werden auch
als Hauptterme (auch “Kernprimterme”) bezeichnet.
O
Als weiteres grafische Verfahren sei hier noch der Einsatz des HÄNDLER-Kreisgraphen
genannt. Es ist wie das KV-Tafelverfahren auf wenige Variablen beschränkt.
1.3.3 Methode von QUINE und MC CLUSKEY (QMC-Verfahren)
Auf der Basis der Schaltungsvereinfachung mithilfe von KV-Tafeln beruht ein tabellarisches Verfahren, das QUINE angegeben hat. Es liefert i.a. vereinfachte, aber nicht immer
optimal vereinfachte Lösungen. Eine Verbesserung in dieser Richtung wurde von
MCCLUSKEY entwickelt. Beide Verfahren können nacheinander angewandt werden;
diese Vorgehensweise wird als “QMC-Verfahren” bezeichnet. Weitere Verbesserungen
sind von BARTEE entwickelt worden. Gegenüber den grafischen Verfahren ist die
Anzahl der Variablen nicht beschränkt; der Algorithmus läßt sich programmieren.
Das QMC-Verfahren setzt ebenfalls auf der DNF auf; wir verweisen in diesem Zusammenhang auf die einleitenden Sätze zum Abschnitt Begriffe in DT 1.2.1. Selbstverständlich läßt sich auch ein gleichartiger Algorithmus auf der Basis der KNF angeben,
doch das ist, von ganz seltenen Ausnahmen abgesehen, nicht üblich.
1. Definitionen
Ordnung eines Terms:
Anzahl der Variablen, um die ein Min- bzw. Maxterm
durch Zusammenfassung verkürzt wurde
(Anmerkung: Ein Min- bzw. Maxterm hat demnach die
Ordnung Null)
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
Länge eines Terms:
Primterm/Primimplikant:
Gewicht eines Terms:
Gewicht einer Bitkette:
Länge einer BOOLEschen
Funktion:
Minimalfunktion:
DT 1.3-8
Anzahl der in ihm enthaltenen Variablen
Term, der sich durch Zusammenfassen mit Termen gleicher Ordnung nicht weiter verkürzen läßt
Anzahl der in ihm enthaltenen nicht-negierten Variablen
Anzahl der in ihr enthaltenen Einsen
Summe der Längen ihrer 2n möglichen Terme
(n=Anzahl der Eingangsvariablen)
fmin(e0, ...en-1) heißt Minimalfunktion zu f(e0, ...en-1), wenn es
keine zu ihr äquivalente Funktion f'(e0, ...en-1) gibt, für die
len f' < len fmin gilt
Anmerkung: Es kann also (wegen "<") auch mehr als eine
Minimalfunktion zu einer DNF von f geben!
2. Das QUINEsche Verfahren
Ausgehend von der DNF der binären BOOLEschen Funktion f(A,B, ...X, ...N), werden
systematisch alle Terme gleicher Ordnung miteinander verglichen und ggf. gekürzt,
bis nur noch Primimplikanten übrig bleiben. Deren disjunktive Verknüpfung bildet
eine i.a. vereinfachte Darstellung von f, die aber nicht immer eine Minimalform darstellen wird. Minimalformen von f findet man erst durch das anschließende Verfahren
von MCCLUSKEY.
Verfahren von QUINE
(1) DNF bilden.
(2) Terme gleicher Ordnung n in Gruppen gleichen Gewichts anordnen.
(3) jeden Term des Gewichts i mit jedem Term des Gewichts i+1 vergleichen; die an
der Verkürzung beteiligten Terme abhaken und Verkürzungen in neue Spalte
schreiben (n-te Vereinfachung ergibt Terme n-ter Ordnung).
(4) solange neue Spalte nicht leer, gehe zu (3), sonst Ende des Verfahrens.
Wir gehen die Schritte anhand eines Beispiels durch.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-9
Bsp.: Q = <1,2,3,5,7,10,11,13>
(1) DNF bilden
Dies erfolgt am einfachsten über die Wahrheitstafel der binären Funktion.
DÄ
DNF
DCBA
Q
0
0000
0
1
0001
1
2
0010
1
3
0011
1
4
0100
0
5
0101
1
6
0110
0
7
0111
1
8
1000
0
9
1001
0
10
1010
1
11
1011
1
12
1100
1
13
1101
1
14
1110
0
15
1111
0
Minterme
Bitmuster
DCBA
Gr
0001
1
D
&C
&BA
0010
1
0011
2
D
&C&
BA
0100
2
D
&CBA
0111
3
DC
&BA
&
1010
2
1011
3
1100
2
1101
3
&C
&&
BA
D
D
&C
&BA
&
DC
&BA
DC&
BA
&
DC&
BA
Praktischer Hinweis: Statt der Minterme notieren wir die sie repräsentierenden Dualzahlen (in der Tabelle als “Bitmuster” bezeichnet).
(2) Terme ordnen
Wegen der in (3) anzuwendenden Kürzungsregel
A B ... X ... N v A B ... X
& ... N = A B ... N
lassen sich nur solche Terme miteinander kombinieren, die sich in genau einer Variablen derart unterscheiden, daß diese Variable (in der Regel oben ist das X) in dem
einen Term negiert und im anderen Term direkt vorkommt. Daher ist es für eine
systematische Vorgehensweise sinnvoll, solche Gruppen zu bilden, die jeweils genau
die Terme enthalten, die mit denen der Vorgängergruppe kombinierbar sein können.
So werden die Gruppen nach der Anzahl der in ihnen enthaltenen direkten Variablen
gebildet.
Das gibt folgende Gruppierungen:
Gruppe 0:
Gruppe 1:
...
Gruppe N-1:
A
&&
B&
C... &
N
A&
B&
C... &
N, &
AB&
C... &
N, ... &
A&
B&
C...N
A B C... N
Die Terme innerhalb der i -ten Gruppe (0<i<N) unterscheiden sich in mindestens 2
Variablen, sind also zwecks Kürzens nicht miteinander kombinierbar.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-10
Für das Beispiel wurde die Gruppenzugehörigkeit bereits in der Wahrheitstafel angegeben. Die Gruppenordnung ist für die Bitmuster-Darstellung besonders leicht anzugeben; denn die Gruppennummer ist identisch mit dem Gewicht (=Anzahl der
Einsen) des betreffenden Bitmusters.
(3) Termvergleich und Primimplikanten
Bezeichnen wir die Spalte mit den Mintermen für den Augenblick als die 0-te Vereinfachung, dann ergibt sich die 1. Vereinfachung dadurch, daß jeder Term der Gruppe i
mit jedem Term der Gruppe i +1 verglichen und ggf. gekürzt wird. Können zwei
Terme gekürzt werden, wird das Kürzungsergebnis in die Spalte der 1. Vereinfachung
unter der Gruppe i eingetragen und beide Terme als vereinfacht abgehakt. Aus Gründen der besseren Übersichtlichkeit für das weitere Verfahren tragen wir beim Kürzungsergebnis an der Stelle der weggelassenen Variablen ein Platzhaltersymbol ein,
beispielsweise einen “—”, “*” o.ä.
Auf diese Weise entsteht die 1. Vereinfachung. Die weiteren Vereinfachungen erhält
man dadurch, daß der Termvergleich mit den verkürzten Termen fortgesetzt wird. Am
Vergleich können wegen der Kürzungsregel natürlich nur die Terme beteiligt sein, die
an denselben Stellen das Platzhaltersymbol aufweisen; das vereinfacht das weitere
Vorgehen.
Das Verfahren endet, wenn die nächste Vereinfachungsspalte leer ist, also keine
Vereinfachungen mehr möglich sind.
P
Im Laufe des Verfahrens treten schließlich Terme auf, die sich nicht mehr vereinfachen
lassen, möglicherweise auch Minterme selbst. Solche Terme heißen Primimplikanten
(Primterme). Beim QUINEschen Verfahren bildet ihre disjunktive Verknüpfung eine i.a.
einfachere Form als die DNF, jedoch (wie in unserem Beispiel der Fall) nicht unbedingt
eine minimale Form.
Wir gehen nun auf einige Details ein und beziehen uns auf das oben angegebene
Beispiel.
1. Teil-Beispiel
Der Minterm m1 aus Gruppe 1 wird verglichen mit allen Mintermen der Gruppe 2 und
liefert die im folgenden Tabellenausschnitt dargestellten Ergebnisse. Dabei wurde
dieser Term in der Hilfsspalte “i.V.” als “im Vergleich befindlich” abgehakt, ferner
wurden auch die vereinfachten Terme in der Hilfsspalte “k” abgehakt. Solche Hilfsspalten sollte man der besseren Kontrolle wegen in jeder weiteren Vereinfachungsspalte ebenfalls mitführen.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
Gr
1
2
Minterme
1. Vereinfachung
DNF
i.V.
k
D
&C
&&
BA
&C
&BA
&
D
T
T
&C
&BA
D
&
BA
DC&
&BA
&
DC
DC&
BA
&
DT 1.3-11
DC
&
&-A
&
BA
D-&
T
T
2. Teil-Beispiel
Der dritte Term Gr.1 der 1. Vereinfachung der folgenden nunmehr vollständigen
Tabelle, D C B , wird mit allen “passenden” Termen (das sind die mit dem Platzhaltersymbol an der Position der Variablen A
&) verglichen, also nur mit D C B und D CB . Als
Ergebnis erhält man D B , wobei D C B mit abgehakt werden kann. Dagegen kann D CB
nicht weiter vereinfacht werden, ist also Primimplikant.
Anmerkung: Dieser Vorgehensweise entspricht die Bildung einer Unter-KV-Tafel, hier
für die Variablen B,C und D.
Gr.
1
2
3
Minterme
D
&C
&&
B A TT
&C
D
&BA
& TT
D
&C
&BA
D
&C&
BA
DC
&BA
&
DC&
BA
&
D
&CBA
DC
&BA
DC&
BA
TT
TT
TT
TT
T
T
T
1. Vereinf.
DC
&
&-A
&-&
D
BA
&C
D
&B-C
&BA
&
D-BA
&
-C
&BA
&C-A
D
-C&
BA
&BDC
DC&
B-
TT
TT
TT
TT
2. Vereinf.
D--A
&
&
D--A
-&
C B&B-C
PI
p3
p4
T
T
T
p1
T
f(A,B,C,D) = p1 w p2 w p3 w p4
= AB
&C w &
B CD w AD
& w BC
&
p2
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-12
Kurzdarstellung:
Gr
Minterme
1. Vereinf.
2. Vereinf.
PI
1
0 0 0 1 TT
0 0 1 0 TT
00-1
0-01
001-010
TT
TT
TT
TT
0--1
-01-
p3
0-11
-011
01-1
-101
101110-
T
T
T
2
3
0011
0101
1010
1100
0111
1011
1101
TT
TT
TT
TT
p4
p1
T
p2
T
T
T
3. Das Verfahren von MCCLUSKEY
Das QUINEsche Verfahren liefert zwar eine i.a. vereinfachte Form, jedoch nicht immer
eine Minimalform. Das wird an unserm Beispiel deutlich, wenn wir die KV-Tafel
zeichnen. Dort zeigt sich nämlich, daß der Term AB
&C überflüssig (redundant) ist, weil
die beteiligten Minterme AB
&CD und AB
&CD
& bereits durch die Primimplikanten AD
&
und &
B CD erfaßt ("überdeckt") werden, was allerdings der algebraischen Form
f(A,B,C,D) nicht anzusehen ist.
Hier führt das Verfahren von MCCLUSKEY weiter. Dort werden die Überdeckungen der
die DNF bildenden Minterme durch die mit dem Verfahren von QUINE gefundenen
Primimplikanten p1,...pk tabellarisch erfaßt und dann eine Überdeckungsfunktion
U(p1,...pk) gebildet, die angibt, welche Primimplikanten (PI) notwendig oder möglich
sind. Solche Alternativen werden durch ODER verknüpft, notwendige Terme durch
UND. U wird nach den Regeln der binären booleschen Algebra vollständig aufgelöst.
Die einfachste(n) Konjunktion(en) stellt bzw. stellen die Minimalform(en), die DMF,
dar.
Für unser Beispiel sieht dies folgendermaßen aus:
DNF \ PI
p1= -CB
&A
p2= DCB
&-
&C
&&
BA
D
&C
&BA
&
D
&C
D
&BA
&
BA
DC&
&BA
&
DC
DC&
BA
&
&CBA
D
&BA
DC
DC&
BA
p3= D
&--A
½
V
V
V
p4= -C
&B½
V
V
V
V
ja
ja
V
V
½
HT
o
ja
o
o
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-13
Terme, die nur einmal in einer Zeile auftreten, sind für die DMF zwingend notwendig;
sie heißen "Hauptterme" (HT). Wir haben sie in der Tabelle durch ½ kenntlich gemacht, und zwar nur einmal je Spalte. Genauso lassen wir sie bei mehrfachem Auftreten in U fort (Idempotenz-Gesetz), siehe zweite Zeile im Folgenden.
U = p3(p3 w p4)(p3 w p4)(p1 w p3)p4p4p2(p1 w p2)
vollständige Form
= p2p3p4(p3 w p4)(p3 w p4)(p1 w p3)(p1 w p2)
= p2p3p4 (p1 w p3)(p1 w p2)
p3,p4 bereits vorhanden
= p2p3p4(p1 w p2p3)
= p1p2p3p4 w p2p3p4
Umin = p2p3p4
Zur Bildung der DMF genügen also die Primimplikanten p2 ,p3 und p4, so daß jetzt gilt:
f(A,B,C,D) = &
BCD w AD
& w BC
&
in Übereinstimmung mit der KV-Tafel.
Die etwas umständlichen formelmäßigen Vereinfachungen der Überdeckungsfunktion
lassen sich auch in gewissem Rahmen bereits in der Überdeckungstafel direkt durchführen, indem die folgenden beiden Regeln beachtet werden:
(1) alle Zeilen löschen, die durch einen HT überdeckt werden (im Beispiel überdeckt
p3 den 1., 3., 4. und 5. Minterm; die betreffenden Zeilen sind also zu löschen);
(2) den HT zur DMF notieren und die zugehörige Spalte löschen.
Auf diese Weise kann eine einfachere Überdeckungstabelle entstehen, aus der eine
vereinfachte Überdeckungsfunktion abgelesen werden kann. Es gibt weitere Regeln,
um die Überdeckungstafel zu vereinfachen, doch wollen wir hier nicht weiter darauf
eingehen.
Zu erwähnen ist auch, daß beispielsweise BARTEE ein Verfahren angegeben hat, das auf
dem QMC-Verfahren aufsetzt und die Vereinfachung von Funktionsbündeln (mehrere
Funktionen auf derselben Menge von Eingangsvariablen oder einer Teilmenge davon)
erlaubt. Dabei werden sogenannte “Koppelterme gesucht. Das sind solche (möglichst
weitgehend vereinfachten) Terme, die von mehr als einer Funktion gemeinsam genutzt
werden.
Es ist anzumerken, daß das QMC-Verfahren erst bei einer Vielzahl von unabhängigen
Variablen an Wert gewinnt; denn natürlich ist sein Aufwand bei <5 überhaupt nicht
gerechtfertigt, weil hier die KV-Tafel wesentlich schneller zum Ziel führt. Seine gute
Eignung für rechnergestützte Synthesetechniken dürfte angesichts der logischen
Vorgehensweise, wie das Verfahren praktiziert, unmittelbar einleuchten.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-14
Abschließend soll noch einmal das inzwischen vertraute Beispiel zusammenhängend
in der verkürzten (und damit etwas abstrakten) Form vollständig dargestellt werden.
Der Aufbau der Tabelle(n) erfolgte hier nach ergonomischen Gesichtspunkten, die
leicht nachvollziehbar sein dürften.
Gr
DNF
1. V.
2. V.
1
0 0 0 1
0 0 - 1
0 - - 1
0 0 1 0
0 - 0 1
- 0 1 -
-101
110-
0--1
-01-
q
q
0 0 1 - 0 1 0
2
0 0 1 1
0 - 1 1
0 1 0 1
- 0 1 1
1 0 1 0
0 1 - 1
1 1 0 0
- 1 0 1
V
V
V
V
V
q
1 0 1 1 1 0 3
0 1 1 1
V
1 0 1 1
1 1 0 1
V
V
V
4. Umfangreichere Beispiele
(1) Eine binäre BOOLEsche Funktion f(A,B,C,D,E) sei durch die folgende DNF beschrieben:
f(A,B,C,D,E) = <0,3,10,12,13,14,16,19,24,27,28,30,31>.
Suchen Sie die DMF. (Es gibt in diesem Fall mehr als eine DMF!)
(2) Zu realisieren seien drei binäre BOOLEsche Funktionen X, Y und Z, die von den
Variablen A, B, C und D in folgender Weise abhängen:
X = <7,8,10,14,15>,
Y = <1,3,10,14,15>,
Z = <1,4,10,12,14,15>.
Ermitteln Sie zunächst getrennt für X, Y und Z die DMFs. Versuchen Sie dann, X,
Y und Z in der Weise optimal zu realisieren, daß Sie gemeinsam nutzbare Teilfunktionen (Koppelterme) herausfinden und verarbeiten.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-15
1.3.4 Struktursynthese
Die bisher beschriebenen Verfahren zur Schaltungsoptimierung setzen eine BOOLEsche
Algebra voraus; sie sind daher zunächst einmal für PALs, PLAs und GALs geeignet.
Sie berücksichtigen aber in keiner Weise die beschränkten Möglichkeiten realer Gatter,
was auch bei PALs und GALs zu Problemen führen kann. Zwar kann aus einer DF
leicht eine zweistufige Schaltung in NAND-vor-NAND-Technik und aus einer KF
leicht eine solche in NOR-vor-NOR-Technik durch Anwendung des DE-MORGANschen
Theorems gewonnen werden; weitere strukturelle Gesichtspunkte bleiben aber, wie
gesagt, unberücksichtigt. Zu diesen gehören die Berücksichtigung der Anzahl der
Eingänge oder das Vorhandensein spezieller Gatter bzw. vorgefertigter Strukturen.
Hier kann die Struktursynthese Abhilfe schaffen. Eine allgemeingültige Lösung gibt es
allerdings nicht. Wir wollen exemplarisch zwei Vorgehensweisen der Struktursynthese
hier vorstellen. Die eine ist geeignet, gemeinsame Monome, sogenannte Koppelterme,
zu nutzen, die andere benutzt eine vorgefertigte Struktur (PAL, GAL, FPLA, FPGA).
Die Zerlegung einer Funktion in Teilfunktionen, wobei gewisse Randbedingungen
berücksichtigt werden, nennt man Dekomposition, auch Faktorisierung. Man unterscheidet zwischen zergliedernder Faktorisierung und aufbauender Faktorisierung.
Beide Verfahren setzen auf bereits nach bestimmten Kriterien vereinfachten BOOLEschen Ausdrücken auf, die als DF oder als KF vorliegen (wir beschränken uns wieder
auf den Fall der DF) und verlangen letztendlich wieder ein gewisses Maß an Erfahrung
oder an Intuition, soll möglichst effizient ein Ergebnis erreicht werden. Das erstgenannte Verfahren ist etwas einfacher zu handhaben und soll hier vorgestellt werden. Als
zweites Verfahren stellen wir exemplarisch die Faktorisierung nach vorgegebenen
Strukturen vor.
1 Zergliedernde Faktorisierung
Sei f(x) ein BOOLEscher Ausdruck über Bn. Man sucht nun Terme (x), die in möglichst
vielen Monomen von f(x) vorkommen, und klammert sie aus. Dabei entsteht
f(x) = ( 1(x) v f1(x)) w ...( k(x) v fk(x)) w ρ1(x)
Auf die Teilfunktion f'(x)=( 1(x) v f 1(x)) w ...( k(x) v f k(x)) kann das Verfahren ggf.
weiter angewendet werden, wobei dann wieder Terme fi'(x) und Reste ρi'(x) entstehen,
usf.
Außer formelmäßig, wie wir dies im folgenden vorführen, kann man die Faktorisierung auch mithilfe von KV-Tafeln durchführen; hierauf gehen wir nicht näher ein.
Beispiel
Es liege der beispielsweise nach dem QMC-Verfahren ermittelte BOOLEsche
Ausdruck
y = abc
G v ac
Gd v Gabc v Gacd v bc
Gd
vor. Seine Kostenfunktion liefert den Wert 20.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-16
Wir klammern 1(x)=acG und 2(x)=a
G c aus und erhalten
G v Gac)(b v d) v bcGd
y = (ac
Der Rest ρ(x)=bcGd ist nicht weiter faktorisierbar.
Wir haben so eine dreistufige Lösung erhalten, deren Kostenfunktion durch die
Mehrfachnutzung der Koppelterme den Wert 15 liefert. Im Gegensatz zur ursprünglichen Form (es würde ein ODER5 benötigt!) ist sie auch technisch z.B. mit
handelsüblichen TTL-Gattern der 74er-Serie realisierbar.
O
Das Dekompositionsverfahren kann überhaupt genutzt werden, um von oft technisch
nicht realisierbaren zweistufigen zu höherstufigen, dafür aber technisch realisierbaren
Lösungen zu gelangen.
Beispiel
Gegeben sei eine KF (ein konjunktives Polynom)
y = ( bv c)( av b v c)(a v b v d)
Wir faktorisieren das zweite und dritte disjunktive Monom und erhalten
y = ( bv c)(b v ( av c)(a v d))
Hierdurch ist ein vierstufiger BOOLEscher Ausdruck entstanden, dessen Teilausdrücke höchstens die Länge 2 haben, d.h. die zur seiner Realisierung verwendbaren Gatter müssen nur zwei Eingänge haben. Die Kostenfunktion wächst dabei
von ursprünglich 11 auf 12.
Durch mehrfache Anwendung des Theorems von DE MORGAN gelangt man von
einer zweistufigen ODER-vor-UND-Struktur zu einer vierstufigen NORvor_NOR-Struktur, deren Kostenfunktion natürlich immer noch 12 liefert:
y =( bvc) v(b v(( av c) v(a vd)))
O
2 Faktorisierung nach vorgegebenen Strukturen
Daß sich UND-vor-ODER-Strukturen für die Faktorisierung eignen (sowie NAND-vorNAND-Strukturen und natürlich auch die zu beiden dualen Strukturen), haben wir im
vorhergehenden Unterabschnitt gesehen. Wir wollen an einem Beispiel zeigen, daß
dies auch bei komplexeren Strukturen möglich sein kann. Als Beispiel wählen wir die
Multiplexerstruktur, konkreter die des 4-auf-1-MUX. Dessen Ausgang Y ergibt sich mit
den Steuervariblen S0 und S1 und den Eingangsvariablen x0, x1, x2 und x3 zu
Y = x0 S1 S0 v x1 S1 S0 v x2 S1 S0 v x3 S1 S0
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-17
Damit läßt sich jede Schaltfunktion aus B2 realisieren; denn wir haben hier die Struktur
der DNF über B2 vor uns, wenn wir {S1,S0} mit B2 identifizieren. Die xi sind die Koeffizienten ci in der früher (DT1.2) angegebenen DNF
f(x0,x1, ... xn-1) =
w ci mi x0 , x1 , . . . xn&1
mit ci0B
;.
i
Beispiel
Es soll die Funktion A :| B mit einem 4-auf-1-Multiplexer realisiert werden.
Lösung
Die Steuereingänge des Multiplexers werden mit (S1S0) := (B,A) belegt und die
vier Eingänge (x3, x2, x1, x0) mit (0, 1, 1, 0), so daß sich aufgrund der Funktionsgleichung des 4:1-Mux die geforderte Funktion ergibt.
O
Für Schaltfunktionen mit n>2 wählt man höhere Multiplexer aus oder schaltet Multiplexer hintereinander. Dabei empfiehlt es sich, einem etwas anderen Ansatz zu folgen,
wie wir dies am folgenden Beispiel vorführen.
Beispiel
Die Funktion
y = f(a,b,c,d) = ab v b(c : d)
soll mit 2:1-Multiplexern realisiert werden. Wir wollen den Lösungsweg andeuten.
Die Übertragungsfunktion eines 2:1-Mux mit dem Steuereingang S, den beiden
Eingängen (I1,I0) sowie dem Ausgang Y lautet:
Y = SI1 v &
S I0
Entwickeln wir andererseits allgemein y = f(a,b,c,d) nach dem Entwicklungssatz
nach a, so erhalten wir:
f(a,b,c,d) = af(1,b,c,d) v &
a f(0,b,c,d)
Nun können wir a mit S identifizieren, und die
beiden Restfunktion bezüglich der Entwicklung
nach a, die wir im Augenblick mit f(a) bzw. f(&)
a
bezeichnen wollen, wobei f(a) = f(1,b,c,d) und
f(&)
a =(0,b,c,d) ist, identifizieren wir mit I1. bzw.
mit I0. f(a) wird dann nach der nächsten Variablen entwickelt usf.
Bild 1.3-2: Beschaltung des
letzten 2:1-Mux
für das Beispiel
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-18
Bei unserm konkreten Beispiel empfiehlt es sich, y umzuformen und nach b zu
entwickeln:
y = ab v b(c : d) = b(a v (c : d))
= by(b) v &
b0
mit y(b) = a v (c : d), das an den Eingang I1 des letzten der insgesamt drei erforderlichen 2:1-Mux gelegt wird, ferner 0 an I0 und b an S. Nun entwickeln wir
I 1 weiter beispielsweise nach a, wobei dann zwei Restfunktionen entstehen, usw.
Die so entstandene Lösung ist sicherlich nicht eben einfach oder kostengünstig,
aber hier sollte gezeigt werden, wie sich das Dekompositionsverfahren auf eine
komplexere Struktur anwenden läßt.
O
Auch Majoritätsgatter (mit negierendem Ausgang) lassen sich zur Realisierung von
Schaltfunktionen einsetzen; denn mit ihnen läßt sich eine BOOLEe Algebra realisieren,
wie wir zeigen wollen. Dazu betrachten wir als einfaches Gatter
Y = maj(A,B,C) = ABw ACw BC
Man sieht sofort, daß
A v B = maj(A,B,C=0) und
A w B = maj(A,B,C= 1)
gelten, d.h. daß die beiden Verbandsoperationen mit
einem Majoritätsgatter realisiert werden können. Somit
sind auch alle anderen Binärfunktionen mit Majoritätsgattern (mit negierendem Ausgang bzw. unter Hinzunahme von Invertern) realisierbar. Systematische Verfahren, binäre Funktionen mittels Schwellwertfunktionen, von denen die Majoritätsgatter eine Unterklasse
darstellen, herzuleiten, sind derzeit offenbar nicht bekannt.
Bild 1.3-3:
3
-Majoritätsgatter
2
1.3.5 Technische Aspekte
Der vorhergehende Abschnitt führte uns bereits an den Bereich technischer Aspekte
der Schaltungsentwicklung. Wir wollen jetzt näher darauf eingehen, wobei nicht mehr
als eine kurze Einführung gegeben werden kann.
1. Stufigkeit und Laufzeitprobleme
Die “klassischen” Entwurfs- und Optimierungsverfahren liefern durchgängig zweistufige UND-vor-ODER-Lösungen. Diese haben zwei Vorteile:
—
durchgängig gleiche Laufzeiten in jedem Signalpfad, daher so gut wie keine
Laufzeitprobleme (race-Probleme) mit daraus resultierenden statischen und
dynamischen Hasards (hazards) oder Signalverlängerungen,
—
leichte Anpaßbarkeit an die Strukturen von PLAs, oft auch von PALs.
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-19
Durch das Gegenteil der Absorption, nämlich durch Expansion, läßt sich ein Signalgleichlauf erzwingen:
x) und T = T w (x v G
x),
T = T v (x w G
d.h. ein BOOLEscher Ausdruck T kann konjunktiv bzw. disjunktiv um eine weitere
Variable x erweitert werden. Eine weitere Möglichkeit besteht in der umgekehrten
Anwendung Gesetze der Absorption oder der Distributivität. Im folgenden Bild wird
ein sehr einfaches Beispiel hierfür vorgestellt.
Bild 1.3-4: Vermeidung von Hasards durch durch Anwendung des Distributivitätsaxioms
Bei der Schaltung im linken Bildteil entsteht durch die Laufzeitverzögerung des UNDGatters (Ausgang r) eine Verlängerung des Signals y dann, wenn a und gleichzeitig bc
von 0 auf 1 gehen. Ein Hasard an y entsteht dann, wenn a von 1 auf 0 und gleichzeitig
bc von 0 auf 1 gehen. Unter der Voraussetzung, daß die Laufzeitdifferenzen zwischen
den beiden UND-Gattern im rechten Bildteil verschwinden, treten bei dieser die
genannten Probleme nicht auf.
2. Hasards
Es wird zwischen statischen und dynamischen Hasards sowie zwischen Funktionenund Strukturhasards unterschieden. Ein Funktionenhasard entsteht durch unterschiedliche Verzögerungen beim “gleichzeitigen” Pegelwechsel mindestens zweier
Eingangssignale; solche Pegelwechsel werden wir bei den Schaltwerken als KSW
(kritische Signalwechsel) wiedertreffen.
Beispiel für ein Funktionenhasard
Sei y = ab v &
a c. Ändert sich beispielsweise die Eingangsbelegung (a,b,c) von
(0,1,1) nach (1,0,0), so können u.a. diese
einschrittigen (und damit realen) Signalkombinationen entstehen:
(0,1,1) (1,1,1) (1,1,0) (1,0,0),
(0,1,1) (0,0,1) (1,0,1) (1,0,0),
(0,1,1) (0,1,0) (1,1,0) (1,0,0).
Bei den ersten beiden Signalfolgen geht y
von 1 auf 0 (zu unterschiedlichen Zeitpunkten), ohne daß ein Hasard überhaupt
Bild 1.3-5: Ein dynamisches
Funktions-1-Hasard
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-20
entstehen kann; dagegen kann ein Hasard bei der letzten Signalfolge mit (1,1,0)
entstehen. Es handelt sich übrigens dabei um ein dynamisches Funktionshasard,
wie weiter unten erläutert werden wird. Man kann dies übrigens sehr schön
anhand einer KV-Tafel nachvollziehen, siehe das hierzu gezeigte Bild.
O
Die durch mehrschrittige Eingangssignaländerungen entstehenden Hasards werden
auch als glitches bezeichnet.
Wie wir weiter oben bereits angedeutet haben, können Signalverfälschungen und auch
Hasards durch eine ungünstige Schaltungsstruktur entstehen; die so auftretenden
Hasards heißen daher Strukturhasards. Sie lassen sich durch geeignete Strukturänderungen vermeiden; einige Möglichkeiten wurden oben genannt.
Die Unterscheidung zwischen statischen und dynamischen Hasards ist folgende. Ein
statisches Hasard kann entstehen, wenn sich das zu erwartende Ausgangssignal bei
einer (mehrschrittigen) Eingangssignaländerung nicht ändern dürfte. Ändert sich das
zu erwartende Ausgangssignal bei einer (mehrschrittigen) Eingangssignaländerung,
dann kann ein dynamisches Hasard entstehen.
Beispiel
Wir wählen dieselbe Situation wie im vorhergehenden Beispiel. Doch soll nun ein
Übergang von (a,b,c)=(1,1,0) nach (0,0,1) betrachtet werden. Vor der Änderung
der Eingangsbelegung ist y=1, danach auch. Es sind u.a. folgende einschrittigen
(und damit realistischen) Signalfolgen möglich:
(1,1,0)ö(1,1,1)ö(0,1,1)ö(0,0,1),
(1,1,0)ö(1,1,1)ö(1,0,1)ö(0,0,1),
(1,1,0)ö(1,0,0)ö(1,0,1)ö(0,0,1).
Die erste Folge ist unkritisch, bei den beiden
anderen können statische 1-Hasards (unterschiedlicher Länge) auftreten.
O
Bild 1.3-6: Statische Funktions1-Hasards
Laufzeitprobleme werden durch die Schaltalgebra
nicht beschrieben und damit auch nicht erfaßt. Gute
(und teure!) Entwicklungswerkzeuge erlauben es, solche Fehler in Simulationsläufen
zu erkennen.
3. Zellenlogik
Siehe hierzu das Skript ZL zur Vorlesung DT II).
FH Köln, Campus Gummersbach, Prof. T. Drescher: Digitaltechnik I
DT 1.3-21
Literatur
[1]
[2]
[3]
Uwe Haferstroh
Digitale Schaltwerke
Lexika
ISBN 3-920353-73-0
Günter Hotz
Schaltkreistheorie
De Gruyter
ISBN 3-11-002050-5
S. L. Hurst
Schwellwertlogik
UTB/Hüthig
ISBN 3-7785-0293-X
[4]
Helmut Groh, Wolfgang Weber
Digitaltechnik I
VDI-Verlag, Düsseldorf 1969
[5]
Garret Birkhoff, Thomas C. Bartee
Angewandte Algebra
R. Oldenbourg
ISBN 3-486-34231-2

Weitere Themen:
1.4
Spezielle Schaltnetze
Zuordner. Umschlüßler. Multiplexer/Demultiplexer. Rechenschaltungen
2
Digitale Schaltwerke (siehe Skript "Aspekte Zeitverhalten" zu DT II)
2.1
Elementare Speicherbausteine
Monoflops. B-Flipflops. A-Flipflops. Z-Flipflops
2.2
Entwurf und Optimierung von synchronen Schaltwerken
Tabellenverfahren. Übertragungsgleichungen. Übergangsgleichungen. Technische
Aspekte
2.3
Spezielle Schaltwerke
Register. Zähler und Taktverteiler. Rechenwerke (ALUs)
2.4
Abstrakte Automaten (Zustandsmaschinen, FSM)
MOORE. MEALY. MEDWEDEW (siehe auch Skript AUT zur Vorlesung RS II)
3
Fehler: Erkennung, Behandlung, Vermeidung
(Skript FESN)
Document
Kategorie
Seele and Geist
Seitenansichten
9
Dateigröße
547 KB
Tags
1/--Seiten
melden