Upload
others
View
18
Download
0
Embed Size (px)
Citation preview
Grundlagen der Digitaltechnik
Grundlagen der Informatik 2Grundlagen der Informatik 2Grundlagen der DigitaltechnikGrundlagen der Digitaltechnik
2. Digitale Schaltfunktionen 2. Digitale Schaltfunktionen und Normalformtheorieund Normalformtheorie
Prof. Dr.Prof. Dr.--Ing. Jürgen TeichIng. Jürgen TeichDr.Dr.--Ing. Christian Ing. Christian HaubeltHaubelt
Lehrstuhl für HardwareLehrstuhl für Hardware--SoftwareSoftware--CoCo--DesignDesign
Technische Informatik I 2
Von der Funktion zur SchaltungVon der Funktion zur Schaltung
FunktionellerZusammenhang
f
. . . y
x1x2
xn
Wichtige Fragen: Wie beschreibt man logische Schaltungen?Wie analysiert man logische Schaltungen?Wie realisiert und optimiert man logische Schaltungen?
Technische Informatik I 3
Von der Funktion zur SchaltungVon der Funktion zur Schaltung
FunktionellerZusammenhang
f. . . y
x1x2
xn
? DigitaleSchaltung. .
. y
x1x2
xn
• Antwort: – Beschreibung der Schaltung durch eine Schaltfunktion
f: (x1,x2,…,xn) −> y– Implementierung der Schaltfunktion durch logische Gatter
Technische Informatik I 4
Von der Funktion zur SchaltungVon der Funktion zur Schaltung
• Beispiel: Addierer für zwei Binärzahlen S=A+Bmit S=(s4, s3, s2, s1, s0), A=(a3, a2, a1, a0) und B=(b3, b2, b1, b0)
s0s1s2s3s4
0c0c1c2c3+b0b1b2b3
a0a1a2a3
B
FunktionalerZusammenhang
f
AS
VAa0b0
0
c0
s0c0
VAa1b1
s1c1
s0
0
b0
a0
VAa2b2
s2c2
s1
c1+b1
a1
VAa3b3
s3c3 s4
Technische Informatik I 5
Von der Funktion zur SchaltungVon der Funktion zur Schaltung
• Beispiel: Addition zweier Binärzahlen S = A+BAufbau einer Volladdiererzelle (VA)
VAaibi
ci-1 si
ci
1 11 1 1
0 11 1 0
0 11 0 1
1 01 0 0
0 10 1 1
1 00 1 0
1 00 0 1
0 00 0 0si cici-1 ai bi
Beschreibung des funktionalen Zusammenhangs der Voll-addiererzelle durch eine Funktionstabelle
Technische Informatik I 7
Von der Funktion zur SchaltungVon der Funktion zur Schaltung
• Beispiel: Addition zweier Binärzahlen S = A+BAufbau einer Volladdiererzelle
1 11 1 1
0 11 1 0
0 11 0 1
1 01 0 0
0 10 1 1
1 00 1 0
1 00 0 1
0 00 0 0si cici-1 ai bi
ai
bi
ci-1si
ci
Technische Informatik I 8
FragenFragen
• Gibt es eine Systematik zur Abbildung von Funktionstabellen auf logische Schaltungen (kanonische Formen)?
• Wieviele Gatter besitzt die kleinste Schaltung, die diese Funktion realisiert (Logikminimierung)?
• Welche elementaren Gatter(funktionen) gibt es?• Ist es immer möglich, die kleinste Schaltung zu finden?
Technische Informatik I 9
AntwortenAntworten
• Schaltalgebra:– Spezielle Interpretation der Booleschen Algebra– Basis für die formale Entwicklung binärer Digitalschaltungen
• Schaltfunktion:– 2n Zuordnungen xj → fj (xj Belegung, fj zugeordneter
Funktionswert)– Begriffe:
Nullstellenmenge N, Einsstellenmenge E, Redundanzmenge R
Technische Informatik I 14
FunktionsbegriffFunktionsbegriff
– Definition einer Schaltfunktion (s ist das Argument, t der Funktionswert):
Angabe aller Paare (s, t) mit s ∈ { 0, 1 }n (= Belegung) und t ∈ { 0, 1 }
FunktionellerZusammenhang
f
. . . y
x1x2
xn
X = (xn, ... , x2, x1 )
xi ∈ { 0, 1 }
y ∈ { 0, 1 }
Technische Informatik I 16
FunktionsdefinitionFunktionsdefinition
Abbildungsvorschrift: Funktionsdarstellung:
(a3 a2 a1) f
→ y
(0, 0, 0) → 0 (0, 0, 1) → 1 (0, 1, 0) → 1 (0, 1, 1) → 0 (1, 0, 0) → 1 (1, 0, 1) → 0 (1, 1, 0) → 0 (1, 1, 1) → 1
j0 a3 a2 a1 y 0 0 0 0 0 1 0 0 1 1 2 0 1 0 1 3 0 1 1 0 4 1 0 0 1 5 1 0 1 0 6 1 1 0 0 7 1 1 1 1
Technische Informatik I 17
Klassen von SchaltfunktionenKlassen von Schaltfunktionen
• häufig gilt: nicht allen Belegungen kann/muss ein Funktionswert zugeordnet werden– solche Zuordnungen: -> Redundanz- oder Freistellen der
Funktion-> Kennzeichnung: xj → - (sogenanntes don´t care)-> Stelle kann wahlweise mit 1 oder 0 belegt werden
• Also: 3 Teilmengen von Belegungen:- Nullstellenmenge N = { xj | xj → 0 }- Einsstellenmenge E = { xj | xj → 1 }- Redundanzmenge R = { xj | xj → - }
• Beispiel: Funktion mit Freistellen-> Funktion für BCD Zahlen, wobei Eingangskombinationen,
die Pseudotetraden entsprechen, mit Freistellen belegt werden
Technische Informatik I 18
Klassen von SchaltfunktionenKlassen von Schaltfunktionen
-111117
-011116
-101115
-001114
-110113
-010112
Pseudotetraden
11001119
00001108
0111077
1011066
0101055
0001044
1110033
0010022
0100011
0000000
ya0a1a2a3j0Ziffer
Technische Informatik I 19
Klassen von SchaltfunktionenKlassen von Schaltfunktionen
• Reale technische Anwendungen
- Freistellen überwiegen häufig gegenüber 0- / 1-Stellen- Man definiert daher zwei Hauptklassen von Funktionen:
- eine vollständig definierte Schaltfunktionordnet allen Belegungen xj einen Funktionswertaus fj ∈ { 0, 1 } zu
- eine unvollständig definierte Schaltfunktionordnet mindestens einer Belegung xj keinenFunktionswert aus fj ∈ { 0, 1 } zu
- Wegen |{0, 1}n| = 2n gilt:Bei unvollständigen Schaltfunktionen lässt sich aus jeweils zwei Teilmengen die fehlende dritte Teilmenge bestimmen
Technische Informatik I 20
Graphische Darstellung von FunktionenGraphische Darstellung von Funktionen
• Neben tabellarischer Darstellung: es existieren graphisch orientierte Darstellungen
– Tafelmethoden (sogenannte KV-Diagramme)vor über 100 Jahren von Karnaugh und Veitch vorgeschlagen
– Nachteile von KV-Diagrammen bei Werten n > 4 (unübersichtliche Darstellung!)
Technische Informatik I 21
Graphische Darstellung von FunktionenGraphische Darstellung von Funktionen
• Beispiel: Darstellung der Schaltfunktion y = f(a3,a2,a1,a0) (durch 3 teilbare BCD-Zahl) mittels Symmetriediagramm
--10
----
1010
0000
14151110
16171312
6732
4510
a3
a2
a1
a0
y
Technische Informatik I 22
SymmetriediagrammeSymmetriediagrammeEntwicklung einesSymmetriediagramms•0
V1
n=0 n=1
n=2 n=3
n=4 n=5
n=6
122 −+= altneu jj
•3•2
•1•0
H1
x1
H1x2
•1•0
x1
V1
112 −+= altneu jj
•6•7•3•2
•4•5•1•0
V2
x1
x2
x3
V2
132 −+= altneu jj
•14•15•11•10
•16•17•13•12
•6•7•3•2
•4•5•1•0
H2
x1
x2
x3
H2x4142 −+= altneu jj •30•31•35•34•14•15•11•10
•32•33•37•36•16•17•13•12
•22•23•27•26•6•7•3•2
•20•21•25•24•4•5•1•0
V3
x2
x1 x1
x4
x5
x3
V3
152 −+= altneu jj
•60•40
•77
•70•50
•30•31•35•34•14•15•11•10
•32•33•37•36•16•17•13•12
•22•23•27•26•6•7•3•2
•20•21•25•24•4•5•1•0
H3
x1 x1
x5
x2
x2x6
x3
H3x4
162 −+= altneu jj
Technische Informatik I 23
Graphische Darstellung von FunktionenGraphische Darstellung von Funktionen
• Spezifikation / Schaltfunktionen: Funktionstabelle stellt bei großen Werten von n keine besonders effizienteDarstellungstechnik dar, da die Spaltenzahl mit n, die Zeilenzahl jedoch mit 2n wächst
-> Es existieren weitere Möglichkeiten zur Darstellung von Schaltfunktionen in Form spezieller Graphen
z.B. Binary Decision Diagrams (BDDs)
Technische Informatik I 24
Graphische Darstellung von FunktionenGraphische Darstellung von Funktionen
• Beispiel für die Darstellung mittels BDD:
0
b
1
b
a
c
1
1
11
0
0
00
⇔
beide Darstellungen repräsentieren die gleiche Funktion
a
0 0
a
0 1
b
a
0 1
a
1 1
b
c
j0= 0 1 2 3 4 5 6 7
0 1 0 1 0 1 0 1
0 0
0
1 1
1
Technische Informatik I 25
Graphische Darstellung von FunktionenGraphische Darstellung von Funktionen
• Binary Decision Diagrams (BDDs)
- Funktionen lassen sich kanonisch (eindeutig) darstellen
Diese Eigenschaft von BDDs lässt für Äquivalenzprüfungen von Funktionen ausnutzen -> Isomorpie-Test
- darüber hinaus: es existieren eine Reihe von Verfahren, welche die rechnergestützte Verarbeitungvon in BDD-Form dargestellten Funktioneneffizient ermöglichen
Technische Informatik I 26
SchaltfunktionenSchaltfunktionen
– Eigenschaft: Mit der Anzahl n von binären Variablen wächst dieAnzahl möglicher Schaltfunktionen (MF) explosionsartig!
– Gesucht: Grundsätzliche Konstruktionsvorschrift für Schaltfunktionen (unabhängig von n)?
– Ziel: Hardware-Realisierung von Schaltfunktionen
n = 0 MF = 2
n = 1 MF = 4
n = 2 MF = 16
n = 3 MF = 256.
n = 10 MF = 21024 ≈ 10308
Beispiele:
Technische Informatik I 27
MMöglicheögliche Schaltfunktionen bei n=2Schaltfunktionen bei n=2
n = 2: MF = 16 y = f(x2, x1)
111111110000000011111100001111000001110011001100110010101010101010101000
y17y16y15y14y13y12y11y10y7y6y5y4y3y2y1y0x1x2
neg .
Dis
junk
tion
(neg
. Im
plik
atio
n)
neg
. Im
plik
atio
n
Ant
ival
enz
neg.
Kon
junk
tion
Äqu
ival
enz
Impl
ikat
ion
(Impl
ikat
ion)
Dis
junk
tion
Kon
junk
tion
Technische Informatik I 28
MMögliche Schaltfunktionen bei n=2ögliche Schaltfunktionen bei n=2
Eigene Symbole und Namen:
y10 : &, ∧ Konjunktion, UND-Verknüpfung, AND
y16 : +, V Disjunktion, ODER-Verknüpfung, OR
y7 : ,~& neg. Konjunktion, neg. UND-Verknüpfung, NAND (NOT AND)
y1 : V ,~V neg. Disjunktion, neg. ODER-Verknüpfung, NOR (NOT OR)
y6 : ≡ ,~≡ Antivalenz XOR
y11 : ≡ Äquivalenz
y13 : → Implikation, x2 impliziert x1, x2 → x1
(analog: y15 : x1 impliziert x2, x1 → x2)
&
Technische Informatik I 29
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme
• Besondere Funktionen: Konjunktion und Disjunktion
– Null- und Einsstellenmenge teilen sich extrem auf, jeweils in: 1 zu 2n-1 Belegungen
Konjunktion: (1, 1) → 1 , sonst → 0 Disjunktion: (0, 0) → 0 , sonst → 1
– entsprechen den Operatoren der sog. Schaltalgebra, einer speziellen Variante der Booleschen Algebra
Technische Informatik I 30
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme
Symmetriediagramme:
6732
4510
0100
0000
x3
x2
x1y
n = 3 y = x 3 & x 2 & x 1
6732
4510
1111
1110
x3
x2
x1y
y = x 3 V x 2 V x 1
n = 2
32
10
10
00
x2
x1y
y = x 2 & x 1
32
10
11
10x2
x1y
y = x 2 V x 1
Technische Informatik I 31
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme
• Gesucht: Grundsätzliche Konstruktionsvorschrift für Schaltfunktionen (unabhängig von n)?
– Bauprinzip in Anlehnung an die Reihenentwicklung in der Mathematik
– geeignete (z.B. orthogonale) Basisfunktionen bk(x) und Koeffizienten Ak
• Frage: Gibt es Basisfunktionen und geeignete Koeffizienten für beliebige Schaltfunktionen?
∑−
=−−
⋅=⋅++⋅+⋅==1N
0kkk1N1N1100 )x(bA)x(bA)x(bA)x(bA)x(fy K
Technische Informatik I 32
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme
• Notwendig: Konjunktion / Disjunktion -> Funktionswert1(0) beliebiger Belegung zuordnen können
• Beispiel: n=3
Konjunktion: y = x3 & x2 & x1
x1
6732
4510
0100
0000
x3
x2
y
Beliebige Einsstelle: y = ?
x1
6732
4510
0000
1000
x3
x2
yModifikation der Konjunktion
123 x&x&xy =
Abbildung der
Belegung
Technische Informatik I 33
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme
• Beispiel: n=3
Disjunktion:Beliebige Nullstelle: y = ?
x1
6732
4510
1111
0111
x3
x2
yModifikation der Konjunktion
123 xxxy ++=
Abbildung der
Belegung
x1
6732
4510
1011
1111
x3
x2
y
123 xxxy ++=
Technische Informatik I 34
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme
• Ergebnis: Belegungsabbildung -> beliebige Eins- / Nullstelle für jede Belegung -> Minterm- und MaxtermfunktionenAllgemein gilt für n = beliebig:
1Mm0M&mmMMm
12k,j0,kj1MM0m&m
xxMx&&xm
0fürx1fürx
xxxxxy
0fürx1fürx
xx&x&&x&xy
jjjj
jjjj
n
kjkj
1nj
1nj
121nn
121nn
=∨=
==
−≤≤≠=∨=
∨∨=
=
⎩⎨⎧
=∨∨∨∨=
⎩⎨⎧
==
−
−
&&K&&
&&K&&
&&&&&&K&&&&
&&&&&&K&&&&
0x&x&x&xm&m
x&xm,x&xm,x&xm,x&xm
2n:Beispiel
121221
123122
121120
==
==
===
Minterm(funktion)Maxterm(funktion)
Technische Informatik I 35
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme• Gesucht: Grundsätzliche Konstruktionsvorschrift für
Schaltfunktionen (unabhängig von n):Verwendung orthogonaler Minterm- und Maxtermbasisfunktionen möglich?
• Mögliche Funktion: Disjunktion aller Minterme
71111000000016011010000001510100100000140010001000013110000010001201000000100111000000001010000000000011j0x1x2x3y = m0 v m1 v m2 v m3 v m4 v m5 v m6 v m7
Technische Informatik I 36
HerleitungHerleitung derder NormalformtheoremeNormalformtheoreme• Erweiterung: Einführung von Koeffizienten Aj für
Minterm- und Maxtermbasisfunktionen.– Dadurch: Darstellung beliebiger Funktionen möglich– Reihenentwicklung: Gewichtung der Basisfunktionen mj mit Aj
∈ {0, 1}
7111A70000000A7
60110A6000000A6
510100A500000A5
4001000A40000A4
31100000A3000A3
201000000A200A2
1100000000A10A1
00000000000A0A0
j0x1x2x3y = A0&m0 v A1&m1 v A2&m2 v A3&m3 v A4&m4 v A5&m5 v A6&m6 v A7&m7
Technische Informatik I 37
Beispiel: VolladdiererBeispiel: Volladdierer
1 11 1 10 11 1 00 11 0 11 01 0 00 10 1 11 00 1 01 00 0 10 00 0 0si cici-1 ai bi
)b&a&c()b&a&c()b&a&c()b&a&c(s ii1iii1iii1iii1ii −−−− ∨∨∨=
VAaibi
ci-1 si
ci
)b&a&c()b&a&c()b&a&c()b&a&c(c ii1iii1iii1iii1ii −−−− ∨∨∨=
DNF:
Technische Informatik I 38
Beispiel: VolladdiererBeispiel: Volladdierer
1 11 1 10 11 1 00 11 0 11 01 0 00 10 1 11 00 1 01 00 0 10 00 0 0si cici-1 ai bi
)bac(&)bac(&)bac(&)bac(s ii1iii1iii1iii1ii ∨∨∨∨∨∨∨∨= −−−−
VAaibi
ci-1 si
ci
KNF:
)bac(&)bac(&)bac(&)bac(c ii1iii1iii1iii1ii ∨∨∨∨∨∨∨∨= −−−−
Technische Informatik I 39
NormalformtheoremeNormalformtheoreme• Normalformen einer Schaltfunktion
-> kanonische Formen
)Mf(y
)Mf(&)Mf(&&)Mf(&)Mf(y
)m&f(y
)m&f()m&f()m&f()m&f(y
jj
1n2
0j
00112n22n21n21n2
jj
1n2
0j
00112n22n21n21n2
&
V
∨=
∨∨∨∨=
=
∨∨∨∨=
−
=
−−−−
−
=
−−−−
K
K
Konjunktive Normalform (KNF):
DisjunktiveNormalform (DNF):
oder kürzer
oder kürzer
Ergebnis: Allein mit den 3 Grundverknüpfungen (Operatoren) Konjunktion, Disjunktion und Negation ist es möglich, jede beliebige Schaltfunktiondarzustellen. Man sagt: [&, V,
_] ist ein Basissystem der Schaltalgebra
Technische Informatik I 40
NormalformtheoremeNormalformtheoreme
• Hauptsatz der Schaltalgebra:
– Jede beliebige vollständig definierte Schaltfunktiony = f (xn, ... , x1) lässt sich als Disjunktion von Mintermen<Konjunktion von Maxtermen> eindeutig darstellen.
– In der Disjunktion <Konjunktion> treten genau diejenigen Minterme <Maxterme> auf, die zu den Einsstellen <Nullstellen> der Schaltfunktion gehören.
Technische Informatik I 41
DerDer HauptsatzHauptsatz derder SchaltalgebraSchaltalgebra
Beispiel: y = f(x4, x3, x2, x1) = 1, wenn die entsprechende Oktalzahldurch 3 teilbar ist
)(&)(&)(&)(&)(&)(&)(&)(&)(&)(&)(:
12341234
123412341234
123412341234
123412341234
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy
∨∨∨∨∨∨
∨∨∨∨∨∨∨∨∨
∨∨∨∨∨∨∨∨∨
∨∨∨∨∨∨∨∨∨=KNF
)&&&()&&&()&&&()&&&()&&&(:
12341234
123412341234
xxxxxxxxxxxxxxxxxxxxy
∨
∨∨∨=DNFx3
114015111010
016117013012
16071302
04050100
x4
x2
x1y
Technische Informatik I 42
Beziehungen zwischen den BegriffenBeziehungen zwischen den Begriffen
)11,,,0(:Bsp.
xxx
2xj
j1j2nj
n
1i
1iij
K
K=
⋅= ∑=
−
Index
12n
j1j2nj
ijn
1ij
x&x&&x:Bsp.
x&x&&x
xm &
K
&&&&K&&
&&
=
==
Minterm
12n
j1j2nj
ijn
1ij
xxx:Bsp.
xxx
xM V
∨∨∨
∨∨∨=
==
K
&&&&K&&
&&
Maxterm
1jfjjj
1n2
0jmV)m&f(f V =
−
===
DNF
0jfjjj
1n2
0jM&)Mf(&f
=
−
==∨=
KNF
( )( )1,1,0,:Bsp.
x,x,,xX j1j2njj
K
K=
Belegung
( ) ( ){ }jjjj Xfff,X:f =
Funktionstabelle
⎩⎨⎧
=
==
0xwenn,x1xwenn,x
xijij
ijij
ij&&
jj Mm = jj mM =
Technische Informatik I 43
NormalformtheoremeNormalformtheoreme: : PraktischePraktische AnwendungAnwendung
• Notwendig: für jeden Operatortyp eine passende technische Realisierung
• Mindestens Schaltglieder (Gatter) für Konjunktion, Disjunktion und Negation notwendig.
• Definition: Schaltnetz (angelehnt an DIN IEC 748)Ein Schaltnetz ist eine Digitalschaltung, in der es für jede mögliche Kombination von digitalen Signalen an den Eingängen eine - und nur eine - Kombination von digitalen Signalen an den Ausgängen gibt.
SNF YX
Technische Informatik I 44
NormalformtheoremeNormalformtheoreme: : PraktischePraktische AnwendungAnwendung
• Gattersymbole nach DIN-Norm (DIN 40900):
&
UND-Glied :abcd
y = a & b & c & d
≥1
ODER-Glied :abcd
y = a v b v c v d
1a y = a
Negationsglied:
1a y = a
(Zum Vergleich alte Norm)abcd
y
abcd
y
a y
a y
Technische Informatik I 45
NormalformtheoremeNormalformtheoreme: : PraktischePraktische AnwendungAnwendung
• Gattersymbole (internationale Norm):
„0“
„1“
AND
OR
XOR
NAND
NOR
XNOR
Treiber
Negation
Funktion Symbol
1
≥1
=1
&
1
&
≥1
=1
Symbol (DIN)
0
1
Technische Informatik I 46
Normalformtheoreme: Praktische AnwendungNormalformtheoreme: Praktische Anwendung
• Ableitung einer Schaltung aus der DNF am Beispiel Volladdierer:
)b&a&c()b&a&c()b&a&c()b&a&c(s ii1iii1iii1iii1ii −−−− ∨∨∨=
VAaibi
ci-1 si
ci
Technische Informatik I 47
Normalformtheoreme: Praktische AnwendungNormalformtheoreme: Praktische Anwendung
• Ableitung einer Schaltung aus der KNF am Beispiel Volladdierer:
VAaibi
ci-1 si
ci
)bac(&)bac(&)bac(&)bac(s ii1iii1iii1iii1ii ∨∨∨∨∨∨∨∨= −−−−
Technische Informatik I 48
NormalformtheoremeNormalformtheoreme: : PraktischePraktische AnwendungAnwendung
• Normalformorientierte Strukturen:– DNF als Beispiel– 2n UND-Glieder in der 1. Stufe und ein bzw. mehrere
ODER-Glieder in der 2 StufeBeispiel 1: ULA (Universal Logic Array)
ODER-Matrix
(fest)
x1
2n Mintermfunktionen
DNFm1
UND-Matrix
(fest) m2n
x2
xn
m2
Y = f(X)
Technische Informatik I 49
NormalformtheoremeNormalformtheoreme: : PraktischePraktische AnwendungAnwendungBeispiel: y = m1 v m4 v m5 v m6 v m7
Personalisierung (Programmierung):Möglich beim Bilden der Minterme in der 1. Stufe und/oder Auswählen der Minterme in der 2. Stufe.
& & & && & &&
1
1
1
V
1
x1x2x2x3x3
10
y = f(X)
X
0 m1 0 0 m4 m5 m6 m7
0x1
(Einsstellenmenge)(Nullstellenmenge)
Technische Informatik I 50
NormalformtheoremeNormalformtheoreme: : PraktischePraktische AnwendungAnwendung
• Normalformorientierte Strukturen:
Beispiel 2: ROM (Read Only Memory)
ODER-Matrix
(progr.)
x1
2n Mintermfunktionen
DNFm1
UND-Matrix
(fest) m2n
x2
xn
m2
Y = f(X)
Technische Informatik I 51
NormalformtheoremeNormalformtheoreme: : PraktischePraktische AnwendungAnwendung
Beispiel: y = m1 v m4 v m5 v m6 v m7
& & & && & &&
1
1
1
V
x1
x2x2x3x3
y = f(X)
X
m1 m4 m5 m6 m7
x1
Personalisierung erfolgt hier in der 2. Stufe
Technische Informatik I 52
LogikoptimierungLogikoptimierung
• Beispiel Volladdierer:Direkte DNF-Realisierung
• Gesamtkomplexität: 10 Gatter mit bis zu 4 Eingängen (Inverter noch nicht einmal mitberücksichtigt!)
VAaibi
ci-1 si
ci
si ci
Technische Informatik I 53
LogikoptimierungLogikoptimierung
• Beispiel Volladdierer:Optimierte Schaltung
• Gesamtkomplexität: 5 Gatter mit maximal 2 Eingängen
VAaibi
ci-1 si
ci
ai
bi
ci-1si
ci
ci