Logischer Entwurf digitaler Systeme (eBook)

Hans Liebig 1939 in Ebersbach geboren. 1958–1963 Studium der Elektrotechnik an der Technischen Hochschule München; 1963–1965 Entwicklungsingenieur im Fachgebiet Informationstechnik – Elektronische Rechenanlagen – bei TELEFUNKEN in Konstanz; 1965–1970 wissenschaftlicher Assistent am Institut für Informationsverarbeitung der Technischen Universität Berlin; ab 1970 Professor für Informatik an der Technischen Universität Berlin. Seit 1968 Vorlesungen über Logischer Entwurf digitaler Systeme, über Rechnerorganisation sowie über Prinzipien der Rechnerstrukturen.

Vorwort 5
Inhaltsverzeichnis 9
1 Boolesche Algebra, Automaten, Algorithmen 12
1.1 Aussagenlogik 12
1.1.1 Logische Grundverknüpfungen 13
1.1.2 Logische Ausdrücke 20
1.1.3 Äquivalenz 25
Axiome 28
Sätze 29
Dualität und Negation 30
1.1.4 Implikation 32
1.2 Boolesche Funktionen 34
1.2.1 Einfache Funktionen (Skalarfunktionen) 34
1.2.2 Systeme von Funktionen (Vektorfunktionen) 40
1.2.3 Kanonische Formen 43
Normalformdarstellung einer Funktion 44
Ausgezeichnete Normalformen 47
Minimale Normalformen 51
1.2.4 Konstruktion kanonischer Formen aus Tafeln 53
Minimierung von Skalarfunktionen 54
Von der Funktion zum Schaltnetz 61
1.3 Endliche Automaten, boolesche Algorithmen 62
1.3.1 Grundlegende Begriffe 63
1.3.2 Automatenmodelle 67
1.3.3 Darstellungsmittel 72
1.4 Kooperierende Automaten, parallele Algorithmen 80
1.4.1 Ereignis- versus taktgesteuerter Zustandsfortschaltung 81
1.4.2 Synchronisation von Prozessen 89
1.5 Lösungen der Aufgaben 95
2 Schaltnetze, Schaltketten 109
2.1 Schaltungsstruktur und Funktionsweise 109
2.1.1 Schalter und Schalterkombinationen 112
2.1.2 Durchschaltglieder 118
2.1.3 Verknüpfungsglieder 125
2.1.4 Mehrstufige Logik 134
2.1.5 Rückgekoppelte Logik 144
2.2 Schaltnetze zur Datenverarbeitung 149
2.2.1 Schaltketten für die Addition 150
2.2.2 Arithmetisch-logische Einheiten 154
2.2.3 Beschleunigung der Übertragsweiterleitung 158
2.3 Schaltnetze zum Datentransport 165
2.3.1 Multiplexer, Demultiplexer 166
2.3.2 Shifter 170
2.3.3 Vernetzer, Busse 173
2.4 Schaltnetze zur Datencodierung, -decodierung und -speicherung 178
2.4.1 Übersicht 179
2.4.2 Codierer, Decodierer 181
2.4.3 Konfigurierbare /programmierbare Speicher 185
2.5 Lösungen der Aufgaben 193
3 Asynchron-Schaltwerke 209
3.1 Schaltungsstruktur und Funktionsweise 209
3.1.1 Eine typische Aufgabe: Asynchroner Datentransfer 215
3.1.2 Interprozeß-Kommunikation 218
3.1.3 Asynchroner Datentransfer: Pegelgraph 225
3.2 Entwurf Teil 1: Vom Petri-/Graphennetz zur Flußtafel 226
3.2.1 Verfahren 227
3.2.2 Eingangssignale wechselseitig abhängig 230
3.2.3 Eingangssignale voneinander unabhängig 233
3.2.4 Asynchroner Datentransfer: Flußtafel 239
3.3 Hazards in Schaltnetzen, hazardfreier Entwurf 240
3.3.1 Strukturelle Hazards 241
3.3.2 Funktionelle Hazards 243
3.3.3 Zwei Tests zur Feststellung von Hazards 245
3.4 Hazards in Schaltwerken, hazardfreier Entwurf 250
3.4.1 Strukturelle Hazards (static hazards) 251
3.4.2 Funktionelle Hazards (essential hazards) 255
3.4.3 Konkurrente Hazards (critical races) 259
3.5 Entwurf Teil 2: Von der Flußtafel zur Schaltung 264
3.5.1 Verfahren 264
3.5.2 Entwurfsbeispiele und -aufgaben 268
3.5.3 Determiniertheit/Indeterminiertheit 276
3.5.4 Asynchroner Datentransfer: Schaltung 277
3.6 Lösungen der Aufgaben 280
4 Synchron-Schaltwerke 296
4.1 Schaltungsstruktur und Funktionsweise 296
4.1.1 Eine typische Aufgabe: Synchroner Speicher 301
4.1.2 Takterzeugung 304
4.1.3 Getaktete Flipflops, Darstellung mit Taktsignalen 306
4.1.4 Getaktete Flipflops, Abstraktion von Taktsignalen 312
4.2 Schaltwerke zur Datenspeicherung 320
4.2.1 Speicherung einzelner Bits: Flipflops 320
4.2.2 Speicherung binärer Datenwörter: Register 322
4.2.3 Speicherung von Datensätzen: Speicher 325
4.2.4 Speicher mit spezifischen Zugriffsarten 333
4.3 Schaltwerke zur Datenverarbeitung: Aufbau und Entwurf 341
4.3.1 Zähler 342
4.3.2 Synchroner Speicher: Entwurf des Zählers 352
4.3.3 Shiftregister und -werke 354
4.3.4 Logik-/Arithmetikwerke einschließlich Fließbandtechnik 357
4.4 Schaltwerke zur Programmsteuerung: Aufbau und Entwurf 363
4.4.1 Elementare Steuerwerke 364
4.4.2 Synchroner Speicher: Entwurf des Steuerwerks 366
4.4.3 Hierarchisch gegliederte Steuerwerke 369
4.4.4 Parallele Steuerwerke einschließlich Fließbandtechnik 375
4.5 Lösungen der Aufgaben 379
5 Prozessoren, Spezialrechner, Universalrechner 398
5.1 Funktionsbeschreibung digitaler Systeme 398
5.1.1 Parallelität „im kleinen“ 400
5.1.2 Prozedurale Darstellung: Sprachen 404
5.1.3 Zeichnerische Darstellung: Graphen 409
5.1.4 Matrixförmige Darstellung: Tabellen 410
5.1.5 Parallelität „im großen“ 412
5.1.6 Strukturelle Darstellung: Blockbilder 415
5.2 Datenflußarchitekturen für spezielle Algorithmen 417
5.2.1 Datenflußnetze 418
5.2.2 Additionsketten und -bäume zur Multiplikation 421
5.2.3 Datenflußnetze für 2-Komplement-Arithmetik 428
5.2.4 Datenflußwerke 433
5.3 Programmfluß- bzw. Fließbandarchitekturen 440
5.3.1 Fließbandtechnik 441
5.3.2 Application-Specific-Instruction-Prozessor, Prozessoren mit n-Code-Instruktionen 444
5.3.3 Very-Long-Instruction-Prozessor, Prozessoren mit n-Befehl-Instruktionen 448
5.3.4 Reduced-Instruction-Set-Prozessor, Prozessoren mit Ein-Befehl-Instruktionen 454
5.4 Aufbau und Funktionsweise von Universalrechnern 465
5.4.1 Akkumulator-Architektur 469
5.4.2 Register/Speicher-Architektur 472
5.4.3 Lade/Speichere-Architektur 476
5.4.4 Very-Long-Instruction-Word-Architektur 480
Literatur 504
Sachverzeichnis 506

3 Asynchron-Schaltwerke (S. 198-199)

3.1 Schaltungsstruktur und Funktionsweise

Asynchron-Schaltwerke haben im Gegensatz zu Schaltnetzen speichernden Charakter, ein „Gedächtnis". Ihrer Struktur nach sind Asynchron-Schaltwerke rückgekoppelte Schaltnetze, wobei nur ein Teil der Ausgänge rückgekoppelt ist (Vektor u), der andere Teil nicht (Vektor y). Demgemäß erscheint die Funktion des Schaltnetzes aufgespalten in zwei Teile: die Übergangsfunktion f und die Ausgangsfunktion g. Mit der Signalverzögerung ihrer Bauelemente bewirkt f einen Speichereffekt (hochgestellter Index d – delay – an u, also ui einen Moment später).1 Diese Delays werden i.allg. nicht extra aufgebaut, ggf. zur Verlängerung der in den Bauelementen vorhandenen Signalverzögerungen (siehe 3.4). – Die Funktion von Asynchron-Schaltwerken folgt den Gesetzen der Automatentheorie, wobei die Zustandsfortschaltung aufgrund der Änderung der Eingangsignale (Vektor x) geschieht (siehe ereignisgesteuerte Zustandsfortschaltung, S. 70). Damit läßt sich der Begriff Asynchron-Schaltwerk wie folgt definieren: • Ein Asynchron-Schaltwerk ist die schaltungstechnische Realisierung eines booleschen Automaten/Algorithmus. Es wird mathematisch beschrieben durch die Übergangsfunktion f und die Ausgangsfunktion g mit u als Rückkopplungsvektor, x als Eingangsvektor und y als Ausgangsvektor.

In der Praxis ist es bei Asynchron-Schaltwerken durchaus möglich, ja bei großen Systemen sogar üblich, daß Rückkopplungen wie auch Eingänge über Taktsignale synchronisiert sind. Solche Schaltwerke spielen gewissermaßen eine Doppelrolle: Sie werden Synchron-Schaltwerke genannt, wenn der Takt als rein technisches Signal betrachtet wird und Zustandsänderungen ausschließlich durch den Takt erfolgen. Sie werden Asynchron-Schaltwerke genannt, wenn der Takt wie alle anderen Signale, nämlich als rein logisches Signal behandelt wird, d.h., wenn Zustandsänderungen nicht nur durch den Takt, sondern durch mindestens ein weiteres Signal möglich sind.

Natürlich sind alle Schaltwerke, bei denen wenigstens ein Signal nicht taktsynchronisiert ist, keine Synchron-Schaltwerke, sondern Asynchron-Schaltwerke, Schaltwerke ganz ohne Taktsignale sind per se Asynchron-Schaltwerke. Man spricht hinsichtlich ihrer Zustandsfortschaltung von asynchronem Verhalten und hinsichtlich Entwurf und Darstellung von Asynchrontechnik.

Zur Signalverzögerung. Bild 3-1 zeigt eine sehr einfache Übergangsfunktion, gebildet mit einem Minimum an Variablen: nämlich die ODER-Verknüpfung mit einer einzigen Rückkopplungs- und einer einzigen Eingangsvariablen. Zwei Interpretationen sind möglich:

1. Unter der Annahme nicht existierender Signalverzögerungen in der Verknüpfung stellt die Übergangsfunktion eine Gleichung dar mit der Maßgabe, sie z.B. mit Hilfe einer Tabelle zu lösen (Interpretation Bestimmungsgleichung), wie man sieht, existieren nur für 3 von 4 Kombinationen von u- und x-Werten Lösungen der Gleichung.