Technische Grundlagen der Informatik 1 Digitale Systeme · 2011-04-11 · Wir haben uns in diesem Semester entschlossen ein Skript anzubieten, ... Allgemein fur A1 und A2 als zwei

REV

1468

Technische Grundlagen der Informatik 1

Digitale Systeme

Technische Universitat BerlinFakultat IV Informatik und ElektrotechnikInstitut fur Technische InformatikFG RechnertechnologieFranklinstraße 28/29 D-10587 Berlin

REV

1468

Vorwort

Wir haben uns in diesem Semester entschlossen ein Skript anzubieten, das mit etwasGluck diesen Namen auch verdient. Auch wenn der Inhalt des Skripts nahezu deckungs-gleich mit den Folien der Vorlesung ist, so erhoffen wir uns von einem Skript dennochVorteile gegenuber dem Abdrucken der Folien (Handouts). Zum einen ist es naturlichkompakter, zum anderen hoffen wir, dass es auch etwas lesbarer ist und dadurch vielleichteher einen Nachschlagecharakter hat. Beim Neugestalten haben wir auch versucht dieAbbildungen aneinander anzugleichen und im Aussehen konsistenter zu machen, sodassein hoherer Wiedererkennungswert zwischen den einzelnen technischen Darstellungen inden unterschiedlichen Kapiteln gegeben ist. Bedanken wollen wir uns vor allem auch beiden Tutoren, die uns beim Umsetzen des Vorhabens unter die Arme gegriffen haben:

Sven-Garrit CzarnianCarsten DulsenThomas Faber

Matthias HartmannEvren Kucukbayraktar

Marcus SchubertJan Wetter

Wir hoffen, dass die Arbeit nicht umsonst war und wenigstens ein paar Studierendengefallt.

Dr. Carsten GremzowNico Moser

c© Carsten Gremzow, Nico Moser 2010-2011

I

REV

1468

Inhaltsverzeichnis

1 Zweiwertige Logik 11.1 Grundbegriffe der Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Aussagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Grundverknupfungen . . . . . . . . . . . . . . . . . . . . . . . . . 31.1.3 Ausdrucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.4 Umformung logischer Ausdrucke . . . . . . . . . . . . . . . . . . . 81.1.5 Formal wahre, formal falsche Ausdrucke . . . . . . . . . . . . . . 9

1.2 Logische Funktionen und Funktionsbundel . . . . . . . . . . . . . . . . . 111.2.1 Logische Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . 111.2.2 Vollstandige Systeme . . . . . . . . . . . . . . . . . . . . . . . . . 121.2.3 Funktionsbundel . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3 Das Karnaugh-Veitch-Diagramm . . . . . . . . . . . . . . . . . . . . . . 15

2 Zahlendarstellung 182.1 Stellenwertsysteme (B-adische Systeme) . . . . . . . . . . . . . . . . . . . 18

2.1.1 Darstellung naturlicher Zahlen . . . . . . . . . . . . . . . . . . . . 182.1.2 Zerlegung nach dem Horner-Schema . . . . . . . . . . . . . . . . . 18

2.2 Vorzeichenlose Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.2 Subtraktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.3 Zahlenbereich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Vorzeichenbehaftete Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . 202.4 2-Komplement-Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.1 Bildung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.4.2 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.4.3 Subtraktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.4.4 Zahlenbereich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5 Gray-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3 Logische Normalformen und Primtermdarstellung 253.1 Disjunktive Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.1 Allgemeine disjunktive Normalform . . . . . . . . . . . . . . . . . 263.1.2 Kanonische disjunktive Normalform . . . . . . . . . . . . . . . . . 27

3.2 Konjunktive Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.2.1 Allgemeine konjunktive Normalform . . . . . . . . . . . . . . . . . 303.2.2 Kanonische konjunktive Normalform . . . . . . . . . . . . . . . . 31

II

REV

1468

3.3 Zusammenhang zwischen den Normalformen . . . . . . . . . . . . . . . . 333.4 Normalformen und partiell definierte Funktionen . . . . . . . . . . . . . . 343.5 Karnaugh-Veitch-Diagramm und Normalformen . . . . . . . . . . . . . . 353.6 Primtermdarstellung logischer Funktionen . . . . . . . . . . . . . . . . . 36

3.6.1 Implikanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.6.2 Primimplikanten . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4 Analyse und Synthese von Schaltnetzen 424.1 Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2 Gattersymbolik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.3 Elementare Verfahren zur Schaltnetzsynthese . . . . . . . . . . . . . . . . 44

4.3.1 Kanonische Abbildungen . . . . . . . . . . . . . . . . . . . . . . . 444.3.2 Entwicklungssatz (Shannon) . . . . . . . . . . . . . . . . . . . . . 454.3.3 Iterative Strukturen . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.4 Minimale zweistufige AND-OR-Schaltnetze . . . . . . . . . . . . . . . . . 464.4.1 Kosten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.4.2 Bestimmung der Primimplikanten . . . . . . . . . . . . . . . . . . 474.4.3 Kostenoptimierung (minimale Uberdeckung) . . . . . . . . . . . . 49

4.5 Schaltnetze mit mehreren Stufen . . . . . . . . . . . . . . . . . . . . . . . 524.5.1 Baumstruktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.5.2 Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.5.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5 Komplexe Schaltnetze 555.1 Codierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2 Decodierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.3 Multiplexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.4 Demultiplexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.5 Komparatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.6 Arithmetische Schaltnetze (Addierer) . . . . . . . . . . . . . . . . . . . . 64

5.6.1 Halbaddierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.6.2 Volladdierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.6.3 Mehrstellige Addierer . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.7 Arithmetisch/Logische Einheit (ALU) . . . . . . . . . . . . . . . . . . . . 675.8 Schaltketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.9 Schiebeeinheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6 Speicherglieder 786.1 Begriffe und Kenngroßen . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.1.1 Speicherelement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786.1.2 Speicherkapazitat . . . . . . . . . . . . . . . . . . . . . . . . . . . 786.1.3 Speicherorganisation . . . . . . . . . . . . . . . . . . . . . . . . . 786.1.4 Arbeitsgeschwindigkeit . . . . . . . . . . . . . . . . . . . . . . . . 786.1.5 Weitere Kenngroßen . . . . . . . . . . . . . . . . . . . . . . . . . 79

III

REV

1468

6.2 Klassifizierung digitaler Speicher . . . . . . . . . . . . . . . . . . . . . . . 796.2.1 Einteilung nach Arbeitsgeschwindigkeit und Kapazitat . . . . . . 796.2.2 Einteilung nach der Art des Zugriffs . . . . . . . . . . . . . . . . . 796.2.3 Einteilung nach Art des Datenverkehrs . . . . . . . . . . . . . . . 80

6.3 Halbleiterspeicher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 816.3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 816.3.2 Bistabile Kippstufe . . . . . . . . . . . . . . . . . . . . . . . . . . 836.3.3 Dynamischer MOS-Speicher . . . . . . . . . . . . . . . . . . . . . 836.3.4 Ein-Bit-Flipflopspeicher . . . . . . . . . . . . . . . . . . . . . . . 846.3.5 Speicherorganisation eines SRAMs . . . . . . . . . . . . . . . . . 87

7 Programmierbare Logik 887.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 887.2 Schaltnetze aus Multiplexern . . . . . . . . . . . . . . . . . . . . . . . . . 887.3 Programmierbare Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907.3.2 ROM-Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917.3.3 Speicherzellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947.3.4 Anwendungsbeispiele fur ROM-Logik . . . . . . . . . . . . . . . . 96

7.4 Programmable Logic Array (PLA) . . . . . . . . . . . . . . . . . . . . . . 967.4.1 Uberblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 967.4.2 Schaltungsprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

7.5 Andere programmierbare Logikschaltungen . . . . . . . . . . . . . . . . . 987.6 Programmierbares Gate Array (FPGA) . . . . . . . . . . . . . . . . . . . 99

8 Technische Aspekte des Logikentwurfs 1048.1 Realisierung der Schaltalgebra durch Logikgatter . . . . . . . . . . . . . 104

8.1.1 Positive Und Negative Logik . . . . . . . . . . . . . . . . . . . . . 1048.1.2 Pegelbereiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1058.1.3 Ubertragungs(Transfer)Kennlinie . . . . . . . . . . . . . . . . . . 1058.1.4 Statischer Storabstand . . . . . . . . . . . . . . . . . . . . . . . . 1068.1.5 Dynamischer Storabstand . . . . . . . . . . . . . . . . . . . . . . 1068.1.6 Belastbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1078.1.7 Verlustleistung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088.1.8 Schaltzeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088.1.9 Geschwindigkeit-Leistungs-Produkt . . . . . . . . . . . . . . . . . 109

8.2 Dynamisches Verhalten von Schaltnetzen . . . . . . . . . . . . . . . . . . 1098.2.1 Hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1098.2.2 Funktionshazards . . . . . . . . . . . . . . . . . . . . . . . . . . . 1118.2.3 Strukturhazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1118.2.4 Vermeidung von Hazards . . . . . . . . . . . . . . . . . . . . . . . 113

9 Synchrone Schaltwerke 1159.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

IV

REV

1468

9.2 Schaltwerkssynthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1179.3 Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

9.3.1 Ubersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1219.3.2 Technische Realisierung statischer Parallel- und Serienspeicher . . 122

9.4 Zahler und Untersetzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1249.4.1 Ubersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1249.4.2 Untersetzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1249.4.3 Zahler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

10 Hardwarebeschreibungssprache VHDL 12910.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12910.2 Entwurfssichten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12910.3 Historische Entwicklung . . . . . . . . . . . . . . . . . . . . . . . . . . . 13010.4 Aufbau einer VHDL-Beschreibung . . . . . . . . . . . . . . . . . . . . . . 132

10.4.1 Entity-Relationship-Modell . . . . . . . . . . . . . . . . . . . . . . 13210.4.2 Ubersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13210.4.3 Schnittstellenbeschreibung . . . . . . . . . . . . . . . . . . . . . . 13310.4.4 Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13310.4.5 Konfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13410.4.6 Packages und Libraries . . . . . . . . . . . . . . . . . . . . . . . . 135

10.5 Entwurfssichten in VHDL . . . . . . . . . . . . . . . . . . . . . . . . . . 13510.5.1 Verhaltensmodellierung . . . . . . . . . . . . . . . . . . . . . . . . 13510.5.2 strukturelle Modellierung . . . . . . . . . . . . . . . . . . . . . . . 137

10.6 Entwurfsebenen in VHDL . . . . . . . . . . . . . . . . . . . . . . . . . . 13710.6.1 Algorithmusebene . . . . . . . . . . . . . . . . . . . . . . . . . . . 13710.6.2 Register-Transfer-Ebene . . . . . . . . . . . . . . . . . . . . . . . 13810.6.3 Logik(Gatter)ebene . . . . . . . . . . . . . . . . . . . . . . . . . . 138

10.7 Logiktypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13910.8 Testumgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Stichwortverzeichnis 142

V

REV

1468

1 Zweiwertige Logik

1.1 Grundbegriffe der Logik

1.1.1 Aussagen

Jede wortlich formulierte Behauptung ist eine Aussage (z.B. “3 + 5 = 8”,“er lauft”).Von solchen Satzen lasst sich im Allgemeinen bestimmen, ob sie zutreffen oder nicht,d.h. ob sie wahr oder falsch sind. Es lasst sich somit der Wahrheitswert einer Aussagebestimmen.

Definition 1. Ein Satz, dem eindeutig ein Wahrheitswert zugeordnet werden kann,heißt Aussage. Ist A eine Aussage, dann ist W(A) der Wahrheitswert der Aussage mit:W(A) := wahr (falsch), falls Aussage A zutrifft (falls Aussage A nicht zutrifft).

Verknupfungen von Aussagen

Mehrere Aussagen lassen sich zu einer neuen Aussage zusammenfassen – auch dafurlasst sich ein Wahrheitswert finden. Diese Zusammenfassung von Einzelaussagen wirdumgangssprachlich mit bestimmten Wortern gebildet.

Beispiel 1. Verknupfungen von Aussagen5 ist eine Primzahl und 10 ist durch 5 teilbar.Ist a durch 4 teilbar, dann ist a auch durch 2 teilbar.

Allgemein fur A1 und A2 als zwei Aussagen gilt:

A1 und A2 KonjunktionA1 oder A2 (einschließendes) Oder, Disjunktionentweder A1 oder A2 ausschließendes Oder, Antivalenzwenn A1 dann A2 Folgerung, ImplikationA1 genau dann, wenn A2 Aquivalenz

Die Bindeworter verknupfen Aussagen. Jeder dieser aus Aussagen zusammengesetzteSatz ist selbst wieder eine Aussage. Wahrheitswerte der Einzelaussagen stehen demWahrheitswert der zusammengesetzten Aussagen gegenuber.

1

REV

1468

Wahrheitswert der Verknupfung

Aussagenlogik betrachtet unter Vernachlassigung des Inhalts der Aussagen nur die Wahr-heitswerte. Fur entsprechende Verknupfungen zwischen den Wahrheitswerten soll gelten:

Verknupfung der Wahrheitswerte der Einzelaussagen =Wahrheitswert der zusammengesetzten Aussage

Ist z. B. “A1 und A2“ eine zusammengesetzte Aussage, dann soll gelten:

WpA1q und WpA2q WpA1 und A2q

Diese Gleichung muss fur alle moglichen Kombinationen der Wahrheitswerte von A1 undA2 gelten.

Wertetabelle, Wahrheitstabelle

Die Aussage “A1 und A2” ist nur dann eine wahre Aussage, wenn beide EinzelaussagenA1 und A2 zutreffen. Fur die entsprechende Verknupfung lasst sich eine Wertetabellebzw. Wahrheitstabelle aufstellen. Fur die Konjunktion (Symbol: ^) gilt folgende Wer-tetabelle:

WpA1q WpA2q WpA1q ^ WpA2qfalsch falsch falschfalsch wahr falschwahr falsch falschwahr wahr wahr

Vereinfachung

Wahr und falsch wird durch w und f oder durch 1 und 0 dargestellt. w und f sindinnerhalb der Aussagenlogik ublich, 1 und 0 in der formalen Logik. Fur die Wertetabelleder Konjunktion oder UND-Verknupfung gilt dann:

WpA1q WpA2q WpA1q ^ WpA2q0 0 00 1 01 0 01 1 1

Logische Operationen

Entsprechend der Wertetabelle fur die Konjunktion, lasst sich eine Tabelle fur alle ande-ren zusammengesetzten Aussagen aufstellen. Diese Verknupfungen werden auch logischeOperationen genannt. Entsprechend der Anzahl der Wahrheitswerte oder Operanden,die miteinander verknupft werden, spricht man von ein-, zwei- oder allgemein n-stelligenOperationen. Die Konjunktion ist ein Beispiel fur eine zweistellige Operation.

2

REV

1468

Negation

Aussagen lassen sich auch verneinen. Dementsprechend gibt es in der Aussagenlogik dieeinstellige Operation der Negation (Symbol: ).

Erkenntnis

Die Aussagenlogik untersucht die formalen Zusammenhange zwischen Aussagen. Diesekonnen entweder wahr oder falsch sein.

1.1.2 Grundverknupfungen

Logische Operationen

Die Grundverknupfungen werden als logische Operationen durch Symbole dargestellt.Fur die veranderlichen Operanden wird der Begriff der logischen Variablen eingefuhrt.

Definition 2. Ein Zeichen, welches anstelle eines Elementes aus t0, 1u steht, heißtlogische Variable. Eine Zuordnung konkreter Werte zu den Variablen heißt Belegung derVariablen.

Schaltalgebra

Eine Sonderform der Booleschen Algebra ist die Schaltalgebra. Mit ihrer Hilfe lassen sichDigitalschaltungen berechnen und vereinfachen. Die Schaltalgebra kennt Variablen undKonstanten. Es gibt nur zwei mogliche Konstanten: 0 und 1. Die Konstanten entsprechenden logischen Zustanden 0 und 1. Eine Variable kann entweder den Wert 0 oder 1annehmen. Jede Große, mit Wert 0 oder Wert 1, stellt eine Variable dar. Ausdruckewie (a^ b), die z. B. aus zwei Variablen bestehen, konnen wie eine Variable behandeltwerden, denn ihr Wert kann ebenfalls nur 0 oder 1 sein. Eine Variable der Schaltalgebraist also eine binare Große.

3

REV

1468

Operation Symbolik Bindeworter Wahrheitstabelle

Negation a nicht aa a0 11 0

Konjunktion a^ b, a b a und b

a b a^ b0 0 00 1 01 0 01 1 1

Disjunktion a_ b, a b a oder b

a b a_ b0 0 00 1 11 0 11 1 1

Aquivalenz a b, a Ø b a aquivalent b

a b a b0 0 10 1 01 0 01 1 1

Antivalenz a b, a` b a antivalent b

a b a b0 0 00 1 11 0 11 1 0

Implikation a Ñ b a impliziert b

a b a Ñ b0 0 10 1 11 0 01 1 1

Sheffer-Funktion (NAND) a^ b, a b, a|b a und b nicht

a b a^ b0 0 10 1 11 0 11 1 0

Peirce-Funktion (NOR) a_ b, a b, a Ó b weder a noch b

a b a_ b0 0 10 1 01 0 01 1 0

2-stellige Operationen

Neben den Grundverknupfungen sind weitere Verknupfungen zwischen a und b denk-bar. In einer Wertetabelle fur zwei Operanden kann jede beliebige Kombination von

4

REV

1468

a b a^

b

a b a

b

a_

b

a_

b

a

b

b a aÑ

b

a^

b

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Tabelle 1.1: mogliche Kombinationen 2-stelliger logischer Operationen

0-1-Werten eingesetzt werden, was eine zweistellige Operation ergibt. Nicht alle dieseOperationen haben einen Namen oder eine symbolische Bezeichnung. Es ergeben sich222 16 Moglichkeiten (siehe Tabelle 1.1).


Fur einstellige Operationen, wie z.B. die Negation ergeben sich 221 4 Moglichkeiten:

a a a0 0 0 1 11 0 1 0 1


Konstanten werden als nullstellige Operationen bezeichnet. Es existieren 220 2 ver-schiedene Anordnungen von 0 und 1. Die Konstanten haben somit die Werte 0 (Kontra-diktion/nie) oder 1 (Tautologie/immer).

1.1.3 Ausdrucke

n-stellige Operationen

Verknupfungen von nur zwei Operanden sind im Allgemeinen nicht ausreichend und beimehrstelligen Operationen wachst die Zahl der moglichen Verknupfungen rasch an. Bein-stelligen Operationen ergeben sich 2n verschiedene Moglichkeiten fur die Belegung derVariablen. Diesen Belegungen konnen wieder 22n 0-1-Kombinationen als Ergebnisse zu-geordnet werden. Mehr als zweistellige Operationen lassen sich durch 1- und 2-stelligeOperationen ausdrucken. Die Grundverknupfungen genugen, um samtliche weiteren logi-schen Zusammenhange zu beschreiben. Dazu kombiniert man verschiedene Operationen,was zum Begriff des Ausdrucks fuhrt.

Definition 3. Eine Verknupfung von endlich vielen Konstanten und logischen Variablenmittels Grundverknupfungen heißt ein Ausdruck. Die Reihenfolge, in der Operationenanzuwenden sind, wird durch Klammern bestimmt. Ausdrucke die nur aus den Operatio-nen (Negation), ^ (Konjunktion) und _ (Disjunktion) zusammengesetzt sind, heißenboolesche Ausdrucke.

5

REV

1468

Beispiel 2. Ausdruckeapa^ bq _ 1pa Ñ bq ^ pc Ó aqppppa_ b Ø cq ` aq _ cqppa^ bq _ pa^ bqqpppa^ bq _ pb^ cqq ^ 1kein Ausdruck ist:a Ñ b` cweil die Reihenfolge der Operationen nicht eindeutig ist

Ermittlung des Wahrheitswerts eines Ausdrucks

Die aktuellen Variablenwerte werden in den Ausdruck eingesetzt und schrittweise derKlammerung entsprechend abgearbeitet. Dabei werden jeweils die Grundverknupfungendurch den Wahrheitswert ersetzt, der durch die zugehorige Wertetabelle gegeben ist.

Beispiel 3. Mit a 1, b 0, c 1 gilt fur den Wahrheitswert des Ausdruckspa Ñ bq ^ pc Ó aq :

pa Ñ bq ^ pc Ó aq p1 Ñ 0q ^ p1 Ó 1q 0^ 0 0

Soll der Ausdruck vollstandig durch eine Wertetabelle beschrieben werden, ist es meistsinnvoll, auch Zwischenschritte mit in der Tabelle zu notieren.

Beispiel 4. Die Verknupfung pa Ñ bq ^ pc Ó aq soll durch eine Wertetabelle vollstandigbeschrieben werden:

a b c pa Ñ bq pc Ó aq pa Ñ bq ^ pc Ó aq0 0 0 1 1 10 0 1 1 0 00 1 0 1 1 10 1 1 1 0 01 0 0 0 0 01 0 1 0 0 01 1 0 1 0 01 1 1 1 0 0

Aquivalente Ausdrucke

Definition 4. Zwei Ausdrucke A1, A2 heißen aquivalent (A1 = A2) genau dann, wennsie bei gleicher Belegung gemeinsamer Variablen stets gleiche Wahrheitswerte annehmen.A1 = A2 heißt dann eine logische Gleichung.

Dabei ist nicht gefordert, dass beide Ausdrucke genau dieselben Variablen enthalten.

6

REV

1468

Beispiel 5. Seien a, b, c logische Variable.Behauptung: a_ pb^ bq a_ pc^ cqBeweis (durch Wertetabelle):

a b c pa_ pb^ bqq a_ pc^ cq0 0 0 0 00 0 1 0 00 1 0 0 00 1 1 0 01 0 0 1 11 0 1 1 11 1 0 1 11 1 1 1 1

Beide Ausdrucke hangen weder von b noch von c ab, und gerade dann gilt auch nur dieAquivalenz unter derartigen Ausdrucken. Solche uberflussigen (redundante oder fiktive)Variablen konnen eliminiert werden.

Vorrangregeln

Bei komplexeren Ausdrucken kann die Zahl der Klammern stark zunehmen. Zur Vermei-dung zahlreicher Klammern werden unter den wichtigsten Grundverknupfungen, Vorr-angregeln eingefuhrt. Das geschieht ahnlich wie unter den arithmetischen Rechenarten(”Punktrechnung vor Strichrechnung”, etc.).

Definition 5. Bei der Ausfuhrung von Operationen in logischen Ausdrucken gelten fol-gende Prioritaten: Geklammerte Verknupfungen haben Vorrang vor Negation ( ) hatVorrang vor Konjunktion (^) hat Vorrang vor allen anderen Operationen. Reicht dasNegationszeichen ( ) uber mehrere Variable oder Konstante, gelten diese als geklam-mert und die Negation gilt fur den Klammerausdruck. Bei mehreren aufeinanderfolgen-den zweistelligen Grundverknupfungen gleicher Vorrangstufe, also bei Hintereinander-ausfuhrung gleicher Verknupfungen, wird von links nach rechts abgearbeitet. Das Kon-junktionszeichen kann weggelassen werden, wenn keine Verwechslungen mit anderen Va-riablen moglich sind.

Beispiel 6. Seien a, b, c, d logische Variablen.a_ pb^ cq a_ b^ c a_ bc,pa^ bq _ pc^ dq ab_ cd,a Ñ b Ñ c pa Ñ bq Ñ c,pa_ bq ^ pa_ cq pa_ bqpa_ cq,aber:a^ b a b ab

7

REV

1468

1.1.4 Umformung logischer Ausdrucke

Regeln zur Vereinfachung und Umformung gegebener Ausdrucke

Es wird sich auf boolesche Ausdrucke beschrankt, weil es fur diese Ausdrucke eine ent-sprechende algebraische Struktur gibt, namlich die Boolesche Algebra. Andererseits las-sen sich alle anderen Operationen als boolesche Ausdrucke schreiben. Beweisen lassensich diese Regeln in einfachster Weise durch Vergleich der Wertetabellen der Ausdruckeauf beiden Seiten der Gleichung.

Satz 1. Seien a, b, c logische Variablen, dann gelten folgende Regeln:

Name Gesetzmaßigkeit

Negation der Negation a a

Kommutativgesetz a^ b^ c c^ a^ ba_ b_ c c_ a_ b

Assoziativgesetz a^ pb^ cq pa^ bq ^ ca_ pb_ cq pa_ bq _ c

Distributivgesetz a^ pb_ cq pa^ bq _ pa^ cqa_ pb^ cq pa_ bq ^ pa_ cq

Idempotenzgesetz a^ a aa_ a a

Komplementgesetz a^ a 0a_ a 1

0-1-Gesetz a^ 1 aa^ 0 0a_ 1 1a_ 0 a

Absorptionsgesetze a^ pa_ bq aa_ pa^ bq apa^ bq _ pa^ bq apa_ bq ^ b a^ bpa^ bq _ b a_ bpa_ bq ^ pa_ bq a

De Morgan’sche Regeln a^ b a_ ba_ b a^ b

8

REV

1468

Beweis 1. Der Beweis erfolgt durch Wertetabelle. Exemplarisch soll er hierfur das vor-letzte Absorptionsgesetz durchgefuhrt werden.pa^ bq _ b a_ b

a b a^ b pa^ bq _ b a_ b0 0 0 0 00 1 0 1 11 0 1 1 11 1 0 1 1

Die Spalten fur pa^ bq _ b und a_ b stimmen uberein (was zu zeigen war).

Vereinfachung komplexer boolescher Ausdrucke

Die angefuhrten Regeln erlauben, komplizierte boolesche Ausdrucke haufig zu vereinfa-chen.

Beispiel 7. pa_ bqa bppa_ bqpa_ bq _ pca_ cqq De Morgan’sche Regel

pa_ bqpa_ bqppa_ bqpa_ bq _ pca_ cqq Absorptionsgesetz apa_ pca_ cqq Absorptionsgesetz a

Beispiel 8. x_ yz_ px^ yzq yz_ x_ px^ yzq yz_ px_ xq ^ px_ yzq yz_ 1^ px_ yzq yz_ px_ yzq yz_ yz_ x 1_ x 1

Logische Gleichungen lassen sich in analoger Weise beweisen, denn bei mehr als 3 Va-riablen wird der Beweis mittels Wertetabelle recht aufwandig.

1.1.5 Formal wahre, formal falsche Ausdrucke

Ein haufig beschrittener Weg zur Vereinfachung von Ausdrucken ist die Suche nach“Teilausdrucken”, die immer logisch 0 oder immer 1 sind, um anschließend die 0-1-Gesetze anzuwenden.

Definition 6. Ein Ausdruck heißt formal wahrer Ausdruck, wenn er fur jede Belegungden Wahrheitswert 1 liefert. Ein Ausdruck heißt formal falsch, wenn er fur jede Belegungden Wahrheitswert 0 liefert.

9

REV

1468

Beispiel 9.Formal wahre Ausdrucke: Formal falsche Ausdrucke:a_ a 1 a^ a 0

ab_ ab_ ab_ ab 1 pab_ ab_ ab_ abq 0pa Ñ bq _ pb Ñ aq 1 a` a 0pa Ø bq _ pa Ø bq 1 a^ b^ c^ 0 0pa^ bq _ 1 1

Tautologie, Kontradiktion

Bei formal wahren/falschen Ausdrucken handelt es sich in der Aussagenlogik um Aus-sagen, die immer zutreffen mussen (formal wahr) oder nie zutreffen konnen (formalfalsch). Die Behauptung “n=m oder n m” (a_ a) trifft immer zu, unabhangig vonden Werten der Einzelaussagen “(n = m)” und “(n m)”. Immer falsch dagegen ist dieAussage “n=m und n m” (a^ a). Also schon aus der Form des Ausdrucks lasst sichder Wahrheitswert bestimmen. Solche Ausdrucke werden auch Tautologien oder Allge-meingultigkeiten genannt, wenn sie formal wahr sind, bzw. Kontradiktionen im Falleformal falscher Ausdrucke.

Einfache Satze zur Umformungen von Ausdrucken

Der folgende Satz ist eine Verallgemeinerung der De Morgan’schen Regel.

Satz 2. Ein boolescher Ausdruck lasst sich negieren, indem man alle Operatoren _durch ^ und alle ^ durch _ ersetzt und die Konstanten und Variablen negiert. DieKlammerungen bleiben dabei erhalten.

Mit Hilfe de DeMorgan’schen Regeln lasst sich die Gultigkeit gut veranschaulichen:

Beispiel 10. pa1 ^ a2 ^ a3 ^ ...anq a1 _ a2 _ a3 _ ..._ anpa1 _ a2 _ a3 _ ..._ anq a1 ^ a2 ^ a3 ^ ...^ anppa1a2 _ a2a3qpa4 _ a5qq pa1 _ a2qpa2 _ a3q _ a4a5pp1_ a1a2q ^ ppa1 ^ 1q _ 0q p0^ pa1 _ a2qq _ ppa1 _ 0q ^ 1q 0pa1 _ a2q _ pa1 _ 0q1pa1 a2 _ a1a2 _ a1a2 _ a1a2q pa1 _ a2qpa1 _ a2qpa1 _ a2qpa1 _ a2q

Beweis 2. pa1a2a3...anq ppa1a2a3...an1qanq (wegen Vorrangr.)

pa1a2...an1q _ an (De Morgansche Regel)

ppa1...an2qan1q _ an a1 _ a2 _ a3 _ ..._ an

Satz 3. Eine Konjunktion a1 ^ a2 ^ a3 ^ ....^ an ist fur eine Belegung pa1, a2, ..., anqfalsch genau dann, wenn es (mindestens) ein i gibt mit ai 0, i P 1, 2, ..., n. Eine Dis-junktion a1 _ a2 _ ..._ an ist fur eine Belegung pa1, a2, ..., anq richtig genau dann, wennes (mindestens) ein i gibt mit ai 1, i P 1, 2, ..., n.

10

REV

1468

Der Satz kann naturlich auch umgekehrt formuliert werden:

Satz 4. Eine Konjunktion a1 ^ a2 ^ ..^ an ist genau dann wahr, wenn alle Variablenai mit 1 belegt sind. Eine Disjunktion a1 _ a2 _ .._ an ist genau dann falsch, wenn alleVariablen ai mit 0 belegt sind.

Diese Aussagen werden spater bei der Behandlung der Normalformen benotigt.

1.2 Logische Funktionen und Funktionsbundel

1.2.1 Logische Funktionen

Begriff der logischen Funktionen

Ein logischer Ausdruck beschreibt eine Zuordnung zwischen einer Belegung der Variablenund den Wahrheitswerten 0 und 1. Das Ergebnis ist eine Funktion der (unabhangigen)Variablen.

Definition 7. n-stellige logische FunktionSei D t0, 1un, n P N und pa1, a2, ..., anq P D eine Belegung. t0, 1un ist Menge allern Tupel pa1, a2, ..., anq mit ai P t0, 1qu fur alle i 1, 2, ...., n Eine Zuordnungsvorschriftf : D Ñ t0, 1u mit pa1, . . . , anq ÞÑ fpa1, a2, . . . , anq heißt n-stellige logische Funktion oderlogische Funktion genau dann, wenn f eindeutig ist, d.h. jeder Belegung pa1, a2, ..., anq P Dwird genau ein Wert fpa1, a2, ..., anq P t0, 1u zugeordnet. fpa1, a2, ..., anq heißt Funktions-wert, D heißt Definitionsbereich, die Elemente aus D heißen Argumente der Funktion. IstD t0, 1un, so heißt f vollstandig definiert. Ist D t0, 1un, so heißt f partiell definiert.

Partiell definierte logische Funktionen

Eine logische Funktion muss also nicht fur jede Belegung ihrer Variablen definiert sein(D t0, 1un, partiell definierte logische Funktionen), was spater im Zusammenhang mitDon’t-care-Bedingungen in der Schaltalgebra interessant wird. Eine logische Funktionkann praktisch durch eine Wertetabelle (auch Funktionstabelle genannt) oder durcheinen logischen Ausdruck angegeben werden.

Beispiel 11. Vollstandig definierte Funktionenx1 x2 gpx1, x2q0 0 00 1 11 0 01 1 0

fpa, b, cq a_ b Ñ c

Durch logische Ausdrucke konnen nur vollstandig definierte Funktionen angegeben wer-den.

11

REV

1468

Funktionsgleichung

Eine Funktion kann auch durch eine abhangige Variable definiert werden, die selbstin einer Funktion als Variable auftritt. Auf diese Art lassen sich logische Funktionenverschachteln oder verknupfen.

Beispiel 12. Funktionsgleichungy fpa, bqz gpa, c, yq gpa, c, fpa, bqq

Man spricht hierbei auch von Funktionsgleichungen. Diese werden im Zusammenhangmit der Analyse und Synthese von großeren Schaltnetzen zur besseren Ubersicht benutzt.

Dezimales Aquivalent

Unter der Voraussetzung, nur vollstandig definierte Funktionen zu betrachten, gilt,dass es 22n verschiedene n-stellige Funktionen gibt. Wegen der hohen Anzahl hat manKurzschreibweisen fur diese Funktionen eingefuhrt. Es wird der Begriff des dezimalenAquivalents einer Belegung (oder eines logischen Vektors) eingefuhrt.

Definition 8. Dezimales AquivalentSei pa1, . . . , anq eine Folge logischer Konstanten. δpa1a2 . . . anq i P N0 heißt das dezimaleAquivalent zu pa1, a2, . . . , anq, wobei

i °n1j0 bj2

j und bj 1 falls anj 10 falls anj 0

mit bj P N0

N0 : Menge der naturlichen Zahlen, einschließlich der Null

Die Definition sagt, dass die Folge logischer Werte so wie sie dasteht als Dualzahlbn1bn2 . . . b0 aufgefasst wird und als naturliche Zahl im Dezimalsystem wiedergege-ben wird. Umweg uber bj ist notig, um Konfusionen zwischen den Wahrheitswerten 0,1 und den naturlichen Zahlen 0, 1 zu vermeiden. Die lexikographische Anordnung derBelegungen logischer Variablen bedeutet nur, die Belegungen als Dualzahlen zu lesenund sie dann in aufsteigender Reihenfolge zu schreiben (siehe Kapitel 2).

Beispiel 13. Dezimale Aquivalenteδp000q 0δp0010q 2δp10010q 18

1.2.2 Vollstandige Systeme

Darstellung der Grundverknupfungen

Eine logische Funktion kann durch verschiedene zueinander aquivalente Ausdrucke an-gegeben werden.

12

REV

1468

Satz 5. Aquivalenzen zu GrundverknupfungenSeien x1, x2 logische Variable, dann gilt:fpx1, x2q x1 ^ x2 px1 _ x2qfpx1, x2q x1 ` x2 x1x2 _ x1x2 px1 _ x2q _ px1 _ x2qfpx1, x2q x1 _ x2 px1 ^ x2qfpx1, x2q x1 _ x2 x1 ^ x2fpx1, x2q x1 Ø x2 x1x2 _ x1x2 px1 _ x2q _ px1 _ x2qfpx1, x2q x1 Ñ x2 px1 _ x2q x1 _ x2fpx1, x2q x1 ^ x2 x1 _ x2

Beweisen lassen sich diese Behauptungen durch Wertetabellen und die logischen Gesetze.Die Gleichungen zeigen, dass sich alle Grundverknupfungen durch ^,_, ausdruckenlassen, dass sogar _ und genugen, um alle Grundverknupfungen darzustellen.

Satz 6. Boolescher AusdruckSeien a1, a2, . . . , an logische Variable. Jede vollstandig definierte logische Funktiongpa1, a2, . . . , anq lasst sich als logischer Ausdruck, der nur aus den Grundverknupfungen^,_, zusammengesetzt ist, d.h. als boolescher Ausdruck angeben.

Definition 9. Eine Menge logischer Operationen (O1,O2, . . . ,Okq heißt vollstandigesSystem, wenn sich jede vollstandig definierte logische Funktion nur aus diesen Operatio-nen bilden lasst.

Durch (^,_, ) sind alle booleschen Ausdrucke erfasst. Mit booleschen Ausdrucken las-sen sich also alle logischen Zusammenhange beschreiben. Es gibt naturlich noch weiterevollstandige Systeme. Um Vollstandigkeit zu beweisen genugt es zu zeigen, dass mit denbetrachteten Operationen die Grundverknupfungen ^,_, ausgedruckt werden konnen.

Satz 7. Vollstandige Systeme(^, ) und (_, ) sind vollstandige Systeme.

Beweis 3. Seien a, b logische Variablen.a_ b bzw. a^ b lassen sich mit ^ und bzw. _ und angeben.

(^, ): a_ b a^ b (De Morgansche Regel)

(_, ): a^ b a_ b (De Morgansche Regel)

Satz 8. NOR und NAND bilden jeweils ein vollstandiges System.

Mit einer einzigen Verknupfung lassen sich alle vollstandig definierten Funktionen aus-drucken, was die technische Realisierung vereinfacht. Es muss prinzipiell nur ein Ver-knupfungsglied gebaut werden. Allerdings erhoht sich die Anzahl der Verknupfungsgliederdadurch in der Regel. Dennoch genießt das System (^,_, ) eine gewisse Vorzugsstel-lung, weil es uber diese Verknupfungen eine algebraische Struktur gibt.

13

REV

1468

1.2.3 Funktionsbundel

In der Praxis sind haufig Funktionsbundel zu betrachten. Es handelt sich dabei um eine(endliche) Menge logischer Funktionen, die das gleiche Argument haben.

Beispiel 14.Funktionsbundel werden z.B. bei der Umcodierung eines Binarcodes in einen anderen, wiees z.B. bei der Umformung des BCD-Codes in den 1-aus-10-Code der Fall ist, benotigt.Zur Beschreibung der Ausgange werden zehn verschiedene Funktionen benotigt, die viergemeinsame Variablen an den Eingangen haben. z. B.y1 x1x2x3 _ x1x4y2 x1x4 _ x1x2x3

Definition 10. Eine Zusammenfassung σ logischer Funktionen f1, f2, . . . , fm, die dasgleiche Argument (a1, . . . , an) haben (m, n P N), heißt ein Funktionsbundel oder eine Vek-torfunktion.Schreibweise:σpa1, a2, . . . , anq py1, y2, . . . , ymq

mit

y1 f1pa1, . . . , anqy2 f2pa1, . . . , anq. . .ym fmpa1, . . . , anq

Darstellung von Funktionsbundeln

Die Darstellung von Funktionsbundeln kann durch eine Anzahl m verschiedener logischerAusdrucke gegeben sein oder durch eine Wertetabelle.

Beispiel 15. Funktionsbundel σpa, b, cq px, y, z, tqa b c x y z t0 0 0 1 1 1 00 0 1 1 1 1 10 1 0 1 0 1 00 1 1 0 0 1 01 0 0 0 0 0 11 0 1 1 0 0 01 1 0 1 0 0 01 1 1 1 1 0 1

Anwendung

Durch das Zusammenfassen mehrerer Funktionen zu einem Funktionsbundel kann bei-spielsweise der Hardwareaufwand minimiert werden. Gibt es in mehreren der beteiligtenFunktionen (logischen Ausdrucken) gemeinsame Teile, kann dieser Teil von mehrerenFunktionen gleichzeitig benutzt werden. Dies ermoglicht eine Einsparung von Hardware

14

REV

1468

und Verlustleistung bei der technischen Realisierung. Bisher existiert kein allgemeinerAlgorithmus zur effizienten Berechnung optimaler Losungen von mehrstufigen Schalt-netzen.

1.3 Das Karnaugh-Veitch-Diagramm

Graphische Darstellung

Zur Veranschaulichung logischer Funktionen eignen sich graphische Darstellungen bzw.Diagramme. Eine gute Verbildlichung ist das Karnaugh-Veitch-Diagramm(KV-Diagramm). Diese grafische Form ist vorteilhaft bei der Behandlung der Normalfor-men, die daraus zum Teil direkt abgelesen werden konnen. Das KV-Diagramm ist eineMatrix von Wahrheitswerten. Jedem Element der Matrix ist eindeutig eine Belegung derVariablen der Funktionen zugeordnet, die am Rand des Schemas eingetragen werden.

Beispiel 16. KV-Diagramm mit zwei Variablen

fpa, bq a_ b

δpbaq b a fpa,bq

0 0 0 01 0 1 12 1 0 13 1 1 1

fpa, bqfp0,0q

0

fp0,1q1

fp1,0q2

fp1,1q3

b

a fpa, bq

00

11

12

13

b

a

Beispiel 17. KV-Diagramm mit drei Variablen

gpa, b, cq ab_ ab_ abc

δpcbaq c b a gpa,

b,cq

0 0 0 0 01 0 0 1 12 0 1 0 03 0 1 1 14 1 0 0 15 1 0 1 16 1 1 0 07 1 1 1 1

gpa, b, cq

00

11

02

13

14

15

06

17

c

b

a

Anordnung bei mehr als einer Variable pro Zeile /Spalte

Bei mehr als einer Variable pro Spalte oder Zeile kann man die Bezeichnung auch alsVektor der Eingangvariablen betrachten (im Beispiel a und c bei den Spalten). Die Bele-gungen der Vektoren werden nicht lexikographisch (d.h. entsprechend dem Dualcode) an-geordnet, sondern entsprechend dem Graycode (ra, csSpalte ñ r0, 0s0, r0, 1s1, r1, 1s2, r1, 0s3)ahnlich wie der Dualcode ist auch der Graycode eine Codierung mit 0 und 1. Der Gray-code hat aber die Eigenschaft, sich in der Darstellung von benachbarten Zahlen nur in

15

REV

1468

einer Stelle zu unterscheiden (Hammingdistanz gleich 1). In den Zeilen bzw. Spaltenstehen nur Belegungen nebeneinander, die sich nur in einer Stelle unterscheiden. Dasgilt sogar zwischen dem ersten und letzten Element einer Zeile bzw. Spalte. Man kannAnfang und Ende einer Zeile oder Spalte als benachbart ansehen. Gerade diese sys-tematische Anordnung ermoglicht die Benutzung dieser Diagramme zur Vereinfachunglogischer Ausdrucke (Minimierung). Mit Zunahme der Variablenzahl werden die Ma-trizen abwechselnd nach unten und rechts “umgeklappt”, wodurch sich die Zahl ihrerElemente jeweils verdoppelt.

1-Muster oder 0-Muster

Um Wahrheitswerte eindeutig in ein KV-Diagramm einzutragen, genugt es, entwedernur die 1-Werte oder nur die 0-Werte einzutragen. Es entsteht ein sogn. 1-Muster oder0-Muster. Vielfach schraffiert man auch nur die Kastchen, die eine 1 tragen.

Ubertragung einer Funktion in ein KV-Diagramm

Eine Funktion kann durch Wertetabelle oder logischen Ausdruck angegeben werden.Liegt die Funktion als Wertetabelle vor, ist die Ubertragung in das KV-Diagramm ein-fach. Man sucht zu jeder Belegung die entsprechende Stelle und tragt den Wahrheitswertder Funktion ein. Bei unvollstandig definierten Funktionen, werden in den entsprechen-den Stellen “-” (“don’t-care”) eingetragen

Beispiel 18. Nicht vollstandig definierte Funktionδpcbaq d c b a fpa, b, c, dq

0 0 0 0 0 11 0 0 0 1 12 0 0 1 0 13 0 0 1 1 -4 0 1 0 0 05 0 1 0 1 16 0 1 1 0 17 0 1 1 1 08 1 0 0 0 19 1 0 0 1 1

10 1 0 1 0 -11 1 0 1 1 -12 1 1 0 0 013 1 1 0 1 -14 1 1 1 0 015 1 1 1 1 1

fpa, b, c, dq

10

11

12

-3

04

15

16

07

18

19

-10

-11

012

-13

014

115d

c

b

a

16

REV

1468

Vorgehensweise bei der Funktionsbeschreibung

Sind boolesche Ausdrucke gegeben, um eine Funktion zu beschreiben, lasst sich jederWert einzeln bestimmen und eintragen. Prinzipiell ist jeder boolesche Ausdruck entwederals eine Disjunktion oder als eine Konjunktion anzusehen, abgesehen von einer Negationdes gesamten Ausdrucks. Eine Disjunktion ist immer dann wahr, wenn mindestens eineder Komponenten, aus der die Disjunktion besteht, gleich 1 ist. Somit konnen fur dieeinzelnen Komponenten einer Disjunktion die 1-Werte nacheinander eingetragen werden.

Beispiel 19. Disjunktive Funktion

fpa, b, c, dq a b c c d

fpa, b, c, dq

10

11

12

13

41

5

16

17

18

19

110

111

112

113

114

115d

c

b

a

Eine Konjunktion ist immer dann falsch, wenn mindestens eine der Komponenten derKonjunktion gleich 0 ist. Analog zu Disjunktionen werden nur die 0-Werte zu jedereinzelnen Komponente eingetragen.

Beispiel 20. Konjunktive Funktion

gpa, b, c, dq a b c pc dq

gpa, b, c, dq

00

01

02

03

04

05

06

07

08

09

010 11

012

013

014

015d

c

b

a

17

REV

1468

2 Zahlendarstellung

2.1 Stellenwertsysteme (B-adische Systeme)

2.1.1 Darstellung naturlicher Zahlen

Jede naturliche Zahl ist durch die folgende Summenformel darstellbar:N an1 Bn1 an2 Bn2 a1 B1 a0 B0 °n1

i0 ai Bi

N = Zahl im entsprechenden Stellenwertsystem mit der Stellenanzahl nB = Basis (Radix), z.B. 10 (dezimal), 2 (dual)Bi = Wertigkeit (Gewicht) der i-ten Stelleai = Ziffer (Koeffizient) der i-ten Stelle aus der Menge der Ziffern 0, 1, 2, . . . ,B-1

2.1.2 Zerlegung nach dem Horner-Schema

N °n1i0 ai Bi p. . . pan1 B an2q B a1q B a0

Man erhalt die Ziffern a0, a1, . . . , an1 dadurch, dass man die Zahl N durch B dividiertund man nach der Division den Rest abtrennt und ihn notiert, d.h. man erhalt zuerst a0.Mit dem Quotienten wird dann in derselben Weise verfahren, bis er nach wiederholterDurchfuhrung verschwindet. Die notierten Ziffern ai stellen dann die Zahl im Stellen-wertsystem zur Basis B dar.

Beispiel 21. Konvertierung ins DualsystemAusgehend vom Dezimalsystem und unter Verwendung der Dezimalarithmetik ist esmoglich mit dem beschriebenen Verfahren Dualzahlen zu erzeugen:

16710 Ñ 167 / 2 = 83 Rest 1 Least Significant Bit, LSB83 / 2 = 41 Rest 141 / 2 = 20 Rest 120 / 2 = 10 Rest 010 / 2 = 5 Rest 05 / 2 = 2 Rest 12 / 2 = 1 Rest 01 / 2 = 0 Rest 1 Most Significant Bit, MSB

Ñ 101001112

Beispiel 22. Ruckkonvertierung ins DezimalsystemEinsetzen der Ziffern (Koeffizienten) in die allgemeine Gleichung zur Zahlendarstellungmit B=2 (Summenformel oder Horner-Schema). Im folgenden Beispiel in Form der Sum-menformel:101001112 1 27 0 26 1 25 0 24 0 23 1 22 1 21 1 20 16710

18

REV

1468

2.2 Vorzeichenlose Zahlen

Vorzeichenlose Dualzahlen (unsigned binary numbers, unsigned integers) werden alsnaturliche Zahlen im Stellenwertsystem 2 mit n Stellen ai folgendermaßen dargestellt:D °n1

i0 ai 2i an1 2n1 an2 2n2 a1 21 a0 20

2.2.1 Addition

Die Addition von Dualzahlen wird durchgefuhrt indem paarweise die Stellen der Sum-manden addiert werden (mit Ubertrag). Angewendet werden folgende Rechenregeln:0+0 = 00+1 = 11+0 = 11+1 = 10

Bei 1+1=10 entsteht eine “1” als Ubertrag (Carry c), die eine zusatzliche Stellebenotigt.

Beispiel 23. Addition:5 6 11 Ñ 0101

0110

1011

5 12 17 Ñ 01011100

10001

2.2.2 Subtraktion

Die Subtraktion von Dualzahlen wird durchgefuhrt indem paarweise die Stellen des Sub-trahenden von denen des Minuenden subtrahiert werden (mit Ubertrag). Angewendetwerden folgende Rechenregeln:0-0 = 00-1 = 11-0 = 11-1 = 0

Bei 0-1=1 wird von der nachsthoheren Stelle eine “1” als Ubertrag geborgt (Borrowb).

Beispiel 24. Subtraktion:12 5 7 Ñ 1100

0101

0111

4 5 1 Ñ 01000101

11111

19

REV

1468

2.2.3 Zahlenbereich

Der Zahlenbereich von Dualzahlen kann als Zahlenring dargestellt werden. In der Abbil-dung 2.1 ist die Zahlenbereichsgrenze eingezeichnet. Wird der Zahlenbereich uberschrit-ten, so ist das an dem Ubertragsbit des hochstwertigen Bits zu erkennen (Carry am MostSignificant Bit).

c

200000010

1

000000010

00000000

255

11111111

25411111110

129

10000001128

10000000

127

01111111

Abbildung 2.1: Zahlenring fur vorzeichenlose Dualzahlen

2.3 Vorzeichenbehaftete Zahlen

Es gibt unterschiedliche Moglichkeiten negative Dualzahlen darzustellen. Ausgangspunktbei der Codierung negativer Zahlen ist die Codierung positiver Dualzahlen. Im Folgen-den werden die verbreitetsten Varianten aufgelistet:

• Vorzeichen-/Betrags-Zahlen (VB-Zahlen):Hochstwertiges (n-tes) Bit bestimmt das Vorzeichen: “0” zeigt eine positive , “1”eine negative Zahl an. Die restlichen n-1 Bits sind codiert wie vorzeichenlose Dual-zahlen und bestimmen den Betrag der Zahl.

• 1-Komplement-Zahlen (1K-Zahlen):Negative Zahlen erhalt man durch das bitweise Invertieren einer vorzeichenlosenDualzahl mit selben Betrag. Hochstwertiges (n-tes) Bit impliziert das Vorzeichen:“0” zeigt eine positive , “1” eine negative Zahl an.

20

REV

1468

• 2-Komplement-Zahlen (2K-Zahlen):Negative Zahlen werden erzeugt indem die entsprechenden positiven Dualzahl bit-weise invertiert wird und anschließend eine “1” addiert wird. Hochstwertiges (n-tes) Bit (Negative n) impliziert das Vorzeichen: “0” zeigt eine positive , “1” einenegative Zahl an.

Beispiel 25. Zahlen mit 4-Bit-Wortlange:positive Zahlen negative Zahlendez. dual dez. VB-Zahl 1K-Zahl 2K-Zahl+0 0 000 -0 1 000 1 111 —+1 0 001 -1 1 001 1 110 1 111+2 0 010 -2 1 010 1 101 1 110+3 0 011 -3 1 011 1 100 1 101+4 0 100 -4 1 100 1 011 1 100+5 0 101 -5 1 101 1 010 1 011+6 0 110 -6 1 110 1 001 1 010+7 0 111 -7 1 111 1 000 1 001

-8 — — 1 000

2.4 2-Komplement-Zahlen

In der Praxis werden (nahezu) ausschließlich vorzeichenbehaftete Zahlen (signed binarynumbers, signed integers) in 2K-Codierung benutzt. Im Stellenwertsystem 2 mit n Stellenai werden sie als ganze Zahlen folgendermaßen dargestellt:Z an1 2n1 °n2

i0 ai 2i (d.h. mit negativem Gewicht fur die Vorzeichenstelle n-1).

2.4.1 Bildung

Das Darstellen einer 2-Komplement-Zahl, d.h. die 2-Komplement-Bildung, folgt der Vor-schrift:Z = pan1 2n1 °n2

i0 ai 2iq an1 2n1 °n2i0 ai 2i

= an1 2n1 °n2i0 ai 2i p2n1 1q p2n1 1q

= an1 2n1 2n1 °n2i0 ai 2i °n2

i0 2i 1

= p1 an1q 2n1 °n2i0 p1 aiq 2i 1

21

REV

1468

Beispiel 26. 2-Komplement-Bildung:011010012 = 10510

Invertierung : 100101102

Addition von Eins : 12-Komplement : 100101112K = 10510

und zuruck:100101112K = 10510

Invertierung : 011010002

Addition von Eins : 12-Komplement : 011010012K = 10510

2.4.2 Addition

Genau wie bei den vorzeichenlosen Dualzahlen, findet die Addition der 2K-Zahlen stel-lenpaarweise statt und es gibt einen Ubertrag. Auch bei 2K-Zahlen kann es zu einerBereichsuberschreitung kommen, diese wird aber zur Unterscheidung von der bei denvorzeichenlosen Dualzahlen Uberlauf (Overflow v) genannt.

Beispiel 27. Addition:5 p4q 1 Ñ 0101

1100

10001

Es gibt keinen Uberlauf, da die beiden ‘obersten’ Ubertrage 1 sind (v 1` 1 0). Eshandelt sich um das korrekte positive Ergebnis: 00012K 110.

2.4.3 Subtraktion

Aquivalent zur Addition erfolgt die Subtraktion der 2K-Zahlen genau so wie bei den vor-zeichenlosen Zahlen. Auch hier findet eine Bereichsuberschreitung bei einem Uberlaufstatt.

Beispiel 28. Subtraktion:p128q 127 255 Ñ 1000 0000

0111 1111

0000 0001

Es gibt einen Uberlauf, da nur einer der beiden ‘obersten’ Ubertrage 1 ist (v 0` 1 1).Es ensteht ein falsches positives Ergebnis: 0000 00012K 110.

2.4.4 Zahlenbereich

Der Zahlenkreis verdeutlicht wie sich der Zahlenbereich, und somit die Grenze an dereine Bereichsuberschreitung stattfinden kann, verschoben hat.

22

REV

1468

Die ‘0’ markiert im Gegensatz zu den vorzeichenlosen Zahlen nicht mehr das untereEnde des Zahlenbereiches, sondern die Mitte, und die Grenze ist zu der anderen Stelledes Zahlenkreises gewandert, an der das hochstwertigste Bit (MSB, negative Bit) seinenWert andert. Die Zahlenbereichsuberschreitung ist am Uberlauf (Overflow v) zu erken-nen.

v

+200000010

+1

000000010

00000000

-1

11111111

-211111110

-127

10000001-128

10000000

+127

01111111

Abbildung 2.2: Zahlenring fur 2-Komplement-Zahlen

2.5 Gray-Code

Neben der Codierung zur Informationsdarstellung und -verarbeitung gibt es weitere Co-dierungsmoglichkeiten bei deren Verwendung andere Randbedingungen im Vordergrundstehen. Bei dem Gray-Code sind diese Bedingungen Sicherheit und Zuverlassigkeit, diedarin Berucksichtigung finden, dass benachbarte Codes sich jeweils durch genau ein Bitunterscheiden. Der Ubergang von einem Code zum nachsten findet somit durch einewohldefinierte Veranderung statt. Fur die Erzeugung des Gray-Code gibt es eine rekur-sive Bildungsvorschrift:

rGi1s2npi1q

0...0

n

Y

Gi

ni

1...1

n

Y

GR

i

ni

, G1

01

21

,i ¥ 1n . . . Anzahl der Codes in Stufe iGRi . . . Gi gespiegelt

23

REV

1468

Den reflektierten Code erhalt man durch Spiegelung in der Zeilenmitte.

Beispiel 29. Gray-Code fur 3 Bit:

Dez. Gray-Code010 000110 001210 011310 010410 110510 111610 101710 100

24

REV

1468

3 Logische Normalformen undPrimtermdarstellung

Logische Normalformen

Eine vollstandig definierte logische Funktion kann durch einen logischen Ausdruck an-gegeben werden. Der logische Ausdruck ist aber nicht eindeutig bestimmt, d. h. es gibtmehrere aquivalente Darstellungen fur eine Funktion. Fur Verfahren oder Algorithmen,die auf eine Funktion angewendet werden sollen, ist es aber meist notig, von einer Stan-darddarstellung der Funktion auszugehen. Solche standardisierten Darstellungsformensind die logischen Normalformen. Die Notwendigkeit einer solchen Vereinheitlichungwird z. B. notwendig, wenn die Aquivalenz von Ausdrucken gezeigt werden soll. Ab-gesehen vom Vergleich mittels Wertetabellen, mussten die Ausdrucke durch aquivalenteUmformungen auf eine gemeinsame Form gebracht werden. Dabei sollte die prinzipielleGestalt der Ausdrucke nach Umformung bekannt sein, um vergleichen zu konnen.

Beispiel 30. Aufzeigen der Aquivalenz zweier Funktionen mittels einer Normalform

f1 pa bq Ñ a c f2 pa cq Ñ a b

a b a c pa cq Ñ a b

a b a c a c a b

a c a b

a b a c

also : f1 f2

Definition 11. TermEinen logischen Ausdruck oder einen Teil eines logischen Ausdruckes, der selbst ein lo-gischer Ausdruck ist, nennt man auch Term. Eine Konjunktion X1 X2 Xn heißtn-stelliger Konjunktionsterm, wenn alle Xi, i P 1, . . . , n, entweder logische Variablen odernegierte logische Variablen sind und jede Variable nur einmal vorkommt. Ein 0-stelligerKonjunktionsterm soll mit der logischen Konstanten 1 identisch sein. Eine DisjunktionX1 X2 Xn heißt n-stelliger Disjunktionsterm, wenn jedes Xi, i P 1, . . . , n, entwe-der logische Variablen oder negierte logische Variablen sind und jede Variable nur einmalvorkommt. Ein 0-stelliger Disjunktionsterm soll mit der Konstanten 0 identisch sein.

Umformung aquivalenter Ausdrucke

Jeder Ausdruck lasst sich aquivalent in einen booleschen Ausdruck umformen, da p,, qein vollstandiges System ist. Fur dieses System stehen eine Menge von Umformungsre-

25

REV

1468

geln zur Verfugung, mit denen gerechnet werden kann. Als Ausgangsposition werden be-stimmte Formen boolescher Ausdrucke genannt. Dabei unterscheidet man hauptsachlichzwei Typen von Normalformen: die disjunktive Normalform (DNF) und die konjunktiveNormalform (KNF).

3.1 Disjunktive Normalform

3.1.1 Allgemeine disjunktive Normalform

Definition 12. Disjunktive Normalform (DNF)Ein logischer Ausdruck der Form K1 K2 Kk, k P N, heißt disjunktive Normal-form (DNF), wenn alle Ki, i P t1, 2, . . . , ku, paarweise verschiedene Konjunktionstermesind. Gilt fpa1, a2, . . . , anq K1 K2 Kk, k, n P N, so heißt K1 K2 Kk ei-ne disjunktive Normalform der Funktion f.

Beispiel 31. Disjunktive Normalformen sind:a b c a c a cx1 x2 x3 x4 x1 x3 x4 x1 x2 x4x y z x y z x y z x y z x y z x y z x y z

Eine DNF ist fur eine gegebene vollstandig definierte Funktion i. A. nicht eindeutigbestimmt.

Beispiel 32. Umformung in DNF

fpa,b,c,dq b pc Ñ a dq b pc a dq b c a b d

b c a b c d/////////// a b c d

a b c a b c a b c d

a b c d a b c d a b c a b c d

a b c d a b c d a b c d a b c d a b c d

Umformung eines logischen Ausdrucks in eine mogliche DNF

1. Umformung des logischen Ausdrucks in einen Booleschen Ausdruck (Eliminierungder Verknupfungen Ñ,,`,NAND,NOR).

2. Anwendung der De Morganschen Regeln (a b a b, a b a b) bis die Ne-gation nur noch bei Variablen auftritt.

3. Anwendung des Distributivgesetzes, des Komplementgesetzes, des 0-1-Gesetzesund des Idempotenzgesetzes.

26

REV

1468

4. Mehrfach auftretende Konjunktionsterme werden nach dem Idempotenzgesetzpa a aq zusammengefasst.

Das Komplementgesetz und das 0-1-Gesetz sind nur zwischen Variablen anzuwenden,die schon durch Konjunktionszeichen miteinander verbunden sind. Es werden dabeimehrfach auftretende Variablen innerhalb dieses Terms eliminiert. Nur so erhalt mandie geforderten Konjunktionsterme. Mit dem Idempotenzgesetz wird erreicht, dass keinKonjunktionsterm mehrfach auftritt. Dieser letzte Schritt erubrigt sich jedoch meist.

Beispiel 33. Umformung in DNF

fpa,b,c,dq a b c d Ñ pa bq pa b c d a b c dq Ñ pa bq pa b c d a b c dq pa bq pa b c d a b c dq a b

pa b c dq pa b c dq a b

a c a d b c b d a b c d a b

Sonderfalle

Eine DNF kann auch aus nur einem einzigen Konjunktionsterm bestehen. Besteht derumzuwandelnde logische Ausdruck nur aus der Konstanten 1, entspricht dies der DNFeines formal wahren Ausdrucks. Fur formal falsche Ausdrucke gibt es keine DNF.

3.1.2 Kanonische disjunktive Normalform

Problem

Die DNF eines logischen Ausdrucks i. A. nicht eindeutig bestimmt ist, was zu Schwierig-keiten beim Vergleich logischer Funktionen fuhrt. Es gibt aber eine ausgezeichnete oderkanonische disjunktive Normalform, die diese Schwierigkeit umgeht.

Definition 13. Kanonische disjunktive Normalform (KDNF)Erweiterung einer disjunktiven Normalform zu einer vollstandig definierten n-stelligenlogischen Funktion heißt kanonisch (oder ausgezeichnet) (KDNF), wenn jeder der vor-handenen Konjunktionsterme alle n Variablen enthalt und nur einmal auftritt.

Umformung der DNF zu KDNF

Die kanonische disjunktive Normalform (KDNF) ist fur jede vollstandig definierte lo-gische Funktion eindeutig bestimmt. Sie hat aber die unangenehme Eigenschaft, die

”langste“ DNF der jeweiligen Funktion zu sein. Jeder Konjunktionsterm ist n-stellig,

falls die Funktion n-stellig ist, enthalt also alle Variablen. Die kanonische disjunktiveNormalform kann aus jeder beliebigen DNF gewonnen werden. Die Konjunktionsterme,

27

REV

1468

die noch nicht alle Variablen enthalten, werden mit dem Komplementgesetz pa a 1qum die nicht vorhandenen Variablen erweitert. Dabei entsteht naturlich noch jeweils einweiterer Konjunktionsterm. Mehrfach auftretende Konjunktionsterme werden nach demIdempotenzgesetz pa a aq zusammengefasst.

Schritte zur Umformung DNF in KDNF

Gegeben sei eine DNF einer n-stelligen Funktion.

1. Jeder Konjunktionsterm, der nicht n-stellig ist, wird konjunktiv mit dem Termpaj ajq verknupft, wobei aj eine Variable ist, die in diesem Konjunktionstermnicht enthalten ist.

2. Auf den so erhaltenen neuen Konjunktionsterm wird dasDistributivgesetz pK paj ajq K aj K ajq angewandt.

3. Mehrfach auftretende Terme werden nach den Idempotenzgesetzen zusammenge-fasst

Wiederholte Anwendung der vorstehenden Schritte liefert die KDNF.

Beispiel 34. Umformung DNF in KDNF

fpa,b,cq a b

a pb bq pa aq b

a b a b a b a b

a b a b a b

a b pc cq a b pc cq a b pc cq a b c a b c a b c a b c a b c a b c

Aufstellung der KDNF fur Funktionen, die durch Wertetabellen gegeben sind

Die Konjunktionsterme einer KDNF werden auch Minterme genannt. Es gibt 2n Min-terme bei n Variablen, namlich so viele Minterme, wie es Belegungen gibt.

Definition 14. Ein n-stelliger Konjunktionsterm uber n Variablen a1, a2, . . . , an heißtn-stelliger Minterm.

28

REV

1468

Beispiel 35. Wertetabellen einiger Mintermed c b a abcd abcd

0 0 0 0 0 0 01 0 0 0 1 0 02 0 0 1 0 0 03 0 0 1 1 0 04 0 1 0 0 0 05 0 1 0 1 0 06 0 1 1 0 0 07 0 1 1 1 0 08 1 0 0 0 0 19 1 0 0 1 0 0

10 1 0 1 0 0 011 1 0 1 1 0 012 1 1 0 0 0 013 1 1 0 1 1 014 1 1 1 0 0 015 1 1 1 1 0 0

Mit dieser Kenntnis uber Minterme lasst sich nun leicht eine KDNF aus der Werte-tabelle einer vollstandig definierten Funktion ableiten. Da ein Minterm immer nur fureine Belegung den Wert 1 annimmt, steht jeder Minterm in einer KDNF fur genau eineBelegung, bei der die gesamte disjunktive Normalform eine 1 liefert (0-1-Gesetz). DieAnzahl der Minterme gibt dabei an, wie oft der Wahrheitswert 1 im Ergebnisvektor derzugehorigen Funktion steht.

Aufstellung einer kanonischen disjunktiven Normalform aus der Wertetabelle:

Gegeben sei die Wertetabelle einer vollstandig definierten logischen Funktion, die 0ist.

1. Zu jeder Belegung, die den Funktionswert 1 hat, wird der Minterm ermittelt, indemdie Variablen, die in dieser Belegung 0 sind, als negierte Variablen und die, die 1sind, als einfache Variablen konjunktiv verknupft werden.

2. Die Disjunktion dieser Minterme ist die KDNF der gegebenen Funktion.

Die KDNF wird um so langer, je haufiger der Wert 1 im Ergebnisvektor auftritt. Wegendes Kommutativgesetzes ist die Reihenfolge der Minterme in der KDNF gleichgultig. Esist aber ublich, die Minterme nach aufsteigenden Indizes i aufzuschreiben. Die Reihen-folge der Variablen in den Mintermen ist dabei stets gleich.

29

REV

1468

Beispiel 36. KDNF aus Wertetabelle:c b a fpa, b, cq Minterm

0 0 0 0 01 0 0 1 02 0 1 0 1 abc3 0 1 1 1 abc4 1 0 0 0

5 1 0 1 1 abc6 1 1 0 07 1 1 1 1 abc

fpa, b, cq abc abc abc abc

3.2 Konjunktive Normalform

3.2.1 Allgemeine konjunktive Normalform

Definition 15. Ein logischer Ausdruck der FormD1 D2 Dk, k P N, heißt konjunktive Normalform (KNF), wenn alleDi, i P t1, 2, . . . , ku paarweise verschiedene Disjunktionsterme sind.Gilt fpa1, a2, . . . , anq D1 D2 Dk, k, n P N, so heißt D1 D2 Dk eine konjunkti-ve Normalform der Funktion f.

Beispiel 37. Konjunktive Normalformen sind:

1. pa b cq pa cq pa b cq2. px1 x2 x3 x4q px1 x3 x4q px2 x3 x4q x1

3. px y zq px y zq px y zq px y zq px y zq px y zqpx y zq px y zq

Auch die KNF ist fur eine Funktion i. A. nicht eindeutig bestimmt.

Beispiel 38.

fpa, b, c, dq b pc Ñ a dq b pc a dq b c a b d

pb c aq pb c bq pb c dq pb aq pc aq b pb dq pc dq pc bq pa b cq pa b cq pc aq b pb dq pc dq pa b c dq pa b c dq pa b cq pc aq b pb dq pc dq

30

REV

1468

Umformung eines logischen Ausdrucks in eine mogliche KNF

1. Umformung des logischen Ausdrucks in einen Booleschen Ausdruck (Eliminierungder Verknupfungen Ñ,,`,NAND,NOR).

2. Anwendung der De Morganschen Regeln, bis Negation nur noch bei einzelnenVariablen auftritt.

3. Anwendung des Distributivgesetzes, des Komplementgesetzes, des 0-1-Gesetzesund des Idempotenzgesetzes.

4. Mehrfach auftretende Disjunktionsterme werden nach dem Idempotenzgesetz zu-sammengefasst. Komplementgesetz und 0-1-Gesetz mussen angewandt werden, uminnerhalb der einzelnen Disjunktionen zu erreichen, dass jede Variable nur einmalauftritt.

Sonderfalle

Die konjunktive Normalform kann auch aus nur einem Disjunktionsterm bestehen. An-dererseits braucht ein Disjunktionsterm nicht mehr als eine Variable zu enthalten. Dasbedeutet aber, dass die DNF fpa, b, c, dq a b c d ebenfalls eine konjunktive Normal-form ist, und zwar sogar die ”kurzeste”. Die Konstante 0 ist eine KNF eines formalfalschen Ausdrucks. Fur formal wahre Ausdrucke lasst sich keine KNF konstruieren. Dieangegebenen Regeln zur Gewinnung der Normalformen fuhren nicht automatisch zurminimalen Form.

3.2.2 Kanonische konjunktive Normalform

Definition 16. Eine konjunktive Normalform einer vollstandig definierten n-stelligenlogischen Funktion heißt kanonisch (oder ausgezeichnet)(KKNF), wenn jeder der auftre-tenden Disjunktionsterme alle n Variablen enthalt und nur einmal auftritt.

Die Herleitung der KKNF aus einer beliebigen KNF geschieht auch hier durch Er-weitern der Disjunktionsterme um nicht vorhandene Variablen. Anschließend werdenmehrfach auftretende Disjunktionsterme wieder zusammengefasst.

Schritte zur Umformung KNF in KKNF

Gegeben sei eine KNF einer n-stelligen Funktion.

1. Jeder Disjunktionsterm, der nicht n-stellig ist, wird disjunktiv mit dem Termpaj ajq verknupft, wobei aj eine Variable ist, die in diesem Disjunktionsterm nichtenthalten war.

2. Auf den so erhaltenen neuen Disjunktionsterm wird das DistributivgesetzD paj ajq pD ajq pD ajq angewandt.

31

REV

1468

3. Mehrfach auftretende Terme werden nach den Idempotenzgesetzen zusammenge-fasst.

Wiederholte Anwendung der vorstehenden Regeln liefert die KKNF.

Beispiel 39. Umformung von KNF in KKNF

fpa, b, cq a b

pa pb bqq pb pa aqq pa bq pa bq pb aq pb aq pa bq pa bq pa bq ppa bq pc cqq pa b pc cqq ppa bq pc cqq pa b cq pa b cq pa b cq pa b cq pa b cq pa b cq

(3.1)

Den Mintermen bei den KDNF entsprechen die Maxterme oder Volldisjunktionen beiden KKNF. Die Disjunktionsterme einer KKNF heißen Maxterme und liefern fur genaueine Belegung eine 0, sonst immer 1.

Beispiel 40. Wertetabellen einiger Maxtermed c b a a b c d a b c d

0 0 0 0 0 1 11 0 0 0 1 1 12 0 0 1 0 0 13 0 0 1 1 1 14 0 1 0 0 1 15 0 1 0 1 1 16 0 1 1 0 1 17 0 1 1 1 1 08 1 0 0 0 1 19 1 0 0 1 1 1

10 1 0 1 0 1 111 1 0 1 1 1 112 1 1 0 0 1 113 1 1 0 1 1 114 1 1 1 0 1 115 1 1 1 1 1 1

Bei n Variablen gibt es 2n Maxterme (entsprechend der Zahl moglicher Belegungen),wobei jeder Maxterm ein n-stelliger Disjunktionsterm ist.

Definition 17. Ein n-stelliger Disjunktionsterm uber n Variablen a1, a2, . . . , an heißtn-stelliger Maxterm

Satz 9. Eine konjunktive Normalform einer vollstandig definierten n-stelligen logischenFunktion ist kanonisch, wenn die Disjunktionsterme paarweise verschiedene n-stelligeMaxterme sind.

32

REV

1468

Gewinnung der KKNF aus einer Wertetabelle

Eine Konjunktion D1 D2 Dk wird genau dann 0, wenn mindestens ein Di 0 ist.Ein Maxterm wird fur genau eine Belegung 0 und dementsprechend steht jeder Maxtermin einer KKNF fur genau eine Belegung, bei der diese Normalform 0 ist. Es treten soviele Maxterme auf, wie im Ergebnisvektor der Wahrheitswert 0 auftritt.

Aufstellung einer kanonischen konjunktiven Normalform aus der Wertetabelle:

Gegeben sei die Wertetabelle einer vollstandig definierten logischen Funktion, die nichtidentisch 1 ist.

1. Zu jeder Belegung, die den Funktionswert 0 hat, wird der Maxterm ermittelt,indem die Variablen, die in der entsprechenden Belegung 1 sind, als negierte Va-riablen und die, die 0 sind, als einfache Variablen disjunktiv verknupft werden.

2. Die Konjunktion dieser Maxterme ist die KKNF der Funktion.

Beispiel 41. KKNF aus Wertetabelle:c b a fpa, b, cq Maxterm

0 0 0 0 0 a b c1 0 0 1 0 a b c2 0 1 0 1

3 0 1 1 0 a b c4 1 0 0 0 a b c5 1 0 1 16 1 1 0 17 1 1 1 1

fpa, b, cq pa b cq pa b cq pa b cq pa b cq

Praktischer Hinweis

Wie bei der KDNF ist es auch hier ublich, die Maxterme nach aufsteigenden Indizesi innerhalb einer KKNF anzugeben. Die Reihenfolge der Variablen in den einzelnenMaxtermen ist stets gleich. Sie ist festgelegt durch die Anordnung in der Wertetabelleoder durch die Angabe des Argumentes der Funktion oder – bei logischen Ausdrucken– durch die lexikographische Reihenfolge.

3.3 Zusammenhang zwischen den Normalformen

Uberfuhrung kanonische disjunktive ô kanonische konjunktive Normalformen

Haufig muss eine DNF in die KNF umgeformt werden und umgekehrt. Diese Umrech-nung wird oft recht umfangreich nach den bisher bekannten Regeln. Fur die Umformungeiner kanonischen Normalform in die andere lassen sich die Kenntnisse uber Min- undMaxterme anwenden. Die KKNF besteht aus k Maxtermen Mi.

33

REV

1468

i P I t0, 1, 2, . . . , 2n 1u, k |I| ¤ 2n

Jedem Maxterm entspricht eine”0“ im Ergebnisvektor der zugehorigen Funktion. Die

KDNF besteht dementsprechend aus 2n k Mintermen mj, denn jedem Minterm ent-spricht eine 1 im Ergebnisvektor. Dabei treten nur Minterme mit solchen Indizes j auf,die in der KKNF nicht auftreten.j P J t0, 1, 2, . . . , 2n 1u und JX I H und JY I t0, 1, ..., 2n 1u

Umformung KDNF ô KKNF

Gegeben sei eine KDNF (KKNF).

1. Die KDNF (KKNF) wird mittels Mintermsymbolen m (Maxtermsymbolen M) dar-gestellt.

2. Die KKNF (KDNF) erhalt man als Konjunktion (Disjunktion) derjenigen Max-terme (Minterme), deren Indizes nicht in der KDNF (KKNF) vorkommen.

Beispiel 42. fKKNF pa b cq pa b cq pa b cq M1 M3 M4

Es gibt 23 = 8 Minterme und ebensoviele Maxterme (0 ¤ i ¤ 7q. Die in der KKNF nichtauftretenden Indizes pi 0, 2, 5, 6, 7q sind die Indizes der Minterme.fKDNF m0 m2 m5 m6 m7 a b c a b c a b c a b c a b c

Bemerkung:

Die angegebenen Regeln zur Gewinnung der Normalform beruhen nur auf der Anwen-dung der bisher bekannten Umformungsregeln und Satze. Danach ist eine Normalformeine aquivalente Darstellung einer vollstandig definierten logischen Funktion. Es fehltbisher der Beweis der Eindeutigkeit der kanonischen Normalform, der hier an dieserStelle nicht aufgefuhrt wird.

3.4 Normalformen und partiell definierte Funktionen

Partiell definierte Funktionen

Ein logischer Ausdruck stellt eine vollstandig definierte Funktion dar. In der Praxistreten jedoch auch partiell definierte Funktionen auf, die nicht fur jede Belegung einenFunktionswert haben. Sie sind fast immer durch Wertetabellen gegeben. Die Realisierungals Schaltnetz erfordert jedoch eine Funktion als booleschen Ausdruck.

Vorgehensweise

Ist eine Funktion fur eine Belegung nicht definiert, tritt diese Belegung entweder nie auf,oder es ist in diesem Moment gleichgultig, welcher Funktionswert auftritt (

”don’t care“).

Beispiel 43. Partiell definierte FunktionFunktion zum Erkennen einer bestimmten Ziffer des BCD-Codes. Bei einem 4-stelligenArgument gibt es 6 Belegungen, die nicht vorkommen konnen (die Dualzahlen 10 bis 15)

34

REV

1468

Werden nun den nicht definierten Belegungen der Funktion beliebige Funktionswertezugewiesen, so ist dies ohne praktische Relevanz.

Vervollstandigung einer Wertetabelle zur Gewinnung einer KDNF oder KKNF

Das Ergebnis der Vervollstandigung liefert eine neue, vollstandig definierte Funktion,die mit der ursprunglichen Funktion in den definierten Belegungen ubereinstimmt. Ummoglichst kurze kanonische Normalformen zu erhalten, erganzt man die Wertetabelle:mit 0, falls eine KDNF gewonnen werden soll, mit 1, falls eine KKNF gewonnen werdensoll. Dies gilt aber nur fur kanonische Normalformen. Fur moglichst kurze Normalformenmussen die fehlenden Werte gezielt erganzt werden.

Beispiel 44. Partiell definierte logische Funktion

c b a fpa, b, cq fKDNFpa, b, cq fKKNFpa, b, cq0 0 0 0 1 1 11 0 0 1 - 0 12 0 1 0 0 0 03 0 1 1 - 0 14 1 0 0 0 0 05 1 0 1 0 0 06 1 1 0 1 1 17 1 1 1 - 0 1

fKDNFpa, b, cq m0 m6 a b c a b cfKKNFpa, b, cq M2 M4 M5 pa b cq pa b cq pa b cq

3.5 Karnaugh-Veitch-Diagramm und Normalformen

Abbildung boolescher Ausdrucke in Karnaugh-Veitch-Diagramme

Die Abbildung boolescher Ausdrucke in KV-Diagramme vereinfacht sich betrachtlich,wenn man von kanonischen Normalformen ausgeht. Jedem Feld des Diagramms ist genauein Minterm bzw. Maxterm zugeordnet. Das dezimale Aquivalent der Belegung, die zueinem Feld des Diagramms gehort, stimmt mit dem Index i des zugehorigen Min- bzw.Maxterms uberein. Bei einer KDNF wird fur jeden Minterm eine 1 in das entsprechendeFeld eingetragen. Bei einer KKNF verfahrt man entsprechend, indem man fur jedenMaxterm eine 0 eintragt.

Beispiel 45.

fpa, b, cq a b c a b c a b c a b c

m1 m2 m4 m7

pa b cq pa b cq pa b cq pa b cq M0 M3 M5 M6

35

REV

1468

Fur die Min- bzw. Maxterme ergeben sich folgende Diagramme:

KDNF

01

1

12 3

145

61

7

c

b

aKKNF

00 1

20

3

40

5

067

c

b

a

Bestimmung eines logischen Ausdrucks aus dem KV-Diagramm einer vollstandigdefinierten Funktion

Um die KKNF oder KDNF zu gewinnen, benutzt man das eben beschriebene Verfahrenin umgekehrter Richtung. KDNF: Jede 1 im KV-Diagramm entspricht einem Mintermder KDNF. KKNF: Jede 0 im KV-Diagramm entspricht einem Maxterm der KKNF.

Beispiel 46. Bestimmung der KDNF und KKNF aus KV-Diagramm

fpa, b, cq

10

11

12

03

14

05

06

17

c

b

a

Also liest man ab:KDNF: fpa, b, cq m0 m1 m2 m4 m7

KKNF: fpa, b, cq M3 M5 M6

Mit KV-Diagramm lassen sich kurzere nicht kanonische Normalformen ermitteln. Be-nachbarte Einsen ergeben in der KDNF stets zwei Minterme, die sich zu einem n-1stelligen Konjunktionsterm zusammenfassen lassen.

3.6 Primtermdarstellung logischer Funktionen

Fur technische Realisierungen logischer Funktionen ist es wunschenswert, Darstellungenals moglichst kurze boolesche Ausdrucke zur Verfugung zu haben. Zu deren Gewinnungsollen jedoch zunachst als technische Hilfsmittel spezielle Konjunktionsterme, namlichdie Primterme, eingefuhrt werden.

3.6.1 Implikanten

Vorbemerkung

Bekannt sind aus der Logik die Sprechweisen”A impliziert B“ oder

”aus A folgt B“,

wobei A und B z. B. mathematische Aussagen sind. Eine solche Implikation muss formal

36

REV

1468

wahr sein, wenn sie in einem Theorem oder Satz auftritt. Sind zwei n-stellige logischeFunktionen g und f gegeben und soll beschrieben werden, dass fur jede Belegung, fur dieg den Wert 1 hat, auch f in ihrem Definitionsbereich D den Wert 1 annimmt, so zeigtdie Wertetafel der Implikation, dassgpa1, . . . , anq Ñ fpaj, . . . , anq 1 fur alle pa1, . . . , anq P D t0, 1ungesetzt werden muss, d. h. der Ausdruck gpa1, . . . , anq Ñ fpa1, . . . , anq muss formal wahrsein. In diesem Falle wird als Abkurzung auch einfach g Ñ f 1 geschrieben.

Definition 18. ImplikantSeien f und i n-stellige logische Funktionen, ipa1, . . . , anq ein Konjunktionsterm undi Ñ f 1, dann heißt ipa1, . . . , anq Implikant von fpa1, . . . , anq oder auch kurz von f.

Bei einer Darstellung im KV-Diagramm wurde das bedeuten, dass das 1-Muster derFunktion f das 1-Muster des Implikanten uberdeckt.Man sagt daher auch: f uberdeckt i.

Beispiel 47. f uberdeckt if a, i a b

a b Ñ a a b a a b a 1

fpa, b, cq

00

11

02

13

04

15

06

17

c

b

a

Beispiel 48. Implikanten der Funktion fGegeben: fpa, b, cq m0 m1 m2 m3 m5 m7

und die Terme: m5, b c, a, b, c, a c

c b a fpa, b, cq m5 b c a b c a c0 0 0 0 1 0 0 1 0 0 11 0 0 1 0 0 0 0 0 0 02 0 1 0 1 0 0 1 1 0 13 0 1 1 0 0 0 0 1 0 04 1 0 0 1 0 0 1 0 1 15 1 0 1 1 1 0 0 0 1 16 1 1 0 1 0 1 1 1 1 17 1 1 1 1 0 1 0 1 1 1

m5, b c, a, c sind Implikanten von f, b ist kein Implikant von f, da b Ñ fpa, b, cq 0 fur(a, b, cq p1, 1, 0q ist, a c impliziert zwar fpa, b, cq fur alle Belegungen, ist jedoch keinKonjunktionsterm und daher kein Implikant von f.KV-Diagramme fur fpa, b, cq, b c, a, c:

37

REV

1468

fpa, b, cq

10

01

12

03

14

15

16

17

c

b

ab c

00

01

02

03

04

05

16

17

c

b

a

a

10

01

12

03

14

05

16

07

c

b

ac

00

01

02

03

14

15

16

17

c

b

a

Die 1-Muster der Implikanten werden vom 1-Muster der zugehorigen Funktion f uberdeckt.

Zusammenfassung von Implikanten

Offenbar ist jeder Minterm, der zur KDNF einer Funktion gehort, ein Implikant die-ser Funktion. Zwei Minterme, die sich nur in einer Variablen unterscheiden, lassen sichinnerhalb der DNF zu einem neuen kurzeren Konjunktionsterm zusammenfassen (Ab-sorptionsgesetz: K a K a Kq. Dieser neu entstandene Term ist wieder Implikant derFunktion. Dies gilt nicht nur fur Minterme, sondern allgemein fur Implikanten, die sichmit Hilfe der Absorptionsgesetze (K a K a K und K K a K) zu einem neuenkurzeren Konjunktionsterm zusammenfassen lassen.

Beispiel 49. Zusammenfassung von ImplikantenImplikant c im letzten Beispiel kann entstanden sein durch:m1 a b cm3 a b cm5 a b cm7 a b c

m1 m3 a c und m5 m7 a c ergebena c a c c

oder:

m1 m5 b c und m3 m7 b c ergebenb c b c c

Die zwei Implikanten, aus denen sich der neue kurzere Implikant bilden lasst, sind auchImplikanten dieses neuen Konjunktionsterms.Also gilt:m1 Ñ a c,m3 Ñ a c,m5 Ñ a c,m7 Ñ a c, a c Ñ c, a c Ñ c, c Ñ fpa, b, cqSatz 10. Zusammenfassung von ImplikantenSeien f eine n-stellige logische Funktion und i1pa1, . . . , anq, i2pa1, . . . , anq Implikanten vonf.

38

REV

1468

1. Lassen sich i1pa1, . . . , anq und i2pa1, . . . , anq nach den Absorptionsgesetzen zu einemneuen kurzeren Konjunktionsterm i3pa1, . . . , anq zusammenfassen, so isti3pa1, . . . , anq wieder Implikant von f.

2. i1pa1, . . . , anq und i2pa1, . . . , anq sind Implikanten von i3pa1, . . . , anq.3. Jeder Konjunktionsterm einer DNF von f ist Implikant von f.

4. Jede DNF von f ist eine Disjunktion von Implikanten von f.

3.6.2 Primimplikanten

Vorbemerkung

Im Beispiel wird deutlich, dass es in der Menge der Implikanten einer Funktion solchegibt, die sich nicht mehr disjunktiv zu neuen Implikanten verknupfen lassen. Im Beispielwaren es a und c. Gerade solche, nicht weiter zusammenfassbare Implikanten sind furMinimierungsverfahren von Interesse.

Definition 19. Primimplikant (Primterm)Sei ppa1, . . . , anq Implikant einer n-stelligen logischen Funktion f. ppa1, . . . , anq heißt Pri-mimplikant oder Primterm von f, wenn es keinen von ppa1, . . . , anq verschiedenen Impli-kanten ipa1, . . . , anq mit p Ñ i 1 gibt.

Folgerung

Primimplikanten einer vollstandig definierten n-steligen logischen Funktion f sind genaudie Implikanten von f, die sich mit keinem anderen Implikanten von f zu einem von diesemPrimimplikanten verschiedenen Implikanten von f disjunktiv zusammenfassen lassen.

Beispiel 50. Implikanten und Primimplikantenfpa, b, cq a b a b c a b cFolgende Implikanten von f lassen sich erkennen:

a b, a b c, a b c direkt aus fa b wegen a b c a b c a ba wegen a b a b a

Die vollstandige Liste der Implikanten von f lautet jedoch:a b c, a b c, a b c, a b c, a b, a c, a c, a b, aa ist ein Primimplikant von f.

Beispiel 51. Implikanten und Primimplikantenhpa, b, cq a b c a b c a b c m0 m3 m6

Minterme a b c, a b c, a b c sind die einzigen Implikanten von h. Da sie sich nichtzusammenfassen lassen, handelt es sich um Primimplikanten.

39

REV

1468

Satz 11. Primtermdarstellung einer FunktionSei f eine vollstandig definierte n-stellige logische Funktion und ppa1, . . . , anq, i 1, . . . , kseien alle Primimplikanten von f.Dann gilt:fpa1, . . . , anq p1pa1, . . . , anq pkpa1, . . . , anq.

Offenbar ist die Disjunktion aller Primterme eine spezielle disjunktive Normalform.Diese spezielle DNF, auch Primtermdarstellung der Funktion genannt, lasst sich mitden Absorptionsgesetzen nicht weiter vereinfachen. Diese Primtermdarstellung ist nichtin jedem Falle schon die kurzeste. Es kann Primimplikanten geben, auf die man bei derDarstellung der Funktion verzichten kann.

Implikanten und Primimplikanten im KV-Diagramm

Beispiel 52. Implikanten und Primimplikanten

1. fpa, b, cq a b a b c a b c

'&$%

fpa, b, cq

01

1

21

3

41

5

61

7

c

b

a

2. gpa, b, cq a c a c a b c

'&$%

gpa, b, cq

01

1

2 3

14

15

16

17

c

b

a

3. hpa, b, cq a b c a b c a b c

hpa, b, cq

10 1

21

3

45

167

c

b

a

Aspekte zu Primimplikanten

Werden im KV-Diagramm 1-, 2-, . . . , 2i-Gruppen beieinanderliegender Einsen gebildet,so entspricht jede dieser Gruppen einem Implikanten. Die disjunktive Verknupfung zwei-

40

REV

1468

er Implikanten zu einem neuen bedeutet dann die Zusammenlegung zweier gleichgroßerGruppen zu einer nachstgroßeren. Lasst sich eine Gruppe nicht mehr vergroßern, liegtein Primimplikant vor. Im letzten Beispiel gibt es keine benachbarten Felder, die mit

”1“ belegt sind, deshalb sind die drei Minterme auch die einzigen Implikanten und da-

her Primimplikanten. Die von Implikanten belegten Felder von Einsen sind nicht immerdisjunkt, auch die von Primimplikanten nicht, wie Beispiel (2) zeigt. Mit dem KV-Diagramm lassen sich also Primterme ermitteln. Alle Primimplikanten lassen sich ausanderen Implikanten kombinieren oder sind selbst Minterme. (2) zeigt aber, dass diebenotigten Implikanten nicht immer von vornherein bekannt sind.

Ermittlung der Primimplikanten einer logischen Funktion

1. Aufstellung der KDNF der Funktion. (Alle in der KDNF auftretenden Mintermesind Implikanten).

2. Alle bisher vorhandenen Implikanten der Funktion werden – soweit moglich – paar-weise disjunktiv zu neuen Implikanten verknupft.

3. Hat man neue Implikanten erhalten, fahrt man mit 2. fort.

4. Implikanten, die sich nicht mehr mit anderen zu neuen verknupfen lassen, sinddann die Primimplikanten der Funktion.

Nur wenn man von der KDNF ausgeht, erhalt man so alle Implikanten.

Beispiel 53. gpa, b, cq a c a c a b c

1. gpa, b, cq a b c a b c a b c a b c a b c

2. Implikanten sind:init 2nd 3rd

a b c//////// a c//// c

a b c//////// b c//// c

a b c//////// b c////

a b c//////// a c////

a b c//////// a b

Es wurden die Implikanten durchgestrichen, die sich mit einem anderen disjunktivzu einem neuen verknupfen ließen.

3. Primterme sind die nicht markierten Implikanten a b und c.

Das beschriebene Verfahren wird sehr umfangreich und schnell unubersichtlich, wenndie zu untersuchende Funktion mehr als drei Variable und folglich eine

”lange“ KDNF

hat. Rechnergestutztes Verfahren: Quine McCluskey.

41

REV

1468

4 Analyse und Synthese vonSchaltnetzen

Dieses Kapitel behandelt die Synthese von zweistufigen AND-OR-Schaltnetzen (disjunk-tive und konjunktive Normalform) unter Anwendung von Wahrheitstafeln und der De-Morgan’schen Gesetze. Im weiteren Verlauf werden auch Schaltnetze mit mehreren Stu-fen behandelt.

Das Ziel der Synthese ist die Begrenzung der Anzahl der Gattereingange (Gate-Array-Technik, Vollkundenentwurf oder Standardbausteine) und die Optimierung der Laufzei-ten und der Verlustleistung

4.1 Begriffe

Eine boolesche Funktion ist die Abbildung von n binaren Variablen auf einen Wert(0 oder 1). Die einzelnen Variablensymbole (z.B. x, x) werden Literale genannt. Varia-blen konnen drei Werte annehmen: 0, 1 und – (unbestimmt oder don’t care). Literalelassen sich zu Min- und Maxtermen zusammensetzen. Ein Minterm ist ein Konjunkti-onsterm und definiert einen einzelnen Punkt innerhalb eines Wertefeldes von Variablen.Ein Maxterm hingegen definiert ein ganzes Wertefeld bis auf einen Punkt. Ein Implikantdefiniert eine Gruppe von 1-Punkten.

a b

00

01

02

13

b

a a b

00

11

12

13

b

a

a b

00

01

02

13

04

05

06

17

c

b

a

Abbildung 4.1: Ein Minterm, Maxterm und Implikant dargestellt in einem KV-Diagramm

Der Primimplikant ist ein Implikant, der so groß wie moglich ist, ohne dabei vollstandigTeil anderer Implikanten zu sein. Dabei darf durch weglassen einer einzigen Variablender Wert der Funktion nicht verandert werden.

Ein wichtiges Ziel der Analyse und Synthese ist die Optimierung der Funktion. Je nachSichtweise kann

”Optimierung“ verschiedenes bedeuten. Aus mathematischer Sicht kann

beispielsweise ein Ergebnis mit moglichst wenig Gattern (Termen) und moglichst wenig

42

REV

1468

a b, a c, b c

00

01

12

13

04

15

06

17

c

b

a

Abbildung 4.2: Primimplikanten in einem KV-Diagramm dargestellt

Eingangen (Literalen) als ideal angesehen werden. Aus physikalischer oder elektrotech-nischer Sicht ist eine moglichst kleine Chipflache (also wenige Bauelemente und guteVerdrahtbarkeit), eine minimale Laufzeit (wenige Gatterebenen, Fanin, Fanout) und ei-ne minimale Verlustleistung (Gatterstruktur, Anzahl der Gatterebenen, Fanin, Fanout)optimal. Ein Problem ist, dass sich spezielle Schaltungstechniken wie dynamische Logikund Pass-Logik nur schwer in Logikansatze integrieren.

4.2 Gattersymbolik

Neben Funktionen, Wertetabellen und KV-Diagrammen ist noch eine weitere Darstel-lung etabliert - die Gattersymbolik. Bei der Gattersymbolik handelt es sich um einegrafische Darstellung, der die Grundstruktur einer Schaltung zu entnehmen ist. Dabeiwerden Terme der realisierten Funktion durch Grundgatter symbolisiert, deren Funk-tionalitat den Grundfunktionen der Booleschen Algebra entsprechen. Die Anzahl derin den jeweiligen Term involvierten Eingangsvariablen spiegelt sich in der Anzahl derEingange eines jeden Gatters wieder. Die Negation von Eingangsvariablen und Termenwird durch eingangs- oder ausgangsseitige Kreise symbolisiert. In der Abbildung 4.3 wirddie Funktion

y pa b cq pd` eqdargestellt.

abc

de

y

&

1

¥ 1

(a) DIN-Symbole

abc

de

y

(b) US-Symbole

Abbildung 4.3: Beispiele fur die Verwendung unterschiedlicher Gattersymbolik

Neben der DIN Symbolik aus Abbildung 4.3a, die auch im weiteren Verlauf des SkriptsVerwendung findet, gibt es unter anderem auch die in Abbildung 4.3b gezeigte. Auf diese

43

REV

1468

stoßt man hauptsachlich in englischsprachigen Publikationen, aber auch in Entwurfs-werkzeugen, die im Digitalentwurf Gebrauch finden.

4.3 Elementare Verfahren zur Schaltnetzsynthese

Zur Synthese von Schaltungen betrachten wir drei Moglichkeiten:

• Die Realisierung durch Gatter mit Hilfe von kanonischen Abbildungen

• Die Realisierung durch Schalter mit Hilfe des Entwicklungssatzes von Shannon

• Iterative Strukturen

4.3.1 Kanonische Abbildungen

Bei der Bildung von kanonischen Abbildungen verwenden wir Normalformen. Dabei wirdunterschieden zwischen der disjunktiven Normalform mit AND/OR-Strukturen (Darstel-lung der 1-Felder—NAND) und der konjunktiven Normalform mit OR/AND-Strukturen(Darstellung der 0-Felder—NOR).

Beispiel 54. Disjunktive und konjunktive Normalform

y

00

01

02

13

14

05

16

17

x3

x2

x1

y x1 x2 x1 x3 disjunktive Normalformy x1 x3 x1 x2 Umformung nach DeMorgany px1 x3q px1 x2q konjunktive Normalform

x1x2

x1x3

y

&

&

¥ 1

(a) Gatterrealisierung einer DNF

x1x3

x1x2

y

¥ 1

¥ 1

&

(b) Gatterrealisierung einer KNF

Abbildung 4.4: Gatterrealisierungen unterschiedlicher Normalformen

44

REV

1468

4.3.2 Entwicklungssatz (Shannon)

Der Entwicklungssatz nach Shannon erlaubt das Herausheben einer oder mehrerer Va-riablen aus einer Schaltungsfunktion.

Satz 12. Entwicklungssatz (Shannon)

y fpx1, x2, . . . , xi1, xi, xi1, . . . , xnqy xi fpx1, . . . , xi1, 1, xi1, . . . , xnq xi fpx1, . . . , xi1, 0, xi1, . . . , xnq

Beispiel 55. Shannony x1 x2 x1 x3y x2 x3 p1q x2 x3 px1q x2 x3 px1q x2 x3 p0q nach x2, x3 entwickelty x1 px2q x1 px3q nach x1 entwickelt

1

0

x1

x1

y

x2 x3

x2 x3

x2 x3

x2 x3

(a) nach x2, x3 entwickelt

x2

x3

y

x1

x1

(b) nach x1 entwickelt

Abbildung 4.5: Schaltermatrizen fur Entwicklung nach unterschiedlichen Variablen

4.3.3 Iterative Strukturen

Einfache iterative Netzwerke bestehen aus eindimensionalen Arrays von Gattern. Damitlassen sich jedoch nicht alle Funktionen abbilden.

x2 x3 x4

x1 y

Abbildung 4.6: Grundstruktur eines eindimensionalen iterativen Schaltnetzes

45

REV

1468

Beispiel 56. Iterative Implementierung

y x1 x2 x3

y

00

01

02

13

14

15

16

17

x3

x2

x1x1x2

x3y

&

&

4.4 Minimale zweistufige AND-OR-Schaltnetze

Zur Minimierung einer Funktion in ein zweistufiges AND-OR-Schaltnetz mussen zuerstalle Primimplikanten der Funktion f bestimmt werden. Aus diesen werden dann diePrimimplikanten ausgewahlt, die alle 1-Punkte der Funktion f uberdecken und minimaleKosten aufweisen.

4.4.1 Kosten

Kosten beschreiben die Zahl der Gatter und Eingange z.B. bei der disjunktiven Normal-form. Die Kosten eines Primimplikanten stehen in Relation zum Optimierungsziel (Zahlder Literale). Es wird davon ausgegangen, dass Literale sowohl komplementiert als auchnicht komplementiert zur Verfugung stehen.

Bei der Minimierung nach Gatteranzahl hat jeder Primimplikant mit zwei oder mehrVariablen einen Kostenwert von 1. Ein Primimplikant mit nur einer Variable hat einenKostenwert von 0. Wenn mehrere Primimplikanten verknupft werden, erhohen sich dieKosten zusatzlich um 1. Der Kostenwert entspricht also der Anzahl der Gatter.

Soll nach Anzahl der Gattereingange minimiert werden, so gilt fur einen Primimpli-kanten mit einem Eingang ein Kostenwert von 1 und fur Primimplikanten mit n ¡ 1Eingangen ein Kostenwert von n 1.

abc

dy

&

¥ 1

Abbildung 4.7: Schaltnetz mit zwei Gattern

46

REV

1468

4.4.2 Bestimmung der Primimplikanten

Bestimmung der Primimplikanten (Quine/McCluskey)

Eine Moglichkeit zur Bestimmung der Primimplikanten ist der Quine-McCluskey-Algo-rithmus:

1. Aufstellung einer Tabelle aller 1- und don’t-care-Punkte () der Funktion f, sortiertnach der Anzahl der Variablen mit Wert 1, in die Gruppen S0, S1, . . . , Sn. Umdon’t-cares richtig zu beachten muss dabei auch der Funktionswert in die Tabelleeingetragen werden.

2. In allen benachbarten Gruppen Si und Si1, fur alle i mit 0 ¤ i n, werden Paaregesucht, bei denen sich nur eine Variable unterscheidet. Aus diesen Paaren werdenneue Implikanten gebildet, bei denen jeweils die unterschiedliche Variable auf denWert

”unbestimmt“ gesetzt wird. Der Funktionswert ist genau dann don’t care,

wenn beide kombinierten Terme an dieser Stelle don’t care angeben, sonst 1. Dieso erzeugten Implikanten werden in die Gruppe S1i eingeordnet, die kombiniertenTerme werden markiert.

3. Der zweite Schritt wird wiederholt, um beispielsweise S1i mit S1i1 zu S2i zu kombi-nieren. Dabei mussen unbestimmte Variablen (don’t care) immer ubereinstimmen.

4. Wenn keine weiteren Paare gebildet werden konnen, sind alle Terme, die nie kom-biniert wurden (also nicht markiert sind) Primimplikanten.

Beispiel 57. Bestimmung der Primimplikanten nach Quine/McCluskey

Eingangsvariable: x3, x2, x1

1-Punkte: tp1, 0, 0q, p0, 1, 0q, p0, 0, 1q, p1, 1, 0qu ; m4,m2,m1,m6

(–)-Punkte: tp1, 1, 1qu ; m7

x3 x2 x1 fm4 1 0 0 1 !

S1 m2 0 1 0 1 !m1 0 0 1 1

S2 m6 1 1 0 1 !S3 m7 1 1 1 !

1 0 1S11 1 0 1S12 1 1 1

Ergebnis: Primimplikanten: tx1 x2 x3, x1 x3, x1 x2, x2 x3u

47

REV

1468

Bestimmung der Primimplikanten (Tison 1965)

Eine weitere Moglichkeit zur Bestimmung der Primimplikanten ist der Algorithmus vonTison:

1. Die disjunktive Funktion f A B . . . G mit S tA,B, . . . ,Gu ist als Aus-gangspunkt gegeben. Zuerst werden alle Terme geloscht, die vollstandig uberdecktwerden. Dann wird eine Variable ausgewahlt, die in negierter und nichtnegierterForm vorkommt.

2. Bilden der Uberdeckungsmengen aus jedem Term mit der nichtnegierten Variablemit jedem Term der negierten Variable. Die Uberdeckungsmengenterme werdenzur Menge S hinzugefugt und vollstandig uberdeckte Terme werden geloscht.

3. Wiederholung von Schritt 2 mit allen anderen Variablen, die in negierter und nicht-negierter Form vorkommen. Wenn die Voraussetzung fur eine Variable entfallt,entfallt auch dieser Schritt fur diese Variable.

4. S enthalt jetzt alle Primimplikanten.

Beispiel 58. Bestimmung der Primimplikanten nach Tison

y x1 x2 x4 x1 x3 x2 x3 x3 x4

Die beiden Variablen die sowohl negiert als auch nichtnegiert auftreten sind x3 und x4.Von diesen wird zunachst x3 gewahlt. Ein mogliches Termpaar zum Bilden der Uber-deckungsmengen ist x1 x3 und x2 x3. Der Uberdeckungsmengenterm lautet x1 x2. Erentsteht durch das

”verunden” der beiden Terme bei Vernachlassigung der vorher gewahl-

ten Variable x3. Das zweite und letzte mogliche Paar ist x1 x3 und x3 x4. Daraus folgtanalog x1 x4. Der Term x1 x2 x4 der Ursprungsfunktion wird durch den neu gefundenenTerm x1 x2 uberdeckt und entfallt somit.

'&$%

'&$%

'&$%

'&$%

y

10

11

12

13

04

15

06

17

08

09

110

111

012

113

014

115x4

x3

x2

x1

Ergebnis: Primimplikanten: x1 x3, x2 x3, x3 x4, x1 x2, x1 x4

Vergleich der Verfahren zur Bestimmung der Primimplikanten

Wahrend die Tison-Methode vor allem bei großer Variablenzahl flexibel ist, kann die Qui-ne-McCluskey-Methode don’t cares berucksichtigen, ist gunstiger fur rechnergestutzteVerfahren und vorteilhaft, wenn die Funktion durch Minterme vergegeben ist.

48

REV

1468

4.4.3 Kostenoptimierung (minimale Uberdeckung)

Die gefundenen Menge an Primimplikanten ist in der Regel nicht frei von Redundanz.Zur weiteren Kostenoptimierung mussen die Primimplikanten bestimmt werden, die zwaralle 1-Punkte der Funktion abdecken, sich dabei aber minimal Uberdecken und somitminimale Kosten verursachen. Die Minimierung von Hand kann in tabellarischer Formdurchgefuhrt werden. Dazu wollen wir vereinbaren, dass x1 das niederwertigste Bit undxn das hochstwertigste Bit ist.

Fur eine Reihe der folgenden Verfahren konnen die bestimmenden Faktoren (Pri-mimplikanten, Minterme) nach Kosten gewichtet werden. Da diese Gewichtung fur dasVerstandnis der Verfahren jedoch unerheblich ist, gehen wir bei der Erlauterung derVerfahren von Primimplikanten und Mintermen mit egalisierter Gewichtung aus.

Wir werden vier Verfahren behandeln, die in der Regel in einer Kombination ange-wandt werden:

• wesentlicher Primimplikant

• Reihendominanz

• Spaltendominanz

• Branching

Der Einsatz einiger dieser Verfahren ist in der Praxis erst bei sehr komplexen Funktionen,die jedoch nicht didaktisch zur Erlauterung geeignet sind, ratsam. Im Folgenden werdendaher Beispiele bemuht, die in dieser Form nicht unmittelbar aufgestellt werden konnen(zum Beispiel als Ergebnis eines Quine-McCluskey). Ihr Zustandekommen kann mit einervorher erfolgten, in dem jeweiligen Beispiel aber nicht aufgefuhrten Anwendung andererMinimierungsverfahren erklart werden.

Methode der wesentlichen Primimplikanten

m1 m2 m4 m6 m7

P1 x1 x2 x3 1P2 x1 x3 1 1P3 x1 x2 1 1P4 x2 x3 1 –

Abbildung 4.8: Besetzungstabelle der Primimplikanten aus dem Beispiel 57

Ein wesentlicher Primimplikant uberdeckt als einziger einen Minterm einer Funktion.Wenn Pi als einziger Primimplikant mi uberdeckt, muss Pi ein Bestandteil der minimalenUberdeckung sein. Alle Spalten (Minterme), die von Pi uberdeckt werden, konnen danneliminiert werden.

49

REV

1468

Beispiel 59. Methode des wesentlichen Primimplikanten anhand Abb. 4.8Der Primimplikant P3 uberdeckt als einziger den Minterm m2 und ist damit ein wesent-licher Primimplikant. P3 uberdeckt weiterhin m6. Es konnen also insgesamt zwei Spaltenentfernt werden. Mit der Eliminierung von m6 kann auch P4 entfernt werden, denn derFunktionswert von m7 ist lediglich don’t care. Es bleibt damit die reduzierte Besetzungs-tabelle:

m1 m4

P1 1P2 1

Somit ist die minimale Uberdeckung der Primimplikanten P1, P2, P3 bzw. x1 x2 x3,x1 x3, x1 x2

Methode der Reihendominanz

Nachdem die Menge an Primtermen beispielsweise durch die Methode der wesentlichenPrimimplikanten reduziert wurde, kann oft noch eine weitere Vereinfachung erfolgen.

Wie der Name Reihendominanz schon suggeriert, wird bei dieser Methode eine ReihePi gesucht, die eine andere Reihe Pj dominiert. Dominieren bedeutet, dass die Reihe Pi

alle 1-Punkte der Reihe Pj abdeckt und zudem geringere (oder gleiche) Kosten aufweist(CpPiq ¤ CpPjq). In diesem Fall kann die dominierte Reihe Pj entfernt werden, da so dieminimale Kostenfunktion durch Pi erhalten bleibt.

Zusammengefasst: Seien MPx ,MPy Mengen aller durch Px oder Py abgedeckten Min-terme. Dann gilt fur MPx MPy : Py dominiert Px.

Beispiel 60. Methode der Reihendominanz

ma mb mc md me

P1 1 1P2 1 1 1 1P3 1 1 1P4 1 1

In diesem Beispiel dominiert die Reihe P2 die Reihe P1, die somit eliminiert werdenkann. Daraus ergibt sich die reduzierte Uberdeckungstabelle:

ma mb mc md me

P2 1 1 1 1P3 1 1 1P4 1 1

In dieser ist P2 ein wesentlicher Primimplikant fur mb. Nach Anwenden der Methodedes wesentlichen Primimplikanten bleibt nur die Spalte md ubrig:

md

P3 1P4 1

50

REV

1468

Jetzt dominiert P3 P4, allerdings dominiert P4 auch P3. Der Primimplikant wird nachKosten ausgewahlt. In diesem Beispiel sind die minimalen Uberdeckungen also: tP2,P3uoder tP2,P4u.

Methode der Spaltendominanz

Dominanz lasst sich auch auf Spalten anwenden, dabei muss jedoch eine andere Methodeverwendet werden. Eine Spalte mi dominiert eine Spalte mj, wenn jeder Primimplikant,der mj uberdeckt, maximal auch mi uberdeckt. Zum Beispiel kann mj 1-Punkte in allenReihen haben, in denen auch mi 1-Punkte hat. Die Spalte mj kann eliminiert werden,denn jede Uberdeckungsmenge der reduzierten Tabelle uberdeckt auch mi.

Zusammengefasst: Seien Pmx ,Pmy Mengen aller Primterme, die mx oder my abdecken.Dann gilt fur Pmx Pmy : mx dominiert my.

Beispiel 61. Methode der Spaltendominanz

ma mb mc md me

P1 1 1P2 1 1 1 1P3 1 1 1P4 1 1

mb dominiert ma. Außerdem dominiert mc me und umgekehrt. Es konnen also ma undme (oder mc) eliminiert werden.

mb mc md

P1 1P2 1 1P3 1 1P4 1

P2 dominiert P1 und P3 dominiert P4 (Reihendominanz). Das Ergebnis lautet somit:tP2,P3u ist die minimale Uberdeckung

Methode des Branching

Die drei bisher vorgestellten Methoden fuhren nicht zum Ziel, wenn keine der entspre-chenden Kriterien zutreffen. Diese Tabellen werden als zyklisch bezeichnet und konnenmit der Methode des Branching reduziert werden.

Dazu wird eine Teilmenge R von Reihen ausgewahlt, so dass jede Losung ein Elementvon R enthalten muss. Danach wird Pi aus R gewahlt. Die Spalten, die von Pi uberdecktwerden, werden eliminiert. Pi ist nun ein Bestandteil der Losung. Dieser Ablauf wirdmit einer anderen Reihe von R wiederholt. Gegebenenfalls muss zum Auffinden desMinimums jedes Element von R gewahlt werden.

Beispiel 62. Methode des Branching

51

REV

1468

ma mb mc md me

P1 1 1 1P2 1 1P3 1 1P4 1 1P5 1 1P6 1 1

Es wird die Spalte ma ausgewahlt. Aus ma ist ersichtlich, dass jede Uberdeckungsmenge P1

und/oder P3 enthalten muss. Daraus folgt Branching um ma. Es gibt zwei Moglichkeiten:

• P1 wird gewahlt und alle Spalten von P1 werden eliminiert.

• P3 wird gewahlt und alle Spalten von P3 werden eliminiert.

P1 mc md

P2 1P3 1P4 1P5 1 1P6 1

P3 mb md me

P1 1 1P2 1P4 1 1P5 1P6 1 1

Beide Tabellen konnen nach den bisherigen Regeln weiter reduziert werden. Die mi-nimalen Uberdeckungsmengen sind tP1,P5u, tP3,P6,P1u, tP3,P6,P4u oder tP3,P1,P4u.Gegenuber den anderen drei Losungen weist tP1,P5u die geringeren Kosten auf und istdeshalb die optimale Losung dieser Spaltenauswahl.

Hinweis Branching kann mit jeder Spalte durchgefuhrt werden. Jedoch sollten ausGrunden minimaler Rechenzeit die Spalten mit geringer Anzahl von 1-Punkten gewahltwerden.

4.5 Schaltnetze mit mehreren Stufen

Schaltnetze mit mehreren Stufen bieten einen Kompromiss aus Hardwareaufwand undGeschwindigkeit. Sie ermoglichen es, den Ein- und Ausgangslastfaktor zu beschranken(fanin, fanout, z.B. Gate-Array-Technik). Dies wird durch die Aufspaltung von Gatternmit vielen Eingangen moglich, denn dadurch kann die Zahl der Eingange beschranktwerden. Die Ausgangslast sinkt somit.

4.5.1 Baumstruktur

Eine Schaltung, bei der die Ausgange eines jeden Gatters nur mit einem Gattereingangverknupft werden, wird als Baumstruktur bezeichnet.

52

REV

1468

Beispiel 63. Mehrstufiges Schaltnetz: Parityfunktion

fpx1, x2, . . . , xnq x1 ` x2 ` . . .` xn

Ist das Ziel eine Realisierung mit moglichst wenigen Stufen, so erfordert diese Realisie-rung die Verwendung von 2n1 AND-Gatter mit jeweils n Eingangen, ein OR-Gatter mit2n1 Eingangen und n Interver. Unter Berucksichtigung der Inverter ergeben sich ins-gesamt drei Stufen. Der Aufwand lasst sich jedoch reduzieren, indem Parityschaltungenfur 2 Bit kaskadierend miteinander verbunden werden. Es sind dazu log2 n bzw. unterBerucksichtigung der internen Struktur der einzelnen Stufen 3 log2 n Stufen notwendig.Der Aufwand verringert sich damit auf 3pn 1q NAND-Gatter mit 2 Eingangen und2pn 1q Inverter. Die Erhohung der Stufenzahl fuhrt jedoch zur Erhohung der Laufzei-ten.

x1x2

x3x4

...

xn1xn

y

1

1

1

1

1

1

(a) Parity-Baum

x1

x2

y1

1

&

&

¥ 1

(b) Parity Stufe fur 2 Bit

Abbildung 4.9: Parity-Baum

4.5.2 Faktorisierung

Die Umformung in Schaltungen mit mehr als zwei Stufen kann durch Faktorenzerlegungerfolgen.

Beispiel 64. Zerlegung in Faktoren

f x1 x2 x3 x4 x1 x2 x3 x4

Die Funktion kann wegen des gemeinsamen Faktors x1 x2 zerlegt werden in:

f x1 x2 px3 x4 x3 x4q

Die Stufenzahl erhoht sich dabei von 2 auf 3, die Zahl der Eingange pro Gatter reduziertsich von 4 auf 2. Es ergibt sich jedoch das Problem der unterschiedlichen Pfadlangen.

53

REV

1468

x1x2

x3x4

x1x2

x3x4

y

&

&

¥ 1

x1x2

x3x4

x3x4

y&

&

&

¥ 1

&

Abbildung 4.10: zweistufige Realisierung und dreistufige Realisierung mit zerlegten Fak-toren

4.5.3 Zusammenfassung

Jedes Schaltnetz kann in eine aquivalente Schaltung umgeformt werden, um die Rand-bedingungen bezuglich der Eingangs- und Ausgangsfaktoren (fanin, fanout) zu erfullen.

Beispiel 65. n-Eingangs-AND-GatterEin AND-Gatter mit n Eingangen kann durch einen Baum von 2-Eingang-AND-Gatterersetzt werden. Die Anzahl der Stufen betragt log2 n fur n 2N n,N P N bzw. log2pn 1qfur n 2N.

Ein Ausgangslastfaktor von n kann ersetzt werden durch eine Baumstruktur mit log2 nStufen, wobei jedes Gatter einen Eingang und ein Fanout von 2 aufweist (Verstarker-stufe). Bisher existiert allerdings kein allgemeiner Algorithmus zur effizienten Berech-nung optimaler Losungen von mehrstufigen Schaltnetzen.

& &

1

1

1

1

1

1

Abbildung 4.11: Reduzierung der Ausgangslast durch Baumstruktur

54

REV

1468

5 Komplexe Schaltnetze

5.1 Codierer

Funktion

Ein Codierer entspricht einem Schaltnetz, welches eine Menge von Eingangswerten ineine Menge von Ausgangswerten ubersetzt (Codeumsetzung).

XYInformation

in den Zeichendes Codes A

Informationin den Zeichendes Codes B

Abbildung 5.1: Schaltzeichen eines Codierers

Das Schaltzeichen deutet an, dass ein Codierer ein Schaltnetz ist, das eine Vektorfunk-tion realisiert (ÝÑy fpÝÑx q). Die Anzahl der Ein- und Ausgange eines Codeumsetzers istabhangig von der Wortlange des Binarcodes, in dem die Information dargestellt ist.

Beispiel 66. Schaltnetzentwurf fur die 8421-BCD zu 7-Segment-Umsetzung

Aufgabe:Dezimalziffern werden haufig in einem BCD-Code (Binary Coded Decimal) dargestelltund in 7-Segmenteinheiten eingesetzt. Dies kann durch einen Codeumsetzer realisiertwerden.

Annahme:Die Dezimalziffern liegen im 8421-BCD-Code vor.

Codeumsetzung:1. Die Zuordnung (Codierung) der Dezimalziffern vom 8421-BCD-Code zu den Segmen-ten der 7- Segment-Anzeige wird in einer Wertetabelle festgelegt.

55

REV

1468

A

B

C

D

a

bc

de

fg

XYa

b

c

d

e

f g

(a) Blockschaltbild

Dezimal- 8421-BCD-Code 7-Segment-Codeziffer D C B A a b c d e f g

0 0 0 0 0 1 1 1 1 1 1 01 0 0 0 1 0 1 1 0 0 0 02 0 0 1 0 1 1 0 1 1 0 13 0 0 1 1 1 1 1 1 0 0 14 0 1 0 0 0 1 1 0 0 1 15 0 1 0 1 1 0 1 1 0 1 16 0 1 1 0 0 0 1 1 1 1 17 0 1 1 1 1 1 1 0 0 0 08 1 0 0 0 1 1 1 1 1 1 19 1 0 0 1 1 1 1 0 0 1 110 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1

(b) Wertetabelle

Abbildung 5.2: 8421-BCD-Code zu 7-Segment Codierer

2. Fur die Ausgangsvariablen a, b, ...., g werden die Funktionsgleichungen aus der Wer-tetabelle in der DNF hergeleitet. Nimmt man an, dass die Pseudotetraden nicht vor-kommen (Zustand 10 bis 15), konnen diese bei der Vereinfachung im KV-Diagramm alsdon’t care-Terme benutzt werden.

3. Nach der Minimierung lauten die Funktionsgleichungen fur die Ausgangsvariablena, b, ...., g in DNF:

a D A C A C A B e A B A Cb C A B A B f D A B A C B Cc A B C g D A B B C B Cd A B A C B C A B C

5.2 Decodierer

Funktion

Decodierer sind Codierer mit mehreren Ein- und Ausgangen, bei denen fur jede Kombi-nation von Eingangssignalen immer nur je ein Ausgang ein Signal abgibt. Am Ausgangeines Decodierers liegt die Information in den Zeichen eines 1-aus-n-Codes vor.

56

REV

1468

1 1 1 1

A B C D

&

&

&

&

&

&

&

&

&

¥1

¥1

¥1

¥1

¥1

¥1

¥1

a b c d e f g

Abbildung 5.3: Schaltnetz fur einen 8421-Code in 7-Segment Codierer

Definition 20. 1-aus-n-CodeEin 1-aus-n-Code ist dadurch gekennzeichnet, dass die Anzahl der Binarstellen gleich

der Anzahl der darzustellenden Zeichen ist. D.h. fuhrt eine Bitstelle des Codewortes ein1- (bzw. 0-) Signal, dann fuhren alle anderen Stellen ein 0- (bzw.1-) Signal.

Beispiel 67. 3-Bit Adressdecodierer

Uber die Adresseingange wird ein Ausgang des Decodierers angewahlt, der dann 1-Signal fuhrt (siehe Wertetabelle). Hat ein Adressdecodierer n-Eingange, dann konnen2n-Ausgange angewahlt werden.

Anwendungen

Decodierer finden als Adressdecodierer Anwendung in digitalen Rechensystemen. Bei-spielsweise werden Peripheriegerate oder Speicherzellen mit einer Adresse angewahlt.

57

REV

1468

A0

A1

A2

Q0

Qn

3-BitAdress-deco-dierer

(a) Blockschaltbild

Eingang AusgangA2 A1 A0 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7

0 0 0 1 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 0 00 1 0 0 0 1 0 0 0 0 00 1 1 0 0 0 1 0 0 0 01 0 0 0 0 0 0 1 0 0 01 0 1 0 0 0 0 0 1 0 01 1 0 0 0 0 0 0 0 1 01 1 1 0 0 0 0 0 0 0 1

(b) Wertetabelle

Abbildung 5.4: 3-Bit Adressdecodierer

5.3 Multiplexer

Funktion

Ein Multiplexer ist ein auswahlendes Schaltnetz. Uber Steuereingange wird einer derDateneingange auf den Ausgang durchgeschaltet.

MUX

D0D1

Dn

S0S1 Sn

y

(a) Blockschaltbild

D0, ...,Dn DateneingangeS0, ..., Sm Steuereingange

Y AusgangG Steuereingange steuern Dateneingange

durch UND-Verknupfung

E Aktivierungseingang Enable (Low-aktiv)

(b) Ein- und Ausgange

Abbildung 5.5: Multiplexer

Beispiel 68. 4-zu-1 MultiplexerDie Funktion eines 4-zu-1 Multiplexers wird durch eine Wertetabelle beschrieben.

LogikfunktionJeweils ein Dateneingang wird mit dem entsprechenden Steuerwort UND-verknupft undauf den Ausgang geschaltet.

Y S0 S1 D0 S0 S1 D1 S0 S1 D2 S0 S1 D3

58

REV

1468

G03 Y

S0

S1

D0

D1

D2

D3

E

(a) Schaltzeichen

S1 S0 Y0 0 D0

0 1 D1

1 0 D2

1 1 D3

(b) Wertetabelle

&

&

&

&

¥ 1

11

S1 S0

D0

D1

D2

D3

(c) Schaltnetz

Abbildung 5.6: 4-zu-1 Multiplexer

SchaltnetzAus der Logikfunktion ergibt sich das Schaltnetz (siehe Abbildung).

Multiplexer mit großerer Wortbreite

Typische Datenwortlangen, die in einem Rechenwerk verarbeitet werden, sind 4 bis 64Bits. Ein Multiplexer, der Datenworte von einem auswartigen Register auf die ALUdurchschaltet, muss auch 4 bis 64 Bit-Eingangsdaten auf den Ausgang mit entsprechen-der Wortlange schalten.

Beispiel 69. 2x4-zu-4 Multiplexer

Es werden die Dateneingange A0, ..,A3 oder B0, ..,B3 auf den Ausgang Y durchge-schaltet. Die Funktion des 2x4-Bit zu 4-Bit Multiplexers wird durch die Wertetabellebeschrieben. Die Auswahl der Eingangsdatenworte wird durch die Steuervariable S fest-gelegt.

5.4 Demultiplexer

Funktion

Der Demultiplexer ist ein verteilendes Schaltnetz. In Abhangigkeit vom Steuerwortwird ein Dateneingang auf einen der moglichen Datenausgange geschaltet. Mit n Steuereingangenkann auf einen von 2n Datenausgangen verteilt werden.

59

REV

1468

S

Y0

Y1

Y2

Y3

A0

A1

A2

A3

B0

B1

B2

B3

MUX2x4:4

(a) Blockschaltbild

S Y0 A0...3

1 B0...3

(b) Werteta-belle

Abbildung 5.7: 2x4-zu-4 Multiplexers

Q0Q1

Qn

S0S1 Sn

D DEMUX

(a) Blockschaltbild

D DateneingangS0, ..., Sm SteuereingangeQ0, ...,Qn Ausgange

G Steuereingange steuern Dateneingangdurch UND-Verknupfung

(b) Ein- und Ausgange

Abbildung 5.8: Demultiplexer

60

REV

1468

Beispiel 70. 1-zu-4 Demultiplexer

G03

01

S0S1

D

Q0

Q1

Q2

Q3

(a) Schaltzeichen

S1 S0 Q3 Q2 Q1 Q0

0 0 0 0 0 D0 1 0 0 D 01 0 0 D 0 01 1 D 0 0 0

(b) Wertetabelle

Q0 S0 S1 DQ2 S0 S1 DQ1 S0 S1 DQ3 S0 S1 D

(c) Schaltfunktio-nen

&

&

&

&

Q0

Q1

Q2

Q3

11

S1 S0

D

(d) Schaltnetz

Abbildung 5.9: 1-zu-4 Demultiplexer

Die Steuerworteingange und der Dateneingang sind wie beim Multiplexer UND-verknupft.Aus der Wertetabelle ergeben sich fur die Ausgange die entsprechenden Schaltfunktionen.

Mehrfach-Demultiplexer

Um ein Mehr-Bit Dateneingangswort D0...3 auf verschiedene Mehr-Bit AusgangskanaleQA,...,D schalten zu konnen, mussen entsprechende Demultiplexer vorhanden sein. DieFunktion eines 1x4-Bit zu 4x4-Bit Demultiplexers wird durch folgende Wertetabelle be-schrieben:

61

REV

1468

D0..3

S0S1

QA,0..3

QB,0..3

QC,0..3

QD,0..3

DEMUX

(a) Blockschaltbild

S1 S0 QA0...3 QB0...3 QC0...3 QD0...3

0 0 D0...3 0 0 00 1 0 D0...3 0 01 0 0 0 D0...3 01 1 0 0 0 D0...3

(b) Wertetabelle

Abbildung 5.10: 1x4-zu-4x4 Demultiplexers

5.5 Komparatoren

Funktion

Komparatoren vergleichen analoge oder binare Signale. In Digitalsystemen sind Kom-paratoren Schaltnetze, die zwei Binarzahlen miteinander vergleichen. Fur zwei Binarzahlena und b gelten z. B. die Vergleichskriterien a=b, a<b und a>b .

Komparatorschaltnetz fur zwei einstellige Binarzahlen

Aus der Wertetabelle konnen die Schaltfunktionen direkt angegeben werden (siehe Ab-bildung 5.11).

Komparatorschaltnetz fur zwei zweistellige Binarzahlen

Sollen mehrstellige Binarzahlen auf =, > oder < untersucht werden, dann sind ver-schiedene Schaltungskonfigurationen denkbar. Mithilfe der Stellenwertigkeit der beidenBinarzahlen kann der Vergleich in einer Wertetabelle dargestellt werden. Aus der Werte-tabelle wiederum ergeben sich nach Vereinfachung die entsprechenden Schaltfunktionen,die dann als Schaltnetz realisiert werden konnen.

Beispiel 71. 2-Bit Komparator

Fur zwei zweistellige Binarzahlen A a1a0 und B b1b0, wobei a0, b0 den Stellenwert20 haben, und a1, b1 den Stellenwert 21, ergibt sich die Wertetabelle:

62

REV

1468

a

b

a b py1qa b py2qa ¡ b py3q

Komparator

(a) Blockschaltbild

y1 y2 y3b a a b a¡b a b0 0 1 0 00 1 0 0 11 0 0 1 01 1 1 0 0

(b) Wertetabelle

y1 a by2 a by3 a b

(c) Schaltfunktionen

1 1

1

&

&

ab

y1

y2

y3

(d) Schaltnetz

Abbildung 5.11: 1-Bit Komparator

63

REV

1468

a0a1

b0b1

A

B

A B pY1qA B pY2qA ¡ B pY3q

Komparator

Abbildung 5.12: 2-Bit Komparator

B A Y1 Y2 Y3

b1 b0 a1 a0 A B A ¡ B A B0 0 0 0 1 0 00 0 0 1 0 0 10 0 1 0 0 0 10 0 1 1 0 0 10 1 0 0 0 1 00 1 0 1 1 0 00 1 1 0 0 0 10 1 1 1 0 0 11 0 0 0 0 1 01 0 0 1 0 1 01 0 1 0 1 0 01 0 1 1 0 0 11 1 0 0 0 1 01 1 0 1 0 1 01 1 1 0 0 1 01 1 1 1 1 0 0

Aus der Wertetabelle ergeben sich nach Vereinfachung die Schaltfunktionen in der DNF:

Y2 a1 b1 a1 a0 b0 a0 b1 b0 fur A BY3 a1 b1 a0 b1 b0 a1 a0 b0 fur A ¡ BY1 Y2 Y3 Y2 Y3 fur A B

Diese Schaltfunktionen konnen als Schaltnetz realisiert werden.

Vergleich mehrstelliger Binarzahlen

Es wird ein Algorithmus angewandt, der schrittweise alle Bit-Stellen miteinander ver-gleicht. Der Vergleich kann mit der MSB-Stelle (werthochste) oder der LSB-Stelle (wert-niedrigste) beginnen. Die Realisierung fuhrt zu mehrstufigen Schaltnetzen.

5.6 Arithmetische Schaltnetze (Addierer)

In einem Computer gehoren Addierer zur arithmetisch/logischen Einheit (engl.: Arith-metic Logic Unit [ALU]). Addierer sind Schaltnetze, die zwei Dualzahlen miteinander

64

REV

1468

addieren. Dualzahlen werden wie Dezimalzahlen stellenweise addiert, beginnend bei derniederwertigsten Stelle (least significant bit [LSB]).

5.6.1 Halbaddierer

Die Addition zweier einstelliger Dualzahlen A und B ergibt vier Wertekombinationen.Das Ergebnis wird mit Summe Z und Ubertrag C gekennzeichnet. Diese vier Kombi-nationen konnen in eine Wertetabelle ubertragen werden, aus der man die Schaltfunk-tionen fur Z und C in eine DNF ubertragen kann.

A B Z C0 0 0 00 1 1 01 0 1 01 1 0 1

(a) Wertetabelle

Z A B A B A` BC A B

(b) Schaltfunktionen

&

1

C

Z

B

A

(c) Schaltnetz

HA

BA

C

Z

(d) Schaltsymbol

Abbildung 5.13: Halbaddierer

Ubertragt man diese Funktion in ein Schaltnetz, erhalt man die Gatterstruktur fureinen einfachen Addierer. Betrachtet man nun den Addierer als ein Gatter mit denzwei einstelligen Eingangen A und B und den Ausgangen Z und C, so erhalt man einenHalbaddierer (HA).

5.6.2 Volladdierer

Bei Addition von zwei mehrstelligen Dualzahlen (A und B) werden nicht zwei sonderndrei Bit addiert, weil der Ubertrag (Ci) von der nachst niedrigeren Stelle hinzukommt.Ein Schaltnetz, das drei Bit addieren kann und daraus die Summe Z und den UbertragCi1 bildet, wird Volladdierer (VA) genannt. Solche Additionen konnen nicht miteinem Halbaddierer durchgefuhrt werden.

Auch fur den Volladdierer gibt es eine Wertetabelle und Schaltfunktion, die zu einemwesentlich komplexeren internen Aufbau des Volladdierers im Vergleich zum Halbaddie-rer fuhren.

65

REV

1468

Ci A B Z Ci1

0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

(a) Wertetabelle

Z A B Ci A B Ci A B Ci A B Ci

Z A` B ` Ci

Ci1 A B A Ci B Ci

Ci1 A B pA BqCi

(b) Schaltfunktionen

&

¥ 1

&

&

&

¥ 1

&

¥ 1

A B Ci

Z

Ci1

(c) Schaltnetz

VA

BA

Ci Ci1

Z

(d) Schaltsymbol

Abbildung 5.14: Volladdierer

66

REV

1468

5.6.3 Mehrstellige Addierer

Addition zweier mehrstelliger Dualzahlen kann bitseriell oder bitparallel erfolgen. Manspricht daher auch von Serienaddierer und Paralleladdierer. Beide Addiernetze un-terscheiden sich wesentlich im Hardwareaufwand und in der Addierzeit. Serienaddiererfuhren pro Taktschritt nur eine Stelle der Addition aus (mit Speicherelementen). Par-alleladdierer hingegen fuhren wahrend eines Taktschrittes die Addition aller Stellenaus.

5.7 Arithmetisch/Logische Einheit (ALU)

Die Basisfunktionalitat von programmgesteuerten datenverarbeitenden Geraten wirdvon arithmetisch-logischen Einheiten abgebildet. Sie stellen somit den Kern des da-tenverarbeitenden Operationswerks dar. Ihre Komplexitat ist hoch genug um mehrereelementare Operationen durchfuhren zu konnen. Diese lassen sich - wie man dem Namender Einheit entnehmen kann - in arithmetische und logische Operationen gruppieren.Trotz der Vielzahl an durchfuhrbaren Operationen ist die strukturelle Komplexitat (derAufbau) einer ALU, bedingt durch die Ahnlichkeiten zwischen den einzelnen Operatio-nen, relativ gering.

Der wesentliche Unterschied zwischen den arithmetischen und logischen Operationenbesteht darin, dass erstere auf 2-Komplement-Zahlen arbeiten, letztere aber auf einzelnenBits, wobei diese jedoch zu Bitvektoren zusammengefasst werden konnen.

Es konnen alle 16 logischen Operationen (siehe Tabelle 1.1) durchgefuhrt werden, diemit zwei Variablen moglich sind. Bei den arithmetischen Operationen sind nur elemen-tare realisierbar (Zahlen, Komplementieren, Addieren, Subtrahieren). Komplexere Ope-rationen (Multiplizieren, Dividieren, Radizieren) werden durch zusatzliche Programme,Schaltwerke oder Schaltnetze abgebildet.

Herleiten der ALU-Struktur

Bei der Verarbeitung von 2-Komplement-Zahlen ist es wichtig, Strukturen vorzusehen,die den Austausch von Informationen uber die einzelnen Bitstellen hinweg ermoglichen.Bei dem Volladdierer ist eine solche Struktur mit dem Ubertrags-Bit vorhanden. MitHilfe der Volladdierergleichung und einigen Umformungen lasst sich aus einem Vollad-diererglied ein ALU-Glied ableiten.

Die Volladdierergleichungen:

ci1 ai bi pai biq ci Ubertragungsfunktionzi ai bi ci Summenfunktion

lassen sich durch folgende Ersetzungen:

Gi ai bi Generate (Ubertrag generieren)Pi ai bi Propagate (Ubertrag propagieren)

67

REV

1468

umschreiben zu:

ci1Gi Pi cizi ai bi ci

pai bi ai biq cipGi Piq ci

Aus dem einfachen 1-Bit-Volladdierer entsteht eine 1-Bit-ALU, indem die so ent-standenen Gleichungen um einen Steuervektor s erweitert wird. Dieser dient dazu dieGenerate- und Propagate-Funktions-Variable erzeugen zu konnen sowie die Funktiona-litat um logische Operationen zu erweitern.

Mit dem Steuervektor s rs0s1s2s3s4s lauten die Gleichungen des ALU-Glieds:

Gi s0 ai bi s1 ai bi

Pi ps2 ai biq ps3 ai biqci1Gi Pi cizi pGi Piq ps4 ciq

Durch Variation von s0 . . . s4 konnen zusatzlich zur Addition (Steuervektor s r10010s)eine Vielzahl weiterer Operationen gebildet werden. s4 dient dazu zwischen den bei-den Operationsgruppen zu unterscheiden. Mit s4 0 ist das Ergebnis zi abhangig vomUbertrag ci, weil sich die Gleichung wieder auf zi pGi Piq ci reduzieren lasst. s4 0kennzeichnet somit die arithmetischen Operationen. Demzufolge werden die logischenOperation durch s4 1 gekennzeichnet, denn dadurch wird das Ergebnis (zi Gi Pi)vollig unabhangig vom Ubertrag ci.

Samtliche ALU-Operationen mit n-stelligen 2-Komplement-Zahlen bzw. Bitvektorenlassen sich der Tabelle 5.1 entnehmen.

68

REV

1468

& ¥1

¥ 1 &

¥1

& &

¥1

ai bi

ci1ci

zi

(a) VA-Glied

& & ¥1

¥1

¥1

&

¥ 1 &

¥1

¥1

& &

¥1

ai s1 s2 bi

s0 s3

ci1ci

s4

zi

(b) ALU-Glied

Abbildung 5.15: Gegenuberstellung eines Volladdierer-Gliedes mit einem ALU-Glied

69

REV

1468

s0 s1 s2 s3 arithmetische Operationen logische Operationen0 0 0 0 Z 1 c0 Z 00 0 0 1 Z A_ B c0 Z A_ B0 0 1 0 Z A_ B c0 Z A^ B0 0 1 1 Z A c0 Z A0 1 0 0 Z A^ B 1 c0 Z A^ B0 1 0 1 Z pA_ Bq pA^ Bq c0 Z B0 1 1 0 Z A B 1 c0 Z A B0 1 1 1 Z pA^ Bq A c0 Z A^ B1 0 0 0 Z pA_ Bq 1 c0 Z A^ B1 0 0 1 Z A B c0 Z A B1 0 1 0 Z pA_ Bq pA^ Bq c0 Z B1 0 1 1 Z pA^ Bq A c0 Z A_ B1 1 0 0 Z A 1 c0 Z A1 1 0 1 Z pA_ Bq A c0 Z A_ B1 1 1 0 Z pA_ Bq A c0 Z A_ B1 1 1 1 Z A 2 c0 Z 1

Tabelle 5.1: Operationen einer ALU. Anmerkung: logische Operationen werden hier mit_ und ^ dargestellt, um sie von den arithmetischen (Addition , Multipli-kation ) unterscheiden zu konnen.

5.8 Schaltketten

Schaltketten sind mehrstufige Schaltnetze, die vorwiegend aus identischen bzw. generi-schen Teilschaltnetzen aufgebaut sind. Sie treten bei der Realisierung rekursiver Funk-tionen auf. Charakteristisch fur solche Funktionen ist, dass auf beiden Seiten der Funk-tionsgleichung Variablen mit gleichem Namen (nur durch einen Index unterschieden)auftreten. Zum Beispiel:

wi1 fpai, bi,wiq, fur i 0, 1, . . . , n 1

Dies gilt als Kurzschreibweise fur

wn fpan1, bn1, fpan2, bn2, . . . , fpa0, b0,w0qqq mit w0 1 oder w0 0

Mit rekursiven Funktionen lassen sich Operationen zwischen Dualzahlen (Addition,Multiplikation, Vergleich) gut beschreiben. Derartige Schaltungen haben Bedeutung inRechenanlagen. Ein Typisches Beispiel fur rekursive Schaltfunktionen ist die Ubertrags-funktion bei der Addition. Eine Verknupfung von Volladdierern zum Zwecke der Addi-tion zweier n-Stelliger Zahlen ergibt dabei eine Schaltkette. Wir vereinbaren dazu, dassDualziffern ohne Umbenennung als Schaltvariablen behandelt werden.

Beispiel 72. Additionsschaltkette fur zwei DualzahlenMit Volladdierern als Zelle wird ein Addierer fur zwei Dualzahlen a anan1 . . . a0,b bnbn1 . . . b0 als Schaltkette folgendermaßen realisiert:

70

REV

1468

ci1 ai bi ai ci bi ci Fpai, bi, ciq Ubertragsfunktion

zi pai ` biq ` ci Gpai, bi, ciq Summenfunktion

VAVA

VA

cn1zn

an bn

cn

zn1

z0

an1 bn1

cn1 c1

a0b0

c0

Abbildung 5.16: Additionsschaltkette fur zwei Dualzahlen

Die Glieder einer Schaltkette werden auch Kettenglieder genannt. Sie haben stets dasgleiche Schaltverhalten und verarbeiten neben Eingangsvariablen ai, bi auch Ubertrageci vom vorherigen Kettenglied, die durch die Ubergangsfunktion F bestimmt sind. DieUbertrage fur das 1. Kettenglied (c0 0) werden als Anfangswerte bezeichnet. Da An-fangswerte meist Schaltkonstanten sind, ist das 1. Glied der Kette haufig eine einfachereSchaltung. Jedes Kettenglied kann außerdem Ausgangsvariablen haben (hier zi). Diedazugehorige Schaltfunktion (das zugehorige Funktionsbundel) heißt Ausgangsfunktion(G). Auch die Ubergangsfunktion kann ein Funktionsbundel sein.

Beispiel 73. Eindimensionale Schaltkette

KGKG

KG

cn1yn

en

cn

yn1

y0

en1

cn1 c1

e0

c0

Abbildung 5.17: Verallgemeinerte eindimensionale Schaltkette

Es werden die folgenden n-Tupel von Schaltvariablen gebildet:

71

REV

1468

ei pe1i, e2i, . . . , eriq Eingangsvektor

ci pc1i, c2i, . . . , criq Ubergangsvektor

yi py1i, y2i, . . . , yriq Ausgangsvektor

ci1 Fpei, ciq Ubergangsfunktion

yi Gpei, ciq Ausgangsfunktion

c0 Anfangsvektor

F

G

eici

yi

ci1

Abbildung 5.18: Kettenglied

Jedes Kettenglied kann selbst ein Schaltnetz sein. Beim Entwurf von Schaltketten istzunachst eine schaltalgebraische Beschreibung des Problems mit rekursiver Ubergangs-funktion und Ausgangsfunktion aufzustellen. Danach ist das Kettenglied als Schaltnetzzu entwerfen. Es ist jedoch nicht jedes schaltalgebraische Problem dazu geeignet, mitSchaltketten realisiert zu werden.

Beispiel 74. Komparator fur zwei DualzahlenEntwurf einer Schaltkette, die zwei n 1-stellige Dualzahlen auf Gleichheit pruft:

a anan1 . . . a0

b bnbn1 . . . b0

w "

1, fur a b0, fur a b

Zur Vereinfachung werden Aquivalenzgatter verwendet. Gleichheit tritt genau dannein, wenn die Dualziffern an jeder Stelle paarweise gleich sind:

w pan bnq pan1 bn1q . . . pa0 b0qDieser logische Ausdruck kann rekursiv abgearbeitet werden:

w1 a0 b0 pa0 b0q w0 mit w0 1

w2 pa1 b1q w1

wn1 pan bnq wn

w wn1

72

REV

1468

Die Ubergangsfunktion ist:

wi1 Fpai, bi,wiq pai biq wi i 1, . . . , n

w1 a0 b0

Das erste Kettenglied wurde mit dem Anfangswert w0 1 vereinfacht.

a0 b0

w1

a1 b1

w2

bn1an1

wn

wn1

anbn

&&

&

Abbildung 5.19: Komparator fur zwei Dualzahlen

Laufzeitproblem

Schaltketten konnen betrachtliche Langen erreichen. Das bringt lange Signallaufzeitenund eventuell Hazards mit sich. Die Laufzeit ist das Produkt aus der Zahl der Ketten-glieder und der Verzogerungszeit eines Gliedes. Die Nachteile sind nur teilweise durchschaltungstechnischen Mehraufwand auszugleichen. Ein 2-Stufiges Schaltnetz garantiertnicht die minimale Signallaufzeit. Es ist effizienter, einige Kettenglieder (meist 2, 4 oder8) zusammenzufassen und 2-stufig zu realisieren. So werden beispielsweise 2-, 4- und8-Bit-Volladdierer und 4- und 8-Bit-Vergleicher als Bausteine/Zellen eingesetzt, die sichdann wieder als Kettenglieder in Schaltketten verwenden lassen. Diese Bausteine sindallerdings nicht immer zweistufig realisiert.

Zwei- und mehrdimensionale Schaltketten

Bei zweidimensionalen Schaltketten empfangt jedes Kettenglied von zwei verschiedenenKettengliedern Ubergangssignale und gibt Signale an zwei Kettenglieder ab.

Beispiel 75. MultiplikationsschaltketteEine Schaltkette zur Multiplikation zweier 4-stelliger Dualzahlen

a a3a2a1a0 und b b3b2b1b0

Die Multiplikation von Dualzahlen wird nach dem vom dezimalen Rechnen her gelaufigenAlgorithmus durchgefuhrt. Der Multiplikant wird mit jeder Ziffer des Multiplikators mul-tipliziert. Das Endergebnis ergibt sich durch die stellenwertrichtige Aufsummierung derTeilprodukte.

73

REV

1468

a3 a2 a1 a0 b0

a3 a2 a1 a0 b1

a3 a2 a1 a0 b2

a3 a2 a1 a0 b3

m7 m6 m5 m4 m3 m2 m1 m0 a b

Es gilt:

ai bi "a, falls bi 10, falls bi 0

Um das Problem rekursiv formulieren zu konnen, erfolgt die Einfuhrung der Zwischen-summen:

zi zi7zi6 . . . zi0

z0 0000000

zi1 zi 2iabi fur i 0, 1, 2, 3

Damit gilt fur das Produkt:

z4 m7m6m5m4m3m2m1m0 a b

Fur die Schaltalgebraische Beschreibung erhalt man:

zi1j pzij ` paji biqq ` cij

cij1 zij paji biq zij cij paji biq cij

zii4 ci1,i4

ciis0J

0 0

*Anfangswerte fur i 0, 1, 2, 3 und j i, i 1, i 2, i 3

Fur die Dualziffern des Produktes a b gilt:

mj zj1 fur j 0, 1, 2

mj z4j fur j 3, 4, 5, 6

m7 c37

Die Beschreibung der Produktziffern wurde so gewahlt, um unnotige Kettenglieder einzu-sparen. Statt 16 Kettengliedern wurden sonst 28 benotigt, von denen 12 nur 0 addieren.Ein Kettenglied stellt sich dann wie in Abbildung 5.20a dar. Das in 5.20b dargestellteSchaltnetz wurde durch Ausnutzung der Anfangswerte vereinfacht.

74

REV

1468

aji bi

zij cij

zi1,j ci,j1

&

VA

(a) Kettenglied

& & & &

& & & &

VA VA VA HA

& & & &

VA VA VA HA

& & & &

VA VA VA HA

b0

b1

b2

b3

a3 a2 a1 a0

m0m1m2m3m4m5m6m7

(b) Multiplikationsschaltkette

Abbildung 5.20: Multiplikation zweier Dualzahlen

75

REV

1468

5.9 Schiebeeinheit

Eine weitere elementare Operation, neben den gezeigten arithmetsich-logischen Opera-tionen, ist die Schiebeoperation (Shift). Auch wenn es unterschiedliche Auspragungenvon Schiebeoperationen gibt, so ist die prinzipielle Funktion immer die gleiche: bei einemBitvektor wird jedes einzelne Bit von seiner ursprunglichen Stelle in diesem Vektor zueiner anderen verschoben.

Unterschieden werden die Schiebeoperationen zunachst nach der Richtung in welchegeschoben wird und nach der Art wie mit den Bits am Anfang und Ende des Bitvektorsumgegangen wird. Bits die sich an diesen Stellen befinden, werden durch die Schiebe-operation entweder aus dem Bereich des Vektors hinausgeschoben, oder Stellen mussensinnvoll aufgefullt werden. In Abbildung 5.21 sind die unterschiedlichen Varianten auf-gefuhrt. Neben der Schieberichtung und -art kann man Shift-Einheiten auch noch um

1 0 1 1 0 1 0 1

0 1 1 0 1 0 1 0

0

(a) logischer Links-Shift

1 0 1 1 0 1 0 1

0 1 0 1 1 0 1 0

0

(b) logischer Rechts-Shift

1 0 1 1 0 1 0 1

0 1 1 0 1 0 1 0

0

(c) arithmetischer Links-Shift

1 0 1 1 0 1 0 1

1 1 0 1 1 0 1 0

(d) arithmetischer Rechts-Shift

1 0 1 1 0 1 0 1

0 1 1 0 1 0 1 1

(e) Links-Rollen

1 0 1 1 0 1 0 1

1 1 0 1 1 0 1 0

(f) Rechts-Rollen

Abbildung 5.21: Die unterschiedlichen Auspragungen der Schiebeoperation (Shift)

eine variable Shift-Weite erganzen, die es ermoglicht einen Bitvektor um jede beliebigeStellenanzahl in jede Richtung zu verschieben. Schiebe-Operationen mit diesem Funkti-onsumfang sind in einer relativ einfachen ALU nicht realisierbar, da man beispielsweiseden Ubertrag eines Gliedes auch an die niederwertigen Glieder weitergeben konnen muss,um Schiebeoperationen nach rechts durchfuhren zu konnen. Deswegen werden Schiebe-operationen oft in extra Funktionseinheiten realisiert. Der bekannteste Vertreter einerSchiebeeinheit ist der Barrelshifter (siehe Abbildung 5.22).

76

REV

1468

i0

i1

i2

i3

i4

i5

i6

i7

ir

il

o0

o1

o2

o3

o4

o5

o6

o7

Abbildung 5.22: Multiplexerbasierte Implementierung eines Barrelshifters zur Realisie-rung von Schiebeoperationen mit variabler Schiebeweite

77

REV

1468

6 Speicherglieder

6.1 Begriffe und Kenngroßen

6.1.1 Speicherelement

Ein Speicherelement muss zwei physikalische Zustande besitzen, die den binarenWerten 0 und 1 zugeordnet werden konnen. Beide Werte mussen von außen verandertwerden konnen (Schreiben bzw. Speichern). Außerdem mussen die Speicherelementenach bestimmten Kriterien wieder aufgefunden werden konnen (z.B. durch Adresse oderInformationsinhalt).

6.1.2 Speicherkapazitat

Die Speicherkapazitat gibt die Anzahl der Speicherelemente oder Zellen im Speicher an.Die gebrauchlichen Einheiten sind Bit und Byte, wobei 8 Bits 1 Byte entsprechen.Großere Speicherkapazitaten werden mit Großenfaktoren Ki (kibi) , Mi (mebi) und Gi(gibi) bezeichnet. Hierbei gilt, abweichend vom Dezimalsystem (Kilo = 103, Mega = 106,Giga = 109):Ki = 210 = 10241 = 1.024Mi = 220 = 10242 = 1.048.576Gi = 230 = 10243 = 1.073.741.824Die Abweichung beruht auf der dualen Speicheradressierung.

6.1.3 Speicherorganisation

Die Speicherorganisation beschreibt die Speicherkapazitat und die Auswahlmoglichkeit.

6.1.4 Arbeitsgeschwindigkeit

Die Arbeitsgeschwindigkeit kann je nach Speichertyp durch die Großen Zugriffszeit,Zykluszeit und Datenrate/Ubertragungsgeschwindigkeit charakterisiert werden.

Zugriffszeit tz

Die Zugriffszeit ist die Zeitspanne zwischen dem Adressieren einer Speicherzelle bis zumAnstehen der gesuchten Daten am Ausgang.

78

REV

1468

D

T

Q

(a) Zugriffszeit

D

T

Q

(b) Zykluszeit

Abbildung 6.1: Ein-Bit-Speicherzelle

Zykluszeit tc

Die Zykluszeit entspricht dem minimalem Zeitabstand mit dem zwei aufeinanderfolgendeDaten eingeschrieben bzw. ausgelesen werden konnen. Im Grenzfall kann die Zykluszeitgleich der Zugriffzeit werden. Im Allgemeinen ist sie aber großer.

Datenrate oder Ubertragungsgeschwindigkeit

Die Datenrate entspricht der Geschwindigkeit, mit der Daten ausgelesen und eingeschrie-ben werden konnen (meistens Kehrwert der Zykluszeit).

6.1.5 Weitere Kenngroßen

Neben den Kosten pro Bit (Bitpreis) wird Speicher auch nach der Speicherdichte klas-sifiziert, wobei letzteres in Bit pro mm2 angegeben wird. Zudem gibt es dann nochdie Zuverlassigkeit des Speichers. Diese wird durch die Ausfallrate und das Signal-Rauschverhaltnis (engl.: Signal-to-Noise-Ratio [SNR]) angegeben.

6.2 Klassifizierung digitaler Speicher

6.2.1 Einteilung nach Arbeitsgeschwindigkeit und Kapazitat

Die Hauptparameter Arbeitsgeschwindigkeit, Kapazitat und Kosten konnen nichtgleichzeitig optimiert werden. Hohe Arbeitsgeschwindigkeit bedeutet beispielsweise hoheKosten und wird meist mit Speichern kleinerer Kapazitat realisiert. Es ist daher je nachAnwendungsfall ein Kompromiss zu schließen. Fur Rechenanlagen wird ein hierarchi-sches Speichersystem eingesetzt.

6.2.2 Einteilung nach der Art des Zugriffs

Informationen konnen im Wesentlichen durch zwei Arten wiederaufgefunden werden.Zum einen kann durch Adressierung eines ortsadressierten Speichers der Inhalt erreichtwerden. Die andere Moglichkeit ist das Auffinden von Dateninhalten in inhaltsadressier-ten Speichern (engl.: content adressed memory [CAM]).

79

REV

1468

zentrale Verarbeitungseinheit

Registerspeicher

Pufferspeicher

Arbeitsspeicher

Hintergrundspeicher

On-line-Massenspeicher

Datenarchiv

interne Speicher

externe Speicher

KapazitatArbeitsge-schwindigkeit

Abbildung 6.2: Aufbau der Speicherhierarchie

Adressierung

Beim Wiederauffinden der Information durch Adressierung wird zwischen wahlfreiemZugriff (random access) und seriellem Zugriff (serial access) unterschieden.

Beim Random-Access kann jede Speicherzelle unabhangig von den Anderen adressiert,beschrieben und gelesen werden. Diese Zugriffsart ermoglicht die kurzeste Zugriffszeit.Sie findet beispielsweise im Hauptspeicher von Rechner Verwendung.

Der seriellen Zugriff ist abhangig von einer bestimmter Reihenfolge, so dass der Spei-cherplatz nicht direkt erreichbar ist. Der Durchlaufspeicher ist ein Beispiel dafur. Diezuerst angekommenen Daten werden auch wieder zuerst ausgegeben (first-in-first-out-Prinzip [FIFO]).

Dateninhalt

Typische Vertreter dieser Assoziativspeicher sind beispielsweise Caches und Renaming-Register wie sie in superskaleren Prozessoren verwendet werden aber auch das mensch-liche Gehirn.

6.2.3 Einteilung nach Art des Datenverkehrs

Schreib-Lese-Speicher

Die Daten konnen mehrfach gespeichert (Schreiben) und wieder abgerufen (Lesen)werden.

80

REV

1468

Adressieren

Treffer/Lesen

Maske/Schreiben

0 1 0 1

0 1 0 1

1

Abbildung 6.3: Zugriff auf inhaltsadressierte Speicher

Lesespeicher/Festwertspeicher

Das Einschreiben erfolgt einmalig, wahrend des Herstellungsprozesses. Diese Speichernennt man (nur) Lesespeicher (engl.: read only memory [ROM]). Ist diese einmaligeEinspeicherung durch den Anwender moglich, so spricht man von programmierbarenLesespeichern (programmable ROM, PROM, EPROM). Wenn die Einspeicherung ein re-versibler Prozess ist, also mehrmals moglich ist,dann werden solche Speicher als EAROM,EEROM (electrical erasable ROM) bezeichnet (z. B. Flash-Speicher).

6.3 Halbleiterspeicher

6.3.1 Einleitung

Uberblick

Der Bedarf große Datenmengen zu speichern fuhrte in den letzten 30 Jahren zur Ent-wicklung zahlreicher Technologien. Bei Halbleiterspeichern konnten große Fortschrittebei der Kapazitatserhohung und der Kostensenkung pro Bit erzielt werden. DieKosten je Bit haben sich seither auf unter ein 1/100 reduziert und liegen 2007 etwa bei10 Euro je GiBit. Die Kapazitat hat 2GiByte je Chip erreicht.

Ein weiterer Grund fur den Einsatz von Halbleiterspeichern ist die Kompatibilitatzwischen Speicher und Prozessor. Hierbei sind die jeweiligen Betriebsspannungen undPegel gleich, da die Speicher und Prozessoren in der gleichen Technologie hergestelltsind. Dadurch entfallen teure und storanfallige Interfaceschaltungen. Zusatzlich bestehtdie Moglichkeit großere Speichersysteme modular aus kleineren Bausteinen aufzubauen.

81

REV

1468

Jahr

DRAM[Mbit]

Strukturgroße[µm]

1980 1990 2000 2010

1

10

102

103

104

105

106

2

0.2

0.1

0.04

4 Mbit

64 Mbit

1 Gbit

16 Gbit

256 Gbit

1 MTr

50 MTr

1 GTr

Trans. pro Mikroprozessor

DRAM-Komplexitat (bit)

Abbildung 6.4: Uberblick der Technologie-Generationen

Realisierung unterschiedlicher Organisationsformen

Die Schreib-Lese-Speicher konnen statisch oder dynamisch ausgefuhrt sein. Diestatischen Zellen halten die Information solange, wie Versorgungsspannung anliegt. Diedynamischen Zellen erfordern in bestimmten Zeitabstanden sogenannte Refresh-Impulse,damit die Daten nicht verloren gehen. Festwertspeicher sind nichtfluchtige Spei-cher.

Statische Halbleiterspeicher

Statische Halbleiterspeicher besitzen kurze Zugriffszeiten. Im Vergleich zu dynami-schen Speichern ist aber fur die Realisierung ein hoherer Schaltungsaufwand not-wendig. Anwendung finden die statische Halbleiterspeicher hauptsachlich in Speicher-bausteinen kleiner und mittlerer Kapazitat. Ihr Einsatz wird vorrangig durch eine kurzeZugriffszeit bestimmt. Realsiert werden diese Speicher in Bipolar- und MOS-Technik.

Dynamische Halbleiterspeicher

Dynamische Halbleiterspeicher kommen in komplexen Speichersystemen wegen ihrer ho-hen Integrationsdichte zum Einsatz. Hergestellt werden diese Speicher nur in MOS-Technik.

82

REV

1468

6.3.2 Bistabile Kippstufe

Funktionsprinzip der statischen Speicherung

Realisiert werden statische Speicher mit zwei Invertern, deren Ausgange auf die Eingangeder jeweils anderen Stufe zuruckgefuhrt sind. Diese Schaltung mit zwei kreuzgekoppeltenInvertern wird als bistabile Kippstufe oder als Flipflop bezeichnet.

T1 T2

RL1 RL2

UDD

UDD0 V

U1 U2

(a) Zustand 1

T1 T2

RL1 RL2

UDD

0 VUDD

U1 U2

(b) Zustand 2

Abbildung 6.5: Bistabile Kippstufe

Funktionsweise der Kippstufe (Abbildung 6.5)

Fur die Anfangsbetrachtung sei T1 leitend, U1 wird auf etwa 0 V gezogen. Diese Spannungliegt gleichzeitig am Gate von T2 an, der somit sperrt. Wegen des Widerstandes RL2 stelltsich die Spannung U2 auf UDD ein. Da diese Spannung auch am Gate von T1 anliegt,bleibt T1 leitend.

6.3.3 Dynamischer MOS-Speicher

Funktion

Die einfachste dynamische Speicherzelle ist das 1-Transistorelement. Uber den TransistorT wird eine Kapazitat C geladen und die Spannung an ihr wieder abgefragt.

Schreiben

Der Transistor T wird mit einer”1“ auf der Wortleitung leitend und die Kapazitat C

wird auf den Pegel der Datenleitung aufgeladen.

Lesen

Der Transistor T wird mit einer”1“ auf der Wortleitung leitend und die Ladung der

Kapazitat C wird abgefragt. War eine”0“ gespeichert, befand sich keine Ladung auf C.

83

REV

1468

T

C

Datenleitung

Wortleitung

Abbildung 6.6: Dynamische 1-Transistor-Zelle

Da beim Lesen der Ladung von C entnommen wird, muss sie anschließend regeneriertwerden.

6.3.4 Ein-Bit-Flipflopspeicher

Asynchrones RS-Flipflop

&

&

S

R

Q

Q

(a) NAND-Gattern

¥ 1

¥ 1

S

R

Q

Q

(b) NOR-Gattern

S

RR

S Q

Q

(c) Schaltzeichen

Abbildung 6.7: RS-Flipflop realisiert mit unterschiedlichen Gattertypen

Als Speicherglied wird eine bistabilen Kippstufe aus zwei kreuzgekoppelten NAND- oderNOR-Gattern eingesetzt. Jeweils ein Eingang der beiden Gatter wird fur die Ruckkopp-lung verwendet, die freien Eingange dienen zum Setzen (S) bzw. Rucksetzen (R). Inder Praxis hat dieses RS-Flipflop als Einzelelement zur Speicherung wenig Bedeutung.Der Grund dafur liegt im asynchronen Verhalten, denn die Information wird geladenbzw. geloscht, sobald am Setz- oder Rucksetzeingang ein Signal anliegt. Ein weitererNachteil ist durch die verbotenen Eingangskombinationen (NAND-Gliedern: R S 0,NOR-Gliedern R S 1) gegeben.

Unzulassige Eingangskombination (NOR)

Der Zustand der Ausgange Q und Q ist nicht mehr negiert zueinander. Beide Ein-gangstransistoren werden fur R S 1 leitend und schalten den

”L“-Pegel auf beide

Ausgange.

84

REV

1468

R S Q Q

0 0 Q Q0 1 1 01 0 0 11 1

Abbildung 6.8: Wahrheitstabelle fur NOR-Flipflop

Die mogliche Eingangskombination R 1, S 1 ergibt eine mehrdeutige Ausgangssitua-tion Q 0, Q 0 und ist deshalb unzulassig.

Getaktetes RS-Flipflop

Bei synchronen Schaltwerken soll eine bereits anliegende Information erst zu einem be-stimmten Zeitpunkt in das Flipflop ubernommen werden. Dieses Verhalten wird durchdie jeweilige Verknupfung des R- und S-Einganges mit einem Steuertakt T erzielt.

S

T

R

Q

Q

&

&

¥ 1

¥ 1

(a) Schaltung

1S

C1

1RRTS Q

Q

(b) Schaltzeichen

Abbildung 6.9: Getaktetes RS-Flipflop

Die Wahrheitstabelle bleibt dieselbe wie fur das asynchrone RS-Flipflop. Sie wird ledig-lich durch die Bedingung erweitert, dass sie nur fur den Zeitraum T 1 gilt.

Getaktetes D-Flipflop (Latch)

Der unzulassige Zustand R S 1 (bei NOR) bzw. R S 0 (bei NAND) lasst sichdurch eine Beschaltung des Ruckstelleingangs mit negiertem Signal des Setzeingangesumgehen. Die Kombination R S 0 bzw. R S 1 wird so prinzipiell vermieden.Dieses Flipflop bezeichnet man als Delay-Flipflop oder Latch.

Master-Slave-D-Flipflop

Das einfache D-Latch weist den Nachteil auf, dass wahrend T 1, sich jede Anderung desD-Einganges auf den Ausgang ubertragt (Transparenz). Dies kann durch Anwendungdes Master-Slave-Prinzips vermieden werden. Es werden zwei Flipflops kaskadiert,wobei das zweite mit negiertem Takt angesteuert wird. Dadurch wird gewahrleistet,dass immer nur eines der beiden Flipflops Daten ubernehmen kann.

85

REV

1468

DS

T

R

Q

Q1

&

&

¥ 1

¥ 1

(a) Schaltung

1D

C1

DT

Q

Q

(b) Schaltzeichen

D Qt1

0 01 1

(c) Wertetabelle

Abbildung 6.10: Getaktetes D-Flipflop

1D

C1

1D

C1

1

DT

Q

Q

T

(a) Schaltung

1D

C1

DT

Q

Q

(b) Schaltzeichen

T

T

1 2 3 4

(c) Taktimpuls

Abbildung 6.11: Master-Slave-D-Flipflop

Erlauterung der Arbeitsweise des MS-Flipflops am Verlauf der Taktflanken

Punkt Beschreibung1 Sperren der Eingange des Slave-Flipflops2 Ubernahme der Information in das Master-Flipflop3 Sperren des Dateneingangs des Master-Flipflop4 Ubernahme der Information vom Master-Flipflop in das Slave-Flipflop

Zwischen dem Setzen des Master-Slave-Flipflops und dem Anliegen der Daten an denAusgangen vergeht eine halbe Taktperiode. Da die Ubernahme vom Master zum Sla-ve wahrend einer Taktflanke erfolgt, werden Master-Slave-Flipflops als taktflankenge-steuerte Flipflops bezeichnet.

86

REV

1468

6.3.5 Speicherorganisation eines SRAMs

Zeilenadressdecodierer

Spaltenadressdecodierer

Speicherfeld 4K x 4K Bit

DemuxMux

1BitSpeicherzellepFlipflopq

A11 A0

DIN

A23 A12

DOUT

12

1

12

1

Abbildung 6.12: Speicherorganisation eines SRAMs

87

REV

1468

7 Programmierbare Logik

7.1 Einleitung

Fur die Entwurfsmethodik digitaler Schaltungen gilt es mehrere Dinge zu beachten. DieWahl der Schaltungsstruktur wird durch den Technologiefortschritt beeinflusst. Wurdefruher die Minimierung der Transistoranzahl (Chipflache) angestrebt, sind heute oft kur-ze Entwurfszeit, Low-Power oder Geschwindigkeit wichtiger. Der Trend orientiert sichweg von chipflachenoptimierter Schaltung hin zu synthetisierbaren Strukturen, Ausnah-men bilden komplexitats- und geschwindigkeitsoptimierte Schaltungen.

7.2 Schaltnetze aus Multiplexern

Der Schaltnetzentwurf lasst sich mit Multiplexern (universal logic module ULM) ver-einfachen, wenn weder Schaltgeschwindigkeit, Komplexitat oder Verlustleistung kritischsind. Ein Vorteil ist ihre hohe Programmierbarkeit (FPGAs). Mit Multiplexern fur nKontrollvariablen lassen sich alle Funktionen aus diesen Variablen bilden, fur Funktionenmit mehr Variablen als die des Multiplexers erfolgt eine Kaskadierung von Multiplexernin zwei oder mehreren Ebenen (Datenselektor).

Der logische Entwurf mit Multiplexern erfolgt mit Hilfe des Erweiterungstheorems vonShannon. Die Funktion wird entsprechend der Multiplexerstruktur erweitert.z. B. um x1 und x2:

fpx1, x2, . . . , xnq x1 x2 fp0, 0, x3, . . . , xnq x1 x2 fp0, 1, x3, . . . , xnqx1 x2 fp1, 0, x3, . . . , xnq x1 x2 fp1, 1, x3, . . . , xnq

Beispiel 76. Abbildung einer Funktion auf einen 3-Variablen-Multiplexer:

f x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4

Bei der kaskadierten Erweiterung werden die Teilterme entsprechend erweitert, wobeidie Variablen die Kontrollfunktion fur die nachfolgenden Ebenen ubernehmen.

88

REV

1468

Beispiel 77. Implementierung mit 1-Variablen und 2-Variablen-Multiplexer:

f x1 rx2 x3 px4q x2 x3 px4q x2 x3 p0q x2 x3 p1qsx1 rx2 x3 p0q x2 x3 p0q x2 x3 px4q x2 x3 px4qs

Beispiel 78. Eine weitere Implementierungsvariante ist, alle Variablen mit Kontroll-funktion zu versehen (z. B. FPGA):

f x1 x2 rx3 x4 p0q x3 x4p1q x3 x4 p1q x3 x4 p0qsx1 x2 rx3 x4 p0q x3 x4 p0q x3 x4 p1q x3 x4 p1qsx1 x2 rx3 x4 p0q x3 x4 p0q x3 x4 p0q x3 x4 p0qsx1 x2 rx3 x4 p0q x3 x4 p1q x3 x4 p1q x3 x4p0qs

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

x4

x4

0

1px4 x4q0

0

x4

x4

x1 x2 x3

f

(a) 3-Variablen-Multiplexer

0 0

0 1

1 0

1 1

x4

x4

0

1

x2 x3

0 0

0 1

1 0

1 1

0

0

x4

x4

x2 x3

0

1

x1

f

(b) 1- und 2-Variablen-Multiplexer

0 0

0 1

1 0

1 1

0

1

1

0

x3 x4

0 0

0 1

1 0

1 1

0

0

1

1

x3 x4

0 0

0 1

1 0

1 1

0

0

0

0

x3 x4

0 0

0 1

1 0

1 1

0

1

1

0

x3 x4

0 0

0 1

1 0

1 1

x1 x2

f

(c) 2-Variablen-Multiplexer mitvoll expandierter Funktion

Abbildung 7.1: Implementierung der Funktion unter Verwendung verschiedener Multi-plexervarianten

89

REV

1468

Implementierung von Funktionsbundeln

Stehen passende Multiplexer zur Verfugung, kann eine Minimierung entfallen, da dieFunktionen vollstandig expandiert zur Verfugung stehen.

Beispiel 79. Funktionsbundel mit Multiplexern:

f1 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3x4x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4

f2 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4x1 x2 x3 x4 x1 x2 x3 x4

f3 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4

x1, x2 und x3 werden als Kontrollvariable eingesetzt:

f1 x1 x2 x3 p0q x1 x2 x3 px4q x1 x2 x3 px4q x1 x2 x3 p0qx1 x2 x3 p0q x1 x2 x3 p1q x1 x2 x3 p1q x1 x2 x3 p0q

f2 x1 x2 x3 p0q x1 x2 x3 p0q x1 x2 x3 p1q x1 x2 x3 p0qx1 x2 x3 p0q x1 x2 x3 p1q x1 x2 x3 px4q x1 x2 x3 p0q

f3 x1 x2 x3 px4q x1 x2 x3 p1q x1 x2 x3 p0q x1 x2 x3 p0qx1 x2 x3 p0q x1 x2 x3 p1q x1 x2 x3 px4q x1 x2 x3 p0q

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

0

x4

x4

0

0

1

1

0

f1

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

0

0

1

0

0

1

x4

0

f2

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

x4

1

0

0

0

1

x4

0

f3

x1

x2

x3

Abbildung 7.2: Implementierung des Funktionsbundels

7.3 Programmierbare Logik

7.3.1 Einleitung

Programmierbare Bausteine haben eine feste Struktur und konnen in ihrer Funktion spe-ziell fur eine Anwendung programmiert werden. Die programmierbare Logik nimmt bei

90

REV

1468

den Entwurfsstilen eine mittlere Stellung bezuglich Integrationsgrad und Entwicklungs-dauer ein, wobei die Entwicklungskosten zum großen Teil von der Entwicklungsdauerbeeinflusst werden. Die programmierbare Logik ist insbesondere wegen ihrer flexiblenAnderbarkeit attraktiv, ein Problem ist jedoch, dass die Programmierinfrastruktur dieIntegrationsdichte, Geschwindigkeit und Verlustleistung beeintrachtigt.

Programmierbare Schaltungen werden nach ihrer Struktur klassifiziert. Es gibt u.a.:

• Festwertspeicher (Read-Only Memories, ROMs): PROM, EPROM

• Schreib-/Lesespeicher: EPROM, EEPROM, EAPROM

• Programmierbare Logische Anordnungen (Programmable Logic Arrays, PLAs):PLA, PLD, GAL, PLM, FPLA, EPLD, Mehrfach-Array PLD

• strukturprogrammierbare Bausteine: FPGAs, PLSs (XILINX, ACTEL)

Programmierbare Array-Bausteine haben die Eigenschaft, dass die Komplexitat we-sentlich durch die Zahl der Anschlusse und die Laufzeit begrenzt wird und dass der Lo-gikentwurf der Synthese auf Gatterebene entspricht. Es gibt zwei verschiedene Moglich-keiten diese Bausteine zu programmieren. Bei irreversiblen Speichern (Festwertspeicher)werden Maskenprogrammierung und elektrische Programmierung eingesetzt, wobei dieMaskenprogrammierung beim Halbleiterhersteller durchgefuhrt wird und nur bei großenStuckzahlen (¡ 1M) kostengunstig ist. Der Vorteil ist die hohe Schaltungskomplexitat.Trotzdem werden maskenprogrammierte Bausteine heute weitgehend durch EPROM(OTP) ersetzt. Heutzutage ist jedoch die elektrische Programmierung eher vorzufinden.

Bei reversiblen Speichern (Schreib-/Lesespeicher) wird elektrisch geschrieben und ent-weder elektrisch oder durch UV-Licht geloscht. Die elektrische Programmierung erfolgtbeim Anwender im Labor und ist flexibel fur kleinste Stuckzahlen geeignet, die Nachteilesind der hohere Preis und die geringere Schaltungskomplexitat und -geschwindigkeit.

7.3.2 ROM-Logik

Verschiedene Funktionsstrukturen haben verschiedene Einsatzbereiche, die Konjunktion(fpxq x1x2x3...xn) z.B. dient zur Realisierung von Mikroprogrammsteuerwerken, zurProgrammierung einer Schaltnetzfunktion und zur Darstellung von Wertetabellen undmathematischen Funktionen.

Die Spalten einer ROM-Matrix stellen NOR-Gatter mit N Eingangen dar, die aus denEingangsvariablen A, B und C dekodiert werden (1 aus n Code). Die Ausgangsfunktionenwerden wegen der quadratischen Anordnung ebenfalls dekodiert. Eine ROM-Matrix mitN-Bit Adresse und M-Bit Ausgangscode benotigt demnach M * N Speicherbits.

Ein Nachteil der ROM-Logik ist der Umstand, dass fur alle N Zeilen und alle M Spal-ten Transistorplatze vorgesehen werden mussen, auch wenn sie zum Teil nicht benotigtwerden. Meistens werden vom Schaltungsproblem auch nicht alle N Adressplatze (Zei-len) belegt, aufgrund der Redundanz ist die ROM-Logik also fur die Implementierungeinfacher Logikfunktionen ineffizient. Ein Vorteil liegt in der regelmaßigen Struktur der

91

REV

1468

SprungInkrement

logic

SequenceROM

ControlROM ALU

Ausgabepuffer

Datenregister

Eingabebefehle

Dateneingabe

Abbildung 7.3: Blockschaltbild eines µP mit zwei ROMs: fur Folgeadresse (SequenceROM) und Steuerwort (Control ROM)

VDD

Q1 Q2 Q3

1 2 3 M

A

B

C

1

2

3

N

Abbildung 7.4: ROM-Matrix in MOS-Technik mit N Eingangen und M Ausgangen

ROM-Matrix, diese ermoglicht ein kompaktes Layout. Der Speicherinhalt kann leichtdurch 1 bis 2 neue Masken programmiert werden, ohne dass eine Anderung der ROM-Architektur notig wird.

Beispiel 80. f1 xyz xyz; f2 xz; f3 xyz xz

92

REV

1468

VDD

1

1

1

x

y

z

f1 xyz xyz

f2 xz

f3 xyz xz

Abbildung 7.5: Beispiel einer ROM-Logik

93

REV

1468

7.3.3 Speicherzellen

Speicherzellen irreversibler Festwertspeicher sind aufgebaut aus Speicherelementen,die einer Kopplungsschaltung zwischen Wort- und Bitleitungen entsprechen, diese Kop-pelelemente bestehen entweder aus Dioden, Bipolar- oder MOSFET-Transistoren.

R

A1

A0

B

(a) Diode

R

A1

A0

B

(b) Bipolar

A1

A0

B

TL

(c) MOS

Abbildung 7.6: ROM-Matrizen basierend auf unterschiedlichen Technologien

Bei maskenprogrammierbare Speicherelemente sind die Speicherzellen also z.B. Dioden-oder Bipolartransistormatrizen. Das Datenmuster dieser Matix wird durch die Verdrah-tung festgelegt, dies geschieht am Ende des Herstellungsprozesses, bei dem mit einer sog.Verdrahtungsmaske die Verbindung festgelegt wird. Bei einer Transistormatrix in MOS-Technik wird durch Maskenprogrammierung die Dicke der Gateisolierschicht festgelegt,wobei eine dicke Isolierschicht ein Schalten des Transistors trotz angelegter Spannungverhindert.

Elektrisch programmierbare Festwertspeicher (PROM) werden durch das Durchschmel-zen (Zerstoren) eines Widerstandes (fusable link) oder einer Diode programmiert. Einspezieller Widerstand wird zur Basis des Bipolartransistors oder zur Diode in Reihe ge-schaltet. An der entsprechenden Speicherzelle wird an diesen Widerstand mit Hilfe einesProgrammiergerates eine hohe Spannung (ca. 10 V) angelegt, die den Widerstand bzw.die Diode wie ein Sicherungselement durchschmilzt.

Reversible Festwertspeicher besitzen die Eigenschaften, dass ihr Urzustand wie-derhergestellt werden kann, das Loschen ist je nach Speichertechnologie auf zwei Artenmoglich. Einerseits durch UV-Licht-Bestrahlung des Speicherchips, dabei wird die ge-samte Speichermatrix auf einmal geloscht, andererseits durch elektrische Impulse, durchdie jede Zelle einzeln geloscht werden kann.

Erasable PROM (EPROM) folgen dem 1-Transistor-FAMOS-Speicherelement in n-Kanal-Technik Speicherprinzip, bei dem (FAMOS = Floating Gate Avalanche InjectionMOS) das Gate des Speichertransistors nach außen vollig isoliert in seinem Potential

”schwebt“. Der Speichereffekt beruht auf einer Verschiebung der Schwellenspannung ei-

nes MOS-Transistors, d.h zum Programmieren wird der Source-Gate-Ubergang des Spei-

94

REV

1468

R

A1

A0

B

”1“

”0“

R

A1

A0

B

”1“

”0“

+

+

R

A1

A0

B

”1“

”0“

Abbildung 7.7: Elektrisch programmierbare Speicherelemente fur Lesespeicher mitSchmelzsicherung

chertransistors mit hoher Spannung bis zum Avalanche-Durchbruch belastet. Der Spei-chertransistor arbeitet im programmierten und unprogrammierten Zustand als selbst-sperrender Typ, die Loschung erfolgt mit UV-Licht. Die Bausteinkapazitaten liegt z.Z.bei 16 MBit.

GND +5V

+5V

GND +6V

+12V

Approximately

Source Drain

Substrate

Source Drain

Substrate

Floating gate

Select gate

Floating gate

Select gate

Abbildung 7.8: 1-Transistor-FAMOS-Speicherlement

Zur Neuprogrammierung im System wurden elektrisch loschbare Speicher (EAROM= Electrically Alterable ROM bzw. EEROM = Electrically Erasable ROM) entwickelt,bei denen der Speichereffekt durch Speicherung von Ladung in einem schwebenden Gate(FAMOS) erreicht wird. Die Nachteile dieser Speicher sind hohe Programmierspannun-gen und langere Zugriffzeiten.

GND +5V

+5V

GND +6V

+12V

+12VApproximately

GND

Source Drain

Substrate

Source Drain

Substrate

Source Drain

Substrate

Floating gate

Select gate

Floating gate

Select gate

Floating gate

Select gate

Abbildung 7.9: Programmierung einer FAMOS-EAPROM-Zelle

Die Vorteile der ROM-Logik liegen in leistungsfahigen Schaltnetzen mit mehrfachenEin- und Ausgangen (Typische Anwendungen sind z.B. Codierer, Arithmetikschaltun-gen und ahnliches), der hohen Komplexitat der Standardbausteine, und dass kein direk-ter Entwicklungsaufwand zur Minimierung der Logikfunktionen auf Gatterebene notig

95

REV

1468

ist. Die Nachteile der ROM-Logik sind u.a. die langsamere Arbeitsgeschwindigkeit ge-genuber irregularer Logik (Kundenschaltung), diese Verzogerung wird verursacht durcheine zusatzliche Adressdecodierung und Matrixkapazitaten. Hinzu kommt eine rechtschlechte Ausnutzung der Chipflache, wegen unbenutzter Speicherbereiche und das Feh-len zusatzlicher Schaltungsmoglichkeiten, wie z. B. Negation oder Selektion von einzelnenBits. Aufgrund dieser Nachteile ist die ROM-Logik weniger fur kleine Schaltnetze geeig-net, dafur aber fur große kombinatorische Netzwerke mit regelmaßigen Strukturen (z.B.µP -Programme, Funktionstabellen).

7.3.4 Anwendungsbeispiele fur ROM-Logik

Die algorithmische Berechnung arithmetischer Funktionen geschieht durch softwaremaßi-ge Berechnung uber Reihenentwicklungen, wenn keine Geschwindigkeit erforderlich ist:sin x x x3

3! x5

5!.....

Sk1 12pSk N

Skq mit limkÑ8 Sk

?N (Newton-Raphson Verfahren)

Die algorithmische Berechnung kann fur technisch-wissenschaftliche Bereiche zu lang-sam sein, dann erfolgt die tabellarische Berechnung auf Hardwareebene. Die einfachsteRealisierung ist die Verwendung eines ROM als Tabellenspeicher, Argument x als Adres-se und Speicherinhalt als Ergebnis des Funktionswertes von x Hierbei besteht aber derNachteil, dass ein enormer Speicherbedarf bei gebrauchlichen Wortlangen benotigt wird,daher gibt es haufig Mischlosungen mit zusatzlicher Logik.

ROM

sin xcos xsqrt xusw.

x f(x)

Abbildung 7.10: Struktur eines ROM-Schaltnetzes

7.4 Programmable Logic Array (PLA)

7.4.1 Uberblick

Zur Klassifizierung programmierbarer Logikbausteine wird zwischen Array-Logikbausteinenwie PLA, PAL, PLD, GAL, PLM, FPLA, EPLD, Mehrfach-Array PLD und Strukturkon-figurierbaren Gate-Arrays wie XILINX, ACTEL unterschieden. Die physikalische Reali-sierung (Komplexitat) programmierbarer Bausteine wird im wesentlichen durch die Zahlder Anschlusse (Variablen) begrenzt. Ein Problem sind die mit wachsender Komplexitatzunehmenden Leitungslaufzeiten. Der Logikentwurf wird von der Bausteinarchitekturgepragt, dies erfordert in der Regel eine firmenabhangige Entwurfssoftware.

96

REV

1468

7.4.2 Schaltungsprinzip

Vergleich von ROM und PLA: ROM erfordert fur n Adresseingange einen Decodierermit 2n Ausgangen, ein PLA (programmable logic array) wird dagegen direkt adressiertund besteht aus einer UND- Matrix mit einer kaskadierten ODER-Matrix. In der UND-Matrix werden die Eingangsvariablen in konjunktiver Form programmiert, in der ODER-Matrix erfolgt die Verknupfung dieser Produkte. Diese 2-Ebenen-Programmierung er-laubt eine Informationsverdichtung mit Hardware-Einsparung gegenuber der ROM-Logik.

Funktionsstruktur DNF: fpxq x1 x2 x3 x4 x5...xn x6 x7 . . .

ANDmatrix

ORmatrix

A

B

Q0

Q1

P0 P1

A

AB

B

Q0

Q1

P0 P1

A

B

Q0

Q1

P0 P1

1

1

& &

¥ 1

¥ 1

Abbildung 7.11: PLA: Blockdiagramm, Logikdiagramm, Logikschema

Zur PLA-Realisierung werden fur beide Matrizen NAND- oder NOR-Gatter gewahlt,die Umwandlung in NAND-Funktionen ist direkt moglich. Eine NOR-Realisierung er-fordert entweder negierte Ausgangsfunktionen oder die Programmierung der negiertenWerte, NOR-Matrizen werden in MOS-Technik wegen der Parallelschaltung bevorzugt.

Ein Vergleich mit Beispiel in der ROM-Logik zeigt eine erhebliche Aufwandsersparnis.

Es sind nur 27 gegenuber 72 Matrixpunkten erforderlich.Die hohere Informationsdichte des PLA gegenuber dem ROM ist aber auch nachteilig.

Im PLA ist die Anzahl der Zeilen und Spalten auf das Schaltungsproblem abgestimmt,so dass eine Logikanderung gleichzeitig eine Strukturveranderung des PLAs zur Folgehaben. Da die PLA-Matrix kleiner ist als die ROM-Matrix, sind die Verzogerungszeitenkurzer.Die Vorteile fur PLAs gegenuber der Realisierung mit Standard-Gattern sind, dass keinezeitaufwendige Minimierung der Logik mehr notig ist, aber eine Anpassung moglich ist,es bedarf auch keiner speziell entworfenen Logikgatter, außerdem ist die PLA-Strukturaufgrund ihrer einfacheren und regelmaßigeren Struktur leichter skalierbar.Die Nachteile liegen in ihrer geringeren Flexibilitat in der Programmierung gegenuberROM, PLAs konnen keine komplexen Funktionen speichern (insbesondere keine mitvielen Produkttermen), ihre Struktur ist nicht geeignet fur vorstrukturierte Hardware(Gate Arrays, Standardzellen, FPGAs) und eine Matrix verursacht langere Laufzeitengegenuber optimierten Schaltnetzen.

97

REV

1468

VDD

1

1

1

x

y

z

f1 xyz xyz

f2 xz

f3 xyz xz

VDD

1

1

1

x

y

z

f1

f2

f3

Abbildung 7.12: PLA-Beispiel

7.5 Andere programmierbare Logikschaltungen

Neben PLAs gibt es noch weitere Strukturen auf dem Markt, es handelt sich in der Regelum elektronisch programmierbare Schaltungen:

Array-Logikbausteine PLA und PAL

Der PLA ist der Vorlaufer aller Array-Bausteine (PLA ab 1973, FPLA ab 1975) undbesteht aus einem programmierbaren UND-Array und einem programmierbaren ODER-Array. Jeder Produktterm des UND-Arrays kann mit jeder Ausgangsfunktion verknupftwerden.

Der PAL entspricht einer Vereinfachung der PLA-Struktur (ab 1978) durch ein fixiertesODER-Array, auch GAL und PLD genannt. Hierbei werden die Produktterme einerfesten Struktur der Ausgangsfunktion zugeordnet, das ODER-Array wird durch eineeinfache feste Verdrahtungsstruktur ersetzt. Die Kapazitat der PAL-Bausteine liegt imBereich der von PLAs.

Weitere Unterschiede gibt es im Logikentwurf. Bei PLAs konnen Produktterme mehr-fach von verschiedenen Ausgangsfunktionen genutzt werden, bei PALs ist das nichtmoglich, fur jede Ausgangsfunktion mussen eigene Produktterme implementiert werden.Daher benotigen PAL-Entwurfe in der Regel mehr Produktterme als PLA-Entwurfe.Beide ermoglichen eine zweistufige Implementierung jeder booleschen Funktion(UND/ODER, disjunktive Normalform), vorausgesetzt der Baustein enthalt genugend

98

REV

1468

&

&

&

&

&

&

&

&

&

&

&

&

1

i0

1

i1

1

i2

1

i3

1

i4

1

i5

1

i6

1

i7

¥1

o0

¥1

o1

¥1

o2

¥1

o3

(a) PLA-Struktur

&

&

&

&

&

&

&

&

&

&

&

&

1

i0

1

i1

1

i2

1

i3

1

i4

1

i5

1

i6

1

i7

¥ 1 o0

¥ 1 o1

¥ 1 o2

¥ 1 o3

(b) PAL-Struktur

Abbildung 7.13: Strukturen programmierbarer Logikschaltungen

Produktterme.

&

&

&

&

&

&

&

&

&

&

&

&

1

i0

1

i1

1

i2

1

i31

i4

1

i5

1

i6

1

i7

¥1

o0

¥1

o1

¥1

o2

¥1

o3

Abbildung 7.14: PLA-Beispiel

Ahnlich der Struktur von PLAs, PALs und PGAs ist die Struktur von programmier-baren Logik-Sequenzern. Flipflops konnen vom D- oder JK-Typ sein und auch Ruck-kopplungen sind moglich.

7.6 Programmierbares Gate Array (FPGA)

Benutzerprogrammierbare Gate Arrays bieten eine hohe Flexibilitat, da auch Leitungs-segmente programmiert werden konnen. Field Programmable Gate Arrays basieren aufdem Logikblock-Konzept. Ein Logikblock besteht aus einer kleinen Anzahl von Lo-gikgattern, die flexibel programmierbar sind. Die Logikfunktion wird in Multiplexern

99

REV

1468

(Look-up tables, LUTs) oder RAM-Blocken abgelegt, zusatzlich konnen noch Registerexistieren. Jedes FPGA enthalt eine großere Anzahl von Logikblocken (100 bis 500),jeder Block ist mit den anderen Blocken und den I/O-Ports durch programmierbareVerknupfung verbunden. Dadurch ist eine Verknupfung der Logikblocke untereinandersowie mit den I/O-Ports moglich. Es gibt verschiedene Programmierarten: EPROM/EE-PROM, Schmelzsicherungen, SRAM.

ABCD

G

F

X

Y

Q

S

D

R

Clock

Look uptable

MuxMux

Mux

Mux

Mux

Mux

Abbildung 7.15: Struktur eines konfigurierbaren Logikblocks (Xilinx)

Die EPROM/EEPROM-Programmierung ist identisch mit der von PLDs, bei de-nen durch Floating-Gate-MOS-Transistor die zu programmierende Schalterverbindunggesteuert wird. Durch das Loschen des EPROM ist eine Wiederprogrammierung desFPGA’s moglich.

Die Programmierung mittels Schmelzsicherungen ist ahnlich der Programmierung mitEPROMs, mit der Ausnahme, dass kein Loschen moglich ist. Zur Programmierung sindkeine MOS-Transistoren erforderlich, so dass eine hohe Packungsdichte, geringe Laufzei-ten und ein niedriger Preis erzielt werden konnen.

Bei der SRAM-Programmierung wird der programmierbare Schalter durch eine 1Bit-SRAM-Speicherzelle kontrolliert, bei Spannungsverlust verliert die SRAM-Zelle die In-formation und das FPGA seine Konfiguration. Zur Aufrechterhaltung der Konfigurationwird der Speicherinhalt in ein externes ROM/EPROM geladen, das dann mit einerspeziellen Power-On-Routine das FPGA konfiguriert wird. Ein FPGA benotigt keinespeziellen Programmiergerate (nur fur ROM/EPROM), allerdings Software zur Synthe-se. Die flexible Infrastruktur zur Programmierung verteuert das FPGA gegenuber demPLD und die Software zur Synthese ist aufwendiger und damit teuer, außerdem sind dieVerzogerungszeiten uneinheitlich und erst nach Plazierung und Verdrahtung bestimm-bar.

Beispiel 81. Konfiguration einer NOT-FunktionDer Logikblock hat 8 Eingange und einen Ausgang, besteht aus drei 2:1 Multiplexern undeinem OR-Gatter, die NOT-Funktion wird mit einer 1 am A und S0 Eingang und einer0 am B Eingang festgelegt, die Variable X erzeugt so am SA Eingang die NOT-Funktionam Y-Ausgang.

100

REV

1468

Funktion Gatterbedarf benotigte EingangeNOT 9/14 4/82-AND 9/14 4/82-OR 14/14 6/8

Tabelle 7.1: Auslastungseffizienz einzelner Funktionen

¥ 1

SA

SB

S0

S1

A

B

C

D

Y

Abbildung 7.16: Struktur eines einfachen kombinatorischen Logikblocks

In einem Logikblock (XILINX CMOS LCA)besteht jede Zelle aus einem Schaltnetz undeinem Speicherelement. Die Zellen konnen als jede Funktion von 4 Variablen oder alszwei Funktionen von 3 Variablen programmiert werden und werden als konfigurierbareLogikblocke (CLB configurable logic block) bezeichnet.

Zellverknupfung

Die Verknupfung der Logikblocke und E/A-Module geschieht uber horizontal und verti-kal verlaufende Verbindungen miteinander. Beim kleinsten Baustein (Actel A1010) mit295 Logikblocken erfolgt z.B. die Verknupfung uber 22 horizontale und 13 vertikale Spu-ren. Die Verbindung wird mittels Schmelzsicherungen/Transistoren hergestellt, die nachder Programmierung eine niederohmige (ca. 50 Ω) Verbindung ergeben.

E/A Module

Die externe Schnittstelle wird von E/A-Modulen ubernommen, E/A-Module lassen sichzu vier Konfigurationen programmieren: Eingang, Ausgang, Tri-state-Ausgang, bidirek-tionales Buffer.

Die LCA Architektur (Logic Cell Array) besteht aus einer Matrix identischer Logik-Zellen, die von Ein-/Ausgabezellen umgeben ist. Das Verbindungsnetzwerk besteht ausLeitungssegmenten, die horizontal und vertikal entlang in Kanalen zwischen den Zellen

101

REV

1468

0

1

2

3

4

5

6

7

1 1 1

A B C

f(A,B,C)

Abbildung 7.17: Look-up Funktionsgenerator mit 8 Speicherzellen und 8 zu 1 Multiple-xer

verlaufen. Die Programmierung der Verdrahtung erfolgt durch die Schaltermatrix, diesich an den Kreuzungspunkten zwischen den Reihen und Spalten befindet.

Programmierung

Die Logikzellen, Peripheriezellen und die Verdrahtung sind vom Benutzer program-mierbar. Die Information zur Konfiguration der Logik und Verdrahtung wird im Spei-cher gehalten. Die Programmierung des Speichers erfolgt mittels eines Entwurfssystems,das die Schaltungseingabe, Makrobibliothek, Simulation und Schaltungsumsetzung un-terstutzt. Die Plazierung und Verdrahtung erfolgt automatisch oder interaktiv manuell,dafur ist spezielle Entwurfssoftware erforderlich, die den entsprechenden IC konfiguriert.Die Schaltungskonfiguration kann im EPROM/ROM auf der Platine oder im Rechnergespeichert werden.

102

REV

1468

D Q

D Q

Q D

S

S

clk

clk

clk

I/O Pin

input

output

registeredinput

tristate

Abbildung 7.18: Prinzipieller Aufbau einer Ein-/Ausgabezelle

VHDL oder Verilog Logiksynthese GatternetzlisteASIC

Schaltungsentwurf Plazieren und verdrahtenAnforderungen

erf :ullt?Fertig!

nein

ja

Abbildung 7.19: Programmierungs-Workflow

103

REV

1468

8 Technische Aspekte desLogikentwurfs

8.1 Realisierung der Schaltalgebra durch Logikgatter

Uberblick

Anstelle der Schalterrealisierung durch Reihen- und Parallelschaltung lassen sich dieOperationen + , , mit sogenannte Logikgattern oder digitalen Verknupfungsglie-dern durchfuhren. Es handelt sich dabei meist um elektronische Schaltungen, die auchSchaltkreis genannt werden.Ein Gatter ist als Blackbox mit einem oder mehreren Eingangen und einem Ausgang ge-geben. Von einer solchen Blackbox ist nur das Schaltverhalten bekannt. Dabei bezeichnetdas Schaltverhalten das Verhalten der Spannung am Ausgang in Abhangigkeit von denan den Eingangen angelegten Spannungen. Die am Eingang angelegten Spannungen wer-den als Eingangssignale und die resultierende Spannung am Ausgang als Ausgangssignalbezeichnet.

Zuordnung von Signalen zu Logikwerten

Als Eingangssignale sind bei digitalen Gattern nur zwei verschiedene Spannungswerte(Stromwerte) innerhalb gewisser Toleranzgrenzen zugelassen. Dies gilt auch fur das Aus-gangssignal. Beiden Spannungswerten werden jeweils ein Schaltzustand zugewiesen, z.B.entspricht

”0V“ dem Schaltzustand 0 und

”5V“ dem Zustand 1. Sind somit z.B. 0V und

5V die zulassigen Spannungswerte, lasst sich zu jedem Schaltgatter eine entsprechendeSchalttabelle angeben.

8.1.1 Positive Und Negative Logik

Die Realisierung logischer Funktionen durch Hardware erfordert die Darstellung derbinaren Variablen durch geeignete elektrische Großen. In digitalen Schaltkreisen erfolgtsomit die Darstellung der boolschen Werte 0 und 1 durch zwei unterschiedliche Span-nungspegel bzw. Spannungspegelbereiche. Diese Zuordnung der High-(H) und Lowpe-gel(L) kann entweder durch positive oder negative Logik geschehen.

Pegel phys. GroßeWert pos. Logik neg. Logik pos. Logik neg. Logik

0 L H z.B. 0V z.B. 0V1 H L z.B. +5V z.B. -12V

104

REV

1468

Die Zuordnung der physikalischen Großen kann dabei willkurlich erfolgen, da die ma-thematische Logik keine Unterscheidung in positive und negative Logik besitzt. Diese istsomit nur erforderlich, wenn man die technische Realisierung der logischen Funktionenbetrachtet.

8.1.2 Pegelbereiche

Problemstellung

Die Spannungspegel innerhalb digitaler Schaltungen unterliegen Streuungen. Die Ur-sachen liegen in Bauelementtoleranzen, Temperaturschwankungen, Betriebsspannungs-schwankungen und Storsignalen.

H-Pegel

L-Pegel

Verbotene Zone

5V

2.4V

0.4V

0V

3.3V (typisch)

0.2V (typisch)

Abbildung 8.1: Spannungspegelbereiche fur den H- und L-Pegel

Eine Verringerung des Einflusses der Toleranzen geschieht durch die Zuordnung derSpannungspegel H und L zu einem jeweils relativ breiten Pegelbereich. Beide Pegelbe-reiche werden durch eine verbotene undefinierte Zone getrennt.

8.1.3 Ubertragungs(Transfer)Kennlinie

Elektronisches Verhalten

Die Beziehung zwischen Aus- und Eingangsgroße - z.B. Spannung (UA , UE) - einesGatters heißt Transfer- oder Ubertragungskennlinie. Sie stellt die wichtigste statischeEigenschaft eines Gatters dar. Die Transferkennlinie hangt von der Schaltungsstruktur,den gewahlten Bauelementen, der Belastung und der Temperatur ab. Sie zeigt den ty-pische Logikpegel und den statischen Storabstand.

105

REV

1468

UELmax UEHmin

UALmin

UAHmax

UE

UA

Abbildung 8.2: Ubertragungskennlinie eines Inverters

8.1.4 Statischer Storabstand

Definition des statischen Storabstandes US

Der statische Storabstand US beschreibt den zulassigen Storspannungshub, der den lo-gischen Zustand eines Gatters noch nicht andert. Die Voraussetzung dafur ist, dassdas Storsignal langer als die mittlere Verzogerungszeit dauert. Er definiert auch dieStorspannung, die dem Ausgangssignal einer Stufe uberlagert sein darf, ohne bei ei-ner nachgeschalteten gleichen Stufe den zulassigen Eingangswert zu uberschreiten. DieStorabstande fur L- und H-Pegel sind verschieden und werden getrennt (USL, USH) an-geben.

USH UAHmin UEHmin

USL UELmax UALmax

UAHminUEHmin

UELmaxUALmax

Abbildung 8.3: Definition des statischen Storspannungsabstandes

8.1.5 Dynamischer Storabstand

Problemstellung

Ist die Eingangssignaldauer kleiner als die Gatterverzogerungszeit, ist die Gatterfunktionnicht mehr gewahrleistet.

106

REV

1468

Definition des dynamischen Storabstandes

Der dynamische Storabstand ist die minimal erforderliche Impulslange tmin am Eingangeines Gatters, bei der das Gatter noch korrekt schaltet.

1tmin

Abbildung 8.4: Dynamischer Storabstand

8.1.6 Belastbarkeit

Die Gattereingange bilden Last fur angeschlossene Ausgange. Bei bipolaren Schaltungenhandelt es sich um eine Strombelastung, MOSFET-Schaltungen weisen hingegen nureine kapazitive Last auf. Meistens interessiert nur, wieviele Eingange von nachfolgendenGattern an einen Gatterausgang angeschlossen werden konnen. Man rechnet daher nichtmit Stromen, sondern mit festgelegten Lasteinheiten (unit load), in denen samtliche

”worst-case“-Bedingungen berucksichtigt sind. Die Berechnung der Lastfaktoren erfolgt

getrennt fur H- und L-Pegel. In Datenblattern wird dann der großere bzw. kleinere Wertangegeben.

IEHEingangsstrom bei H-Pegel IEL

Eingangsstrom bei L-PegelIAH

Ausgangsstrom bei H-Pegel IALAusgangsstrom bei L-Pegel

Schaltkreisx1x2

y

IE IA

Abbildung 8.5: Definition der Gatterstrome

Eingangslastfaktor (fan in)

Faktor 1 ist die Belastung des Eingangs eines elementaren Grundgatters.

pfaninqH IEHIEHE

pfaninqL IELIELE

Ausgangslastfaktor (fan out)

Anzahl von Eingangslastfaktoren 1 der gleichen Schaltkreisfamilie, mit der ein Schalt-kreisausgang belastet werden darf.

pfanoutqH IAHIEHE

pfanoutqL IALIELE

107

REV

1468

8.1.7 Verlustleistung

Mittlere statische Verlustleistung PV

Fast alle Schaltkreisfamilien haben unterschiedliche Leistungsaufnahmen bei einem Aus-gangspegel L bzw. H.

PV PVHPVL

2arithmetisches Mittel der Verlustleistung

dynamische Verlustleistung

Bei verschiedenen Schaltkreisfamilien tritt eine hohe dynamische Verlustleistung auf, diedurch den Signalwechsel verursacht wird.

PVCMOS f mit f Taktfrequenz

8.1.8 Schaltzeiten

Problemstellung

Das dynamische Schaltverhalten digitaler Schaltkreise wird durch die Verzogerungszeittp, die Anstiegszeit tr und Abfallzeit tf bestimmt. Die Schaltzeiten hangen somit unteranderem von der Art der Beschaltung des Ausgangs ab.

Verzogerungszeit (propagation delay, Durchlaufzeit) tp

Man unterscheidet zwischen den Verzogerungszeiten tpHL und tpLH entsprechend der HL-oder LH-Ausgangsflanke. Die Verzogerungszeiten werden bei 50% des Signalspannungs-pegels gemessen. Somit ist tpLH das propagation delay von L nach H und tpHL von Hnach L. Die Gatterverzogerungszeit errechnet sich aus dem arithmetischen Mittelwerttpd 1

2 ptpHL tpLHq.

HIGH

Bezugspegel (50%)

LOW

HIGH

Bezugspegel (50%)

LOW

Eingangssignal

Ausgangssignal

tpHL tpLH

Abbildung 8.6: Propagation-Delay

108

REV

1468

Abfallzeit(fall time) und Anstiegszeit(rise time)

Die Anstiegs- bzw. Abfallzeit liegt zwischen 10% und 90% des Spannungshubs bei einerAnsteuerung mit einem idealen Rechteckimpuls am Eingang.

Symbol eng. Beschreibung Taktflankenanderung deutsche Beschreibungtr rise time L Ñ H Anstiegszeittf fall time H Ñ L Abfallzeit

HIGH

LOW

Ausgangssignal

90%

10% 10%

90%

tf tr

Abbildung 8.7: Definition Schaltzeiten

8.1.9 Geschwindigkeit-Leistungs-Produkt

Das Geschwindigkeits-Leistungs-Produkt WG dient haufig als Bewertungskriterium furdas dynamische Verhalten logischer Schaltkreise.Dieses Produkt beschreibt das Verhalt-nis zwischen der Verlustleistung(PV) und der Verzogerungszeit(tpd). Beschleunigt manalso eine Anwendung oder Schaltung geschieht das auf Kosten der steigenden Verlust-leistung oder anders herum. Das Geschwindigkeits-Leistungs-Produkt kann man auchmit der Formel WG PV tpd beschreiben.

8.2 Dynamisches Verhalten von Schaltnetzen

8.2.1 Hazards

Die unterschiedlichen Verzogerungen einzelner Eingangssignale konnen in einem Schalt-netz Eingangskombinationen verursachen, die kurzzeitig zu fehlerhaften Ausgangskom-binationen fuhren konnen. Diesen Effekt bezeichnet man auch als

”Hazard“. Ein Ha-

zard ist ein Ubergang zwischen zwei Eingangskombinationen, bei dem die Moglichkeitbesteht, dass wahrend der Ubergangsphase auf Grund unterschiedlicher Signalverzoge-rungen falsche Ausgangsignale auftreten. Ob dann tatsachlich der Fehler auftritt, hangtvon den realen Verzogerungszeiten der einzelnen Signale ab. Man spricht hierbei dannvon einem hazardbehafteten Schaltnetz.

Gegeben sei folgender boolscher Ausdruck: y x2 x0 x2 x1.Als Beispiel kann man hier den Ubergang von der Eingangskombination (x2, x1, x0)

110 nach 001 betrachten. Im ersten Fall treten im Ubergangsintervall kurzzeitig falsch-licherweise die Signale 0 und 1 auf. Bei den angenommen Verzogerungen hat das ha-zardbehaftete Schaltnetz auch einen Hazard zur Folge. Im zweiten Fall erfolgt in der

109

REV

1468

x0

x1

x2

y

1

1

&

&

¥ 1

Abbildung 8.8: Hazardbehaftete Schaltung

6

y

00

01

12

13

14

05

16

07

x2

x1

x0

(a) KV Diagramm

x2

x1

x0

y

(b) Verzogerungsva-riante 1

x2

x1

x0

y

(c) Verzogerungsva-riante 2

Abbildung 8.9: Entstehung von Hazards

Ubergangsphase ein eindeutiges Umschalten vom Wert 1 auf den Wert 0. Es ergibt sichkeine falsche Aufeinanderfolge von Werten der Ausgangssignale. In diesem Fall liegt alsofur das gleiche Schaltnetz kein Hazard vor.Bezuglich der Werte der Ausgangssignale, die vor und nach dem Ubergang gefordertsind, unterscheidet man zwischen statischen und dynamischen Hazards.

Statischer Hazard

In einer Schaltung y(x) heißt ein beim Ubergang zwischen den Eingangskombinationenx1 und x2 auftretender Hazard statischer Hazard, wenn bezuglich der Werte der Aus-gangssignale gilt: ypx1q Ñ ypx2q.Bei statischen Hazards unterscheidet man noch zwischen 0-Hazards und 1-Hazards. Einstatischer 0-Hazard (bzw. 1-Hazard) ist ein Hazard, bei dem das Ausgangssignal vor undnach dem Ubergang gleich 0 (bzw. gleich 1) ist.

Dynamischer Hazard

In einer Schaltung y(x) heißt ein beim Ubergang zwischen den Eingangskombinatio-nen x1 und x2 auftretende Hazard dynamischer Hazard, wenn bezuglich der Werte derAusgangssignale gilt: ypx1q Ñ ypx2q.

110

REV

1468

y

y

(a) statischer 0- und 1-Hazard

y

y

(b) dynamischer 0- und 1-Hazard

Abbildung 8.10: Typen von Hazards

8.2.2 Funktionshazards

Statischer Funktionshazard

Ein Schaltnetz y(x) ist bei einem Ubergang zwischen den Eingangskombinationen x1und x2 mit einem statischen Funktionshazard behaftet, wenn es eine Wertekombina-tion g fur die Variablen x gibt, die wahrend des Ubergangs auftritt und fur die gilt:ypx1q Ñ ypgq Ñ ypx2q.Als Kriterien zur Erkennung eines statischen Funktionshazards dienen zum einen derFunktionswert vor und nach dem Ubergang, der gleich sein muss. Zum anderen muss esWertekombinationen des Eingangsvektors g geben, die wahrend des Ubergangs momen-tan auftreten und die eine Anderung des Funktionswerts bewirken.Betrachtet man in der Schaltung y x2 x0 x2 x1 z.B. den Ubergang von 110 nach011, dann tritt ein statischer Funktionshazard auf.

y

00

01

12

13

14

05

16

07

x2

x1

x0

Dynamischer Funktionshazard

Ein Schaltnetz y(x) enthalt beim Ubergang zwischen den Eingangskombinationen x1und x2 einen dynamischen Funktionshazard, wenn es zwei Wertekombinationen g1 undg2 von x gibt, die, ausgehend von x1 zeitlich nacheinander auftreten und fur die gilt:ypx1q Ñ ypg1q Ñ ypg2q Ñ ypx2q.In den KV-Diagrammen sind einige Funktionshazards durch Linien gekennzeichnet.

8.2.3 Strukturhazards

Ursache

Beim Ubergang von 110 nach 010 entsteht kein Funktionshazard, da sich nur ein Varia-blenwert andert. Dennoch kann wahrend dieses Ubergangs ein falsches Ausgangssignalenstehen. Die Ursache des falschen Ausgangssignals sind die Verzogerungen, die inner-halb eines Schaltnetzes zwischen einem Signal und seiner Negation wirksam sind.

111

REV

1468

@@

y

00

01

12

13

14

05

16

07

x2

x1

x0

(a) statisch

```

y

00

01

12

13

14

05

16

07

x2

x1

x0

(b) dynamisch

Abbildung 8.11: Funktionshazard

x0

x1

x2

y

1

1

&

&

¥ 1

(a) Schaltbild

x2

x2

x1

x0

y

(b) Entstehung einesstatischen 1-Strukturhazards

x2

x2

x1

x0

x0

y

(c) Entstehung ei-nes dynamischenStrukturhazards

Abbildung 8.12: Entstehung eines Strukturhazards

112

REV

1468

Das Ausgangssignal nimmt kurzzeitig den Wert 0 an, obwohl es den Wert 1 habensoll. Gemaß der Definition liegt ein statischer 1-Hazard vor.Dieser Hazard wird allerdings in diesem Fall Strukturhazard genannt. Die Ursache diesesStrukturhazards ist, dass die Wertanderungen der Signale x und x nicht genau zeitgleicherfolgen. Es gibt also Zeitpunkte, zu denen beide Signale x und x gleich 0 oder gleich 1sind. Hat x1 den Wert 1 und x0 den Wert 0 und wird der Wert von x2 geandert (Uber-gang von 110 nach 010), tritt in der Schaltung ein statischer Strukturhazard auf. Dieserstatische 1-Strukturhazard ist in dem KV-Diagramm durch eine Linie gekennzeichnet.

y

00

01

12

13

14

05

16

07

x2

x1

x0

Abbildung 8.13: Statischer Strukturhazard

Die Veranschaulichung eines dynamischen Strukturhazards (siehe Abbildung 8.12c)zeigt den Ubergang von 111 nach 010. Dabei wurde angenommen, dass die Verzogerungvon x2 großer ist als die Verzogerung von x0. man erkennt, dass der Wert von y sichzunachst von 0 nach 1 andert, dann noch einmal nach 0 zuruckgeht und erst dannwieder 1 wird. Es ensteht also ein zusatzlicher Einsimpuls.

y

00

01

12

13

14

05

16

07

x2

x1

x0

Abbildung 8.14: Dynamischer Strukturhazard

8.2.4 Vermeidung von Hazards

Ubersicht

Ob die in Schaltnetzen auftretenden Hazards fur eine nachgeschaltete Anordnung kritischsind, hangt im wesentlichen von deren Zeitkonstanten ab. Deshalb ist es notwendig durchgeeignete Maßnahmen die verschiedenartigen Hazardeinflusse zu vermeiden.

Wichtigste Maßnahme zur Vermeidung von Hazards

Es gibt drei wichtige Maßnahmen die man ergreifen kann, um Hazards zu vermeiden.Zum einen verhindert ein Taktbetrieb (eine Synchronisierung der Schaltung), dass aufge-

113

REV

1468

tretene Hazards sich in nachfolgenden Schaltungsteilen ausbreiten konnen. Zum anderenkann man durch gezieltes Hinzufugen von Verzogerungsgattern in die Eingangsleitungeinen Ausgleich von vorhandenen Verzogerungen bewirken. Daruber hinaus kann aucheine Anderung der Schaltstruktur - also Umformung der boolschen Algebra - Hazardsverhindern.

Folgende Funktion beschreibt ein Schaltnetz in dem keine statischen Strukturhazardsauftreten.

y x2 x0 x2 x1 x1 x0

Es kann gezeigt werden, dass durch die Hinzunahme der redundanten Primimplkantenx1 x0 auch die beiden dynamischen Strukturhazards beseitigt werden.

x0

x1

x2

y

1

1

&

&

&

¥ 1

(a) zusatzliches UND-Element einfugen

x2

x2

x1

x0

y

(b) zeitlicher Ablauf

y

00

01

12

13

14

05

16

07

x2

x1

x0

(c) Darstellung als KV-Diagramm

Abbildung 8.15: Beseitigung des Strukturhazards

Eine Schaltung die durch eine disjunktive Normalform beschrieben wird, ist genaudann frei von allen statischen und dynamischen Strukturhazards, wenn die disjunkti-ve Normalform aus allen Primimplikanten der betroffenen Funktion aufgebaut ist. DieVermeidung von Strukturhazards durch hinzufugen von Primimplikanten ist somit sehraufwendig.

114

REV

1468

9 Synchrone Schaltwerke

9.1 Einleitung

Sequentielle Schaltungen (Schaltwerke)

Ein Schaltwerk besteht aus einem Schaltnetz und einem Speicherteil zur Sicherungvorangegangener Informationen. Die Ausgangsvariablen (Steuervariablen) zt hangen vonden Eingangsvariablen xt und von den gespeicherter Information (aktueller Zustand)yt ab. Als Speicherelemente kommen hauptsachlich Master-Slave-D-Flipflops (CMOS)zum Einsatz (siehe 6.3.4). Zur Synchronisation wird der Speicher getaktet (synchronesSchaltwerk).

Schaltnetz

Speicher

Eingangs-variable

Ausgangs-variable

aktuelleZustands-variable

Folge-zustands-variable

xt zt

yt yt1Takt

Abbildung 9.1: Schaltwerksstuktur

Darstellungen fur Schaltwerke

Schaltwerke konnen durch Zustandstabellen bzw. Zustandsgraphen/Ubergangsgraphendargestellt werden. Bei Zustandstabellen werden ausgehend vom aktuellen Zustand yt

in Verbindung mit den Eingangsvariablen xt die Folgezustande yt1 und die Ausgangs-variablen zt aufgezeigt. Zustands-/Ubergangsgraphen visualisieren die Funktionsweiseeines Schaltwerks graphisch. Hierbei reprasentieren die Knoten die Zustande. Die Kan-ten zeigen die Ubergange mit den zugehorigen Eingangs- und Ausgangssignalen an. DieAusgangssignale konnen den Knoten oder den Kanten zugeordnet werden.

Arten von Automaten

Im Wesentlichen kann man zwei Arten von Schaltwerken/Automaten unterscheiden. DerMealy-Automat ist dadurch gekennzeichnet, dass die Ausgangsvariablen zt eine Funk-

115

REV

1468

tion der Eingangsvariablen xt und des aktuellen Zustands yt ist. Die Folgezustande yt1

sind eine Funktion der Eingangsvariablen xt und des aktuellen Zustands yt.

yt1 gpxt, ytqzt fpxt, ytq

Beispiel 82. Mealy-Automat mit Zustandstabelle und Zustandsgraphen

x 0 x 1yt yt1 z yt1 z1 2 1 3 02 2 1 4 03 1 0 4 04 3 1 3 0

(a) Zustandstabelle

1

2

3

4

0,1

1,0

0,1

1,0

0,0

1,0

0,1

1,0

(b) Zustandsgraph

Abbildung 9.2: Mealy-Automat

Der zweite Automatentyp wird Moore-Automat genannt. Dieses Schaltwerk bestimmtdie Ausgangsvariablen zt nur anhand des aktuellen Zustandes yt. Der Folgezustand yt1

bleibt eine Funktion der Eingangsvariablen xt und des aktuellen Zustands yt.

yt1 gpxt, ytqzt fpytq

Beispiel 83. Moore-Automat mit Zustandstabelle und Zustandsgraphen

Eigenschaften der Automatentypen

Beide Steuerwerksarten sind aquivalent und jeweils in den anderen umwandelbar. DieSynthese beider Automatentypen ist ahnlich und muss dementsprechend nicht sepa-rat erklart werden. Moore-Automaten erfordern in der Regel mehr Zustande. Mealy-Automaten hingegen konnen komplexere Ubergangsfunktionen aufweisen. Die Steuer-funktionen konnen beim Mealy-Automaten asynchron reagieren, wenn sie nicht zwi-schengespeichert werden.

116

REV

1468

x 0 x 1yt yt1 yt1 z1 1 2 02 4 3 13 4 3 14 2 1 0

(a) Zustandstabelle

1

0

2

1

3

1

4

0

0

1

0

1

0

10

1

(b) Zustandsgraph

Abbildung 9.3: Moore-Automat

9.2 Schaltwerkssynthese

Schritte zur Schaltwerkssynthese

Die Schaltwerkssynthese kann im Wesentlichen in zwei Schritten realisiert werden. ZuBeginn wird dabei aus der Verhaltensbeschreibung einer sequentiellen Funktion eine Zu-standstabelle bzw. ein Zustandsgraph abgeleitet. Die Ableitung einer Zustandstabelleaus der Verhaltensbeschreibung (High-Level-Synthese) bietet bisher noch nicht umfas-send effiziente Losungen und bleibt z. Z. aktueller Forschungsgegenstand. Der zweiteSchritt beinhaltet die Realisierung der Zustandstabelle durch ein Schaltwerk. Die Um-setzung der Zustandstabelle in ein Schaltwerk ist ein weitgehend erforschter Bereich miteffizienten Losungsansatzen.

Zustandszuordnung (state assignment)

Als eine Zustandszuordnung (state assignment) bezeichnet man eine Zuweisung einerKombination von Zustandsvariablen yi zu einem Zustand des Schaltwerks. Mit zwei-wertigen Speicherelementen sind fur n Zustande des Schaltwerks log2n Speicherelemen-te erforderlich. Daraus ergeben sich dann n! verschiedene Zustandszuordnungen, derenRealisierungen zu unterschiedlich hohem Aufwand fuhren kann. Es sind verschiedeneAlgorithmen bekannt, die zu einer optimalen Zustandszuordnung fuhren. Ziel sind dabeiz.B. eine minimale Anzahl von Gattereingangen, eine minimale Verzogerung oder mini-male Verlustleistung. Eine Minimierung ist aber nur bei Schaltnetzrealisierung relevant,nicht bei ROM-Implementierung.

Beispiel 84. Sequentieller serieller Bitprufer als Moore-Automat mit MS-D-Flipflops

VerhaltensbeschreibungDie Schaltung soll fur die Steuerfunktion z eine 1 erzeugen, wenn in einem bitseriellenDatenstrom 3 oder mehr aufeinanderfolgende Einsen auftreten.

117

REV

1468

Ableitung einer Zustandstabelle bzw. eines ZustandsgraphenZu Beginn muss gemaß der Verhaltensbeschreibung ein Ablaufschema entwickelt werden.Als mogliche Darstellungsform eignen sich eine Zustandstabelle und/oder ein Zustands-graph.

neueraktueller ZustandZustand yt1 Ausgang

yt x 1 x 0 z1 2 1 02 3 1 03 4 1 04 4 1 1

(a) Zustandstabelle

1

0

2

0

3

0

4

1

0

10 1

0

10

1

(b) Zustandsgraph

Abbildung 9.4: Bitprufer

Realisierung der Zustandstabelle durch ein SchaltwerkAuf Grundlage der Verhaltensanalyse durch die Zustandstabelle bzw. den Zustandsgra-phen, ist eine Zustandscodierung vorzunehmen. Fur die Codierung der vier vorgesehenenZustande benotigt man entsprechend zwei Variablen (y2, y1). Folgerichtig ist die Zustand-stabelle neu aufzustellen.

Zustand y2 y11 0 02 0 13 1 14 1 0

(a) Zustandszuord-nung (Gray-Code)

x 1 x 0y2

t y1t y2

t1 y1t1 y2

t1 y1t1 z

0 0 0 1 0 0 00 1 1 1 0 0 01 1 1 0 0 0 01 0 1 0 0 0 1

(b) neue Zustandstabelle

Abbildung 9.5: Zustandstabelle nach Codierung

Aus der neuen Tabelle konnen nun die Ubertragungsfunktionen fur den Folgezustand(y2

t1, y1t1) und den Ausgang (z) ermittelt werden.

y1t1 x y2t y2

t1 x y1t x y2

t x py1t y2tq z y1t y2

t

NOR-NF: y1t1 x y2t y2

t1 x py1t y2tq z y1t y2t

118

REV

1468

Der Bitprufer soll durch ein Schaltwerk aus MS-D-Flipflops realisiert werden. Manbenotigt also entsprechende Ansteuerfunktionen fur die Flipflops. Hierbei ist anzumer-ken, dass die Ansteuerung direkt aus der Ubertragungsfunktion abgeleitet werden kann(D Qt1). Man setzt also D1 fur y1

t1 und D2 fur y2t1 ein. Außerdem wird zur Ver-

einfachung y1t durch y1 und y2

t durch y2 ersetzt.

Ansteuerungsfunktionen:

D1 x y2 D2 x py1 y2q z y1 y2

Das resultierende Schaltwerk ist in der nachfolgenden Abbildung skizziert.

1D

C1

1D

C1

¥ 1¥ 1

¥ 11

¥ 1

xz

y1

Takt

Abbildung 9.6: Prufschaltung mit MS-D-Flipflops

Entwurf mit Festwertspeichern (ROMs)

Ein Schaltwerk kann gegebenenfalls auch mit einem ROM realisiert werden. Hierbei wirddie Zustandstabelle durch den Festwertspeicher abgebildet. Die Eingangsvariablen xt undZustandsvariablen yt werden als Adressbits verwendet. Die Folgezustandsvariablen yt1

und die Ausgangsvariablen zt werden im ROM gespeichert. Durch die Ruckkopplung derFolgezustande auf den Eingang des ROMs wird ein sequentiellen Ablauf erreicht. DieSynchronisation wird mit MS-D-Flipflops oder Latches realisiert.

Entwurfsschritte:Ausgangspunkt ist die Zustandszuordnungs- und die Ausgangstabelle. Die Tabelle wirdals ROM-Ubergangstabelle umgeformt und das Schaltwerk ist komplett realisiert. Haufigist der ROM-Baustein aber großer (mehr Adressen (Zustande) und großere Wortbreite)als fur ein spezielles Problem erforderlich. In diesen Fallen wird das ROM nur teilweisegenutzt.

119

REV

1468

Beispiel 85. Erkennung einer Bitsequenz

Verhaltensbeschreibung:Die Schaltung erzeugt die Steuerfunktion z 1, wenn die Bitsequenz 1010 erscheint. Inallen anderen Fallen erscheint am Ausgang 0.

Ableitung einer Zustandstabelle bzw. eines Zustandsgraphen:

x 0 x 1yt yt1 z yt1 z1 1 0 2 02 3 0 2 03 1 0 4 04 3 1 2 0

(a) Zustandstabelle

1

2

3

40,0

1,0

0,0

1,0

0,0

1,0

0,1

1,0

(b) Zustandsgraph

Abbildung 9.7: Bitsequenz-Erkennung

Realisierung der Zustandstabelle durch ein Schaltwerk:

Zustandszuordnung (Gray-Code):

Zustand y2 y11 0 02 0 13 1 14 1 0

neue Zustandstabelle:

x 0 x 1y2

t y1t y2

t1 y1t1 z y2

t1 y1t1 z

0 0 0 0 0 0 1 00 1 1 1 0 0 1 01 1 0 0 0 1 0 01 0 1 1 1 0 1 0

ROM-Ubergangstabelle:

120

REV

1468

Adresse AusgangA2 A1 A0 D2 D1 D0

y2t y1

t x y2t1 y1

t1 z0 0 0 0 0 00 0 1 0 1 00 1 0 1 1 00 1 1 0 1 01 0 0 1 1 11 0 1 0 1 01 1 0 0 0 01 1 1 1 0 0

Durch eine Umsortierung nach Eingangs- und Ausgangsvariablen erhalten wir die benotig-te ROM-Ubergangstabelle. Der Eingang wird entsprechend als eine Adresse interpretiert.Schaltwerk:

ROM

Speicher

Eingangs-variable

Ausgangs-variable

Zustands-adresse

Folge-zustands-adresse

Aj

A0

D0

Dn

Takt

Abbildung 9.8: ROM-Implementierung

9.3 Register

9.3.1 Ubersicht

Allgemeines

In Speicherorganisationen mit mehr als einem Bit Speicherkapazitat erhalten die Spei-cherzellen eine gemeinsame Steuerung fur die Datenein- und -ausgabe. Aufgebaut wirddieses System dann meist mit Flipflop-Speichern (Parallel- oder Serienspeicher). Spei-cher mit einer geringen Anzahl von Speicherzellen werden Register genannt. Registerfinden Anwendung als schnellen Zwischenspeicher fur kleine Datenmengen.

Parallelspeicher

Die Datenein-/ausgabe erfolgt fur alle Speicherzellen gleichzeitig. Die Steuerleitung T zurDatenubernahme ist parallel an alle Speicherzellen geschaltet. Parallelspeicher konnen

121

REV

1468

aus einfachen D-Latches oder aus MS-D-Flipflops aufgebaut werden.

1D

C1

1D

C1

1D

C1

D1 Q1

Q1

D2 Q2

Q2

Dn Qn

Qn

T

Abbildung 9.9: Parallelregister

Serienspeicher (Schieberegister)

Die Speicherzellen sind bei Serienspeichern in Reihe geschaltet. Jeder Ausgang der vor-angehenden Zelle ist mit dem Eingang der nachfolgenden Zelle verknupft. Die Datenwerden beginnend von der ersten Zelle mit jedem Takt T in die nachste Zelle geschoben.Die Ausgabe der Daten erfolgt an der letzten Zelle der Speicherkette. Schieberegistersollten aus Master-Slave-D-Flipflops bestehen, da jede Speicherzelle gleichzeitig Datenubernehmen und weitergeben muss.

1D

C1

1D

C1

1D

C1

D Q

QT

Abbildung 9.10: Serienspeicher (Schieberegister)

9.3.2 Technische Realisierung statischer Parallel- undSerienspeicher

Eigenschaften

Bei Bibliothekskomponenten handelt es sich meistens um Kombinationen aus Parallel-und Serienspeichern, um deren Anwendungsbereich zu erhohen. Unterschieden werden

122

REV

1468

die Speicher nach Art der Ein- und Ausgabe der Daten an den Speicherzellen (par-allel und/oder seriell). Weitere Eigenschaften der Speicherzellen konnen die Wahl derSchieberichtung nach rechts oder links sowie ein asynchrones Loschen oder Setzen sein.

Beispiel 86. 8-Bit-Schieberegister mit serieller Ein-/Ausgabe und paralleler Ausgabe

1D

C1

1D

C1

1D

C1

&

1

AB

Q8

Reset

Serielle Eingange Q1 Q2

Parallele Ausgange

T

Abbildung 9.11: Schieberegister mit serieller Ein-/Ausgabe und paralleler Ausgabe

Diese Schaltung 9.11 ermoglicht die Serien-/Parallel-Umsetzung der Daten. Von denzwei seriellen Eingange A und B kann jeweils einer zu Steuerzwecken verwendet werden.Ist einer der beiden Eingange ’1’, wird der andere durchgeschaltet.Die Daten werdenwahrend der positiven Taktflanke (SlaveÑMaster) durch das Register geschoben und lie-gen gleichzeitig an den parallelen Ausgangen Q1, ...Q8 an. Das Register kann asynchronuber den Reset-Eingang zuruckgesetzt werden.

Beispiel 87. 8-Bit-Schieberegister mit serieller Ein-/Ausgabe und paralleler EingabeDiese Schaltung 9.12 ermoglicht ebenfalls die Serien-/Parallel-Umsetzung der Daten.Dieses Schieberegister ist umschaltbar zwischen Schiebebetrieb und parallelem Laden.Wenn das Signal Setzen 1 ist, dann wird derTakt an den Flipflops gesperrt und dieparallel anliegenden Daten zu den Eingangen I1, ...I8 unabhangig vom Takt (asynchron)in die Flipflops ubernommen. Andernfalls (Setzen 0) sind die parallelen Eingange ge-sperrt und der Takt ist freigegeben. Die Daten werden dann in Richtung des seriellenAusgangs Q8 abhangig vom Takt (synchron) verschoben. Bei gesetztem Sperren-Eingangwird der Schiebebetrieb unterbrochen und ein paralleles Laden ist ebenfalls nicht moglich.

Beispiel 88. Schieberegister mit zwei SchieberichtungenBei arithmetischen Operationen sind oftmals beide Schieberichtungen erforderlich. FurSchiebeoperation von rechts nach links mussen die Ausgange der Flipflops mit den Eingangender links neben ihnen liegenden Flipflops verknupft werden. Die steuerbare Schieberich-tung erfordert einen Multiplexer, der je nach Schieberichtung den Ausgang mit demEingang des links oder rechts benachbarten Flipflops verbindet. Bei gesetztem RL-Signalwird das Schieben nach rechts vorgegeben. Die Daten von DR werden ubernommen undan Q4 ausgegeben. RL 0 bewirkt folgerichtig das Schieben nach links. Das Verschie-ben der Daten erfolgt mit steigender Taktflanke (0Ñ1). Wahrend des Schiebens darf

123

REV

1468

1D

C1

1D

C1

1D

C1

D Q8

&

I1

&

&

I2

&

&

I8

&

Parallele Eingange

1

¥ 1

&

&

Setzen

Sperren

T

Abbildung 9.12: Schieberegister mit serieller Ein-/Ausgabe und paralleler Eingabe

die Schieberichtung nicht gewechselt werden, da sonst ein undefinierter Zustand auftritt.(siehe Abbildung 9.13)

9.4 Zahler und Untersetzer

9.4.1 Ubersicht

Bei einem Zahler stellt jeder Zustand eine Zahlerstellung dar. Eine einfache Sonder-form der Zahler sind die Untersetzer (Frequenzteiler). Ein Untersetzter bewirkt nureine Abfrage eines vorgegebenen Teilerverhaltnis und ist meist einfacher aufgebaut. Diegebrauchlichsten Zahler sind reine Dual-Code-(modulo 2)-Zahler und der BCD-Code-Zahler, bei dem sechs Zustande des Dualcodes ubersprungen werden. Unterschiedenwerden die Systeme durch ihre jeweilige Betriebsart (asynchron oder synchron). Beimasynchronen Betrieb werden die Flipflops immer von dem in der Zahlfolge vorangehen-den Flipflop getaktet. Bei der synchronen Variante werden alle Flipflops eines Zahlersdurch eine gemeinsame Clock gleichzeitig getaktet.

9.4.2 Untersetzer

Asynchroner Untersetzer

Ein asynchroner Untersetzer kann z. B. durch eine Kaskadierung von D-Latches rea-lisiert werden. Mit der Beschaltung D Q wirken die n D-Latches als Untersetzer imUntersetzungsverhaltnis 2n : 1. Der Q-Ausgang jedes Flipflops wird mit dem Taktein-gang des folgenden Flipflops verbunden. Die Verzogerungszeiten tpd addieren sich mitjeder zusatzlichen Untersetzerstufe (Nachteil). Bei Untersetzern mit einem geringeren

124

REV

1468

1D

C1

1D

C1

1D

C1

Q1

01

Q2

01

Q4

01DR

DL

RL

T

Loschen

Abbildung 9.13: Schieberegister mit zwei Schieberichtungen

1D

C1

1D

C1

1D

C1TaktQ3

(a) Schaltung

T

Q1

Q2

Q3

tpd3 tpd

(b) Impulsdiagramm

Abbildung 9.14: Asynchroner Binaruntersetzer

Teilerverhaltnis als 2n : 1 mussen durch Ruckfuhrungen entsprechend dem gewahltenTeilerverhaltnis Zahlerzustande unterdruckt werden.

Synchroner Untersetzer

Wie fur synchrone Systeme ublich werden alle Flipflops gleichzeitig vom gemeinsamenTakt gesetzt. Als Verzogerungszeit des gesamten Untersetzers tritt also nur die Laufzeiteiner Stufe auf. Die Takteingange konnen dadurch aber nicht zur Bestimmung des Tei-lerverhaltnisses mitbenutzt werden. Damit ergibt sich ein hoherer Schaltungsaufwandgegenuber den asynchronen Untersetzern.In der Abbildung ist ein einfacher synchroner Untersetzer mit Schieberegister dargestellt.Die n Stufen ergeben ein Untersetzungsverhaltnis von n 1. Zusatzlich ist der Ausgangauf den Eingang zuruckgefuhrt. Zu Beginn wird uber das S-Signal das erste Flipflopgesetzt (Q1 1 ) und die beiden anderen Flipflops zuruckgesetzt. Danach wird mit jedemTaktimpuls die ”1”jeweils um eine Stufe verschoben. Bei kreuzweiser Ruckkopplungder Schieberegisterausgange erhoht sich das Untersetzungsverhaltnis auf 2n 1. DasEingangsflipflop wird dann ebenfalls zu Beginn zuruckgesetzt.

125

REV

1468

S

1S

C1

1R

S

1S

C1

1R

S

1S

C1

1R

S

T

1

Q1 Q2Q3

Abbildung 9.15: Synchroner Untersetzer

9.4.3 Zahler

Asynchroner Zahler

Asynchrone Zahler werden ahnlich wie asynchrone Untersetzer entworfen. Es werden ent-sprechend dem verwendeten Zahlcode Zustande ubersprungen. Die asynchronen Zahlerweisen den gleichen Nachteil wie asynchrone Untersetzer auf. Trotzdem kommt dieserZahlertyp wegen seines geringen Aufwands zum Einsatz.Voraussetzung ist dabei aber,dass keine hohe Zahlgeschwindigkeit erforderlich ist.

Beispiel 89. BCD-Code-Zahler

Zahlerstand Q4 Q3 Q2 Q1

0 0 0 0 01 0 0 0 12 0 0 1 03 0 0 1 14 0 1 0 05 0 1 0 16 0 1 1 07 0 1 1 18 1 0 0 09 1 0 0 1

1J

C1

1K

1J

C1

1K

1J

C1

1K

1J

C1

1K

&

Q1

Q2

Q3

”1”

TQ4

Abbildung 9.16: Asynchroner Zahler fur den BCD-Code

126

REV

1468

Synchroner Zahler

Die Zahlfrequenz synchroner Zahler ist unabhangig von der Anzahl der Flipflops. Esaddieren sich hierbei nicht die Flipfloplaufzeiten. Der große Nachteil ist wiederum dererhohte Schaltungsaufwand. Die gebrauchlichsten Zahler arbeiten im reinen Dualcodeoder im BCD-Code.

Beispiel 90. Synchroner 4-Bit Vorwartszahler im Dualcode

1J

C1

1K

1J

C1

1K

1J

C1

1K

1J

C1

1K

&

&

&

Q1 Q2 Q3”1”

T

Q4

C

(a) Schaltung

T

Q1

Q2

Q3

Q4

C

(b) Impulsdiagramm

Abbildung 9.17: Synchroner dualer 4-Bit-Vorwartszahler

Die Schaltung 9.17 ist mit RS-Flipflops realisiert. Der Entwurf des Zahlers erfolgt aus derUbergangstabelle, wobei die Zustande entsprechend dem Dualcode durchlaufen werden.Zur Kaskadierung mehrerer Zahlerbausteine ist ein Ubertragsausgang U vorhanden. DasU-Signal wird auf den Takteingang des nachsten Zahlerbausteins gefuhrt, so dass dieKaskadierung asynchron erfolgt.

Synchroner Ruckwartszahler

Die Vorwartszahlerschaltung kann in einen Ruckwartszahler abgeandert werden, wenndie Q-Ausgange mit den Q-Ausgangen vertauscht werden.

Beispiel 91. Synchroner dualer 4-Bit Ruckwartszahler (siehe Abbidung 9.18)

In integrierten Zahlerbausteinen wird meistens die Vorwarts- und Ruckwartszahlungdurch eine ODER-Schaltung kombiniert. Die Zahlrichtung kann dann uber einen zusatz-lichen Steuereingang bestimmt werden.

127

REV

1468

1J

C1

1K

1J

C1

1K

1J

C1

1K

1J

C1

1K

&

&

&

Q1 Q2 Q3

”1”

T

Q4

U

Abbildung 9.18: Synchroner dualer 4-Bit-Ruckwartszahler

128

REV

1468

10 HardwarebeschreibungsspracheVHDL

10.1 Motivation

Aktuelle Situation beim Entwurf elektronischer Systeme

• Integrationsgrad und Integrationsdichte steigen kontinuierlich

• Konkurrenzdruck und Kundenanforderungen bedingen kurze Entwicklungszeiten

Grunde fur vollstandige, widerspruchsfreie und verstandliche Dokumentation

• Komplexitat, Modularisierung

• Wiederverwendung von Entwurfsdaten und

• Wartung des fertigen Produktes

Kompatibilitat der Entwurfsdaten

• Beschreibungsmittel mussen herstellerubergreifend normiert, rechnerunabhangigsein und mehrere Entwurfsebenen abdecken - Fixierung auf herstellerspezifischeBeschreibungssprache kann hohes wirtschaftliches Risiko bedeuten

10.2 Entwurfssichten

Entwurfsfluss (Top-down-Entwurf) Der Entwurf komplexer elektronischer Systemekann nur durch eine strukturierte Vorgehensweise beherrschbar gestaltet werden. Sys-temspezifikation wird die Schaltungsfunktion partitioniert (funktionale Dekomposition)und die Funktionen einzelnen Modulen zugeordnet. Schrittweise wird der Entwurf fei-ner strukturiert und zunehmend mit Implementierungsdetails versehen, bis die fur dieFertigung notwendigen Daten vorliegen. Dieses sind z. B. Programmierdaten fur Logik-bausteine, Layouts fur PCB‘s oder Maskenbander fur IC-Fertigung.

129

REV

1468

Sichtweisen beim Entwurf elektronischer Systeme

• Verhalten,

• Struktur und

• Geometrie.

Behavioural Domain Structural Domain

Physical Domain

Systems

Algorithms

Register transfers

Logic

Transfer functions

Processors

Hardware modules

ALUs, RAM, etc.

Gates, flip-flops, etc.

Transistors

Physical partitions

Floorplans

Module layout

Cell layout

Transistor layout

Abbildung 10.1: Gajski-Kuhn Y-Diagramm

Zu den drei Sichtweisen (Aste im Y-Diagramm) existieren verschiedene Abstrakti-onsebenen. Der Entwurf elektronischer Systeme kann als Reihe von Transformationen(Wechsel der Sichtweise) und Verfeinerungen (Wechsel der Abstraktionsebene innerhalbeiner Sichtweise) im Y-Diagramm dargestellt werden.

10.3 Historische Entwicklung

1983 Start der VHDL-Entwicklung in den USA Arbeiten im Rahmen des VHSIC-Programms(Very High Speed Integrated Circuit). Ziel der Sprache: Austausch von Entwurfen zwi-schen Herstellern Anlehnung an Ada, da das Verteidigungsministerium diese Sprache inweitem Umfang einsetzt. 1987 Ubernahme von VHDL als IEEE-Standard (IEEE 1076-1987). Dieser erste und bislang einzige IEEE-Standard fur HDL definiert nur die Syntaxund Semantik der Sprache, nicht jedoch ihre Anwendung bzw. einheitliches Vorgehenbei der Anwendung, insbesondere Synthese von Anfang 1992 bis Mitte 1993 Definitionder Version IEEE 1076-1993 Dokumentation des neuen Standards (Language Reference

130

REV

1468

h:ohereEntwurfsebene

SyntheseGeneration

AnalyseExtraktion

VerifikationValidierung

niedrigereEntwurfsebene

Abbildung 10.2: Prinzipieller Verlauf eines Entwurfsschrittes

131

REV

1468

Manual, LRM), wurde 1994 durch das IEEE herausgegeben neue Version enthalt imwesentlichen kosmetische Anderungen (Systematisierung der Syntax), z.B. Einfuhrungeines XNOR-Operators Seit Anfang 90er Jahre weltweiter Durchbruch fur VHDL Heu-tige Konkurrenz von VHDL besteht vor allem in Verilog (USA) und UDL/I (Japan)

10.4 Aufbau einer VHDL-Beschreibung

10.4.1 Entity-Relationship-Modell

Datenmodelle zur HardwarebeschreibungEs gibt zwei unterschiedliche Datenmodelle. Zum einen das herkommliche, strukturelleDatenmodell. In diesem gibt es hierarchische, netzartige und relationale Datenmodelle.Diese weisen je nach Anwendbarkeit als Hauptnachteil die ungenugende Modellierbar-keit komplexer Objekte auf. Semantischen Datenmodelle konnen zwar machtige Daten-strukturen unterstutzen. Allerdings lassen sich die Operationen oft nur unzulanglichdefinieren.

Allgemeines Grundkonzept des ER-Modells(semantisches DatenmodellMan kann in diesem Modelltyp in zwei unterschiedliche Datentypen unterscheiden. Zumeinen die Entitytypen (Objekttypen) mit denen man einzelne Objekte der realen Weltnachbildet. Diese sind im folgenden als Kastchen dargestellt. Zum anderen gibt es dieRelationships, welcher in der Abbildung als Raute dargestellt ist. Diese beschreiben dieRelation zwischen mehreren Entitaten.

Schaltung enthalt Bauteilnm

Abbildung 10.3: Einfaches ER-Diagramm.

Ein Beziehungstyp kann im ER-Modell uber belieb vielen Entitaten definiert sein.Beim IC-Entwurf hat sich die Verwendung von Zellen als Grundstrukturmuster alszweckmaßig erwiesen. Bei der Beschreibung von Zellen unterschiedet man zwischen derSchnittstelle und dem Inhalt einer Zelle, die jeweils selbst wieder sehr komplexe Gebildesein konnen.

10.4.2 Ubersicht

Die wichtigsten Bestandteile eines VHDL-Modells ist die Instanz mit der Schnittstellen-beschreibung(entity), eine oder mehrere Architekturen(architecture), eine oder mehre-re Konfigurationen(configuration), vordefinierte Funktionen, Prozeduren, Komponentenund Konstanten(package) und vordefinierte Bibliotheken(libraries).

132

REV

1468

enthalt

Zelle

InhaltSchnittstelle

1

1 n

Abbildung 10.4: VHDL ER-Diagramm.

10.4.3 Schnittstellenbeschreibung

Schnittstelle der/des zu modellierenden Komponente/Systems Die Ein- und Ausgangesowie deren Konstanten, Unterprogramme und sonstige Vereinbarungen, die auch fur alledieser Entity zugeordneten Architekturen gelten sollen.

0 entity ent ity name i s1 [ generic ( g e n e r i c l i s t ) ] [ port ( p o r t l i s t ) ; ]2 e n t i t y d e c l a r a t i v e p a r t3 [ begin4 pas s i v e concu r r en t s t a t ement ]5 end [ entity ] [ ent i ty name ] ;

Beispiel 92. Schnittstellenbeschreibung (entity) eines OR-Gatters

0 entity or2 i s1 port ( in1 , in2 : in b i t ; out1 : out b i t ) ;2 d e f i n i e r e Pins a l s S i gna l e vom Typ b i t3 end or2 ;

10.4.4 Architektur

Die Architektur - auch architecture genannt - ist eine Verhaltensbeschreibung oder kanneinen strukturellen Charakter besitzen. Man kann mehrere dieser Funktionsbeschreibun-gen kombinieren. Somit kann man fur eine Entity mehrere Architekturen deklarieren.

133

REV

1468

Dadurch konnen fur eine Komponentenschnittstelle mehrere Beschreibungen auf unter-schiedlichen Abstraktionsebenen oder verschiedene Entwurfsalternativen bestehen.

Syntax

0 architecture arch i t ec ture name of ent ity name i s1 a r c h i t e c t u r e d e c l a r a t i v e p a r t2 begin3 a l l c o n c u r r e n t s t a t e m e n t s4 end [ architecture ] [ a r ch i t ec ture name ] ;

Beispiel 93. Architektur (architecture) eines OR-Gatters

0 architecture o r 2 b e h a v i o r a l of or2 i s1 begin2 out1 <= in1 or in2 ; Verha l t en s b e s c h r e i b ung3 end o r 2 b e h a v i o r a l ;

10.4.5 Konfiguration

Eine Konfiguration(configuration) beschreibt welche Zuordnung fur die moglicherweiseverwendeten Submodule in der Architecture einer bestimmten Entity gelten sollen. Eskonnen auch hierarchisch den untergeordneten Entities bestimmte Architekturen oderParameterwerte zugeordnet werden.

Syntax

0 configuration con f igurat ion name of ent ity name i s1 u s e c l a u s e . a t t r i b u t e s p e c i f i c a t i o n 2 blockconfiguration 3

4 for componen t spe c i f i c a t i on5 [ use b i n d i n g i n d i c a t i o n ; ]6 [ b l o c k c o n f i g u r a t i o n ]7 end for ;8

9 end [ con f igurat ion name ] ;

Beispiel 94. Architektur (architecture) eines OR-Gatters

0 configuration o r 2 c on f i g of or2 i s1 for g a t e l e v e l ve r knuep f e a r c h i t e c t u r e g a t e l e v e l2 end for ; mit e n t i t y or23 end o r 2 c on f i g ;

134

REV

1468

10.4.6 Packages und Libraries

Packages fassen Typen oft gebrauchter Funktionen, Prozeduren, Komponenten oderKonstanten zusammen. Dazu zahlen auch Anweisungen, wie Typ- oder Objektdekla-rationen und Beschreibungen von Prozeduren und Funktionen, die in mehreren VHDL-Beschreibungen gebraucht werden. Es gibt vordefinierte Packages wie

”standard“, welche

den zweiwertigen Logiktyp”bit“ und haufig verwendete Funktionen und Typen beinhal-

tet.Syntax

0 package name of the package i s1 p a c k a g e d e c l a r a t i v e p a r t2 end [ package ] [ name of the package ] ;

Bibliotheksobjekte werden in einer Library zusammengefasst. Die Bekanntgabe eineroder mehrerer dieser Bibiliotheken erfolgt durch das library-Tag. Dabei sind Bibliothekenwie std und work in VHDL allgemein bekannt.

Syntax

0 l ibrary l i b ra ry name 1 , l i b r a r y n a m e i ; Aufruf der B i b l i o t h e k1

2 use l ib rary name . a l l ;

10.5 Entwurfssichten in VHDL

10.5.1 Verhaltensmodellierung

Das Verhalten einer Komponente wird durch die Reaktion der Ausgangssignale aufAnderungen der Eingangssignale beschrieben. Die Komponente verzweigt nicht weiterin Unterkomponenten.

Beispiel 95. Verhaltensmodellierung eines KomparatorsDieser Liefert eine boolsche

”1“ wenn a großer ist als b. Außerdem lassen sich mit dem

n beliebig breite Vektoren vergleichen.

0 entity compare i s1 generic (n : p o s i t i v e := 4 ) ;2 port (a , b : in b i t v e c t o r (n1 downto 0 ) ; r e s u l t : out b i t ) ;3 end compare ;4

5 architecture b e h a v i o r a l 1 of compare i s6 begin7 process (a , b )8 begin9 i f a > b then l i e f e r t 1 f a l l s a > b

10 r e s u l t <= ’1 ’ ;

135

REV

1468

11 else12 r e s u l t <= ’0 ’ ;13 end i f ;14 end process ;15 end b e h a v i o r a l 1 ;

Die beiden prinzipiellen Beschreibungsmittel in der Verhaltenssicht sind sequentiel-le(sequential) oder nebenlaufige Anweisungen (concurrent statements). Bei den sequen-tiellen bzw. prozeduralen Beschreibungen werden Konstrukte wie Verzweigungen(if-then-else), Schleifen(loop) oder Unterprogrammaufrufe(function, procedure) verwendet.

Beispiel 96. Modell eines Halbaddierers mit Schnittstelle und ArchitekturAnm.: Die Ergebnisse werden erst beim Verlassen des Prozesses sichtbar.

0 entity ha l f a d d e r i s1 port (a , b : in b i t ; sum , carry : out b i t ) ;2 end ha l f a d d e r ;3

4 architecture b e h a v i o r a l s e q of ha l f a d d e r i s5 begin6 process (a , b )7 begin8 i f ( a = ’1 ’ and b = ’1 ’ ) then sum <= ’0 ’ ; carry <= ’1 ’ ;9 else

10 i f ( a = ’1 ’ or b = ’1 ’ ) then sum <= ’1 ’ ; carry <= ’0 ’ ;11 else sum <= ’0 ’ ; carry <= ’0 ’ ;12 end i f ;13 end i f ;14 end process ;15 end b e h a v i o r a l s e q ;

Bei den nebenlaufigen Anweisungen ist es erlaubt parallel ablaufende Operationen zubeschreiben. Hiermit kann man spezifischer Eigenschaften von Hardware bzw. parallelarbeitenden Funktionseinheiten beschreiben.

Beispiel 97. Architektur des Halbaddierers mit nebenlaufigen AnweisungenAnm.: Die beiden Verknupfungen XOR und AND konnen dabei gleichzeitig aktiv sein.

0 architecture b e h a v i o r a l p a r of ha l f a d d e r i s1 begin2 sum <= a xor b ;3 carry <= a and b ;4 end b e h a v i o r a l p a r ;

136

REV

1468

10.5.2 strukturelle Modellierung

Das Wesen der strukturellen Modellierung besteht aus der Darstellung des inneren Auf-baus aus Unterkomponenten. Die Eigenschaften derUnterkomponenten werden in un-abhangigen VHDL-Modellen beschrieben. Diese stehen kompiliert in Modellbibliothekenzur Verfugung. Eine eindeutige Zuordnung eines VHDL-Modells in eine der beiden Mo-dellierungsarten ist oft schwierig. Daher ist es in VHDL erlaubt beide Beschreibungsarteninnerhalb eines Modells zu benutzen.

Beispiel 98. Halbaddierer, der aus einem XOR2- und einem AND2-Gatter aufgebautist

0 architecture s t r u c t u r a l of ha l f a d d e r i s1 component xor22 port ( c l , c2 : in b i t ; c3 : out b i t ) ;3 end component ;4

5 component and26 port ( c4 , c5 : in b i t ; c6 : out b i t ) ;7 end component ;8

9 begin10 x o r i n s t a n c e : xor2 port map (a , b , sum ) ;11 and in s t ance : and2 port map (a , b , carry ) ;12 end s t r u c t u r a l ;

10.6 Entwurfsebenen in VHDL

10.6.1 Algorithmusebene

Die Schaltung im Beispiel soll immer dann, wenn sie von einem Controller eine Auffor-derung erhalt, eine Adresse aus einem internen Register nach fruhestens 10ns auf denBus legen. Dabei enthalt die Beschreibung keine Angaben uber die spatere Schaltungs-struktur und Takt- oder Rucksetzsignale.

Beispiel 99. Beschreibung eines Schnittstellenbausteins auf Algorithmusebene

0 architecture a l g o r i t hm i c l e v e l of i o c t r l i s1 begin2 . . .3 w r i t e d a t a a l g : process4

5 begin6 wait unti l a d r r e q u e s t = ’ 1 ’ ;

137

REV

1468

7 wait for 10 ns ;8 bus adr <= in t a d r ;9 end process w r i t e d a t a a l g ;

10 end a l g o r i t hm i c l e v e l ;

10.6.2 Register-Transfer-Ebene

Im Unterschied zur Algorithmusebene wird in der Register-Transfer-Ebene ein zeitlichesAblaufschema der Operation vorgegeben und implizit eine Schaltungsstruktur beschrie-ben. Im Beispiel wird ein Taktsignal (clk) hinzugefugt und die Operation in Abhangigkeitdieses Signals beschrieben.

Beispiel 100. Beschreibung eines Schnittstellenbausteins auf Algorithmusebene

0 architecture r t l e v e l of i o c t r l i s1 begin2 . . .3 w r i t e d a t a r t l : process ( c l k )4 variable tmp : boo l ean ;5

6 begin7 i f ( c l k ’ e ven t ) and ( c l k = ’1 ’ ) then8 i f ( ( a d r r e q u e s t = ’1 ’ ) and ( tmp = f a l s e ) ) then tmp := t rue ;9 e l s i f ( tmp = t rue ) then bus adr <= in t a d r ; tmp := f a l s e ;

10 end i f ;11 end i f ;12 end process w r i t e d a t a r t l ;13 end r t l e v e l ;

Wird bei aktiver Taktflanke ein gesetztes adr-request-Signal entdeckt, wird die tem-porare Variable tmp gesetzt, damit bei nachster aktiver Taktflanke (Wartezeit!) dieAdresse auf den Bus geschrieben werden kann. Eine geeignete Wahl der Taktperiodestellt die Wartezeit von mindestens 10ns sicher.

10.6.3 Logik(Gatter)ebene

Elektronische Systeme werden durch logische Verknupfungen digitaler Signale und derenzeitlichen Eigenschaften (Verzogerungszeiten der Verknupfungen) beschrieben. VHDLbesitzt dazu vordefinierte Operatoren wie AND, OR, XOR, NOT, etc. fur binare Si-gnale (’0’, ’1’) und gestattet die Erganzung durch benutzerdefinierte Operatoren. DieKonstrukte zur Modellierung zeitlicher Eigenschaften werden bereitgestellt.

Beispiel 101. Halbaddierer-Architektur auf Logikebene in Verhaltenssichtweise

138

REV

1468

0 architecture l o g i c 1 e v e 1 of ha l f a d d e r i s1 begin2 sum <= a xor b after 3 ns ;3 carry <= a and b after 2 ns ;4 end l o g i c l e v e l ;

Die strukturelle Darstellung entspricht vorherigem Beispiel der Architektur structu-ral. Die Verzogerungszeiten ergeben sich hier aus den internen Verzogerungszeiten derSubkomponenten.

10.7 Logiktypen

9-wertiges Logikwertesystem von VHDL ieee.std logic 1164 MVL9

Das Logikwertesystem ist nicht als Teil der Sprachdefinition definiert und kann an je-weilige Problemstellungen angepasst werden. Der Datenaustausch der VHDL-Modelleund der Einsatz von Synthesewerkzeugen erfordern aber eine Standardisierung. Fur ei-ne hardwarenahe Simulation wird haufig mit den 9 Zustand/Starkewerten von MVL9modelliert. Es beinhaltet eine Berucksichtigung der Signaltreiberstarke. Dies bedeutet,dass bei der Spannungsversorgung , Eingange oder aktive Gatterausgange starkere Werteschwachere Starken uberschreiben. Dabei kann man folgende Festlegung der Signalwertetreffen. Es gibt zum einen die drei Signaltreiberstarken

”stark“,

”schwach“ und

”hoch-

ohmig“. Dazu kommen die Logikpegel”0“,

”1“ und

”unbestimmt“. Daruber hinaus gibt

es die zusatzlichen Werte”nicht initialisiert“ fur die Simulation und ein

”don’t-care“ fur

Syntheseanwendungen.Die Ausgange der Gatter konnen mit einem Bus verbunden werden. Die Auflosung

der zusammengeschalteten Signale an einem Bus erfolgt nach folgender Grafik und vonlinks nach rechts in aufsteigender Reihenfolge.

139

REV

1468

Wert deutsche Beschreibung englische BeschreibungU nicht Initialisiert uninitializedX stark unbestimmt strong unknown0 starker

”0“-Pegel strong low

1 starker”1“-Pegel string high

Z Hochohmig tri-stateW schwach unbestimmt weak unknownL schwacher

”0“-Pegel weak low

H schwacher”1“-Pegel weak high

- don’t-care

(a) Ubersicht uber das Logikwertesystem

-

Z

LH

W

01

X

U

(b) Hasse Diagramm

Abbildung 10.5: 9-wertige Logik

140

REV

1468

VHDL-Konstrukte zur Laufzeitmodellierung

Bei der Laufzeitmodellierung in VHDL muss man verschiedene Delays mit einbauendamit die Simulation so realitatsnah wird wie irgend moglich. Das erste dieser Delays istdas

”Transport-Delay“, bei dem jeder Impuls unabhangig von seiner Dauer verzogert am

Ausgang erscheint. Das”Inertial-Delay“ hingegen gibt nur Impulse weiter deren Dauer

großer als die angegebene Verzogerungszeit des angesteuerten Gatters sind. Es findethier sowohl eine Impulsunterdruckung als auch eine Zeitverzogerung von gleicher langestatt. Im Gegensatz dazu wird bei dem

”Reject-Inertial-Delay“ der Zeitbereich fur die

Impulsunterdruckung und die Zeitverzogerung separat angegeben.

0 entity nand2 i s1 port ( a , b : in s t d l o g i c ; o : out s t d l o g i c ) ;2 end nand2 ;3

4 architecture s e v e r a l d e l a y s of nand2 i s5 begin6 e in f ache Verzoegerung7 o <= transport a nand b after 2 ns ;8

9 Verzoegerung mit Impulsmindes t loenge10 o <= [ inert ia l ] a nand b after 2 ns ;11

12 Verzoegerung mit s ep e ra t e r Impulsmindes t laenge13 o <= reject 1 ns inert ia l a nand b after 2 ns ;14 end s e v e r a l d e l a y s ;

10.8 Testumgebung

Die VHDL-Simulation erfolgt in drei Phasen. Die Elaboration ist der Aufbau der Schal-tung aus den compilierten VHDL-Modellen. Die Initialisierung beinhaltet die Signale,Variablen und Konstanten die Anfangswerte erhalten. Diese Werte ergeben sich aus ex-pliziter Angabe durch die Typ-Spezifikation. Jeder Prozess wird einmal gestartet. DieAusfuhrung ist die Simulation bis zum Ende der spezifizierten Simulationsdauer. ZurStimuli-Generierung und zur Ergebnisauswertung wird das zu testende Modell in eineTestbench eingebunden. Das Modell wird instanziiert und mit den Ein- und Ausgangs-signalen verdrahtet.

141

REV

1468

Stichwortverzeichnis

1-aus-n-Code, 572-Komplement-Zahlen, 212K-Zahlen, 21

Addition2K Zahlen, 22vorzeichenloser Zahlen, 19

Arithmetische Schaltnetze, 64Halbaddierer, 65Volladdierer, 65

Aussagen, 1

Branching, 51

Codierer, 55

Decodierer, 56Demultiplexer, 59

Faktorisierung, 53Flipflop, 83

Asynchrones RS-Flipflop, 84Getaktetes D-Flipflop, 85Getaktetes RS-Flipflop, 85Master-Slave-D-Flipflop, 85

Funktionsbundel, 14

Gray-Code, 23

Implikanten, 36

Karnaugh-Veitch-Diagramm, 15Komparator, 62KV-Diagramm, 15

Multiplexer, 58

Normalformen, 25

allgemeine disjunktive Normalform,26

allgemeine konjunktive Normalform,30

disjunktive Normalform, 26DNF, 26kanonische disjunktive Normalform,

27kanonische konjunktive Normalform,

31KDNF, 27KKNF, 31KNF, 30konjunktive Normalform, 30

Primimplikanten, 39Programmierbare Logik, 88

FPGA, 99PLA, 96

Quine-McCluskey-Algorithmus, 47

Register, 121Parallelspeicher, 121Serienspeicher, 122

Reihendominanz, 50

Spaltendominanz, 51Subtraktion

2K Zahlen, 22vorzeichenloser Zahlen, 19

Synchrone Schaltwerke, 115Mealy-Automat, 115Moore-Automat, 116Zustands-/Ubergangsgraph, 115Zustandstabelle, 115Zustandszuordnung, 117

142

REV

1468

Technische Aspekte des Logikentwurfs,104

Tison-Algorithmus, 48

Untersetzerasynchron, 124synchron, 125

Wahrheitstabelle, 2Wertetabelle, 2

Y-Diagramm, 130

Zahlenbereich2K Zahlen, 22vorzeichenloser Zahlen, 20

Zahlendarstellung, 18Zahler

asynchron, 126synchron, 127

Zweiwertige Logik, 1

143

Documents

Technische Grundlagen der Informatik 1 Digitale Systeme · 2011-04-11 · Wir haben uns in diesem Semester entschlossen ein Skript anzubieten, ... Allgemein fur A1 und A2 als zwei