Grundlagen Digitaler Systeme (GDS) Prof. Dr. Sven-Hendrik Voß | Sommersemester 2015 Technische Informatik (Bachelor), Semester 1 Termin 3, Donnerstag, 23.04.2015 Seite 2 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Inhaltsverzeichnis Themen und Termine Lernziele Normalformen Disjunktive Normalform Konjunktive Normalform Darstellung von Funktionen in Normalformen Minimierung mit Hilfe der Schaltalgebra Zusammenfassung Seite 3 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Themen und Termine - Seminaristischer Unterricht Seminaristischer Unterricht (SU) im Raum B323, donnerstags 10:00 - 11:30 Uhr Nr. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Datum 09.04. 16.04. 23.04. 30.04. 07.05. 14.05. 21.05. 28.05. 04.06. 11.06. 18.06. 25.06. 02.07. 09.07. 16.07. 23.07. 30.07. Themen Einfuhrung; Boolesche Algebra (1) ¨ Boolesche Algebra (2) Vereinfachung logischer Funktionen (1) Vereinfachung logischer Funktionen (2) Zahlensysteme (1) Christi Himmelfahrt Zahlensysteme (2) Logische Grundschaltungen (1) Logische Grundschaltungen (2) ¨ Binar-Codes (1) ¨ Binar-Codes (2) Sequentielle Logik (1) Sequentielle Logik (2) Sequentielle Logik (3) Busse, Entwicklung Addierwerk Klausur Klausurruckgabe und -besprechung ¨ Kurztest 1 2 3 Seite 4 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Lernziele Nach diesem Termin sollten Sie... I in der Lage sein, die Inhalte einer Wahrheitstabelle als disjunktive und ¨ konjunktive Normalform abbilden zu konnen I Boolesche Funktionen von der Normalform in eine Minimalform ¨ uberf uhren konnen ¨ ¨ I ¨ fur ob diese sich in einer ¨ eine gegebene Funktion beurteilen konnen, Normal- respektive Minimalform befindet Seite 5 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Normalformen ¨ In der Praxis haufig: Wie kommt man von konkreter Problemstellung zur ¨ dazugehorigen Schaltfunktion? ¨ Funktion kann allein durch AND, OR und NOT (d.h. Jede binare ¨ verschiedene aquivalente Boolesche Terme) dargestellt werden I systematische Vorgehensweise wunschenswert ¨ I gegeben durch sog. Normalformen (einheitliche normierte Darstellung) Normalformen werden zum Schaltkreisentwurf eingesetzt und sind dazu ¨ unerlasslich! I ¨ Boolesche Funktionen, die in einer Normalform vorliegen, konnen direkt in ein zweistufiges Schaltnetz uberf uhrt werden! ¨ ¨ Vereinfachung logischer Funktionen | Seite 6 Grundlagen digitaler Systeme | Sommersemester 2015 Disjunktive Normalform Man betrachtet die Eingangsvektoren Xi , fur ¨ die die Funktion y = f (x) den Wert 1 annimmt. I es gilt also fur ¨ diese: f (Xi ) = 1 Hier: X0 , X2 , X3 , X5 , X6 Man bildet fur ¨ jeden dieser Eingangsvektoren eine Konjunktion der Elemente xi , die fur ¨ diesen Eingangsvektor den Wert 1 annimmt. Beispiel fur ¨ X5 : m5 = x2 ∧ x1 ∧ x0 Man nennt m5 auch Minterm Wahrheitstabelle Dezimal 0 1 2 3 4 5 6 7 x2 0 0 0 0 1 1 1 1 x1 0 0 1 1 0 0 1 1 x0 0 1 0 1 0 1 0 1 y 1 0 1 1 0 1 1 0 Seite 7 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Disjunktive Normalform Minterme I erhalten alle Eingangsvariablen (daher auch Vollkonjunktion genannt) I umfassen Eingangsvariablen invertiert oder nichtinvertiert (je nachdem, ob entsprechende Eingangsvariable 1 oder 0 ist) I haben fur ¨ einen bestimmten Fall der Eingangsvariablen den Wert 1 Fur ¨ gezeigtes Beispiel: m0 = x2 ∧ x1 ∧ x0 m2 = x2 ∧ x1 ∧ x0 m3 = x2 ∧ x1 ∧ x0 m5 = x2 ∧ x1 ∧ x0 m6 = x2 ∧ x1 ∧ x0 Seite 8 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Disjunktive Normalform Gesamte Funktion wird durch Disjunktion der Minterme dargestellt I Funktion soll Wert 1 bekommen, wenn einer der Minterme 1 wird I Darstellungsweise wird disjunktive Normalform (DNF) genannt Fur ¨ gezeigtes Beispiel lautet die DNF: y = (x2 ∧ x1 ∧ x0 ) ∨ (x2 ∧ x1 ∧ x0 ) ∨ (x2 ∧ x1 ∧ x0 ) ∨ (x2 ∧ x1 ∧ x0 ) ∨ (x2 ∧ x1 ∧ x0 ) Vereinfachung logischer Funktionen | Seite 9 Grundlagen digitaler Systeme | Sommersemester 2015 Konjunktive Normalform Man betrachtet die Eingangsvektoren Xi , fur ¨ die die Funktion y = f (x) den Wert 0 annimmt. I es gilt also fur ¨ diese: f (Xi ) = 0 Hier: X1 , X4 , X 7 Man bildet die sog. Maxterme Mi , d.h. Disjunktionen der Elemente xi , die fur ¨ diesen Eingangsvektor den Wert 0 annehmen. M1 = x2 ∨ x1 ∨ x0 M4 = x2 ∨ x1 ∨ x0 M7 = x2 ∨ x1 ∨ x0 Wahrheitstabelle Dezimal 0 1 2 3 4 5 6 7 x2 0 0 0 0 1 1 1 1 x1 0 0 1 1 0 0 1 1 x0 0 1 0 1 0 1 0 1 y 1 0 1 1 0 1 1 0 Seite 10 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Konjunktive Normalform Maxterme I erhalten alle Eingangsvariablen I umfassen Eingangsvariablen invertiert oder nichtinvertiert (je nachdem, ob entsprechende Eingangsvariable 1 oder 0 ist) I haben fur ¨ einen bestimmten Fall der Eingangsvariablen den Wert 0, d.h. es mussen Eingangsvariablen, die im Eingangsvektor gleich 1 sind, ¨ invertiert im Maxterm auftreten Gesamte Funktion wird durch Konjunktion der Maxterme dargestellt I Funktion soll Wert 0 bekommen, wenn mindestens einer der Maxterme gleich 0 ist I Darstellungsweise wird konjunktive Normalform (KNF) genannt Fur ¨ gezeigtes Beispiel lautet die KNF: y = (x2 ∨ x1 ∨ x0 ) ∧ (x2 ∨ x1 ∨ x0 ) ∧ (x2 ∨ x1 ∨ x0 ) Seite 11 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Darstellung von Funktionen in Normalformen Merke: I KNF und DNF sind bis auf kommutative Vertauschungen eindeutig I KNF und DNF lassen sich direkt aus den Funktionstabellen ablesen KNF und DNF sind gleichwertige Darstellungsformen fur ¨ eine Funktion I oft unterschiedlich komplex I Anzahl der Eingangsvektoren, fur ¨ die die Funktion 1 ist → Anzahl der Minterme I Anzahl der Eingangsvektoren, fur ¨ die die Funktion 0 ist → Anzahl der Maxterme I ¨ wahle gunstigere Form: DNF bei Funktionen mit weniger Einsen als ¨ Nullen, KNF bei Funktionen mit weniger Nullen als Einsen KNF und DNF lassen sich mittels Satz von Shannon ineinander uberf uhren ¨ ¨ Seite 12 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Minimierung mit Hilfe der Schaltalgebra DNF und KNF eignen sich zum Aufstellen der booleschen Gleichungen I zweistufige Schaltung → schnell, aber bzgl. Gatteraufwand nicht ideal I ¨ Normalformen konnen weiter optimiert werden → Vereinfachungsregeln Beispiel: Minimierung folgender Funktion y = (x0 ∧ x1 ∧ x2 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x2 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x2 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x2 ∧ x3 ) ∨(x0 ∧ x1 ∧ x2 ∧ x3 ) Anwendung des Nachbarschaftsgesetzes auf Term 1 und 2, wobei Term 2 ¨ stehengelassen wird, da noch benotigt fur ¨ Zusammenfassung mit Term 3 y = (x0 ∧ x2 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x2 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x2 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x2 ∧ x3 ) ∨(x0 ∧ x1 ∧ x2 ∧ x3 ) Term 2 und 3, sowie 4 und 5 auf die gleiche Art und Weise y = (x0 ∧ x2 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x3 ) ∨ (x0 ∧ x1 ∧ x3 ) y = (x0 ∧ x2 ∧ x3 ) ∨ (x1 ∧ x3 ) → Minimalform (= zwei AND-Gatter und ein OR-Gatter) Seite 13 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Minimierung mit Hilfe der Schaltalgebra Konjunktive oder disjunktive Minimalformen I Ausdruck (Schaltung) mit dem geringsten Aufwand an Variablen (Anzahl ¨ Eingange) und Verknupfungen (Anzahl Logikgatter) ¨ I sowohl Anzahl der Disjunktionen bzw. Konjunktionen, als auch die Anzahl der auftretenden Variablen muss in jedem Disjunktions- / Konjunktionsterm minimal sein I damit: geringere Kosten und weniger Laufzeitprobleme bei zeitkritischen Schaltungen! Seite 14 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Zusammenfassung Heute haben Sie gelernt... I wie man Sachverhalte aus dem Bereich der kombinatorischen Logik in Wahrheitstabellen abbildet I Funktionen in ihre Normalform bringt I wie man aus einer Normalform mit algebraischen Mitteln eine Minimalform ableitet Seite 15 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 ¨ Ausblick auf nachste Stunde ¨ In der nachsten Stunde widmen wir uns... I weiteren Vereinfachungsverfahren der Boolschen Algebra Seite 16 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Hinweise zum Selbststudium Zur Vertiefung wird empfohlen... I GDS-Skript I Dirk Hoffmann: Grundlagen der technischen Informatik, Hanser Verlag, ISBN 3446406913 Seite 17 Vereinfachung logischer Funktionen | Grundlagen digitaler Systeme | Sommersemester 2015 Kritik Nun sind Sie dran: I Kritik: Was funktioniert gut / was schlecht? I Anregungen I Wunsche ¨ I ¨ Verbesserungsvorschlage in Bezug auf Inhalt und Organisation der Vorlesung
© Copyright 2024 ExpyDoc
