Transcription

Grundlagen der Informatik 2Grundlagen der Digitaltechnik2. Digitale Schaltfunktionenund NormalformtheorieProf. Dr.-Ing. Jürgen TeichDr.-Ing. Christian HaubeltLehrstuhl für Hardware-Software-Co-DesignGrundlagen der Digitaltechnik

Von der Funktion zur e Fragen:Wie beschreibt man logische Schaltungen?Wie analysiert man logische Schaltungen?Wie realisiert und optimiert man logische Schaltungen?Technische Informatik I2

Von der Funktion zur taleSchaltungyxnxn Antwort:– Beschreibung der Schaltung durch eine Schaltfunktionf: (x1,x2, ,xn) y– Implementierung der Schaltfunktion durch logische GatterTechnische Informatik I3

Von 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, b0c3c2c1c00s4s3s2s1s0S s00a3b3c0s1VAc1a2b2Technische Informatik Is2VAa3b3c2s3VAc3s44

Von der Funktion zur Schaltung Beispiel: Addition zweier Binärzahlen S A BAufbau einer Volladdiererzelle (VA)ci-1aibisiVAciBeschreibung des funktionalenZusammenhangs der Volladdiererzelle durch eineFunktionstabelleTechnische Informatik Ici-1 ai bisi ci00000001100101001101100101010111001111115

Von der Funktion zur Schaltung Beispiel: Addition zweier Binärzahlen S A BAufbau einer Volladdiererzelleci-1 ai bisi Technische Informatik Isici7

Fragen Gibt es eine Systematik zur Abbildung vonFunktionstabellen auf logische Schaltungen (kanonischeFormen)? Wieviele Gatter besitzt die kleinste Schaltung, die dieseFunktion realisiert (Logikminimierung)? Welche elementaren Gatter(funktionen) gibt es? Ist es immer möglich, die kleinste Schaltung zu finden?Technische Informatik I8

Antworten Schaltalgebra:– Spezielle Interpretation der Booleschen Algebra– Basis für die formale Entwicklung binärer Digitalschaltungen Schaltfunktion:– 2n Zuordnungen xj fj (xj Belegung, fj zugeordneterFunktionswert)– Begriffe:Nullstellenmenge N,Einsstellenmenge E,Redundanzmenge RTechnische Informatik I9

Funktionsbegriff– Definition einer Schaltfunktion (s ist das Argument, t derFunktionswert):Angabe aller Paare (s, t) mit s { 0, 1 }n ( Belegung)und t { 0, 1 }xi { 0, 1 }x1x2.X (xn, . , x2, x1 )FunktionellerZusammenhangfy { 0, 1 }yxnTechnische Informatik I14

FunktionsdefinitionAbbildungsvorschrift:(a3 a2 a1)(0, 0, 0)(0, 0, 1)(0, 1, 0)(0, 1, 1)(1, 0, 0)(1, 0, 1)(1, 1, 0)(1, 1, 1)f Funktionsdarstellung:y01101001Technische Informatik 16

Klassen von Schaltfunktionen häufig gilt: nicht allen Belegungen kann/muss einFunktionswert zugeordnet werden– solche Zuordnungen: - Redundanz- oder Freistellen derFunktion- 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 werdenTechnische Informatik I17

Klassen von udotetradenTechnische Informatik I18

Klassen 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 } zun- Wegen {0, 1}n 2 gilt:Bei unvollständigen Schaltfunktionen lässt sich aus jeweilszwei Teilmengen die fehlende dritte Teilmenge bestimmenTechnische Informatik I19

Graphische Darstellung von Funktionen Neben tabellarischer Darstellung: es existieren graphischorientierte Darstellungen– Tafelmethoden (sogenannte KV-Diagramme)vor über 100 Jahren von Karnaugh und Veitch vorgeschlagen– Nachteile von KV-Diagrammen bei Werten n 4 (unübersichtlicheDarstellung!)Technische Informatik I20

Graphische Darstellung von Funktionen Beispiel: Darstellung der Schaltfunktion y f(a3,a2,a1,a0)(durch 3 teilbare BCD-Zahl) mittels Symmetriediagramma0ya100010504021 30716-12-13-17-16010111-15-14a3a2Technische Informatik I21

SymmetriediagrammeV1Entwicklung einesSymmetriediagrammsx1 0 0 1jneu jalt 21 1H1V1xx11x2jneu jalt 2 0 1 2 3H1x2 0 1 5 4 2 3 7 6jneu jalt 2 3 1H2x32 1V2V2x1x2jneu jalt 2 4 1x5x1x1 0 1 5 4 2 3 7 6 12 13 17 16 10 11 15 14H2x2x4 0 1 5 4 24 25 21 20 2 3 7 6 26 27 23 22 12 13 17 16 36 37 33 32 10 11 15 14 34 35 31 30x3V3n 3n 4H3x5x1x1n 1n 2x4x3V3n 0jneu jalt 2 5 1x2n 5 0 1 5 4 24 25 21 20 2 3 7 6 26 27 23 22 12 13 17 16 36 37 33 32 10 11 15 14 34 35 31 30 50n 6x6 70jneu jalt 2 6 1H3x4 77x2 40 60x3Technische Informatik I22

Graphische Darstellung von Funktionen Spezifikation / Schaltfunktionen: Funktionstabelle stelltbei 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 vonSchaltfunktionen in Form spezieller Graphenz.B. Binary Decision Diagrams (BDDs)Technische Informatik I23

Graphische Darstellung von Funktionen Beispiel für die Darstellung mittels BDD:c0beide Darstellungen repräsentierendie gleiche Funktion1cb00b1a0a11a a0101010100010111j0 01234567Technische Informatik Ib1000 a01b1124

Graphische Darstellung von Funktionen Binary Decision Diagrams (BDDs)- Funktionen lassen sich kanonisch (eindeutig) darstellenDiese Eigenschaft von BDDs lässt für Äquivalenzprüfungen vonFunktionen ausnutzen - Isomorpie-Test- darüber hinaus: es existieren eine Reihe von Verfahren,welche die rechnergestützte Verarbeitungvon in BDD-Form dargestellten Funktioneneffizient ermöglichenTechnische Informatik I25

Schaltfunktionen– Eigenschaft: Mit der Anzahl n von binären Variablen wächst dieAnzahl möglicher Schaltfunktionen (MF) explosionsartig!– Gesucht: Grundsätzliche Konstruktionsvorschrift fürSchaltfunktionen (unabhängig von n)?– Ziel: Hardware-Realisierung von SchaltfunktionenBeispiele:n 0MF 2n 1MF 4n 2MF 16n 3.n 10MF 256MF 21024 10308Technische Informatik I26

Mögliche Schaltfunktionen bei n 2n 2: MF 16 y f(x2, 11111(neg . Implikation)Antivalenzneg. unktionTechnische Informatik IImplikation1neg. Implikation0neg. Disjunktionx x y y y y y y y y y y y y y y y y2 1 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 170 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 127

Mögliche Schaltfunktionen bei n 2Eigene Symbole und Namen:y10 :&, Konjunktion, UND-Verknüpfung,ANDy16 : , VORy7 :& , & neg. Konjunktion, neg. UND-Verknüpfung,NAND (NOT AND)y1 :V , V neg. Disjunktion, neg. ODER-Verknüpfung,NOR (NOT OR)y6 : , AntivalenzXORy11 : y13 : Disjunktion, ODER-Verknüpfung,ÄquivalenzImplikation, x2 impliziert x1, x2 x1(analog: y15 : x1 impliziert x2, x1 x2)Technische Informatik I28

Herleitung der Normalformtheoreme Besondere Funktionen: Konjunktion und Disjunktion– Null- und Einsstellenmenge teilen sich extrem auf, jeweils in:1 zu 2n-1 BelegungenKonjunktion: (1, 1) 1 , sonst 0Disjunktion: (0, 0) 0 , sonst 1– entsprechen den Operatoren der sog. Schaltalgebra, einerspeziellen Variante der Booleschen AlgebraTechnische Informatik I29

Herleitung der NormalformtheoremeSymmetriediagramme:n 2y x2 & x1y x2 V x1x1y0x2n 30020101x23y x3 & x2 & x1x2x101021113y x3 V x2 V x1y0x1y020013x1y015700046x3Technische Informatik Ix2102111311571146x330

Herleitung der Normalformtheoreme Gesucht: Grundsätzliche Konstruktionsvorschrift fürSchaltfunktionen (unabhängig von n)?– Bauprinzip in Anlehnung an die Reihenentwicklung in derMathematik– geeignete (z.B. orthogonale) Basisfunktionen bk(x) undKoeffizienten AkN 1y f(x) A0 b0 (x) A1 b1(x) K AN 1 bN 1(x) Ak bk (x)k 0 Frage: Gibt es Basisfunktionen und geeigneteKoeffizienten für beliebige Schaltfunktionen?Technische Informatik I31

Herleitung der Normalformtheoreme Notwendig: Konjunktion / Disjunktion - Funktionswert1(0) beliebiger Belegung zuordnen können Beispiel: n 3Konjunktion: y x3 & x2 & x1x1yx1y0x2Beliebige Einsstelle: y ?002001305170046Modifikation der 3x3y x 3 & x 2 & x1Technische Informatik I32

Herleitung der Normalformtheoreme Beispiel: n 3Disjunktion:Beliebige Nullstelle: y ?x1yx1y1x2y x 3 x 2 x1102111315071146Modifikation der 3x3y x 3 x 2 x1Technische Informatik I33

Herleitung der Normalformtheoreme Ergebnis: Belegungsabbildung- beliebige Eins- / Nullstelle für jede Belegung- Minterm- und MaxtermfunktionenAllgemein giltfür n beliebig:y &x& n & &x& n 1 & K & &x& 2 & &x& 1y &x& n &x& n 1 K &x& 2 &x& 1Beispiel : n 2m0 x 2 & x1,m1 x 2 & x1,m2 x 2 & x1,m3 x 2 & x1m1 & m2 x 2 & x1 & x 2 & x1 0 x&x& x x&x& xfür 1für 0für 1für 0m j &x& n & K & &x& 1Minterm(funktion)M j &x& n K &x& 1Maxterm(funktion)m j & mk 0M j Mk 1mj M jMj m jmj & Mj 0mj Mj 1Technische Informatik Ij k , 0 j, k 2 1n34

Herleitung der Normalformtheoreme Gesucht: Grundsätzliche Konstruktionsvorschrift fürSchaltfunktionen (unabhängig von n):Verwendung orthogonaler Minterm- undMaxtermbasisfunktionen möglich? Mögliche Funktion: Disjunktion aller Mintermeym0 vm1 vm2 vm311000001010001001010001001011 he Informatik Im6 v35

Herleitung der Normalformtheoreme Erweiterung: Einführung von Koeffizienten Aj fürMinterm- und Maxtermbasisfunktionen.– Dadurch: Darstellung beliebiger Funktionen möglich– Reihenentwicklung: Gewichtung der Basisfunktionen mj mit Aj {0, 1}y A0&m0 v A1&m1 v A2&m2 v A3&m3 v A4&m4 v A5&m5 v A6&m6 v A7&m7 000000A601106A70000000A71117Technische Informatik I36

Beispiel: Volladdiererci-1aibiDNF:ci-1 ai bisi ci000000011001010si01101ci10010101011100111111VAsi (c i 1 & ai & bi ) (c i 1 & ai & bi ) (c i 1 & ai & bi ) (c i 1 & ai & bi )c i (c i 1 & ai & bi ) (c i 1 & ai & bi ) (c i 1 & ai & bi ) (c i 1 & ai & bi )Technische Informatik I37

Beispiel: Volladdiererci-1aibiKNF:ci-1 ai bisi ci000000011001010si01101ci10010101011100111111VAsi (c i 1 ai bi ) & (c i 1 ai bi ) & (c i 1 ai bi ) & (c i 1 ai bi )c i (c i 1 ai bi ) & (c i 1 ai bi ) & (c i 1 ai bi ) & (c i 1 ai bi )Technische Informatik I38

Normalformtheoreme Normalformen einer Schaltfunktion- kanonische FormenDisjunktivey (f n & m n ) (f n & m n ) K (f1 & m1) (f0 & m0 )2 12 12 22 2Normalform (DNF):oder kürzery n2 1V (f & m )j 0jjKonjunktivey (f n M n ) & (f n M n ) & K & (f1 M1) & (f0 M0 )2 12 12 22 2Normalform (KNF):oder kürzery n2 1& (f M )j 0jjErgebnis: Allein mit den 3 Grundverknüpfungen (Operatoren) Konjunktion,Disjunktion und Negation ist esmöglich, jede beliebige Schaltfunktiondarzustellen. Man sagt: [&, V, ] ist ein Basissystem der SchaltalgebraTechnische Informatik I39

Normalformtheoreme 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 diejenigenMinterme Maxterme auf, die zu den Einsstellen Nullstellen der Schaltfunktion gehören.Technische Informatik I40

Der Hauptsatz der SchaltalgebraBeispiel:y f(x4, x3, x2, x1) 1,wenn die entsprechende Oktalzahldurch 3 teilbar istx2DNF : y KNF :y x1y0001050402130716012013117016010111015114x4x3( x4 & x3 & x2 & x1 ) ( x4 & x3 & x2 & x1 ) ( x4 & x3 & x2 & x1 ) ( x4 & x3 & x2 & x1 ) ( x4 & x3 & x2 & x1 )( x4 x3 x2 x1 ) & ( x4( x4 x3 x2 x1 ) & ( x4( x4 x3 x2 x1 ) & ( x4( x4 x3 x2 x1 ) & ( x4 x3 x2 x1 ) & ( x4 x3 x2 x1 ) & x3 x2 x1 ) & ( x4 x3 x2 x1 ) & x3 x2 x1 ) & ( x4 x3 x2 x1 ) & x3 x2 x1 )Technische Informatik I41

Beziehungen zwischen den BegriffenIndexj x ij , wenn x ij 1&x& ij x ij , wenn x ij 0n x ij 2 i 1i 1 x nj K x 2 j x 1jBsp. : ( 0, K , 1, 1 )nmj &i 1M j mjm j MjMintermMj &x& ijBelegung &x& nj & K & &x& 2 j & &x&1jBsp. : x n & K & x 2 & x1DNF(X j x nj ,K , x 2 j , x1jBsp. : (0, K , 1, 1)2 1f j 1f:{(X , f ) fjjj) f (X j )Technische Informatik InV &x&iji 1 &x& nj K &x& 2 j &x&1jBsp. : x n K x 2 x1Funktionstabellenf V (fj & m j ) Vm jj 0MaxtermKNF}n2 1f & ( f j M j ) &M jj 0f j 042

Normalformtheoreme: Praktische Anwendung Notwendig: für jeden Operatortyp eine passendetechnische 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 jedemögliche Kombination von digitalen Signalen an denEingängen eine - und nur eine - Kombination von digitalenSignalen an den Ausgängen gibt.SNXFYTechnische Informatik I43

Normalformtheoreme: Praktische Anwendung Gattersymbole nach DIN-Norm (DIN 40900):(Zum Vergleich alte Norm)aby a&b&c&dycdUND-Glied :abcd&ODER-Glied :abcd 1y a v b vcvdabcdy:Negationsglieda1y aaya1y aayTechnische Informatik I44

Normalformtheoreme: Praktische Anwendung 0“0„1“1ANDSymbol (DIN)&OR 1XOR 1NAND&NOR 1XNOR 1Treiber1Negation1Technische Informatik I45

Normalformtheoreme: Praktische Anwendung Ableitung einer Schaltung ausder DNF am BeispielVolladdierer:ci-1aibisiVAcisi (c i 1 & ai & bi ) (c i 1 & ai & bi ) (c i 1 & ai & bi ) (c i 1 & ai & bi )Technische Informatik I46

Normalformtheoreme: Praktische Anwendung Ableitung einer Schaltung ausder KNF am BeispielVolladdierer:ci-1aibisiVAcisi (c i 1 ai bi ) & (c i 1 ai bi ) & (c i 1 ai bi ) & (c i 1 ai bi )Technische Informatik I47

Normalformtheoreme: Praktische Anwendung Normalformorientierte Strukturen:– DNF als Beispiel– 2n UND-Glieder in der 1. Stufe und ein bzw. mehrereODER-Glieder in der 2 StufeBeispiel 1: ULA (Universal Logic Array)2n ERMatrix(fest)Technische Informatik IY f(X)48

Normalformtheoreme: Praktische AnwendungBeispiel:y m1 v m4 v m5 v m6 v menge)11&&&0m1&0&&m40&m5&m6m7Vy f(X)Personalisierung (Programmierung):Möglich beim Bilden der Minterme in der 1. Stufeund/oder Auswählen der Minterme in der 2. Stufe.Technische Informatik I49

Normalformtheoreme: Praktische Anwendung Normalformorientierte Strukturen:Beispiel 2:ROM (Read Only Memory)2n Mintermfunktionenx1x2xnm1UNDMatrix(fest)m2 ODERMatrixm2nDNFY f(X)(progr.)Technische Informatik I50

Normalformtheoreme: Praktische AnwendungBeispiel:y m1 v m4 v m5 v m6 v m7x1x1x2x2x3x31X11&&&&&m1&m4&m5&m6m7Vy f(X)Personalisierung erfolgt hier in der 2. StufeTechnische Informatik I51

Logikoptimierungci-1 Beispiel Volladdierer:Direkte DNF-Realisierung aibisisiVAcici Gesamtkomplexität: 10 Gatter mit bis zu 4 Eingängen(Inverter noch nicht einmal mitberücksichtigt!)Technische Informatik I52

Logikoptimierung Beispiel Volladdierer:Optimierte Schaltungci-1aibisiVAciaibisici-1ci Gesamtkomplexität: 5 Gatter mit maximal 2 EingängenTechnische Informatik Ici53

Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 2. Digitale Schaltfunktionen und Normalformtheorie Prof. Dr.-Ing. Jürgen Teich Dr.-Ing. Ch